WorksEconomics, Econometrics and Finance
Classification Aggregation with Multiple Memberships
Abstract
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.
Fioravanti acknowledges the financial support from the French National Research Agency within the project ANR-24-EXMA-0001 PEPR MathsVivES CONDORCET. Kurata acknowledges support from KAKENHI (No. 25KJ2146) and Global Research Center (Waseda University). The authors’ email addresses are: Federico Fioravanti, [email protected]; Leo Kurata, [email protected]; Vasilis Stamatis, [email protected]. During the preparation of this work, the authors used Claude (Anthropic) and ChatGPT (OpenAI) in order to assist with language editing and to identify possible algebraic or expository issues. After using these tools, the authors reviewed and edited the content as needed and take full responsibility for the content of the publication.
Introduction
We study the setting where a set of individuals assigns each object to exactly one of the categories, using every category at least once, to obtain a collective classification. This problem, called classification aggregation, has been considered by Maniquet and Mongin [38], who show that an aggregator satisfying the properties of Unanimity, which requires society to respect agreement on an object’s category, and Independence, which requires the collective assignment for that object to depend only on how voters classify it, must adopt the classification of one fixed voter (the dictator) at every profile. In the preference aggregation setting (Arrow, [2]), where a finite society must turn any profile of rankings over at least three alternatives into a complete and transitive ranking of its own, unanimity and independence of irrelevant alternatives also force the existence of a dictator. But non-dictatorial rules become possible when some assumptions are relaxed, such as the social ranking being quasi-transitive (Gibbard, [31]) or being incomplete (Weymark, [49]). In the same spirit, we study classification aggregation correspondences (CACs).1 Each voter still assigns one category to each object, but society may recognize several categories as final memberships of the same object, provided every object receives at least one category and every category remains represented. Which non-dictatorial rules become possible under this relaxation?
Collective classification with multiple memberships can arise in a variety of settings. For example, consider a participatory-budgeting platform that asks residents to classify project proposals. Each resident chooses one primary category per proposal from a list that includes Arts, Biodiversity, and Climate.2 Classifications help determine how public projects are compared and presented to citizens, and may also affect which sources of funding they can access. An urban-greening project may aim both to restore habitats and to support climate adaptation. One resident may therefore identify Biodiversity as its primary category, while another identifies Climate. Listing the project under both headings recognizes both contributions. If eligibility for funding follows the assigned categories, the project could still be considered under Climate when the Biodiversity budget is exhausted. It would retain both memberships even if only the Climate budget funded it.
In another application, a platform combines the predictions of several trained classifiers. Each classifier assigns one thematic label per project description, while the combined classification may retain several labels for the same project, a form of output also studied in multi-label learning (e.g., Gibaja and Ventura, [30]).
To isolate the effect of allowing multiple memberships, we admit every profile of individual classifications in the domain of Maniquet and Mongin [38].3 The requirement that every category remain represented collectively also has a practical interpretation. Some participatory-budgeting schemes allocate separate budgets to thematic categories.4 When these budgets cannot be transferred between categories, leaving a category empty would leave its budget with no eligible proposal; this motivates requiring the collective classification to represent every category.
We also retain Independence, while strengthening Unanimity to Supportiveness, which requires every category collectively assigned to an object to have been proposed for that object by at least one individual. Supportiveness implies Unanimity in our setting and is itself a consequence of Independence and Unanimity in Maniquet and Mongin’s original setting (Maniquet and Mongin, [38], Lemma 1). In this finite-population benchmark with at least three categories, Independence and Supportiveness therefore describe exactly the same class as Independence and Unanimity, namely the dictatorial rules (Proposition 1). In this sense, our approach preserves their individual domain and requirement that every category be represented, while changing the admissible form of the collective outcome. The requirement that no category be left empty concerns the collective classification as a whole, while Independence requires considering each object separately. On the other hand, once multiple memberships are allowed, even under Independence, Unanimity no longer delivers Supportiveness when there are three or more categories. The clearest example is the classification counterpart of an oligarchy. It assigns an object to the category on which the members of a coalition agree and, when they disagree, to every category. This rule satisfies both Independence and Unanimity, and it is non-dictatorial once the coalition has two members (Proposition 2). Under the membership reading, disagreement within the coalition can lead society to assert that the object belongs to categories that nobody, inside or outside the coalition, has proposed. When the designated voters disagree between Biodiversity and Climate, for example, the urban-greening proposal would also be listed under Arts. Supportiveness excludes such a deicision. In § 4.2, we further justify this strengthening of Unanimity from both the interpretational and the technical perspectives.
Accepting every proposed category gives an independent and supportive rule that is non-dictatorial when there are at least two individuals. We ask how decision power over the acceptance of assignments can be distributed while allowing some supported assignments to be rejected. In particular, can a rule treat individuals equally and still reject some proposed memberships if each accepted membership must have a supporter whose report suffices on its own? In the participatory-budgeting example, listing the urban-greening proposal under Climate expresses the panel’s judgement that the project contributes to climate adaptation. The platform may give designated panel members the authority to secure the inclusion of a thematic category. Our Responsibility axiom requires that, for each accepted assignment, some supporting voter’s complete classification be sufficient to sustain it, whatever the other voters report. This requirement is stronger than the mere existence of a supporter. Because thematic categories can overlap, the collective classification can retain both memberships when voters identify different primary categories. Different voters can therefore sustain different memberships, including memberships of the same proposal, and share decision power over the collective classification. For aggregation of learned classifications, the same requirement gives designated classifiers the authority to secure the inclusion of a label.
Our main results characterise the distribution of decision power over collective memberships. Under Independence and Supportiveness, Responsibility and Rejection Stability each characterise the junta rules on finite populations, while Split Stability characterises the subclass in which the junta depends only on the object (Theorems 1 to 3).5 A junta rule fixes, for each object and category, a coalition – which we call a junta – and assigns the object to the category exactly when at least one member of the junta does. To ensure that every object receive a category and every category be used, the juntas for each object must have a common member, as must the juntas for each category (Proposition 3). Under Category Neutrality, the junta depends only on the object; further adding Object Neutrality gives a single junta for all objects and categories. The three axioms reach these characterisations from different directions. Responsibility asks that every assigned category be secured by the complete report of one of its supporters, in the spirit of the expertise conditions of Fioravanti [24]; Split Stability asks that, when support for a category is divided between it and a category previously unused at that object, at least one of the two is accepted exactly when the original was, while the object’s other memberships remain unchanged; and Rejection Stability asks that combining supporters’ unchanged complete reports from two rejecting profiles should not secure the rejected assignment. Every member of a junta can include a category on her own, and different members can include different categories at the same object; this is possible only because multiple memberships are allowed. Note that when outcomes are required to be singletons, every junta shrinks to the same individual and the dictatorship of Maniquet and Mongin [38] is recovered.
We also examine whether individual responsibility and equal treatment of individuals allow some supported assignments to be rejected. Under Independence, Supportiveness and Responsibility, adding Anonymity singles out the full-population junta (Corollary 3). Thus, under the maintained axioms, equal treatment and individual responsibility require the acceptance of every supported assignment. The rule is also neutral for all sizes of the problem, so that multiple memberships escape the non-existence of anonymous and neutral rules found by Cailloux et al. [7].
It turns out that the coalitional structure behind these results is a grill [14]. Grills are related to the filters, familiar from aggregation theory. The decisive coalitions in the theorem of Maniquet and Mongin form an ultrafilter, and an ultrafilter is exactly a family that is both a filter and a grill (Fact 3). Much of the literature on Arrow’s theorem weakens collective rationality while keeping the Pareto principle and (binary) independence, and it finds that the decisive coalitions retain the filter property. Quasi-transitive social preferences lead to oligarchies [31], transitive but incomplete social preferences lead to oligarchies [49], and acyclic social preferences lead to prefilters [5, 3]. Under our axioms, relaxing single-valuedness in classification aggregation corresponds to keeping the other half of the ultrafilter. Grills are the duals of filters (Fact 4), and the coalitions that win under the junta rule with junta, say , are exactly the blocking coalitions of the oligarchy with oligarchs . In the Arrovian literature, each member of a decisive group can block a strict social preference. In our setting, each member of a junta can secure the inclusion of a category. A rule that lets each member of a group block every category she does not propose leaves divided objects with no category at all, violating the requirement that every object receive a category. In this sense, the passage from the theorem of Maniquet and Mongin to junta rules parallels the passage from Arrow’s theorem to oligarchies, with the roles of filters and grills exchanged. Refer to § 5.1 and Table 2 for technical details.
| Social outcome | Axioms | Finite : Structure; rules | Finite : Source | Infinite : Structure; rules | Infinite : Source |
| Preference aggregation | |||||
| Complete, transitive | WP, IIA | Ultrafilter (= Filter Grill); dictatorship | [35] | Ultrafilter, possibly free; non-dictatorial rules possible under AC | [28], [35] |
| Complete, quasi-transitive | WP, IIA | Principal filter; oligarchy | [31] | Filter, possibly nonprincipal; non-oligarchic rules possible | [32] |
| Transitive, possibly incomplete | WP, IIA | Filter (decisive)/ Grill (quasi-decisive); oligarchy | [49], [8] | Filter (decisive)/ grill (quasi-decisive); not necessarily principal | [4], [8] |
| Classification aggregation | |||||
| Single-valued & surjective | I, Unanimity | Ultrafilter (= Filter Grill); dictatorship | [38] | Ultrafilter, possibly free; non-dictatorial rules possible under AC | Corollary 4 |
| Set-valued & covering | I, Supportiveness, SS | Principal grill; | Theorem 2 | Grill; | Theorem 4 |
| ditto | I, Supportiveness, Rej. Stab., CN | Principal grill; | Theorem 3 | Grill; | Theorem 4 |
| ditto | I, Supportiveness, Resp., CN | Principal grill; | Corollary 1 | Principal grill; | Corollary 5 |
Table 2. Coalitional structures and rules in preference aggregation and in classification aggregation.
Under Independence, Supportiveness and Category Neutrality, our three new axioms are equivalent on finite populations when . By contrast, on infinite populations, Responsibility is strictly stronger than the two stability axioms under these conditions. Arrow’s theorem fails in infinite societies, because non-dictatorial rules are obtained whenever an ultrafilter is free [28, 35], and the same holds for the theorem of Maniquet and Mongin (Corollary 4). With multiple memberships, Split Stability, or Rejection Stability together with Category Neutrality, characterises the limiting junta rules, a class that extends the object-dependent junta rules and whose winning coalitions form grills that need not be principal (Theorem 4). The rule that assigns an object to every category with infinitely many supporters belongs to this class and is defined explicitly. Responsibility yields junta rules on every population by directly identifying the individuals whose classifications can sustain an assignment (Corollary 5).
Related literature
The axiomatic study of classification began with partitions, in which the categories carry no labels and their number is not fixed in advance. Mirkin [42] was the first to analyse the aggregation of equivalence relations axiomatically, and Fishburn and Rubinstein [29] show that independence and unanimity leave exactly the conjunctive rules, under which two objects are equivalent in the aggregate partition if and only if they are equivalent for every member of a fixed nonempty coalition (see also Dimitrov et al., [19]). These rules are oligarchies, and they are available because the intersection of equivalence relations is again an equivalence relation: agreement within a coalition always defines an admissible outcome. With designated categories this is no longer the case. Maniquet and Mongin [38] extend to three or more categories a result that Kasher and Rubinstein [34] obtained for two, showing that Independence and Unanimity force dictatorship when individual and collective classifications must leave no category empty, and Dokow and Holzman [21] obtain the counterpart for classifications that place at most one object in each category. Subsequent work retains single-valued collective classifications and varies the remaining requirements. Cailloux et al. [6] weaken Unanimity to citizen sovereignty; Craven [15] shows that domain restrictions permitting majority-based aggregation have very limited scope in this setting, and identifies a hybrid structure in which such aggregation is possible exactly when each object is eligible for at most two categories; Fioravanti [24] examines forms of individual authority over objects or categories; Cailloux et al. [7] drop Independence and study anonymity and neutrality; and Craven [16] considers ranked categories. Filmus [23] characterises all independent rules whose outcome is always surjective, without further assumptions on the objectwise aggregation functions, and derives from it a quantitative version of the dictatorship conclusion. Hervouin [33] also considers classification aggregation correspondences. Relative to this literature, we keep the individual domain of Maniquet and Mongin [38], Independence and the requirement that every category be used, and change only the form of the collective outcome.
Group identification Kasher and Rubinstein [34] is the case in which the objects to be classified are the individuals themselves. Because a group may be left empty there, rules that give individuals authority over their own membership remain available, and the literature characterises the liberal rule together with the consent rules, which balance self-determination against the opinions of others [43, 46, 41]. Cho and Ju [12] determine memberships in three or more groups simultaneously and show that independence of irrelevant opinions, together with symmetry and non-degeneracy, leads to the liberal rule. In these models possibility comes from allowing categories to remain empty; we keep the requirement that every category be used and obtain possibility from multiple memberships instead. Several papers associate an object with several categories through degrees of membership. Cho and Park [13] allow fractional memberships in group identification and characterise weighted-average and fractional consent rules, and fuzzy versions of classification and group identification are studied by Alcantud et al. [1], Fioravanti and Tohmé [27] and Fioravanti [25], the last of which obtains weighted arithmetic means. Our memberships are not graded. An object belongs fully to each category assigned to it, and assigning it to one category does not weaken its membership in another; accordingly, the rules we obtain are coalitional rather than averaging.
Reading each statement “ belongs to ” as a binary issue turns a CAC into a binary aggregator whose admissible collective evaluations form a strictly larger set than the admissible individual ones: an individual assigns each object exactly one category, whereas society assigns it at least one. Our problem therefore belongs to the family in which society is held to a weaker consistency requirement than individuals. In judgment aggregation, allowing incomplete collective judgments while retaining deductive closure yields oligarchies [18], and Dokow and Holzman [20] show that the conditions on the domain that lead to dictatorship without abstentions lead to oligarchy once abstentions are allowed, with Gibbard’s oligarchy theorem among the corollaries. In these models society may take a position on fewer issues than individuals do, so agreement within a coalition remains an admissible outcome. In ours, society may accept more membership statements than any individual does, disagreement is resolved by inclusion rather than abstention, and oligarchies give way to juntas. Graph aggregation Endriss and Grandi [22] provides a close formal analogue. Its groundedness axiom requires every collective edge to belong to some individual graph, as Supportiveness does for memberships, and Endriss and Grandi [22] show that, for graph properties that are contagious and implicative, unanimous, grounded and independent rules that preserve the property are oligarchic. Applied to each membership statement, the quota rules of Dietrich and List [17] accept a category when it has enough supporters; a quota of one for every pair gives , and pair-specific quotas give procedures such as in Example 4. Finally, when individual and collective evaluations are drawn from the same set, Dokow and Holzman [21] and Szegedy and Xu [47] study which domains of non-binary evaluations force supportive or unanimous aggregation to be dictatorial. The setting of Maniquet and Mongin [38] is such a domain, with objects as issues and categories as positions, and CACs fall outside this framework precisely because the collective outcome need not belong to the individual domain.
As recalled earlier, the ultrafilter approach identifies the decisive coalitions of an Arrowian rule with an ultrafilter [35, 32], and weakenings of collective rationality correspond to weakenings of this structure, from filters and oligarchies to prefilters (see also Bossert and Suzumura [4]). Cato et al. [11] develop this approach in an abstract framework in which an aggregation rule may remain silent. Under a stability condition, the decisive coalitions form a filter, and when the set of signals is finite they characterise the rules that approve a signal exactly when some coalition in a given filter or ultrafilter agrees on it. These rules are agreement-based. Junta rules are inclusion-based, and their winning coalitions form grills [14], the duals of filters. To our knowledge, grills have not been used explicitly as the decisive structure of aggregation rules, although they appear under another name: Cato [8] shows that, for transitive but possibly incomplete social preferences, the quasi-decisive coalitions form a quasi-ultrafilter, which by Fact 2 is exactly a grill. In his setting these are the coalitions that can prevent society from ranking an alternative at least as high as one that all their members prefer to it; here they are the coalitions that can secure a membership. Fishburn [28] and Kirman and Sondermann [35] show that Arrow’s conditions can be met by non-dictatorial rules on infinite populations, through free ultrafilters that cannot be explicitly constructed. Mihara [40] shows that in a countably infinite society every rule satisfying Arrow’s conditions that is pairwise computable is dictatorial, and Mihara [39] shows that in infinite societies anonymity is inconsistent with Arrow’s unanimity and independence conditions on sufficiently rich domains. Torres [48] introduces limiting dictatorial rules, of which our limiting junta rules are the counterparts, and Cato [9, 10] study further aspects of preference aggregation with infinite populations. In group identification, Fioravanti and Tohmé [26] show that, with infinitely many voters, the characterisation of the liberal rule survives whereas that of the oligarchic rule does not. A similar divergence appears here. The axiom that identifies individual supporters, Responsibility, characterises junta rules on every population, whereas the axioms that only relate coalitions, Split Stability and Rejection Stability, admit non-principal grills. The resulting rules include the Fréchet rule, which, unlike the rules built on free ultrafilters, is defined without the axiom of choice.
Paper organisation
The paper is organized as follows. § 3 introduces the model and the coalitional families we use. § 4 presents the basic axioms and the benchmark. § 5 discusses the two translations of oligarchy and introduces junta rules. § 6 contains the three characterisations, examines the role of Supportiveness, and concludes by relating Anonymity to responsibility. § 8 turns to infinite populations. § 9 concludes. Longer proofs are collected in Section A, and Section B shows that the axioms in the main characterisations are independent.
Preliminaries
Notation
Let be a set of individuals with at least two members. Unless stated otherwise, is finite; in § 8 and wherever we say so explicitly, may be infinite, for instance . Let be a finite set of objects and a finite set of categories, with .
An individual classification is a surjective mapping . We denote the set of individual classifications by . A social classification is a mapping satisfying . We denote the set of social classifications by .
A profile is a vector of individual classifications. A classification aggregation correspondence (CAC) is a mapping that assigns a social classification to every profile. A CAC is resolute if is a singleton for all and ; resolute CACs are the classification aggregation functions studied by Maniquet and Mongin [38]. The rule they specify is a dictatorial rule, defined by the existence of such that for all and .
Given a profile and an object , we write
for the support set of category at object . Given , we write for the opinion vector at . Given an opinion vector , denotes the support set of category .
Any opinion vector at a fixed object can be obtained from a profile of individual classifications. Note that both lemmas below hold for finite and infinite populations.
Lemma 1. Assume . For every and every , there exists a profile such that .
Proof. Fix and . For each , set . It remains to define on so that is surjective. The category is already attained at . Since , we can assign every category in to at least one object in and assign any remaining objects arbitrarily. ■
When , the profile can be chosen so that changing the opinion vector at never affects surjectivity.
Lemma 2. Assume . For every and every , there exists a profile such that and, for every , the restriction is surjective.
Proof. Fix and , and write . For each , set . Since , we may choose pairwise distinct objects and set for , and for every remaining . Then is surjective, hence so is . ■
A set-valued outcome of CACs admits two readings: membership or tie. Under the membership reading, means that society assigns to , so that may belong to several categories at once. Under the tie reading, lists the categories that remain admissible for , and a single category is to be selected later. We adopt the membership reading throughout. The covering condition in the definition of a social classification is formulated for this reading. It says that every category has at least one member, which is how the surjectivity requirement translates when an object may belong to several categories. Under the tie reading, we would instead require the existence of a surjective selection: a surjective mapping with for every . Under this reading a single category must eventually be selected for each object, and if this selection respects the two postulates of Maniquet and Mongin [38], their impossibility applies at that final stage. Under the membership reading, the set-valued outcome is the final classification.
Examples of CACs
We introduce four running examples involving five rules at a common profile . The examples distinguish whether accepted assignments have supporters, whether an object’s classification depends on reports about other objects, and whether an individual’s report can secure an assignment. They also compare individual decision power with equal treatment of voters. We return to these examples when introducing the axioms and summarise their properties in Table 1.
| Independence | ✓ | ✓ | ✓ | × | ✓ | ✓ |
| Unanimity | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| Supportiveness | × | ✓ | ✓ | ✓ | ✓ | ✓ |
| Split Stability | × | ✓ | × | ✓ | × | ✓6 |
| Responsibility | ✓ | ✓ | ✓ | ✓ | × | × |
| Rejection Stability | × | ✓ | ✓ | ✓ | × | × |
| Object Neutrality | ✓ | ✓ | × | ✓ | × | ✓ |
| Category Neutrality | ✓ | ✓ | × | ✓ | × | ✓ |
| Anonymity | ✓ | ✓ | × | × | ✓ | ✓ |
Table 1. Axioms satisfied (✓) and violated (×) by the rules in Examples 1 to 5.
A participatory-budgeting platform groups project proposals into thematic categories for comparison. Two voters, , classify four proposals, , into three categories, , which we read as Arts, Biodiversity and Climate, respectively. Each voter assigns every proposal to one category and uses every category, whereas the platform may place a proposal in several categories, for instance a project combining public art and habitat restoration in Arts and in Biodiversity. The list denotes the classification , and a social classification is written in the same way. In each of the examples below, the profile is given by
The voters agree on and disagree on the other three proposals. Observe that both classifications are surjective.
Example 1. Let if , and otherwise. At the profile above,
Every category is used, so is a social classification, and the same holds at every profile. The outcome for a proposal depends only on how the two voters classify that proposal, and a proposal on which they agree is placed exactly in the category they chose. At , however, voter 1 proposes Biodiversity and voter 2 Arts, and places the proposal in Climate as well, although neither of them proposed it. In this case, the rule uses every category only because it places each disputed proposal in all of them. ◇
Example 2. Let , so that each proposal is placed in every category that some voter proposes for it. At the profile above,
Like , this rule depends only on the assignments for each proposal and respects agreement, but it never places a proposal in a category that nobody proposed. The voters whose assignments count may also vary across proposals and categories. Let coincide with , except that Biodiversity is assigned to only when voter 2 proposes it, and Climate is assigned to only when voter 1 proposes it, for instance because voter 2 has expertise in biodiversity conservation and voter 1 in climate adaptation. At the profile above,
Every category is still used, and produces a social classification at every profile (see also the discussion in Example 4). ⋄
Note that, under the tie reading of set-valued outcomes, no selection from in Example 2 is surjective, whereas the membership reading is still applicable.
Example 3. Let consist of together with whenever voter 2 uses for at least one other proposal. Voter 2’s assignment for a proposal thus counts only if she uses that category more than once; at the profile above, this is the case only for Arts. Since always contains voter 1’s classification, it is a social classification at every profile, and every category it assigns is proposed by someone. At the profile above,
The rule also uses every category. ⋄
Lastly, the platform may instead use a quota rule, requiring a specified minimum number of supporting voters for each proposal–category pair. If one supporter suffices for every pair, this procedure coincides with . With two voters, a quota of 2 requires both of them to propose the category. Raising every quota to 2 gives at the profile above: three proposals are left without a category, and Biodiversity and Climate are not used.
Example 4. Let require two supporters for Art at , for Biodiversity at , and for Climate at , and one supporter for every other pair. At the profile above, this rule yields
This rule produces a social classification at every profile. Its outcome at the profile above coincides with that of in Example 2, but the reasons behind them are different. Under , voter 1’s assignment of Biodiversity to does not count; under , it counts but is not enough on its own. If the voters exchange their reports, so that voter 1 submits and voter 2 submits , gives , whereas gives the same outcome as before, since the quotas count supporters without regard to who they are. Yet neither voter can secure Biodiversity for by herself. In these cases, all the categories are used because all quotas are reached (which might not always be the case). ⋄
Filters, ultrafilters and grills
We use families of coalitions to describe which groups can secure an assignment. Filters and related families also describe decisive coalitions in preference aggregation ([44, 45]). We recall the definitions used below.
Definition 1. A family of subsets of may have the following properties:
(p.1) .
(p.2) .
(p.3) For all , if and , then .
(p.4) For all , .
(p.5) For all , implies .
(p.6) For all , implies or .
A family of subsets of is called
a filter, denoted by , if it satisfies (p.1)–(p.4);
an ultrafilter, denoted by , if it satisfies (p.1)–(p.5); and
a grill, denoted by , if it satisfies (p.1)–(p.3) and (p.6).
Property (p.6) is called the grill property. Equivalently, letting , the grill property states that is closed under union: if and , then . By induction, if , then for some .
A filter is principal if there is a nonempty coalition such that for all . In that case , where . An ultrafilter is principal if and only if it equals for some , and it is free otherwise. A grill on is principal if for some nonempty , where
and it is free otherwise. Letting , every coalition meeting belongs to by (p.3). Hence, is principal if and only if every member of meets , in which case . When is finite, all filters, ultrafilters and grills on are principal; for grills, this is the content of the next fact.
Fact 1. Let be finite. A family is a grill on if and only if there exists a unique nonempty such that .
Proof. Let be a grill and . By the contrapositive of (p.3), is downward closed, and by the contrapositive of (p.6), it is closed under union. Since and is finite, belongs to and . Let . Then because , and if and only if , that is, if and only if . Uniqueness holds because . Conversely, satisfies (p.1)–(p.3) when , and (p.6) holds because . ■
We record three further properties of grills.
Fact 2. Let be a family of subsets of satisfying (p.1)–(p.3). If satisfies (p.6), then it satisfies (p.5).
Proof. Take any . Since by (p.2), property (p.6) gives or . ■
Cato [8] introduces the notion of a quasi-ultrafilter, defined as a family satisfying (p.1)–(p.3), (p.5), and (p.6). By Fact 2, condition (p.5) is redundant in this definition, so a quasi-ultrafilter is precisely a grill. FACT 2 also leads to the following characterisation of ultrafilters.
Fact 3. A family of subsets of is both a filter and a grill if and only if it is an ultrafilter.
Proof. Let be an ultrafilter. It is a filter by definition, so it remains to verify (p.6). Suppose, to the contrary, that but and for some . By (p.5), and , and so (p.4) gives . Another application of (p.4) yields , which contradicts (p.1).
Conversely, let be both a filter and a grill. Then satisfies (p.1)–(p.4), and it satisfies (p.5) by Fact 2. Hence, is an ultrafilter.
For instance, consider and . This is a grill but not an ultrafilter because for any distinct .
In fact, grills and filters are dual to each other [14]. For a family , let be the family of complements of the sets outside . We call the members of the blocking coalitions of .
Fact 4. Let .
is a grill if and only if is a filter.
If is a grill, then if and only if for every .
For every nonempty , and . In particular, a grill is principal if and only if its family of blocking coalitions is a principal filter.
Proof. (i) The map is a bijection from onto . Under it, (p.1) for corresponds to (p.2) for , (p.2) for to (p.1) for , and upward closure of to upward closure of . Finally, the grill property of says that implies , which is equivalent to whenever , that is, to (p.4) for .
(ii) If and for some , then , contradicting upward closure. If , then and .
(iii) if and only if , that is, if and only if . Likewise, if and only if if and only if .
Basic axioms and the Maniquet–Mongin benchmark
Independence and Unanimity
The first axiom states that the social classification of an object depends only on how the individuals classify that object.
Axiom (Independence). A CAC satisfies Independence if, for all and all , for every implies .
Under Independence, is determined by the family of mappings with and ; by Lemma 1, every is defined on all of .
Maniquet and Mongin [38] use the following requirement together with Independence.
Axiom (Unanimity). A CAC satisfies Unanimity if, for all and all such that for every , it is the case that .
These are the two requirements in Maniquet and Mongin [38]. Allowing multiple memberships makes it necessary to examine whether Unanimity alone provides an adequate connection between individual reports and collectively accepted assignments.
Supportiveness beyond unanimity
Unanimity constrains the outcome when all individuals agree, but it does not in general prevent an unsupported assignment when they disagree. Because our setting allows multimembership, we propose the use of Supportiveness, which strengthens Unanimity. Supportiveness requires every socially assigned category to have at least one individual supporter.
Axiom (Supportiveness). A CAC satisfies Supportiveness if, for all and all ,
Supportiveness can be read as the unanimity principle applied to each membership statement “ belongs to ”. If every individual rejects the statement, so does society. If every individual accepts it, the outcome at is a nonempty subset of , so society accepts it as well. The requirement that society reject unsupported memberships has several precedents. In the single-valued setting, Maniquet and Mongin [38] derive it from their axioms, and it is part (b) of the unary unanimity condition of Craven [15]. It is the supportiveness condition of Dokow and Holzman [21] for non-binary evaluations, it corresponds to the zero unanimity of Fioravanti [25] for fuzzy classification aggregation, the groundedness axiom of Endriss and Grandi [22] for graph aggregation, and the Pareto★ principle of Kurata and Nakamura [36, 37] for Harsanyian aggregation of incomplete preferences.
Supportiveness implies Unanimity in our framework. For let be a CAC and suppose that every individual assigns to ; by Supportiveness, , and follows from , meaning . The converse holds only when and fails when .
Lemma 3. Every CAC that satisfies Supportiveness satisfies Unanimity.
Among the rules of Examples 1 to 4, only violates Independence: at and its outcome changes although nobody changes her classification of these proposals. Only violates Supportiveness: at it adds Climate, which neither voter proposes.
Sections 4 and 5.4 show why Unanimity cannot replace Supportiveness in the Responsibility characterisation when . Although the two axioms are interchangeable in some of our results, Unanimity alone is insufficient under the membership reading. We adopt Supportiveness throughout so that every accepted assignment has an individual supporter. The two axioms differ when individuals disagree. Suppose that some voters classify a proposal as Arts and the others as Biodiversity. Listing the proposal under both categories is a reasonable way of reflecting this disagreement, since each category records the judgement of some members and can be defended by pointing to them. Listing it under Climate as well is different in kind. Nobody proposed Climate for the proposal, so no voter can be asked to justify that assignment, and a resident comparing proposals in Climate would find one that no voter placed there. Unanimity is silent about this profile, since the members do not agree, and so it does not prevent Climate from being added. Supportiveness excludes Climate and allows Arts, Biodiversity or both to be accepted. The rule of Example 1 behaves in exactly this way at : it satisfies Unanimity, yet it lists the proposal under Climate, whereas lists it under Arts and Biodiversity only.
For resolute rules, the distinction does not arise, because there Unanimity, Independence and the requirement that every category be used already imply Supportiveness.
Proposition 1. Let and . For a resolute CAC , the following statements are equivalent.
(i) satisfies Independence and Unanimity.
(ii) satisfies Independence and Supportiveness.
(iii) is dictatorial.
Proof. A dictatorial rule satisfies Independence and Supportiveness, so (iii) implies (ii). By Lemma 3, (ii) implies (i). That (i) implies (iii) is the theorem of Maniquet and Mongin [38] when and Corollary 2 of Cailloux et al. [6] when .
Proposition 1 shows that replacing Unanimity with Supportiveness preserves the benchmark characterisation of Maniquet and Mongin [38]. In their setting it is already implied by Independence, Unanimity and the requirement that the social classification be surjective. In our setting the requirement on the social classification is weaker, because a category can be used by assigning objects to several categories at once, and this derivation of Supportiveness is no longer available. Independence and Unanimity therefore do not suffice to exclude unsupported memberships.
Neutrality
We also consider symmetry requirements on objects and categories. The next axiom requires that the names of the objects be irrelevant for the aggregation.
Axiom (Object Neutrality). A CAC satisfies Object Neutrality if, for all , all permutations and all , , where .
If and is a permutation of , then , since the composition of a surjection with a bijection is a surjection. Category Neutrality requires that the aggregation rule treat all categories symmetrically.
Axiom (Category Neutrality). A CAC satisfies Category Neutrality if, for every permutation of and every , for all , where and for .
Notice that in the running examples, all rules satisfy both neutrality axioms except for and : the former makes whose assignment counts depend on the proposal and category, and the latter makes the required quota depend on them.
Oligarchy and junta rules
Translating oligarchy into a CAC
In preference aggregation, an oligarchy is a coalition whose unanimous strict preference determines the social strict preference, while opposing strict preferences among its members result in social indifference (Gibbard, [31]). There are two ways to carry this idea over to classification: the agreement-based and inclusion-based translations.
The agreement-based translation retains a category only when every member of assigns to it, that is, it selects . This set becomes empty as soon as two members of classify differently, so it defines a CAC only when is a singleton.7 An agreement-based CAC must therefore specify what happens when the members of disagree. We consider that the counterpart of social indifference in our setting is to assign to every category. For a nonempty coalition , the oligarchy rule (with all-category assignment) is defined by
The inclusion-based translation retains every category to which at least one member of assigns :
We call a junta and the uniform junta rule. No restriction is imposed on the size of . With , the rule is of Example 1, and is of Example 2. At the profile of these examples, the two rules agree at , where the voters agree, and differ at the three disputed proposals, where returns and returns only the proposed categories.
Both rules give the members of the same power over exclusive assignments: under either rule, the outcome at is if and only if . They differ in how categories are included. Under , category is included if and only if , whereas under whether is included is not determined by the support of alone, since disagreement among the other members of puts every category into the outcome. By Fact 4, consists exactly of the sets whose complements are not in .
Proposition 2. Let and let be nonempty.
(i) is a CAC that satisfies Independence, Unanimity, Category Neutrality and Object Neutrality.
(ii) is dictatorial if and only if .
(iii) If , then .
(iv) If and , then violates Supportiveness.
The proof is in Section A. It follows from (i) and (iii) of Proposition 2 and Lemma 3 that when , every CAC that satisfies Unanimity satisfies Supportiveness if and only if .
The oligarchy rule is thus the most direct translation of an oligarchy, and it satisfies the axioms of Maniquet and Mongin [38] without being dictatorial. We nevertheless regard it as unsatisfactory. Under the membership reading of § 3.1, the outcome asserts that the object belongs to every category, including categories to which nobody, inside or outside , has assigned it. In the participatory-budgeting example, a proposal on which two members of the oligarchy disagree would be placed in every category, as , and are under in Example 1. The rule also satisfies the requirement that every category be used in an uninformative way: whenever two oligarchs disagree at some object, that object alone covers all categories. The inclusion-based translation satisfies Supportiveness. Under the tie reading, by contrast, the outcome would mean that the question is left open, and would be a reasonable counterpart of an oligarchy; the choice between the two readings is therefore substantive.
The two translations also differ in their coalitional structure. Under , the coalitions that secure the inclusion of a category form the grill , which satisfies (p.6) but is not closed under intersection when , and each member of can include a category on her own. Since consists of the sets whose complements are not in , these are exactly the coalitions that can prevent a strict social preference under the oligarchy with oligarchs : a coalition that can block a strict preference there can force an assignment here. Agreement, by contrast, cannot serve as the criterion for inclusion. If the coalitions that can secure the inclusion of a category formed a filter with , every member of could veto the inclusion of each category she does not propose, which is the counterpart of an oligarch’s veto,8 and a profile at which two members of disagree would leave the object without any category. Such a filter must therefore be an ultrafilter, which on a finite population means a dictatorship. Indeed, an individual with veto power is a dictator, since the outcome at every object is then a nonempty subset of .
The class of junta rules
The uniform junta rule is a special case of the general class in which the junta may depend on both the object and the category. For a family of coalitions , the general junta rule is defined, for all and all , by
Thus, category is assigned to object if and only if at least one member of assigns to . When for every and , the junta depends only on the object, and we obtain the object-dependent junta rule
Likewise, gives a rule whose junta depends only on the category, and gives the uniform junta rule .
A social classification must assign at least one category to each object and leave no category empty. The following proposition characterises when a junta rule is a CAC.
Proposition 3. Let be finite or infinite, , and let be a family of coalitions. Then is a CAC if and only if the following conditions hold:
In particular, is a CAC if and only if
is a CAC if and only if , and is a CAC if and only if .
The two conditions above correspond to the two requirements on a social classification. Condition eq. (1) ensures that, at each object, some individual belongs to the junta for every category. Whatever category she assigns to that object is therefore included in the social classification. Without such an individual, everyone can assign the object to a category whose junta does not contain her, leaving the object without any category.
Condition eq. (2) ensures that, for each category, some individual belongs to its junta at every object. Since her individual classification uses every category, she assigns at least one object to that category, and this assignment is included in the social classification. Without such an individual, everyone can use the category only at an object whose corresponding junta does not contain her, leaving the category empty. The individuals ensuring these requirements may differ across objects and categories.
By the definition of , the rule can be written in terms of its coalition families:
For , fix an object . The support sets have union . By the grill property applied to this finite union, at least one support set belongs to , so the outcome at is nonempty whenever . Ensuring that no category is left empty additionally requires the common-member condition eq. (3). Every individual in has her individual classification included in the social classification, and the assignments of the other individuals are included at the objects to whose juntas they belong.
The rule of Example 2 is with , and for every other pair. Its juntas satisfy eqs. (1) and (2), since voter 2 belongs to every junta at and to every junta for Biodiversity, and voter 1 belongs to every junta at and to every junta for Climate. No voter, however, belongs to all juntas, and neither individual classification is included in : voter 1’s Biodiversity at and voter 2’s Climate at are dropped.
Among the general junta rules that are CACs, only dictatorial rules are resolute. For each , choose , which is nonempty by eq. (1). If some contained , Lemma 1 would give a profile with and , so both and would be accepted at . Thus for every , and eq. (2) implies that all coincide. This recovers the dictatorship of Maniquet and Mongin [38] within the class of junta rules, and allowing multiple memberships is exactly what permits juntas with more than one member.
The next section characterises these rules and then returns to Example 4 to ask whether individual responsibility and equal treatment allow any supported assignments to be rejected.
Characterisations of junta rules
This section characterises junta rules by means of three axioms, each added to Independence and Supportiveness. The three axioms – Responsibility, Split Stability, and Rejection Stability – express different requirements. Responsibility looks for an individual whose report secures an assignment, Split Stability compares profiles before and after the support of a category is split, and Rejection Stability concerns coalitions that fail to secure one. Split Stability and Rejection Stability imply the grill property, the former by splitting a winning coalition and the latter by combining losing ones, while Responsibility identifies the generating junta directly.
Characterisation via Responsibility
We begin with a characterisation of junta rules based on the role of individual reports in ensuring acceptance. Responsibility requires that every accepted category with supporters be secured by one supporter’s complete classification, regardless of the other individuals’ reports.
Consider again the voters classifying proposals into categories for the platform. Each voter assigns every proposal to one category and uses every category, while the platform’s classification may assign several categories to the same proposal. These categories provide different thematic groups for comparing proposals. One may require that every accepted assignment with individual support be retained on the basis of one supporter’s complete classification, whatever the other individuals report. This excludes acceptance that depends on agreement among reports that are separately insufficient. It is an additional normative requirement and does not follow from allowing multiple memberships. Fioravanti [24] motivates granting individuals decisive power by their expertise or their direct connection to the objects or categories involved. Responsibility makes no assumption about individuals’ expertise and does not require decision power to be equally distributed among them.
For , denote by the profile in which individual reports and the other individuals report .
Axiom (Responsibility). A CAC satisfies Responsibility (Resp.) if, for every , and such that and , there exists such that
The individual may depend on the profile, the object and the category, but her report must ensure acceptance for every choice of the other reports. Her report is sufficient for inclusion; it need not be necessary, and more than one individual may satisfy the requirement. Under Supportiveness, every assignment can be traced to at least one such supporter, who in the participatory-budgeting setting could be asked to justify it. This provides a basis for accountability, although Responsibility does not single out a unique supporter.
Example 5. Let be three trained classifiers assigning two proposal descriptions, , to two thematic labels, , read as Arts and Biodiversity. The only surjective classifications are and . Let be majority voting at each object. This rule always uses both categories and therefore defines a CAC on this domain. At , it assigns to . The profiles and retain the reports of individuals 1 and 2, respectively, but both assign to . Neither supporter’s report ensures acceptance, so majority voting violates Responsibility, although each supporter is pivotal at . accepts whenever either supporter retains , whatever the others report.
Responsibility does not imply Supportiveness, since it imposes no condition on accepted categories without supporters; the constant CAC satisfies Responsibility. When Independence also holds, the individual’s assignment at the object suffices, whatever her assignments to the other objects.
Lemma 4. Let satisfy Independence and Responsibility. If and , there exists such that
Proof. Take as in Responsibility and any with . The profile belongs to , and Responsibility gives . Since , this profile and agree at , and Independence gives . ▪
Without Independence the assignment alone need not suffice. Under in Example 3, Arts at is secured by voter 2’s individual classification , which uses Arts twice, but not by her assignment at . If she instead reports , she still assigns to Arts, yet the proposal leaves Arts.
In the single-valued setting, Fioravanti [24] calls an individual minimally semi-decisive for a pair if her assignment of to suffices for society to assign to at every profile. Condition eq. (4) extends this notion to our setting. The power concerns the inclusion of a category, which need not be the only category assigned to the object. One voter may ensure that a proposal is placed in Biodiversity while another ensures that it is placed in Arts, and when they make these assignments both categories appear in the platform’s classification. Multiple memberships allow these powers to coexist at the same object. For each pair , let be the coalition of all individuals satisfying eq. (4). Under Supportiveness, Lemma 4 guarantees that every assigned category has a supporter in the corresponding coalition, and conversely the support of any member suffices. For in Example 2, these coalitions are the ones that define the rule: only voter 2 satisfies eq. (4) for and Biodiversity, only voter 1 for and Climate, and both voters for every other pair. This gives the following representation.
Theorem 1. Let . A CAC satisfies Independence, Supportiveness and Responsibility if and only if there exists a family satisfying eqs. (1) and (2) such that
This family is unique.
Under Category Neutrality the same junta applies to all categories at a given object, and under Object Neutrality as well it applies to all objects.
Corollary 1. Let .
(i) A CAC satisfies Independence, Supportiveness, Responsibility and Category Neutrality if and only if for a family of coalitions satisfying eq. (3).
(ii) A CAC satisfies Independence, Supportiveness, Responsibility, Category Neutrality and Object Neutrality if and only if for a nonempty coalition .
The proof of Theorem 1 identifies a responsible individual directly, so the characterisation also holds when or .
Characterisation via Split Stability
Our second characterisation concerns changes in the support sets. It asks how the social classification should respond when support for one category is divided between that category and a previously unused one.
Given , , distinct categories and a nonempty coalition , let denote the profile obtained from by setting for every and leaving all other entries unchanged. We call the passage from to a defection of to at . The defection is admissible if , that is, if for every . Not every defection from an arbitrary profile is admissible. When , however, Lemma 2 implies that every opinion vector at is realised by a profile at which every defection at is admissible.
Axiom (Split Stability). A CAC satisfies Split Stability if, for all , all , all such that and , and every nonempty such that , the following conditions hold:
(SS.1) .
(SS.2) .
To understand the normative aspect of the condition, consider a profile at which some individuals assign to a category and nobody assigns it to . Suppose that part of the supporters of switch to , for reasons unrelated to manipulation: the two categories may be similar, or new information about may lead some individuals to revise their view. Note that may also be classified into other categories under either profile. Then, condition (SS.1) requires that the categories supported by others be unaffected by this change. Condition (SS.2) requires that at least one of and be accepted after the split exactly when was accepted before it. If the original support was strong enough to place in , then after the split should be placed in or . Conversely, if was not placed in , the defectors should not be able to obtain a membership in or by splitting.
We return to Example 3.
Example 3 (Continued). Suppose now that voter 2 moves from Arts to Climate, a category that nobody had proposed for . Since she still uses Arts for , her new report is a classification, and the profile gives
At , the support for Arts has been split between Arts and Climate. The proposal stays in Arts, enters Climate and remains outside Biodiversity. Under , by contrast, the same change turns into at , so Biodiversity appears although nobody proposed it. At and , nobody changed her classification, yet the outcome changes from to and from to , because voter 2 now uses Arts once and Climate twice. ⋄
When voter 2 moves from Arts to the previously unused category Climate, keeps under Arts, adds Climate and leaves Biodiversity out, as (SS.1) and (SS.2) require. The same move makes add Biodiversity at , contrary to (SS.1). The changes that makes at and violate Independence. Split Stability constrains the outcome only at the object where the split occurs.
When , every individual classification is a bijection, no admissible split exists, and the axiom is vacuous. When , no category is vacant unless the profile is unanimous at ; under Supportiveness, Split Stability then holds automatically. We therefore state the result under .
Theorem 2. Let . A CAC satisfies Independence, Supportiveness and Split Stability if and only if there exists a family of nonempty coalitions satisfying eq. (3) such that . The family is unique.
The proof, in Section A, first shows that whether is assigned to depends only on the support set of at , then that the family of winning support sets does not depend on , and finally that is a grill. Finiteness of is used only at the last step, to conclude that the grill is principal (Fact 1). In particular, the junta at each object must be the same for all categories. The rule of Example 2 shows what goes wrong otherwise: if voter 1 alone proposes Biodiversity for , it is dropped, but if she moves to the previously unused category Climate instead, which is admissible when she uses Biodiversity for another proposal, the proposal enters Climate, contrary to (SS.2). Adding Object Neutrality removes the dependence of the junta on the object.
Corollary 2. Let . A CAC satisfies Independence, Supportiveness, Split Stability and Object Neutrality if and only if it is a uniform junta rule for some nonempty coalition .
Characterisation via Rejection Stability
Our third characterisation starts from the idea that coalitions whose submitted classifications are not enough to secure an assignment should not become enough merely by being combined. Consider again the platform’s classification of proposals, and suppose that a proposal is not placed in Biodiversity at either of two profiles. In each profile, the reports of the individuals who assign the proposal to Biodiversity are insufficient for the assignment. Rejection Stability requires the assignment to remain rejected whenever each supporter in a profile retains her own complete classification from one of the two rejecting profiles. The requirement concerns complete classifications because, without Independence, an individual’s assignments to other objects may affect the classification of the proposal.
Axiom (Rejection Stability). A CAC satisfies Rejection Stability (Rej. Stab.) if, for every , and such that and , we have whenever for every .
The two rejecting profiles may coincide. Each supporting report in must be the same individual’s report in or in , but different supporters may take their reports from different profiles, and only some of the original supporters need retain their support. Individuals who do not support the assignment in may submit arbitrary reports.
Example 6. Take the majority rule of Example 5, and consider , and . The outcome at is under both source profiles and under the target. Both supporters of in retain their reports, since and . Majority voting therefore violates Rejection Stability.
Rejection Stability does not imply Supportiveness either: the constant CAC satisfies it vacuously. The closure in Rejection Stability extends to any finite number of rejecting profiles.
Lemma 5. Let satisfy Rejection Stability, and let , with , be profiles such that for every . If satisfies for every , then .
Proof. We argue by induction on . For , the claim is Rejection Stability. Let , and let be the set of supporters with , so that for . By Lemma 1, there is with . Let be obtained from by replacing with for every . Every supporter of at in retains a report from one of , so by the induction hypothesis. Every supporter in retains her report from or from , and Rejection Stability gives . ■
Lemma 6. Let .
(i) On every population, Supportiveness and Responsibility imply Rejection Stability.
(ii) If is finite, Rejection Stability implies Responsibility.
Proof. (i) Let satisfy Supportiveness and Responsibility. Consider profiles that reject at and a profile satisfying the report condition of Rejection Stability. Suppose that . By Supportiveness, has a supporter in , and Responsibility provides such a supporter whose report ensures acceptance for every choice of the other reports. Since or , one of the source profiles must accept at , a contradiction. Hence Rejection Stability holds.
(ii) Let be finite and suppose that satisfies Rejection Stability. Take , and such that and . Suppose that Responsibility fails at this profile, object and category. Then, for every , there is a profile such that
These finitely many profiles reject at , and every supporter in retains her report from . By Lemma 5, , a contradiction. Thus Responsibility holds. ■
Thus, on finite populations, Responsibility and Rejection Stability are equivalent under Supportiveness, without Independence or either neutrality axiom. Combining Lemma 6 with Theorem 1 and Corollary 1 gives the third characterisation.
Theorem 3. Let .
A CAC satisfies Independence, Supportiveness and Rejection Stability if and only if for a unique family of coalitions satisfying eqs. (4.1a) and (4.1b).
Adding Category Neutrality characterises the object-dependent junta rules satisfying eq. (3), and adding Object Neutrality as well characterises the uniform junta rules with .
Under Independence and Supportiveness and when , Split Stability and Rejection Stability both yield the grill property. Split Stability requires that splitting a winning coalition leaves at least one winning part, while Rejection Stability requires that combining two losing coalitions never produces a winning one. The difference is that Split Stability also forces the winning coalitions to be the same for all categories at a given object, whereas Rejection Stability allows them to depend on the category. Thus, on finite populations, Theorems 2 and 3 show that Split Stability is equivalent to Rejection Stability together with Category Neutrality.
Independence cannot be omitted. The rule of Example 3 satisfies Supportiveness and both neutrality axioms. Every category it accepts is secured by the complete report of voter 1 or of voter 2, so Responsibility holds, and Lemma 6 gives Rejection Stability. Yet it is not a junta rule, since its outcomes at and change although nobody changes her classification of these proposals. Part (ii) of Lemma 6 fails on infinite populations, as § 8 shows.
Relations between the axioms
On finite populations, under Independence and Supportiveness and for , Split Stability is equivalent to Responsibility together with Category Neutrality, and to Rejection Stability together with Category Neutrality (Theorem 2, Corollary 1, and Lemma 6). Rejection Stability implies Responsibility for all , even without Independence or Supportiveness (Lemma 6(ii)). We now examine whether Unanimity can replace Supportiveness in the characterisations and what happens when we impose Anonymity.
Replacing Supportiveness with Unanimity
Our characterisations impose Supportiveness in place of the Unanimity axiom of Maniquet and Mongin [38]. The following proposition identifies when Unanimity and the other axioms already imply Supportiveness.
Proposition 4. Let .
(i) If , every CAC satisfying Unanimity, Independence and Split Stability satisfies Supportiveness.
(ii) Every CAC satisfying Unanimity and Rejection Stability satisfies Supportiveness.
Thus Theorems 2 and 3 and Corollary 2 remain valid when Supportiveness is replaced by Unanimity. For the characterisations through Responsibility in Theorem 1 and Corollary 1, this replacement is valid if and only if (cf. Proposition 2).
For , Supportiveness is therefore needed as a separate assumption in the characterisation through Responsibility. Responsibility, as stated, imposes no condition on accepted categories without supporters. In Example 1, Climate at is such a category: Responsibility imposes nothing on it, and Unanimity does not exclude it because the voters disagree. One could strengthen Responsibility by requiring every accepted category to be secured by some individual’s complete classification, whether or not that individual supports the assignment. Combined with Unanimity, this condition forces the responsible individual to be a supporter: if she assigned to some , letting every other individual do the same would produce a profile that is unanimous on at . Unanimity together with this condition is therefore equivalent to Supportiveness together with Responsibility, and we keep the more transparent second combination.
Anonymity and Responsibility
The preceding characterisations allow individuals to differ in their authority to secure an assignment. We now consider the effect of requiring equal treatment.
Notes: and correspond to and , respectively; is a general junta rule; is a quota rule; and is the majority rule on the domain , used in Example 5.
Axiom (Anonymity). A CAC satisfies Anonymity if, for every bijection and every , .
Note that in the running example, only and violate Anonymity. In Example 2, if the voters exchange their reports, the outcome at becomes instead of ; and in Example 3, only voter 2’s categories are subject to the repetition requirement.
Among general junta rules that are CACs, Anonymity holds if and only if for every object-category pair. Indeed, if one individual’s sole support secures an assignment, Anonymity gives every individual the same authority. The preceding characterisations therefore yield the following result.
Corollary 3. Let be finite and . A CAC satisfies Independence, Supportiveness, Anonymity and either Responsibility or Rejection Stability (or Split Stability, when ) if and only if it is .
Under the maintained axioms, Anonymity and Responsibility are thus compatible only through the whole-population junta rule , which accepts every supported assignment. To retain the possibility of rejecting some supported assignments while preserving Responsibility, individuals must be allowed to differ in whose support suffices. The quota procedure in Example 4 treats individuals equally but violates Responsibility, since neither voter can secure an assignment for which both voters’ support is required. Allowing different individuals to have different decision power therefore permits junta rules to reject some supported assignments.9
Table 1 collects the properties of the running examples. In particular, and illustrate the distinction above: the former satisfies Responsibility and the latter satisfies Anonymity, although they give the same outcome at the original profile. The table also includes the majority rule of Example 5.
Infinite populations
On finite populations, when , the three axioms of § 6 are interchangeable under Independence, Supportiveness and Category Neutrality. This section shows that they come apart when the population is infinite. The question is natural because the theorem of Maniquet and Mongin [38], our benchmark, fails on an infinite population (§ 8.1). Split Stability and Rejection Stability make the winning coalitions a grill that need not ેહ be principal and characterise a strictly larger class, the limiting junta rules (§ 8.2). Responsibility keeps the grill principal and characterises the junta rules as before (§ 8.3). Throughout, is an arbitrary set with at least two members, finite or infinite, while and remain finite with .
Benchmark: the Maniquet–Mongin theorem with an infinite population
Maniquet and Mongin [38] show that the decisive coalitions of a resolute CAC satisfying Independence and Unanimity form an ultrafilter on , with if and only if . Their argument uses the finiteness of only through the fact that every ultrafilter on a finite set is principal.
Corollary 4. Assume the axiom of choice. If is infinite, there exists a resolute CAC satisfying Independence, Supportiveness and Unanimity that is not dictatorial.
Proof. Let be a free ultrafilter on and let for the unique with ; uniqueness and existence follow from (p.4), (p.1) and the grill property of applied to the finite partition . Since is finite, , where , and any individual in this intersection satisfies for every , so the outcome is surjective. Independence and Supportiveness are immediate, and a dictator would give , contradicting freeness. ■
Hence the theorem of Maniquet and Mongin holds if and only if is finite. The rule in Corollary 4 relies on a free ultrafilter, whose existence requires a weak form of the axiom of choice, so it cannot be defined explicitly. This is the classification counterpart of the observation of Fishburn [28] and Kirman and Sondermann [35].
Split Stability and Rejection Stability: limiting junta rules
Fix and . A coalition is winning for at if for every with , and null for at if for every such . We write for the family of winning coalitions.
Under Independence and Supportiveness, Split Stability and Rejection Stability each make every coalition either winning or null for at , and make a grill, whether is finite or infinite (Lemma 7 in Section A). Under Split Stability, or under Rejection Stability and Category Neutrality, does not depend on , and under Object Neutrality as well it does not depend on . On a finite population this grill is principal, which yields the junta rules of § 6. On an infinite population it need not be. To describe the resulting rules, call a nonempty family of nonempty coalitions directed if for all there is with .
Definition 2. Given a family of directed families, the object-dependent limiting junta rule is defined, for all and all , by
It is a uniform limiting junta rule, written , if for every .
Reading each as a committee, a category is attached to exactly when every committee contains someone who attaches it. The rule is the limit of junta rules as the committees shrink along , in the same way as the limiting dictatorial rules of Torres [48] are limits of dictatorships. An object-dependent junta rule is the case .
For each , the family is a grill, every grill arises in this way from the directed family of its blocking coalitions, and if and only if (Lemma 8 in Section A). The limiting junta rules are therefore exactly the rules that accept a category when its support set belongs to a grill. Such a rule is a CAC if and only if
a condition that holds automatically for uniform limiting junta rules. This yields the characterisation on an arbitrary population.
Theorem 4. Let be finite or infinite.
(a) Let . A CAC satisfies Independence, Supportiveness and Split Stability if and only if for a family of directed families satisfying eq. (6).
(b) Let . A CAC satisfies Independence, Supportiveness, Rejection Stability and Category Neutrality if and only if for a family of directed families satisfying eq. (6).
In both cases, adding Object Neutrality characterises the uniform limiting junta rules.
Thus, when is finite or infinite and , a CAC satisfying Independence and Supportiveness satisfies Split Stability if and only if it satisfies Rejection Stability and Category Neutrality. The next proposition compares limiting junta rules with junta rules.
Proposition 5. (i) for some family of coalitions if and only if every has a smallest member, in which case is the smallest member of .
(ii) If is infinite and is the family of cofinite coalitions, then , and is not a junta rule: for every family of coalitions.
By Fact 4, part (i) says that a limiting junta rule is an object-dependent junta rule exactly when every winning family is principal. On a finite population this is always the case: by directedness, a member of of minimal cardinality is contained in every other member, so every limiting junta rule is an object-dependent junta rule. This is the counterpart of the fact that every ultrafilter on a finite set is principal, and it is the only point at which finiteness matters. Under the respective assumptions of Theorem 4, Split Stability and Rejection Stability therefore characterise a class strictly larger than the object-dependent junta rules when is infinite. We call the rule in (ii) the Fréchet rule, since its winning family consists of the infinite sets, which are exactly the sets that meet every member of the Fréchet filter of cofinite sets.10 It satisfies Independence, Supportiveness, Split Stability, Rejection Stability and both neutrality axioms, yet it is not a junta rule. Its committees are defined without any appeal to the axiom of choice, so its existence is provable in ZF, whereas that of the rules in Corollary 4 is not. The difference lies in the form of the output. A set-valued rule needs only a directed family of committees, whereas a single-valued rule needs its decisive coalitions to form an ultrafilter. The Fréchet rule also violates Responsibility: starting from unanimous support for at , retain any one individual’s report and let all others assign to another category, which is possible by Lemma 1; the category then has a single supporter and is rejected.
Responsibility: junta rules on every population
Responsibility continues to characterise junta rules on infinite populations.
Corollary 5. Let be infinite and . Then Theorem 1 and Corollary 1 remain valid. In particular, an object-dependent limiting junta rule satisfies Responsibility if and only if every winning family is principal, that is, if and only if it is an object-dependent junta rule.
In fact, the proofs of Theorem 1 and Corollary 1 do not use the finiteness of . An object-dependent limiting junta rule satisfies Independence, Supportiveness and Category Neutrality, so by Corollary 1(i) it satisfies Responsibility if and only if it is an object-dependent junta rule. By Proposition 5(i) and Fact 4, this holds if and only if every is principal.
The contrast with Theorem 4 lies in the way each axiom identifies the members of a junta. Split Stability and Rejection Stability relate a coalition to two of its parts at a time: if the union of two coalitions is winning, so is one of them (Lemma 7). On a finite population, splitting a winning coalition again and again ends with a single winning individual, and these individuals form the junta. On an infinite population the process need not end. At every accepted category, Responsibility names a supporter whose report secures the category on her own (Lemma 4), so each member of the junta is identified directly, whatever the size of the population. Put differently, under Supportiveness Responsibility requires rejection to survive the combination of any number of rejecting profiles, one for each supporter, whereas Rejection Stability requires this only for finitely many (Lemma 5), and the two coincide when is finite (Lemma 6).
Concluding remarks
This paper asks how little of the framework of Maniquet and Mongin [38] must be given up to escape their impossibility. We keep their individual domain, in which every individual reports a single category for each object and uses every category, together with Independence and the requirement that the social classification classify every object and leave no category empty. We allow an object to belong to several categories in the social classification and strengthen Unanimity to Supportiveness. In the resolute benchmark, Independence and Unanimity already imply Supportiveness (Proposition 1). With at least three categories, Independence and Unanimity permit a set-valued oligarchy rule that places every disputed object in all categories, including unsupported ones (Proposition 2).
On finite populations, Independence and Supportiveness together with either Responsibility or Rejection Stability characterise the general junta rules (Theorems 1 and 3). Together with Split Stability they characterise the object-dependent junta rules when (Theorem 2), and the neutrality axioms reduce the juntas to a single coalition (Corollaries 1 and 2 and Theorem 3). In each case the juntas are uniquely determined by the rule. Supportiveness can be replaced by Unanimity in the characterisations through Split Stability and Rejection Stability but, when , not in the one through Responsibility (Proposition 4). When outcomes are required to be singletons, every junta shrinks to the same individual, and the dictatorship of Maniquet and Mongin reappears as the resolute special case.
The characterisations describe what multiple memberships make possible; they do not single out a recommended junta. Adding Anonymity leaves only , which accepts every proposed membership (Corollary 3). Under the maintained axioms, a rule that rejects some supported memberships while satisfying Responsibility must therefore give some individuals more authority than others, whereas a rule that is selective and treats individuals equally, such as the quota procedure of Example 4, must give up Responsibility.
Table 2 places these results alongside the decisive structures of preference aggregation. An ultrafilter is exactly a family that is both a filter and a grill (Fact 3). The Arrowian literature on weakened collective rationality retains the filter half: under quasi-transitive social preferences, the decisive coalitions form the principal filter of an oligarchy , and each oligarch can veto a strict social preference (Gibbard, [31]). Multiple memberships retain the grill half: for each object and category, the coalitions that secure the membership form the principal grill , and each member of the junta can secure the inclusion of the category she proposes. The two structures are dual (Fact 4), since the coalitions that can block a strict social preference under the oligarchy with oligarchs are exactly those that secure a membership under . If the coalitions able to secure a membership formed a filter with , an object on which two members of disagree would receive no category (§ 5.1). Multiple memberships let the powers of different junta members coexist at the same object, and Supportiveness ensures that every membership they create rests on an individual report.
On infinite populations the three axioms come apart. The theorem of Maniquet and Mongin fails there, as Arrow’s theorem does (Fishburn, [28]; Kirman and Sondermann [35]), but only through free ultrafilters, whose existence requires a weak form of the axiom of choice (Corollary 4). Split Stability, and Rejection Stability together with Category Neutrality, characterise the limiting junta rules, whose winning coalitions form grills that need not be principal (Theorem 4). This class contains the Fréchet rule, which assigns a category to an object exactly when infinitely many individuals propose it and is defined without any appeal to choice (Proposition 5).
Notes. In preference aggregation, individual preferences are complete and transitive, the domain is unrestricted, and the alternative set contains at least three elements. The filter and grill statements concern families of decisive and quasi-decisive coalitions, respectively, and do not by themselves uniquely determine the aggregation rule. The structures called quasi-ultrafilters by Cato [8] are termed grills here. WP denotes weak Pareto, IIA independence of irrelevant alternatives, and AC the axiom of choice. In classification aggregation, I denotes Independence, SS Split Stability, and CN Category Neutrality. The single-valued classification row is stated for . The Split Stability characterisations require , while the Responsibility and Rejection Stability characterisations hold for . The junta and limiting junta rules satisfy the covering conditions stated in the corresponding results.
Responsibility, by contrast, keeps the grills principal on every population (Corollary 5), because it identifies each member of a junta directly instead of reaching her by splitting coalitions. The axioms thus differ in whether a membership must be secured by an individual supporter or may rest on infinite groups, none of whose finite subgroups secures it on its own.
Equal treatment also fares differently than in Arrowian aggregation. On infinite populations, anonymity is inconsistent with Arrow’s unanimity and independence conditions on sufficiently rich domains ([39]). The same is true of resolute CACs satisfying Independence and Unanimity, whose decisive coalitions form an ultrafilter (§ 8.1), since no ultrafilter on is invariant under all permutations of . With multiple memberships, by contrast, satisfies Anonymity on every population, and the Fréchet rule does so on every infinite population, because permutations of preserve whether a support set is nonempty or infinite.
We close with three directions for future research.
In our model individuals report one category for each object, so multiple memberships can arise only in the social classification. In many applications, however, individuals may themselves wish to place an object in several categories; a voter may judge that a project belongs to Biodiversity and Climate. A natural extension lets individual reports take the same form as social classifications, so that the input and output domains coincide. Supportiveness then requires every collective membership to be proposed by some individual, and an independence condition applied separately to each membership statement, combined with Unanimity, already delivers it. The junta rules remain well defined and are CACs under the same conditions on their juntas. Moreover, since single-valued reports remain admissible, any rule satisfying extensions of our axioms that reduce to them on single-valued profiles must coincide with a junta rule on those profiles. An individual may now support several categories at the same object, so the support sets at an object overlap instead of partitioning the population. Responsibility and Rejection Stability are stated in terms of individual reports and extend almost verbatim, whereas Split Stability, which moves supporters from one category to another, admits several non-equivalent reformulations once an individual can add a category without abandoning another. Whether these axioms still deliver grills on the richer domain, and how the rules they characterise behave at profiles with set-valued reports, remain open.
We have not studied incentives. Under a junta rule, an individual’s report at an object matters only through the category she proposes there, and only if she belongs to the junta for that object and category. She can add that category to the social classification, but she cannot remove a category proposed by another member of the corresponding junta. How this limited influence translates into incentives depends on how individuals evaluate social classifications with multiple memberships, for instance by their proximity to their own reports, so a strategic analysis must first specify such evaluations. Under the Fréchet rule, changing the reports of finitely many individuals never changes whether a support set is infinite, so no finite coalition can affect the outcome, while infinite coalitions can; on infinite populations, the relevant notion of manipulation is therefore coalitional.
We have adopted the membership reading throughout. Under the tie reading, the set assigned to an object lists the categories that remain admissible for it, and a single category is selected later. The natural requirement on outcomes is then that some selection be surjective, which means that, for every set of categories, at least objects are assigned a set that meets . The oligarchy rule satisfies this requirement, since the classification of any member of is a surjective selection, and under this reading it becomes a reasonable counterpart of an oligarchy; junta rules may fail it, as in Example 2 does. As noted in § 3.1, if the final selection satisfies the requirements of Maniquet and Mongin [38], their impossibility returns at that stage. The question is therefore what the set-valued stage can achieve by itself, and in particular whether the filter-based structures that are unavailable under the membership reading reappear under the tie reading, as they do in preference aggregation. A related question concerns populations modelled by measure spaces (Cato, [9]), in which individuals may be negligible, and in which the contrast between Responsibility, which relies on individual supporters, and the two stability axioms, which only compare coalitions, can be expected to take a different form.
References
Proofs
Proof of Proposition 2
(i) Fix . By definition, at every object. Thus outcomes are nonempty, and every category is used because is surjective. The outcome at depends only on the reports at , and unanimous support for gives . Hence Independence and Unanimity hold. The definition is unchanged by relabelling objects or categories, so both neutrality axioms hold.
(ii) If , the rule returns at every object. If , Lemma 1 gives a profile where two members disagree at some object. The outcome there is , so the rule is not dictatorial.
(iii) If the members of agree on , both rules return . If they disagree and , both categories have a supporter in , so both rules return .
(iv) Choose distinct , and distinct , , . By Lemma 1, choose a profile where assigns to , assigns it to , and everyone assigns it to either or . The outcome is , so it includes the unsupported category .
Proof of Proposition 3
(a) Suppose that eqs. (4.1a) and (4.1b) hold. Fix a profile . For each , choose . Then , so receives . For each , choose . Surjectivity gives an object with , and ensures that receives . Thus every object receives a category and every category is used.
(b) Conversely, suppose the rule is a CAC. If eq. (4.1a) fails at , each can choose with . By Lemma 1, realise the assignments . No category has a supporter in its junta at , leaving without a category.
(c) Likewise, if eq. (4.1b) fails for , each can choose with . Set and map the remaining objects onto , possible because . Then is surjective and uses only at . Every supporter of is therefore outside the relevant junta, leaving unused.
The special cases follow by substitution.
Proof of Theorem 1
(a) Suppose satisfies Independence, Supportiveness and Responsibility. For each , , let consist of the individuals whose assignment of to guarantees its acceptance at every profile. By Supportiveness and Lemma 4, every accepted assignment has a supporter in . Conversely, the support of any member of ensures acceptance by definition. Thus . This gives eq. (5), and Proposition 3 gives eqs. (4.1a) and (4.1b).
(b) Uniqueness. By Lemma 1, any individual can be the sole supporter of at . At such a profile, is accepted exactly when , which determines every uniquely.
(c) Conversely, let have the stated junta representation. The rule is a CAC by Proposition 3 and satisfies Independence and Supportiveness by its definition. For every accepted assignment, choose . Keeping unchanged preserves this support whatever the others report, so Responsibility holds.
Proof of Corollary 1
(i) By Theorem 1, write . Fix , distinct , , and . By Lemma 1, take a profile where alone supports at . Swapping and makes the sole supporter of at . Category Neutrality therefore gives . Hence for every , and Proposition 3 gives eq. (3). Conversely, these rules satisfy Category Neutrality and the axioms of Theorem 1.
(ii) By (i), write . Take a profile where alone supports at , and swap objects and in every report. Now alone supports at , so Object Neutrality gives if and only if . Thus all equal a common nonempty coalition . Conversely, a uniform junta rule also satisfies Object Neutrality.
Proof of Theorem 2
(a) Suppose satisfies Independence, Supportiveness and Split Stability, and fix . By Independence, write . By Lemma 2, each opinion vector can be realised with every individual’s report surjective on . All changes at below therefore preserve surjectivity.
Claim 1. Whether depends only on .
Proof. Fix and . Start with the opinion vector assigning to members of and to everyone else. To reach any with , move each nonempty group , , from to in turn. Each destination is vacant, so (SS.1) preserves whether is accepted throughout.
Let be the family of support sets that lead to acceptance of . Supportiveness and Lemma 3 give and .
Claim 2. The family is the same for every category .
Proof. Choose distinct , , and a nonempty . Let members of support and everyone else support . Move all of from to the vacant category . By (SS.2), was accepted exactly when or is now accepted. Supportiveness excludes the now unsupported , so if and only if . The empty set belongs to neither family.
Writing for this common family, we have
Claim 3. For disjoint , if and only if or .
Proof. If either set is empty, use . Otherwise, choose distinct , , . Let support and everyone else support , then move to the vacant category . The two support sets become and , so (SS.2) gives the claim.
The claim implies upward closure: if and , apply it to . It also gives the grill property: if , apply it to and use upward closure. Thus is a grill. Since is finite, Fact 1 gives a unique nonempty with . Equation (A.1) then gives , and Proposition 3 gives eq. (3).
(b) Conversely, let satisfy eq. (3). It is a CAC by Proposition 3; its definition gives Independence and Supportiveness. Consider an admissible defection of to a vacant category . Other support sets are unchanged, giving (SS.1). The support of splits into and . At least one part meets exactly when the original set does, giving (SS.2).
Proof of Corollary 2. By Theorem 2, write . Swapping objects as in the proof of Corollary 1(ii) shows that Object Neutrality makes all equal. Conversely, every uniform junta rule satisfies Object Neutrality and the axioms of Theorem 2.
Proof of Theorem 3. On finite populations, Responsibility and Rejection Stability are equivalent under Supportiveness by Lemma 6. Parts (i) and (ii) therefore follow from Theorem 1 and Corollary 1, respectively.
Proof of Proposition 4. In each case, we show that a category with no supporters is rejected. Fix with .
(i) Let be the categories used at in . By Lemma 2, start from a profile where everyone assigns to and every report is surjective on . Unanimity rejects . For , move from to the vacant category . Every move is admissible, and (SS.1) preserves rejection of because . The resulting opinion vector is , so Independence gives .
(ii) By Lemma 1, take a profile where everyone assigns to some . Unanimity rejects there. Apply Rejection Stability with both source profiles equal to and target . Its report condition is vacuous because has no supporter of at , so .
Proof of Theorem 4.
Lemma 7. Let be finite or infinite, and let satisfy Independence, Supportiveness, and either Split Stability (with ) or Rejection Stability (with ). Then, for every and :
(i) every is either winning or null for at ;
(ii) is a grill.
Under Split Stability, or under Rejection Stability and Category Neutrality, does not depend on ; under Object Neutrality as well, it does not depend on .
Proof.
(a) Split Stability. The three claims in the proof of Theorem 2 and the argument following them give the result. Those steps apply to infinite populations as well: the number of defections is finite because is finite.
(b) Rejection Stability. Fix . Suppose rejects with support set , and take any profile with the same support set. Form by taking for and for everyone else. Since , Independence makes reject . Every supporter in retains her report from , so Rejection Stability, with both source profiles equal to , makes reject . Thus every coalition that is not winning is null.
Let be the family of null coalitions. Take and any profile with support set . Choose profiles with support sets , retaining in for and in for . Complete the other reports using Lemma 1. Both profiles reject , and each supporter in retains her report from at least one of them. Rejection Stability therefore makes reject , so is null. Hence is downward closed and closed under union. Supportiveness and Lemma 3 give and . Its complement is therefore a grill.
(c) Neutrality. Swapping and turns each support set for into the same support set for , so Category Neutrality gives . Likewise, swapping and and applying Object Neutrality gives .
Lemma 8. Let be a family of directed families, and write for every .
(i) Each is a grill, and if and only if .
(ii) Conversely, for every grill , its family of blocking coalitions is directed and .
(iii) is a CAC if and only if eq. (6) holds. This condition holds automatically for uniform limiting junta rules.
Proof.
(i) Since is a nonempty family of nonempty coalitions, and . Upward closure follows from the definition. If , choose disjoint from , respectively. Directedness gives with . Then is disjoint from , proving the grill property. The representation of is its definition.
(ii) By Fact 4, is a filter, hence directed, and .
(iii) At each object, the finitely many support sets partition . The grill property therefore makes at least one of them winning, so the outcome is nonempty. It remains to check that every category is used. Suppose eq. (6) holds and is unused. For each , choose disjoint from . Any would then assign no object to , contradicting surjectivity.
Conversely, suppose for each and . Fix and, for each , choose with . Set and map the remaining objects onto , possible because . Thus at every , leaving unused.
For a uniform rule, directedness and finiteness of ensure that every intersection contains a member of . That member is nonempty, so eq. (6) holds.
Proof of Theorem 4.
(a) Suppose satisfies either set of axioms. By Lemma 7, acceptance at is determined by a grill common to all categories. Set . By Lemma 8(ii), is directed and , so . Part (iii) gives eq. (6) because is a CAC. Under Object Neutrality, Lemma 7 makes , and hence , the same for every object.
(b) Conversely, let satisfy eq. (6) and write . By Lemma 8, is a CAC with . This gives Independence and Category Neutrality; gives Supportiveness.
For Split Stability, an admissible defection to a vacant category leaves all other support sets unchanged, giving (SS.1). It splits the original support set into two parts. The grill property and upward closure say that the original set is winning exactly when at least one part is winning, giving (SS.2).
For Rejection Stability, let reject at and let satisfy its report condition. Then . The union is losing by the grill property, and every subset of a losing set is losing by upward closure. Thus rejects at . Uniform limiting junta rules also satisfy Object Neutrality.
Proof of Proposition 5
(i) If is the smallest member of , a coalition meets every member exactly when it meets . Hence .
Conversely, suppose . By Lemma 1, every coalition can occur as a support set at , so . For each , the singleton is winning and therefore meets every member of . Thus is contained in every member. Since is losing, some is disjoint from it, so . Hence is the smallest member. (ii) Since is infinite, cofinite coalitions are nonempty and closed under finite intersections, hence directed. A finite set misses the cofinite set , while an infinite set meets every cofinite set. Thus a category is accepted exactly when its support set is infinite. Suppose this rule were . Fix . Unanimous support is accepted, so . For , Lemma 1 gives a profile where alone supports at . The junta rule accepts there, whereas the limiting rule rejects it because its support set is finite. This is a contradiction.
Independence of the axioms
The following CACs show that no axiom can be dropped from the main characterisations. We assume that has at least two members, and fix distinct categories and an object where needed.
| Characterisation | w/o Independence | w/o Supportiveness | w/o third axiom | w/o neutrality |
| Theorem 1 (Resp.) | – | |||
| Corollary 1(i) (Resp., CN) | ||||
| Theorem 2 (SS) | – | |||
| Corollary 2 (SS, ON) | ||||
| Theorem 3(i) (Rej. Stab.) | – | |||
| Theorem 3(ii) (Rej. Stab., CN) |
Table 3. Examples showing the independence of the axioms. The examples , , and require , or , and , respectively.
. (Requires .) . It satisfies Supportiveness, Responsibility, Rejection Stability, Split Stability and both neutrality axioms, but not Independence (§ 6.3). This is the rule of Example 3. For Split Stability, note that in an admissible defection individual 2 can defect from only if appears elsewhere in , and the vacant category appears elsewhere in because is surjective; hence individual 2 is included before the defection if and only if she is included after it, and the outcome changes only within .
. (Requires or .) For fixed and , . It satisfies Supportiveness, Responsibility and Rejection Stability, because each accepted category is secured by the individual classification of individual 1 or 2, but not Independence.
. The constant CAC satisfies Independence, Split Stability, Responsibility, Rejection Stability and both neutrality axioms, but not Supportiveness.
. for , and if every individual assigns to and otherwise. It is a CAC: category is used at some object other than unless every individual assigns only to , in which case the profile is unanimous on at . It satisfies Independence and Supportiveness. It violates Responsibility at a profile that is unanimous on at , hence also Rejection Stability by Lemma 6, and it violates Split Stability when : if some individuals assign to and the others to , letting all supporters of defect to a vacant category changes the outcome from to , contrary to (SS.2).
. (Requires .) . It satisfies Independence, Supportiveness and both neutrality axioms, but not Responsibility, and hence not Rejection Stability.
. with and for satisfies Independence, Supportiveness, Responsibility and Rejection Stability, but not Category Neutrality.
. with and for satisfies all axioms of Theorem 2 and Corollary 1 except Object Neutrality.
References
- [1]Alcantud, J. C. R., Díaz, S., and Montes, S. (2019). Liberalism and dictatorship in the problem of fuzzy classification. International Journal of Approximate Reasoning, 110:82–95. [5]DOI
- [3]Bossert, W. and Cato, S. (2020). Acyclicity, anonymity, and prefilters. Journal of Mathematical Economics, 87:134–141. [4]DOI
- [4]Bossert, W. and Suzumura, K. (2009). Decisive coalitions and coherence properties. PIE/CIS Discussion Paper 427, Center for Intergenerational Studies, Institute of Economic Research, Hitotsubashi University. [5, 24]
- [5]Brown, D. J. (1975). Aggregation of preferences. Quarterly Journal of Economics, 89(3):456–469. [4]DOI
- [6]Cailloux, O., Hervouin, M., Özkes, A. I., and Sanver, M. R. (2024). Classification aggregation without unanimity. Mathematical Social Sciences, 128:6–9. [4, 11]arxiv.org/abs/2310.11841
- [7]Cailloux, O., Hervouin, M., Özkes, A. I., and Sanver, M. R. (2025). Anonymous and neutral classification aggregation. Working paper, Université Paris Dauphine–PSL. [4, 20]DOI
- [8]Cato, S. (2013). Quasi-decisiveness, quasi-ultrafilter, and social quasi-orderings. Social Choice and Welfare, 41(1):169–202. [5, 9, 24]DOI
- [9]Cato, S. (2021). Preference aggregation and atoms in measures. Journal of Mathematical Economics, 94:102446. [6, 25]DOI
- [10]Cato, S. (2022). Stable preference aggregation with infinite population. Social Choice and Welfare, 59(2):287–304. [6]DOI
- [11]Cato, S., Gonzalez, S., Réмila, E., and Solal, P. (2026). Filters in abstract aggregation with infinite sequences of signals. Mathematical Social Sciences, 142:102551. [5]DOI
- [12]Cho, W. J. and Ju, B.-G. (2017). Multinary group identification. Theoretical Economics, 12(2):513–531. [5]DOI
- [13]Cho, W. J. and Park, C. W. (2018). Fractional group identification. Journal of Mathematical Economics, 77:66–75. [5]DOI
- [14]Choquet, G. (1947). Sur les notions de filtre et de grille. Comptes rendus de l’Académie des sciences, Paris, 224:171–173. [4, 5, 10]
- [15]Craven, J. (2023). Domain restrictions in the aggregation of classifications. Global Philosophy, 33:12. [4, 11]DOI
- [16]Craven, J. (2024). Aggregation of ranked categories. Mathematical Social Sciences, 129:27–33. [4]DOI
- [17]Dietrich, F. and List, C. (2007). Judgment aggregation by quota rules: Majority voting generalized. Journal of Theoretical Politics, 19(4):391–424. [5]
- [18]Dietrich, F. and List, C. (2008). Judgment aggregation without full rationality. Social Choice and Welfare, 31(1):15–39. [5, 12]DOI
- [19]Dimitrov, D., Marchant, T., and Mishra, D. (2012). Separability and aggregation of equivalence relations. Economic Theory, 51(1):191–212. [4]DOI
- [20]Dokow, E. and Holzman, R. (2010a). Aggregation of binary evaluations with abstentions. Journal of Economic Theory, 145(2):544–561. [5]DOI
- [21]Dokow, E. and Holzman, R. (2010b). Aggregation of non-binary evaluations. Advances in Applied Mathematics, 45(4):487–504. [4, 5, 11]DOI
- [22]Endriss, U. and Grandi, U. (2017). Graph aggregation. Artificial Intelligence, 245:86–114. [5, 11]
- [23]Filmus, Y. (2026). Classification aggregation: A quantitative impossibility theorem. arXiv preprint arXiv:2605.17136. [4]arxiv.org/abs/2605.17136
- [24]Fioravanti, F. (2025a). Expert classification aggregation. Mathematical Social Sciences, 137:102406. [3, 4, 15, 16]
- [25]Fioravanti, F. (2025b). Fuzzy classification aggregation. Mathematical Social Sciences, 135:102422. [5, 11]
- [26]Fioravanti, F. and Tohmé, F. (2020). Asking infinite voters ‘Who is a J?’: Group identification problems in ℕ. Journal of Classification, 37(1):58–65. [6]
- [27]Fioravanti, F. and Tohmé, F. (2022). Fuzzy group identification problems. Fuzzy Sets and Systems, 434:159–171. [5]DOI
- [28]Fishburn, P. C. (1970). Arrow’s impossibility theorem: Concise proof and infinite voters. Journal of Economic Theory, 2(1):103–106. [4, 6, 21, 23, 24]DOI
- [29]Fishburn, P. C. and Rubinstein, A. (1986). Aggregation of equivalence relations. Journal of Classification, 3:61–65. [4]DOI
- [30]Gibaja, E. and Ventura, S. (2015). A tutorial on multilabel learning. ACM Computing Surveys (CSUR), 47(3):1–38. [2]DOI
- [32]Hansson, B. (1976). The existence of group preference functions. Public Choice, 28(1):89–98. [5, 24]DOI
- [33]Hervouin, M. (2025). Advances in Classification Aggregation and Proportionality. PhD thesis, Université Paris Dauphine–PSL. [2, 4]
- [34]Kasher, A. and Rubinstein, A. (1997). On the question “Who is a J?”: A social choice approach. Logique et Analyse, 40(160):385–395. [4, 5]
- [35]Kirman, A. P. and Sondermann, D. (1972). Arrow’s theorem, many agents, and invisible dictators. Journal of Economic Theory, 5(2):267–277. [4, 5, 6, 21, 23, 24]
- [36]Kurata, L. and Nakamura, K. (2025). Reservation of judgment and robust collective decisions. arXiv preprint arXiv:2512.16240. [11]arxiv.org/abs/2512.16240
- [37]Kurata, L. and Nakamura, K. (2026). Agreement with reservation of judgment under risk. arXiv preprint arXiv:2601.01334. [11]arxiv.org/abs/2601.01334
- [38]Maniquet, F. and Mongin, P. (2016). A theorem on aggregating classifications. Mathematical Social Sciences, 79:6–10. [2, 3, 4, 5, 6, 7, 10, 11, 13, 14, 19, 20, 21, 23, 24, 25]DOI
- [39]Mihara, H. R. (1997a). Anonymity and neutrality in Arrow’s theorem with restricted coalition algebras. Social Choice and Welfare, 14(4):503–512. [6, 24]DOI
- [40]Mihara, H. R. (1997b). Arrow’s theorem and Turing computability. Economic Theory, 10(2):257–276. [6]DOI
- [41]Miller, A. D. (2008). Group identification. Games and Economic Behavior, 63(1):188–202. [5]DOI
- [42]Mirkin, B. G. (1975). On the problem of reconciling partitions. In Blalock, H. M., Aganbegian, A., Borodkin, F. M., Boudon, R., and Capecchi, V., editors, Quantitative Sociology: International Perspectives on Mathematical and Statistical Modeling, pages 441–449. Academic Press, New York. [4]DOI
- [43]Samet, D. and Schmeidler, D. (2003). Between liberalism and democracy. Journal of Economic Theory, 110(2):213–233. [5]DOI
- [44]Sen, A. K. (1970). Collective Choice and Social Welfare, volume 5 of Mathematical Economics Texts. Holden-Day, San Francisco. [8]
- [46]Sung, S. C. and Dimitrov, D. (2005). On the axiomatic characterization of “Who is a J?”. Logique et Analyse, 48(189–192):101–112. [5]
- [47]Szegedy, M. and Xu, Y. (2015). Impossibility theorems and the universal algebraic toolkit. arXiv preprint arXiv:1506.01315. [5]arxiv.org/abs/1506.01315
- [48]Torres, R. (2005). Limiting dictatorial rules. Journal of Mathematical Economics, 41(7):913–935. [6, 21]DOI
- [49]Weymark, J. A. (1984). Arrow’s theorem with social quasi-orderings. Public Choice, 42(3):235–246. [2, 4, 24]DOI