pith. sign in

arxiv: 2605.17136 · v2 · pith:YRWAFWDKnew · submitted 2026-05-16 · 💻 cs.GT · math.CO· math.PR

Classification aggregation: a quantitative impossibility theorem

Pith reviewed 2026-05-21 09:02 UTC · model grok-4.3

classification 💻 cs.GT math.COmath.PR
keywords classification aggregationsurjectivityimpossibility theoremdictatorshipaggregation functionssocial choice
0
0 comments X

The pith

Surjective classification aggregation must be nearly dictatorial under high-probability guarantees when per-object functions avoid constants.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that classic dictatorship results for exact surjective classification aggregation carry over to the probabilistic case. When each per-object aggregation function stays bounded away from constant and individual opinions are drawn from a symmetric i.i.d. distribution, any mechanism that produces a surjective outcome with probability 1 minus a small epsilon must be close to a dictatorship. A reader would care because this sharply limits the design of non-dictatorial procedures even after relaxing perfect coverage to a likely but not certain outcome. Along the way the authors give a complete characterization of all aggregation rules that guarantee surjectivity in every case, without extra conditions on the functions.

Core claim

We show that similar results hold even if we only require the outcome to be surjective with probability 1-ε with respect to an arbitrary symmetric i.i.d. distribution, provided that the aggregation functions are far from being constant. On the way, we characterize all aggregation mechanisms whose outcome is always surjective without any assumptions on the aggregation functions.

What carries the argument

Characterization of always-surjective aggregation mechanisms under the added requirement that each per-object function stays bounded away from constant.

If this is right

  • Any qualifying mechanism must be close to a dictatorship.
  • The same near-dictatorship conclusion applies to the aggregation of equivalence relations.
  • All mechanisms that guarantee exact surjectivity in every realization are fully described without further restrictions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Relaxing exact surjectivity to high probability does not create substantially more room for non-dictatorial rules.
  • The same quantitative approach could be tested on other multi-decision social choice settings that involve coverage constraints.
  • Empirical measurement of how close real-world aggregation functions come to constants would indicate whether the theorem's conclusion is likely to bind in practice.

Load-bearing premise

The per-object aggregation functions must stay bounded away from constant functions.

What would settle it

An explicit family of aggregation functions bounded away from constants whose combined output fails to cover all categories with probability exceeding epsilon, for some symmetric i.i.d. distribution, would falsify the quantitative impossibility claim.

read the original abstract

A group of individuals wishes to classify $m$ objects into $n$ categories in such a way that no class is left empty, a condition known as surjectivity. The opinions of the individuals are aggregated separately for each object using an aggregation function that can depend on the object. Maniquet and Mongin showed that if the aggregation functions are unanimous and the outcome must always be surjective, then the aggregation mechanism is dictatorial. Cailloux et al. showed that the same holds even if unanimity is relaxed to citizen sovereignty (each object can be classified into any category). We show that similar results hold even if we only require the outcome to be surjective with probability $1-\epsilon$ (with respect to an arbitrary symmetric i.i.d. distribution), provided that the aggregation functions are far from being constant. On the way, we characterize all aggregation mechanisms whose outcome is always surjective without any assumptions on the aggregation functions. Our approach uses a general result of Alekseev and Filmus which has wider applicability. We illustrate this by proving a similar impossibility result for aggregating equivalence relations.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The manuscript proves quantitative extensions of impossibility theorems for aggregating classifications of m objects into n categories. Building on Maniquet-Mongin and Cailloux et al., it shows that if per-object aggregation functions are sufficiently far from constant, then requiring the overall outcome to be surjective with probability 1-ε (under arbitrary symmetric i.i.d. opinion distributions) forces the mechanism to be nearly dictatorial. It also characterizes all always-surjective mechanisms without further assumptions on the functions and applies the same approach, via the Alekseev-Filmus lemma, to obtain an analogous result for aggregating equivalence relations.

Significance. If the central claims hold, the work strengthens existing impossibility results by relaxing strict surjectivity to high-probability surjectivity, which is relevant for noisy or probabilistic settings. The assumption-free characterization of always-surjective mechanisms is a useful standalone contribution. The appeal to the Alekseev-Filmus general result is a methodological strength that enables the equivalence-relation illustration and suggests wider applicability in social choice and judgment aggregation.

