Classification aggregation: a quantitative impossibility theorem
Pith reviewed 2026-05-21 09:02 UTC · model grok-4.3
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.
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
- 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.
Referee Report
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)
- [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.
- [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)
- [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.
- [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.
- [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
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
-
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
-
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
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
axioms (2)
- standard math Standard axioms of probability for symmetric i.i.d. distributions over opinions
- domain assumption Background results on aggregation functions from Maniquet-Mongin and Cailloux et al.
Lean theorems connected to this paper
-
IndisputableMonolith/Foundation/AbsoluteFloorClosure.leanreality_from_one_distinction unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
We show that similar results hold even if we only require the outcome to be surjective with probability 1−ε … provided that the aggregation functions are far from being constant. … uses a general result of Alekseev and Filmus
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
Theorem 1.14 (Polymorphisms of Surj m,n) … dictatorial or certificate
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
-
[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]
Approximate polymorphisms of predicates
Yaroslav Alekseev and Yuval Filmus. Approximate polymorphisms of predicates. Submitted, 2026
work page 2026
-
[3]
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]
Kenneth J. Arrow. A difficulty in the theory of social welfare. J. of Political Economy , 58:328--346, 1950
work page 1950
-
[5]
Kenneth J. Arrow. Social choice and individual values . John Wiley and Sons, 1963
work page 1963
-
[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]
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]
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
work page 2003
-
[9]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
Allan F. Gibbard. Intransitive social indifference and the A rrow dilemma. Working paper, University of Chicago, 1969
work page 1969
-
[23]
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]
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]
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]
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
work page 1970
-
[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]
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
work page 2002
-
[29]
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]
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]
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
work page 1997
-
[32]
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]
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]
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
work page doi:10.1093/acprof:oso/9780199290420.003.0019 2009
-
[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
work page 2014
-
[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]
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
work page internal anchor Pith review Pith/arXiv arXiv 2009
-
[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]
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]
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]
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]
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]
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]
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
work page internal anchor Pith review Pith/arXiv arXiv 2015
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.