Classification Aggregation with Multiple Memberships

Federico Fioravanti, Leo Kurata, Vasilis StamatisarXiv 2026 · arXiv

TL;DR

This paper explores how to aggregate individual opinions into a collective classification when an object can belong to multiple categories simultaneously (e.g., a project being labeled as both "Arts" and "Climate"). The authors prove that under natural fairness and independence conditions, the only valid aggregation methods are "junta rules"—where specific groups of individuals have the power to secure a category's inclusion simply by proposing it.

What Problem Does This Paper Address?

In classical social choice theory, aggregating individual classifications often leads to a "dictatorship" result: if you want a rule that is consistent, independent, and respects unanimous agreement, you are mathematically forced to follow a single person's opinion. This is the classification equivalent of Arrow’s Impossibility Theorem.

However, real-world classification isn't always "one-size-fits-all." In participatory budgeting, a resident might classify a greening project as "Biodiversity," while another calls it "Climate Adaptation." A rigid system forces a choice, but a flexible one allows for multiple memberships. The authors ask: if we allow the collective outcome to be a set of categories rather than just one, what new, non-dictatorial rules become possible?

Methods

The authors use an axiomatic approach, defining desirable properties (axioms) for a Classification Aggregation Correspondence (CAC) and then mathematically deriving the class of rules that satisfy them.

Key axioms introduced include:

  • Supportiveness: A category can only appear in the final result if at least one person proposed it.
  • Responsibility: Every category in the final result must be "secured" by at least one individual’s report, meaning that individual's choice alone is sufficient to include that category regardless of what others say.
  • Split Stability: If support for a category is split between that category and a new, previously unused one, the rule should remain stable in how it treats the original memberships.
  • Rejection Stability: If two different groups of voters fail to get a category included, combining their reports shouldn't suddenly make that category "win."

The paper also bridges social choice with topology by showing that the coalitions capable of securing an assignment form a grill, which is the mathematical dual of a filter (the structure typically found in Arrovian preference aggregation).

Datasets

This is a theoretical paper in mathematical economics and social choice theory; therefore, no empirical datasets were used. The authors illustrate their findings using hypothetical examples, such as a participatory budgeting platform and the aggregation of predictions from multiple machine-learning classifiers.

Key Insights and Ideas

  • From Dictators to Juntas: While single-category outcomes force a dictatorship, multiple-membership outcomes allow for "juntas." In a junta rule, a category is assigned to an object if at least one member of a specific coalition (the junta) proposes it.
  • The Power of Inclusion: In standard voting, power is often about vetoing or deciding the sole winner. Here, power is about inclusion. Different individuals can have the power to include different categories for the same object.
  • Grills vs. Filters: The authors provide a beautiful mathematical symmetry. In traditional preference aggregation (like ranking candidates), decisive coalitions form filters (where everyone in the group must agree). In classification with multiple memberships, they form grills (where any one member can trigger an inclusion).
  • Infinite Populations: The paper explores what happens if the number of voters is infinite. In this case, the axioms diverge. They identify the Fréchet rule, which includes a category only if an infinite number of people support it—a rule that is anonymous and neutral but impossible to implement in finite settings.

Key Results

  • Characterization Theorems: The authors prove that on finite populations, any rule satisfying Independence, Supportiveness, and either Responsibility or Rejection Stability must be a junta rule.
  • Anonymity and Responsibility: If you demand that all voters be treated equally (Anonymity) and that individuals be responsible for inclusions, you are forced to use the full-population junta rule (the "union" rule), where a category is included if anyone proposes it.
  • Escape from Impossibility: By relaxing the output to allow multiple memberships, the authors show that we can finally have rules that are both anonymous and neutral across all problem sizes, bypassing the non-existence results found in recent literature for single-valued classifications.

Limitations and Future Work

  • Single-Valued Inputs: The current model assumes individuals only pick one category, even though the group can pick many. A natural extension would allow individuals to also submit multiple memberships.
  • Strategic Behavior: The paper does not analyze "incentive compatibility." It remains to be seen how voters might lie about their classification to manipulate the collective set of labels.
  • The "Tie" Interpretation: The authors focus on the "membership" reading (the object belongs to all selected categories). They suggest future work could look at the "tie" reading, where the set represents a list of candidates for a final, single-category choice to be made later.

Summary updated

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.
BibTeX
@misc{fioravanti2026classification,
  author = {Federico Fioravanti and Leo Kurata and Vasilis Stamatis},
  title = {{Classification Aggregation with Multiple Memberships}},
  year = {2026},
  eprint = {2611.02984},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.02984},
}
Figure