major comments (2)
  1. [Main theorem (following §2 characterization)] The main quantitative impossibility (abstract and the theorem following the characterization) rests on the aggregation functions being 'far from constant'; the manuscript should state an explicit quantitative relation between the distance-to-constant parameter and ε that yields the near-dictatorship conclusion, as this distance is load-bearing for the claimed quantitative strengthening.
  2. [Proof of main theorem] The proof of the main result invokes the Alekseev-Filmus lemma; a self-contained verification that the classification setting satisfies the lemma's hypotheses (including the symmetry and i.i.d. conditions) would be needed to confirm the reduction, since this step carries the impossibility claim.
minor comments (3)
  1. [Abstract] The abstract states that the result holds 'with respect to an arbitrary symmetric i.i.d. distribution'; clarify whether this distribution is over individual opinions or over full profiles, and whether the same ε works uniformly for all such distributions.
  2. [Characterization section] In the characterization of always-surjective mechanisms, the notation for the per-object functions and the surjectivity condition could be made more uniform with the probabilistic part of the paper to ease reading.
  3. [Equivalence-relations section] The equivalence-relation illustration is only sketched; adding a short explicit statement of the corresponding near-dictatorship conclusion would help readers see the generality of the method.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and the precise suggestions for improving the manuscript. We address each major comment below and will make the indicated revisions.

read point-by-point responses
  1. Referee: [Main theorem (following §2 characterization)] The main quantitative impossibility (abstract and the theorem following the characterization) rests on the aggregation functions being 'far from constant'; the manuscript should state an explicit quantitative relation between the distance-to-constant parameter and ε that yields the near-dictatorship conclusion, as this distance is load-bearing for the claimed quantitative strengthening.

    Authors: We agree that the quantitative strengthening is strengthened by an explicit dependence. In the revised version we will state, both in the main theorem and in a brief remark following the characterization in §2, the precise relation between the distance-to-constant parameter δ and ε that is required for the near-dictatorship conclusion; the relation follows directly from the constants appearing in the Alekseev-Filmus lemma and will be displayed explicitly. revision: yes

  2. Referee: [Proof of main theorem] The proof of the main result invokes the Alekseev-Filmus lemma; a self-contained verification that the classification setting satisfies the lemma's hypotheses (including the symmetry and i.i.d. conditions) would be needed to confirm the reduction, since this step carries the impossibility claim.

    Authors: We accept the suggestion. Although the manuscript already specifies that the opinion profiles are drawn from an arbitrary symmetric i.i.d. distribution, we will insert a short, self-contained paragraph immediately after the statement of the main theorem that verifies, step by step, that the symmetry and independence assumptions place the setting inside the hypotheses of the Alekseev-Filmus lemma. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's derivation extends established impossibility theorems from Maniquet-Mongin and Cailloux et al. by relaxing always-surjective to (1-ε)-surjective under symmetric i.i.d. opinions while adding an explicit far-from-constant condition on aggregators. The characterization of always-surjective mechanisms is presented as an intermediate step without assumptions, and the approach invokes a general result from Alekseev-Filmus only for wider applicability and an illustration on equivalence relations. No step reduces by construction to fitted parameters, self-defined quantities, or a load-bearing self-citation chain; the central quantitative claim retains independent content grounded in prior external literature and is self-contained against those benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard probability axioms for i.i.d. symmetric distributions and on prior social-choice axioms (unanimity, citizen sovereignty) from cited works; no new free parameters or invented entities are introduced.

axioms (2)
  • standard math Standard axioms of probability for symmetric i.i.d. distributions over opinions
    Invoked for the probabilistic surjectivity guarantee with respect to an arbitrary symmetric i.i.d. distribution.
  • domain assumption Background results on aggregation functions from Maniquet-Mongin and Cailloux et al.
    Used as the baseline that the new quantitative result extends.

pith-pipeline@v0.9.0 · 5718 in / 1379 out tokens · 62024 ms · 2026-05-21T09:02:45.260070+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

