Classification Aggregation with Multiple Memberships
Authors: Federico Fioravanti, Leo Kurata, Vasilis Stamatis
Organizations: Université Jean Monnet Saint-Étienne, CNRS, Université Lyon 2, emlyon business school, GATE, 42023, Saint-Étienne, France. · Graduate School of Economics, Waseda University, Tokyo, Japan · University of West Attica, Athens, Greece · LAMSADE, Université Paris Dauphine–PSL, Paris, France
People face the problem of classifying objects into categories while aggregating their opinions. We axiomatically study such a classification aggregation problem with multiple memberships, meaning that each individual assigns one category to every object, whereas the resulting classification may assign more than one category. Under the natural settings and axioms (i.e., Independence and Supportiveness), each of our new axioms -- Responsibility, Split Stability and Rejection Stability -- characterises what we call the junta rules. The rules assign a category to an object exactly when some member of a fixed coalition does so. The coalitions that can secure an assignment form a grill, a topological structure implied by an ultrafilter. Hence, the study parallels the literature on Arrow's theorem characterised by the decisive coalition structures. An infinite population setting is also investigated to clarify the differences among the axioms.
Figures & tables
F1
F2
F2′
F3
F4
F5
Independence
✓
✓
✓
×
✓
✓
Unanimity
✓
✓
✓
✓
✓
✓
Supportiveness
×
✓
✓
✓
✓
✓
Split Stability
×
✓
×
✓
×
✓†
Responsibility
✓
✓
✓
✓
×
×
Rejection Stability
×
✓
✓
✓
×
×
Table 1: Axioms satisfied ( ✓ ) and violated ( × ) by the rules in Examples 1 , 2 , 3 , 4 and 5 .
Finite N
Infinite N
Social outcome
Axioms
Structure; rules
Source
Structure; rules
Source
Preference aggregation
Complete, transitive
WP, IIA
Ultrafilter (= Filter ∩ Grill) ; dictatorship
Kirman and Sondermann (1972)
Ultrafilter, possibly free; non-dictatorial rules possible under AC
Fishburn (1970) , Kirman and Sondermann (1972)
Complete, quasi-transitive
WP, IIA
Principal filter; oligarchy
Gibbard (2014)
Filter, possibly nonprincipal; non-oligarchic rules possible
Judgment aggregation studies how to combine individual judgments on logically related propositions into a collective judgment. Classical impossibility results show that sufficiently strong logical interconnections force dictatorship under natural aggregation axioms. In this paper, we ask whether such impossibility can still arise when the objects of aggregation are required to be genuinely modal judgments rather than plain factual propositions. Since modal logic contains propositional logic, this question is meaningful only if one excludes fact-based aggregation in disguise. We show that Arrow-type impossibility already re-emerges in a strikingly sparse modal setting. We prove an impossibility theorem on a simple cyclic frame for an agenda generated from a single propositional variable by repeated applications of a single modal operator, and we further demonstrate this phenomenon for an alternative family of frames satisfying a natural symmetry condition. Thus, even under a modal-operator requirement, semantic structure alone can generate the logical interconnections needed for dictatorship. Technically, our analysis has two layers. First, we prove a semantic reduction theorem showing that certain iterated modal patterns can be collapsed by shifting the evaluation point. Second, building on this reduction, we identify a local-to-global frame mechanism by which frame geometry yields minimally inconsistent modal judgment sets and the strong path-connectivity required for impossibility. The same reduction also turns consistency checking into a small combinatorial covering problem, which yields efficient implementations of non-dictatorial aggregation procedures.
Yutaka Nagai, Hirotaka Ono
Graduate School of Informatics, Nagoya University, Furo-cho, Chikusa-ku, Nagoya 464–8601, Japan
This paper studies strict majority reasoning in finite electorates using so-called social decision frames: finite sets of voters equipped with distinguished families of coalitions interpreted as those voting blocs evaluated to form a strict majority. A coherence criterion for qualitative majority judgments is identified and shown to give an exact characterization for representability of strict majorities by finitely additive measures. In addition, a minimal natural logic for reasoning about strict majorities is shown to be sound and complete. These developments motivate examination of associated combinatorial questions concerning incoherence in finite families of sets; partial results and a conjecture are given. Finally, the results of this paper are applied to correct a classical representation theorem for weak qualitative probability structures due to Patrick Suppes and to establish a May-type characterization for ordinary strict majority rule for social decision frames.
Lawrence S. Moss, Arthur Paul Pedersen
(†) Dept. of Mathematics, Indiana University, Bloomington. · (‡) Dept. of Computer Science & the Intel Investigations Lab, the City College of New York · the Graduate Center & Remote Sensing Earth Systems Institute, the City University of New York.
Suppose a committee, expert panel, or other group is making judgments on some issues, where these may be not just yes/no-questions, such as whether a defendant is guilty, but also variables with many possible values, such as macroeconomic or meteorological variables or travel directions. Furthermore, there may be interconnections between different issues, as in the case of economic or climate variables. How can the group arrive at "intelligent" collective judgments, based on the group members' individual judgments? We investigate three challenges raised by this judgment-aggregation problem. First, reasonable methods of aggregation (such as defining the collective judgment for each issue as the average or median judgment) can produce inconsistent collective judgments. Secondly, many methods of aggregation are manipulable by strategic voting. Finally, not all methods of aggregation are conducive to tracking the truth on the issues in question. We prove new impossibility or possibility theorems on all three challenges, identifying what it takes to produce collective judgments in a consistent, non-manipulable, and truth-tracking manner and thereby to achieve collective intelligence through aggregation. Overall, the median method, though imperfect, performs reasonably well. We also note the relevance of our analysis for non-human group decisions.
Franz Dietrich, Christian List
We thank two anonymous referees and an editor for very helpful comments.