44 extracted references · 44 canonical work pages · 2 internal anchors

  1. [1]

    N. Alon, I. Dinur, E. Friedgut, and B. Sudakov. Graph products, F ourier analysis and spectral techniques. Geom. Funct. Anal. , 14(5):913--940, 2004. https://doi.org/10.1007/s00039-004-0478-3 doi:10.1007/s00039-004-0478-3

  2. [2]

    Approximate polymorphisms of predicates

    Yaroslav Alekseev and Yuval Filmus. Approximate polymorphisms of predicates. Submitted, 2026

  3. [3]

    (2+ ) - S at is NP -hard

    Per Austrin, Venkatesan Guruswami, and Johan H stad. (2+ ) - S at is NP -hard. SIAM J. Comput. , 46(5):1554--1573, 2017. https://doi.org/10.1137/15M1006507 doi:10.1137/15M1006507

  4. [4]

    Kenneth J. Arrow. A difficulty in the theory of social welfare. J. of Political Economy , 58:328--346, 1950

  5. [5]

    Kenneth J. Arrow. Social choice and individual values . John Wiley and Sons, 1963

  6. [6]

    Algebraic approach to promise constraint satisfaction

    Libor Barto, Jakub Bul\'in, Andrei Krokhin, and Jakub Opr s al. Algebraic approach to promise constraint satisfaction. J. ACM , 68(4):Art. 28, 66, 2021. https://doi.org/10.1145/3457606 doi:10.1145/3457606

  7. [7]

    Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy.SIAM J

    Joshua Brakensiek and Venkatesan Guruswami. Promise constraint satisfaction: algebraic structure and a symmetric B oolean dichotomy. SIAM J. Comput. , 50(6):1663--1700, 2021. https://doi.org/10.1137/19M128212X doi:10.1137/19M128212X

  8. [8]

    Bulatov and Peter Jeavons

    Andrei A. Bulatov and Peter Jeavons. An algebraic approach to multi-sorted constraints. In International Conference on Principles and Practice of Constraint Programming , 2003. URL: https://api.semanticscholar.org/CorpusID:990270

  9. [9]

    Anshu, I

    Gilad Chase, Yuval Filmus, Dor Minzer, Elchanan Mossel, and Nitin Saurabh. Approximate polymorphisms. In S TOC '22--- P roceedings of the 54th A nnual ACM SIGACT S ymposium on T heory of C omputing , pages 195--202. ACM, New York, [2022] 2022. https://doi.org/10.1145/3519935.3519966 doi:10.1145/3519935.3519966

  10. [10]

    Ozkes, and M

    Olivier Cailloux, Matthieu Hervouin, Ali I. Ozkes, and M. Remzi Sanver. Classification aggregation without unanimity. Mathematical Social Sciences , 128:6--9, 2024. URL: https://www.sciencedirect.com/science/article/pii/S0165489624000088, https://doi.org/10.1016/j.mathsocsci.2024.01.002 doi:10.1016/j.mathsocsci.2024.01.002

  11. [11]

    Aggregation of binary evaluations for truth-functional agendas

    Elad Dokow and Ron Holzman. Aggregation of binary evaluations for truth-functional agendas. Soc. Choice Welf. , 32(2):221--241, 2009. https://doi.org/10.1007/s00355-008-0320-1 doi:10.1007/s00355-008-0320-1

  12. [12]

    Dokow & R

    Elad Dokow and Ron Holzman. Aggregation of binary evaluations. J. Econom. Theory , 145(2):495--511, 2010. https://doi.org/10.1016/j.jet.2007.10.004 doi:10.1016/j.jet.2007.10.004

  13. [13]

    Dokow & R

    Elad Dokow and Ron Holzman. Aggregation of binary evaluations with abstentions. J. Econom. Theory , 145(2):544--561, 2010. https://doi.org/10.1016/j.jet.2009.10.015 doi:10.1016/j.jet.2009.10.015

  14. [14]

    Aggregation of non-binary evaluations

    Elad Dokow and Ron Holzman. Aggregation of non-binary evaluations. Adv. in Appl. Math. , 45(4):487--504, 2010. https://doi.org/10.1016/j.aam.2010.02.005 doi:10.1016/j.aam.2010.02.005

  15. [15]

    Between A rrow and G ibbard- S atterthwaite; a representation theoretic approach

    Dvir Falik and Ehud Friedgut. Between A rrow and G ibbard- S atterthwaite; a representation theoretic approach. Israel J. Math. , 201(1):247--297, 2014. https://doi.org/10.1007/s11856-014-1064-5 doi:10.1007/s11856-014-1064-5

  16. [16]

    Aggregation of evaluations without unanimity

    Yuval Filmus. Aggregation of evaluations without unanimity. SIAM Journal on Discrete Mathematics , 40(2):652--674, 2026. https://doi.org/10.1137/25M1748901 doi:10.1137/25M1748901

  17. [17]

    A quantitative version of the G ibbard- S atterthwaite theorem for three alternatives

    Ehud Friedgut, Gil Kalai, Nathan Keller, and Noam Nisan. A quantitative version of the G ibbard- S atterthwaite theorem for three alternatives. SIAM J. Comput. , 40(3):934--952, 2011. https://doi.org/10.1137/090756740 doi:10.1137/090756740

  18. [18]

    Boolean functions whose F ourier transform is concentrated on the first two levels

    Ehud Friedgut, Gil Kalai, and Assaf Naor. Boolean functions whose F ourier transform is concentrated on the first two levels. Adv. in Appl. Math. , 29(3):427--437, 2002. https://doi.org/10.1016/S0196-8858(02)00024-6 doi:10.1016/S0196-8858(02)00024-6

  19. [19]

    A ND testing and robust judgement aggregation

    Yuval Filmus, Noam Lifshitz, Dor Minzer, and Elchanan Mossel. A ND testing and robust judgement aggregation. In S TOC '20--- P roceedings of the 52nd A nnual ACM SIGACT S ymposium on T heory of C omputing , pages 222--233. ACM, New York, [2020] 2020. https://doi.org/10.1145/3357713.3384254 doi:10.1145/3357713.3384254

  20. [20]

    Fishburn and Ariel Rubinstein

    Peter C. Fishburn and Ariel Rubinstein. Aggregation of equivalence relations. J. Classification , 3(1):61--65, 1986. https://doi.org/10.1007/BF01896812 doi:10.1007/BF01896812

  21. [21]

    On the measure of intersecting families, uniqueness and stability

    Ehud Friedgut. On the measure of intersecting families, uniqueness and stability. Combinatorica , 28(5):503--528, 2008. https://doi.org/10.1007/s00493-008-2318-9 doi:10.1007/s00493-008-2318-9

  22. [22]

    Allan F. Gibbard. Intransitive social indifference and the A rrow dilemma. Working paper, University of Chicago, 1969

  23. [23]

    Econometrica 41(4), pp

    Allan Gibbard. Manipulation of voting schemes: A general result. Econometrica , 41(4):587--601, 1973. URL: https://www.jstor.org/stable/1914083, https://doi.org/10.2307/1914083 doi:10.2307/1914083

  24. [24]

    Greenwell and L

    D. Greenwell and L. Lov\'asz. Applications of product colouring. Acta Math. Acad. Sci. Hungar. , 25:335--340, 1974. https://doi.org/10.1007/BF01886093 doi:10.1007/BF01886093

  25. [25]

    Willem H. Haemers. Hoffman's ratio bound. Linear Algebra and its Applications , 617:215--219, 2021. URL: https://www.sciencedirect.com/science/article/pii/S0024379521000689, https://doi.org/10.1016/j.laa.2021.02.010 doi:10.1016/j.laa.2021.02.010

  26. [26]

    Alan J. Hoffman. On eigenvalues and colorings of graphs. In Bernard Harris, editor, Graph Theory and Its Applications , pages 79--91. Academic Press, New York, NY, 1970

  27. [27]

    The geometry of manipulation---a quantitative proof of the G ibbard- S atterthwaite theorem

    Marcus Isaksson, Guy Kindler, and Elchanan Mossel. The geometry of manipulation---a quantitative proof of the G ibbard- S atterthwaite theorem. Combinatorica , 32(2):221--250, 2012. https://doi.org/10.1007/s00493-012-2704-1 doi:10.1007/s00493-012-2704-1

  28. [28]

    A F ourier-theoretic perspective on the C ondorcet paradox and A rrow's theorem

    Gil Kalai. A F ourier-theoretic perspective on the C ondorcet paradox and A rrow's theorem. Adv. in Appl. Math. , 29(3):412--426, 2002

  29. [29]

    On the probability of a rational outcome for generalized social welfare functions on three alternatives

    Nathan Keller. On the probability of a rational outcome for generalized social welfare functions on three alternatives. J. Combin. Theory Ser. A , 117(4):389--410, 2010. https://doi.org/10.1016/j.jcta.2009.10.008 doi:10.1016/j.jcta.2009.10.008

  30. [30]

    A tight quantitative version of A rrow's impossibility theorem

    Nathan Keller. A tight quantitative version of A rrow's impossibility theorem. J. Eur. Math. Soc. (JEMS) , 14(5):1331--1355, 2012. https://doi.org/10.4171/JEMS/334 doi:10.4171/JEMS/334

  31. [31]

    On the question ``who is a J ?'': a social choice approach

    Asa Kasher and Ariel Rubinstein. On the question ``who is a J ?'': a social choice approach. Logique et Anal. (N.S.) , 40(160):385--395, 1997

  32. [32]

    Kornhauser and Lawrence G

    Lewis A. Kornhauser and Lawrence G. Sager. Unpacking the court. The Yale Law Journal , 96(1):82--117, 1986. URL: https://jstor.org, https://doi.org/10.2307/796436 doi:10.2307/796436

  33. [33]

    Aggregating sets of judgments: An impossibility result

    Christian List and Philip Pettit. Aggregating sets of judgments: An impossibility result. Economics and Philosophy , 18(1):89--110, 2002. URL: https://www.cambridge.org/core/journals/economics-and-philosophy/article/aggregating-sets-of-judgments-an-impossibility-result/35BB2A979DC8D2548B3040A1757B058B, https://doi.org/10.1017/S0266267102001098 doi:10.1017...

  34. [34]

    Scale-Free Networks: Complex Webs in Nature and Technology

    Christian List and Clemens Puppe. Judgment aggregation: A survey. In Paul Anand, Prasanta Pattanaik, and Clemens Puppe, editors, The Handbook of Rational and Social Choice , pages 457--482. Oxford University Press, Oxford, UK, 2009. https://doi.org/10.1093/acprof:oso/9780199290420.003.0019 doi:10.1093/acprof:oso/9780199290420.003.0019

  35. [35]

    Judgment aggregation theory can entail new social choice results

    François Maniquet and Philippe Mongin. Judgment aggregation theory can entail new social choice results. Technical Report ECO/SCD-2014-1063, HEC Paris, 2014. URL: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2518422

  36. [36]

    A theorem on aggregating classifications

    François Maniquet and Philippe Mongin. A theorem on aggregating classifications. Mathematical Social Sciences , 79:6--10, 2016. URL: https://www.sciencedirect.com/science/article/pii/S0165489615000852, https://doi.org/10.1016/j.mathsocsci.2015.10.001 doi:10.1016/j.mathsocsci.2015.10.001

  37. [37]

    Arrow's Impossibility Theorem Without Unanimity

    Elchanan Mossel. Arrow's impossibility theorem without unanimity, 2009. URL: https://arxiv.org/abs/0901.4727, https://arxiv.org/abs/0901.4727 arXiv:0901.4727

  38. [38]

    Probability Theory and Related Fields 154(1-2), pp

    Elchanan Mossel. A quantitative A rrow theorem. Probab. Theory Related Fields , 154(1-2):49--88, 2012. https://doi.org/10.1007/s00440-011-0362-7 doi:10.1007/s00440-011-0362-7

  39. [39]

    Elchanan Mossel and Mikl\'os Z. R\'acz. A quantitative G ibbard- S atterthwaite theorem without neutrality. Combinatorica , 35(3):317--387, 2015. https://doi.org/10.1007/s00493-014-2979-5 doi:10.1007/s00493-014-2979-5

  40. [40]

    Approximately classic judgement aggregation

    Ilan Nehama. Approximately classic judgement aggregation. Ann. Math. Artif. Intell. , 68(1-3):91--134, 2013. https://doi.org/10.1007/s10472-013-9358-6 doi:10.1007/s10472-013-9358-6

  41. [41]

    Cambridge University Press, doi:10.1017/CBO9781139814782

    Ryan O'Donnell. Analysis of B oolean functions . Cambridge University Press, New York, 2014. https://doi.org/10.1017/CBO9781139814782 doi:10.1017/CBO9781139814782

  42. [42]

    Fishburn

    Ariel Rubinstein and Peter C. Fishburn. Algebraic aggregation theory. J. Econom. Theory , 38(1):63--77, 1986. https://doi.org/10.1016/0022-0531(86)90088-8 doi:10.1016/0022-0531(86)90088-8

  43. [43]

    Journal of Economic Theory 10(2), pp

    Mark Allen Satterthwaite. Strategy-proofness and A rrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory , 10(2):187--217, 1975. https://doi.org/10.1016/0022-0531(75)90050-2 doi:10.1016/0022-0531(75)90050-2

  44. [44]

    Impossibility Theorems and the Universal Algebraic Toolkit

    Mario Szegedy and Yixin Xu. Impossibility theorems and the universal algebraic toolkit. Papers 1506.01315, arXiv.org, June 2015. URL: https://ideas.repec.org/p/arx/papers/1506.01315.html