REVIEW 2 major objections 5 minor 56 references
Proportional Representation in Rank Aggregation
T0 review · 2 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read Rank aggregation can be made proportional: a sequential Borda rule guarantees every weighted input ranking its agreed share of pairwise comparisons.
desk verdict Solid, significant paper that resolves an open design problem in proportional rank aggregation; the core axioms and proofs hold up, but the one computer-assisted counterexample needs to be made reproducible before I'd trust it fully. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the pairwise-agreement utility function u(≻,▷), which counts the candidate pairs on which an input ranking ≻ and the output ranking ▷ agree. The load-bearing identity is the decomposition u(≻,▷) = sum_{i=1}^{m-1} u(≻, x_i, {x_i, ..., x_m}), which lets each sequential output position be treated as a priced item whose maximum value to any ranking is m-i. Rank-priceability formalizes the resulting payment scheme: each ranking can pay only for utility it receives, never more than its budget, each position costs at most m-i, and total spending must exceed C(m,2) - 1. Pair-priceability refines this to payments for individual candidate pairs. These priceability properties are
What would settle it
The theorems are universal, so a single counterexample would refute them. Run PSB (or FB) with a fixed tie-breaking on any small profile, say all rankings for m = 5 or 6, and check each input ranking's pairwise-agreement count against floor(weight * C(m,2)); any count below the bound falsifies uPJR (or sPJR for FB on subprofiles). A targeted test already appears in the paper: its Proposition 5.1 constructs a 26-candidate, 8-ranking profile on which PSB returns a ranking agreeing with only 292 pairwise comparisons of a group that deserves 293, demonstrating that PSB does not satisfy the stronge
Extended reading notes
Core claim
The paper's central claim is that the Proportional Sequential Borda rule (PSB) satisfies uPJR: for every profile and every input ranking with weight alpha, the output ranking agrees with at least floor(alpha * C(m,2)) pairwise comparisons. PSB works by giving each input ranking a budget of alpha * C(m,2), then in each round placing the candidate with the highest budget-weighted Borda score into the next output position, charging each ranking no more than the utility it gains from that placement, and deleting the candidate. The proof goes through rank-priceability, a payment scheme showing that the collective spending on the output ranking exceeds C(m,2) - 1; the paper proves that any rank-pr
Load-bearing premise
The whole framework rests on measuring 'representation' as the plain count of pairwise comparisons on which two rankings agree, treating every position in the output ranking as equally valuable; if applications care more about the top of the ranking, the fairness guarantees target the wrong quantity and the rules' proportional outcomes may not be the desired ones.
Editorial extensions
If this is right
- Any multi-criteria aggregator using PSB can promise each criterion a concrete lower bound on how many of its pairwise judgments survive in the output ranking.
- uPJR resolves the open problem left by the Squared Kemeny rule: payoff from participatory budgeting and committee-voting fairness notions can be transferred to rank aggregation.
- The Flow-adjusting Borda rule extends the guarantee to coalitions: if several input rankings jointly hold weight alpha, their preferred pairwise comparisons are represented at the floor(alpha * C(m,2)) level.
- Both rules give a linear group-average utility bound, so even small subprofiles receive a predictable amount of representation, not just the individual floor.
- Both rules are described as concrete sequential procedures, so implementation does not require solving a global optimization over all rankings.
Reading between the lines
- The author flags in Section 6 that pairwise-agreement utility treats all output positions equally; a natural test is to rerun PSB and FB with top-weighted utilities, where the priceability payment constraints would need rescaling and the uPJR-style floor becomes a different target.
- The budget-update construction suggests a general recipe: any budget-balanced, priceable rule from participatory budgeting can likely be converted into a proportional SWF by treating each output position as an item of shrinking cost, though whether the uPJR guarantee survives for non-Borda utilities is open.
- The linear group-average bound (alpha/4 * C(m,2) - 3/16) is probably not tight; the paper's own Remark 2 notes an upper bound of about 1/2 * C(m,2), so sharpening the 3/4 leftover-budget bound would improve the constant.
- In practical ranking portals, these rules give each criterion a guaranteed 'screen time' in pairwise comparisons; testing them on real data against Kemeny or plain Borda aggregation would show whether users perceive the output as more balanced.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies proportional representation in rank aggregation. It defines utility as the number of pairwise comparisons on which an input ranking and the output ranking agree, and formulates three axioms: uJR, uPJR, and sPJR. The main results are: (i) the Squared Kemeny rule fails even uJR (Proposition 3.1); (ii) a Chamberlin-Courant-style SWF satisfies uJR (Proposition 3.2); (iii) the Proportional Sequential Borda rule (PSB) is rank-priceable and hence satisfies uPJR (Theorem 4.5 and Proposition 4.2); (iv) PSB guarantees a linear-in-weight average utility bound for every subprofile (Theorem 4.6); (v) PSB fails sPJR (Proposition 5.1, via a computer-assisted argument); and (vi) the Flow-adjusting Borda rule (FB) is pair-priceable and hence satisfies sPJR, with the same average-utility bound (Theorems 5.5 and 5.6). Detailed proofs are provided in the appendices.
Significance. If the results are correct, this is the first exact resolution of the open problem of designing fully proportional social welfare functions in the pairwise-agreement model of Lederer et al. [2024]. The paper makes a substantive methodological contribution by transferring priceability ideas from participatory budgeting to rank aggregation. The main theorems are backed by detailed, structured proofs, and the implications rank-priceability implies uPJR and pair-priceability implies sPJR are clean and short. The paper also gives explicit quantitative guarantees rather than only existential ones. The main reservation concerns the reproducibility of the computer-assisted counterexample in Proposition 5.1, which is load-bearing for the claim that PSB fails sPJR and for the motivation of the stronger FB rule.
major comments (2)
- [Section 5, Proposition 5.1] The proof of Proposition 5.1 states that 'we have shown with the help of a computer that, up to reorderings of x1,...,x4, PSB uniquely chooses' a particular ranking, and that this ranking agrees with only 292 of the required 293 pairwise comparisons. No code, no computational parameters, no verification certificate, and no explicit tie-breaking specification are supplied. Since PSB's tie-breaking can affect the chosen ranking, and since this proposition is the only evidence that PSB fails sPJR, this is a load-bearing gap: without a reproducible computation or an independent analytic proof, the claimed failure of sPJR for PSB is not established. Please provide the full computer-checkable proof (ideally with code and the exact tie-breaking rule) or replace the computer-assisted step with a hand-verifiable certificate.
- [Section 6 and Section 2.1] The paper's fairness guarantees are all defined with respect to the utility function that counts every pairwise comparison equally. This is explicitly acknowledged in Section 6 as the biggest restriction. I do not see this as an internal flaw, but it should be made more prominent in the introduction and abstract: the claims of 'proportional representation' are with respect to this specific utility model only. If an application values top positions more heavily, the uPJR/sPJR guarantees do not transfer. A short caveat in the abstract or introduction would help avoid overclaiming.
minor comments (5)
- [Section 5, Proposition 5.1] When the computation is provided, it should also specify the tie-breaking order over rankings and over candidates, since the statement 'up to reorderings of x1,...,x4' is not enough to uniquely determine the PSB output under an arbitrary tie-breaking rule.
- [Appendix B] The proof of Proposition 3.1 refers to 'Claim (2), Claim (3), and Claim (6)' but the claims are not separately labelled in the proof. Adding explicit labels would improve readability and verifiability.
- [Section A, footnote 6] The footnote about the failure of the unconstrained equal-shares variant is somewhat confusing: it describes what would happen if the utility cap were omitted, but it is not immediately clear that this variant is not the defined RMES. Clarify that the example concerns a different, non-recommended update rule.
- [Definition 2.3] The notation A(▷) is introduced informally as the set of pairwise comparisons induced by ▷. Since sPJR and pair-priceability rely heavily on this set, a formal definition of A(▷) as the ordered pairs (x_i,x_j) with i<j would reduce ambiguity.
- [Theorem 4.6] The final 'equivalently' step in the proof sketch and in Appendix C is somewhat compressed. A one-line justification that A U/(A+1/4) ≤ U/|S| for A=|S|·C(m,2) and |S|≤1 would help the reader.
Circularity Check
No significant circularity: PSB rank-priceability and uPJR are proved from the rule's definition; self-citations are contextual, not load-bearing.
full rationale
The paper's central claim is a theorem chain: Definition 2.1 fixes uPJR in terms of pairwise-agreement utility; Definition 4.1 introduces rank-priceability as a payment condition; Proposition 4.2 derives uPJR from rank-priceability using only the payment bounds; Theorem 4.5 verifies all four rank-priceability conditions for PSB by an induction on the Borda-maximization inequality and the min-based budget update, with a separate leftover-budget argument (≤3/4). The analogous pair-priceability/sPJR chain (Definitions 5.2, Proposition 5.3, Theorem 5.5) is also proved from the flow construction. No fitted parameter is renamed as a prediction, and no axiom is defined in terms of the rule it is said to justify. The cited prior work (Lederer et al. 2024) supplies the pairwise-agreement utility model and the Squared Kemeny rule, but the paper proves that SqK fails uJR rather than importing a guarantee; the MES/priceability inspiration is external. Section 6 explicitly flags the pairwise-agreement utility as the biggest restriction, which is an external modeling caveat about applicability, not a circular step in the derivation.
Assumptions & free parameters
assumptions (4)
- domain assumption Utility of an input ranking is the number of agreeing pairwise comparisons, with all positions counted equally.
- domain assumption Input profiles are probability distributions over strict rankings, and the output is a single strict ranking with a fixed tie-breaking rule.
- standard math The maximum flow / minimum cut theorem applies to the flow networks used by FB.
- ad hoc to paper Borda score, with budget-weighted utilities, is the right selection objective in each round.
Cite this review
Pith. "Pith review of Proportional Representation in Rank Aggregation." pith.science (2026). https://pith.science/paper/5FY7E55J
@misc{pith2026250816177,
author = {Pith},
title = {Pith review of: Proportional Representation in Rank Aggregation},
year = {2026},
howpublished = {\url{https://pith.science/paper/5FY7E55J}},
note = {Machine review of arXiv:2508.16177}
}
read the original abstract
In rank aggregation, the task is to aggregate multiple weighted input rankings into a single output ranking. While numerous methods, so-called social welfare functions (SWFs), have been suggested for this problem, all of the classical SWFs tend to be majoritarian and are thus not acceptable when a proportional ranking is required. Motivated by this observation, we design SWFs that guarantee that every input ranking is proportionally represented by the output ranking. Specifically, our central fairness condition requires that the number of pairwise comparisons between candidates on which an input ranking and the output ranking agree is at least proportional to the weight of the input ranking. As our main contribution, we present a simple SWF called the Proportional Sequential Borda rule which satisfies this condition. Moreover, we introduce a more involved variant of this rule, the Flow-adjusting Borda rule, which satisfies a stronger fairness condition that applies to arbitrary groups of rankings. Many of our axioms and techniques are inspired by results in approval-based committee voting and participatory budgeting, where the concept of proportional representation has been studied in depth.
Reference graph
Works this paper leans on
-
[1]
K. J. Arrow. Social Choice and Individual Values. New Haven: Cowles Foundation, 1st edition, 1951. 2nd edition 1963
work page 1951
-
[2]
K. J. Arrow, A. Sen, and K. Suzumura, editors. Handbook of Social Choice and Welfare, volume 1. North-Holland, 2002
work page 2002
-
[3]
H. Aziz and N. Shah. Participatory budgeting: Models and approaches. In T. Rudas and G. P\' e li, editors, Pathways Between Social Science and Computational Social Science: Theories, Methods, and Interpretations, pages 215--236. Springer International Publishing, 2021
work page 2021
-
[4]
H. Aziz, M. Brill, V. Conitzer, E. Elkind, R. Freeman, and T. Walsh. Justified representation in approval-based committee voting. Social Choice and Welfare, 48 0 (2): 0 461--485, 2017
2017
-
[5]
H. Aziz, P. Lederer, D. Peters, J. Peters, and A. Ritossa. Committee monotonicity and proportional representation for ranked preferences. 2025. Working paper
work page 2025
-
[6]
Rank Aggregation Using Scoring Rules
N. Boehmer, R. Bredereck, and D. Peters. Rank aggregation using scoring rules. Technical report, https://arxiv.org/pdf/2209.08856, 2023
work page Pith review arXiv 2023
- [7]
-
[8]
M. Brill and J. Israel. Dynamic proportional rankings. Social Choice and Welfare, 64: 0 221--261, 2025
work page 2025
Show all 56 references
-
[9]
Brill, S
M. Brill, S. Forster, M. Lackner, J. Maly, and J. Peters. Proportionality in approval-based participatory budgeting. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), pages 5524--5531, 2023
2023
-
[10]
Bulteau, N
L. Bulteau, N. Hazon, R. Page, A. Rosenfeld, and N. Talmon. Justified representation for perpetual voting. IEEE Access, 9: 0 96598--96612, 2021
2021
-
[11]
Can and T
B. Can and T. Storcken. Update monotone preference rules. Mathematical Social Sciences, 65 0 (2): 0 136--149, 2013
2013
-
[12]
Chakraborty, S
D. Chakraborty, S. Das, A. Khan, and A. Subramanian. Fair rank aggregation. In Advances in Neural Information Processing Systems 35, pages 23965--23978, 2022
2022
-
[13]
J. R. Chamberlin and P. N. Courant. Representative deliberations and representative decisions: P roportional representation and the B orda rule. The American Political Science Review, 77 0 (3): 0 718--733, 1983
1983
-
[14]
Chandak, S
N. Chandak, S. Goel, and D. Peters. Proportional aggregation of preferences for sequential decision making. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 9573--9581, 2024
2024
-
[15]
Chatterjee, A
S. Chatterjee, A. Mukhopadhyay, and M. Bhattacharyya. A weighted rank aggregation approach towards crowd opinion analysis. Knowledge-Based Systems, 149: 0 47--60, 2018
2018
-
[16]
Conitzer, M
V. Conitzer, M. Rognlie, and L. Xia. Preference functions that score rankings and maximum likelihood estimation. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI), pages 109--115, 2009
2009
-
[17]
A. H. Copeland. A `reasonable' social welfare function. M imeo, University of Michigan Seminar on Applications of Mathematics to the Social Sciences, 1951
1951
-
[18]
Dwork, R
C. Dwork, R. Kumar, M. Naor, and D. Sivakumar. Rank aggregation methods for the web. In Proceedings of the 10th International Conference on the World Wide Web (WWW), pages 613--622, 2001
2001
-
[19]
Elkind, P
E. Elkind, P. Faliszewski, A. Igarashi, P. Manurangsi, U. Schmidt-Kraepelin , and W. Suksompong. The price of justified representation. ACM Transactions on Economics and Computation, 12 0 (3): 0 1--27, 2024
2024
-
[20]
Fischer, O
F. Fischer, O. Hudry, and R. Niedermeier. Weighted tournament solutions. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors, Handbook of Computational Social Choice, chapter 4. Cambridge University Press, 2016
2016
-
[21]
Freeman, M
R. Freeman, M. Brill, and V. Conitzer. On the axiomatic characterization of runoff voting rules. In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI), pages 675--681, 2014
2014
-
[22]
Gkatzelis, D
V. Gkatzelis, D. Halpern, and N. Shah. Resolving the optimal metric distortion conjecture. In Proceedings of the 61st Symposium on Foundations of Computer Science (FOCS), pages 1427--1438, 2020
2020
-
[23]
J. G. Kemeny. Mathematics without numbers. Daedalus, 88: 0 577--591, 1959
1959
-
[24]
F. E. Kizilkaya and D. Kempe. Plurality veto: A simple voting rule achieving optimal metric distortion. In Proceedings of the 31th International Joint Conference on Artificial Intelligence (IJCAI), pages 349--355, 2022
2022
-
[25]
F. E. Kizilkaya and D. Kempe. Generalized veto core and a practical voting rule with optimal metric distortion. In Proceedings of the 24th ACM Conference on Economics and Computation (ACM-EC), pages 913--936, 2023
2023
-
[26]
Kolde, S
R. Kolde, S. Laur, P. Adler, and J. Vilo. Robust rank aggregation for gene list integration and meta-analysis. Bioinformatics, 2012
2012
-
[27]
M. Lackner. Perpetual voting: Fairness in long-term decision making. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pages 2103--2110, 2020
2020
-
[28]
Lackner and J
M. Lackner and J. Maly. Proportional decisions in perpetual voting. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), pages 5722--5729, 2023
2023
-
[29]
Lackner and P
M. Lackner and P. Skowron. Utilitarian welfare and representation guarantees of approval-based multiwinner rules. Artificial Intelligence, 288: 0 103366, 2020
2020
-
[30]
Lackner and P
M. Lackner and P. Skowron. Multi-winner voting with approval preferences. https://arxiv.org/abs/2007.01795, 2022
2007 arXiv
-
[31]
Lackner and P
M. Lackner and P. Skowron. Multi-Winner Voting with Approval Preferences. Springer-Verlag, 2023
2023
-
[32]
P. Lederer. Bivariate scoring rules: Unifying the characterizations of positional scoring rules and K emeny's rule. Journal of Economic Theory, 218: 0 105836, 2024
2024
-
[33]
Lederer, D
P. Lederer, D. Peters, and T. W a s. The squared K emeny rule for averaging rankings. Proceedings of the 25th ACM Conference on Economics and Computation (ACM-EC), 2024
2024
-
[34]
S. Lin. Rank aggregation methods. WIREs computational statistics, 2010
2010
-
[35]
Masa r \' i k, G
T. Masa r \' i k, G. Pierczy\' n ski, and P. Skowron. A generalised theory of proportionality in collective decision making. In Proceedings of the 25th ACM Conference on Economics and Computation (ACM-EC), pages 734--754, 2024
2024
-
[36]
Michorzewski, D
M. Michorzewski, D. Peters, and P. Skowron. Price of fairness in budget division and probabilistic social choice. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), 2020. Forthcoming
2020
-
[37]
Nitzan and A
S. Nitzan and A. Rubinstein. A further characterization of B orda ranking method. Public Choice, 36 0 (1): 0 153--158, 1981
1981
-
[38]
S. Niu, Y. Lan, J. Guo, X. Cheng, L. Yu, and C. Long. Listwise approach for rank aggregation in crowdsourcing. In Proceedings of the 8th ACM International Conference on Web Search and Data Mining, pages 253--262, 2015
2015
-
[39]
Peters and P
D. Peters and P. Skowron. Proportionality and the limits of welfarism. In Proceedings of the 21nd ACM Conference on Economics and Computation (ACM-EC), pages 793--794, 2020
2020
-
[40]
Peters, G
D. Peters, G. Pierczy\'nski, and P. Skowron. Proportional participatory budgeting with additive utilities. In Proceedings of the 35th Annual Conference on Neural Information Processing Systems (NeurIPS), pages 12726--12737, 2021
2021
-
[41]
Pitoura, K
E. Pitoura, K. Stefanidis, and G. Koutrika. Fairness in rankings and recommendations: an overview. The VLDB Journal, 31 0 (431--458), 2022
2022
-
[42]
R. C. Prati. Combining feature ranking algorithms through rank aggregation. In International Conference on Neural Networks, pages 1--8, 2012
2012
-
[43]
A. D. Procaccia, J. S. Rosenschein, and A. Zohar. On the complexity of achieving proportional representation. Social Choice and Welfare, 30: 0 353--362, 2008
2008
-
[44]
M. E. Renda and U. Straccia. Web metasearch: rank vs score based rank aggregation methods. In ACM Symposium on Applied Computing, pages 841--846, 2003
2003
-
[45]
Rey and J
S. Rey and J. Maly. The (computational) social choice take on indivisible participatory budgeting. Technical report, https://arxiv.org/pdf/2303.00621.pdf, 2023
2023 arXiv
-
[46]
S \'a nchez-Fern \'a ndez, E
L. S \'a nchez-Fern \'a ndez, E. Elkind, M. Lackner, N. Fern \'a ndez, J. A. Fisteus, P. Basanta Val , and P. Skowron. Proportional justified representation. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), 2017
2017
-
[47]
Sarkar, S
C. Sarkar, S. Cooley, and J. Srivastava. Robust feature selection technique using rank aggregation. Applied Artificial Intelligence, 28 0 (3): 0 243--257, 2014
2014
-
[48]
Skowron and A
P. Skowron and A. G\'orecki. Proportional public decisions. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pages 5191--5198, 2022
2022
-
[49]
Skowron, P
P. Skowron, P. Faliszewski, and J. Lang. Finding a collective set of items: From proportional multirepresentation to group recommendation. Artificial Intelligence, 241: 0 191--216, 2016
2016
-
[50]
Skowron, M
P. Skowron, M. Lackner, M. Brill, D. Peters, and E. Elkind. Proportional rankings. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), pages 409--415, 2017
2017
-
[51]
J. H. Smith. Aggregation of preferences with variable electorate. Econometrica, 41 0 (6): 0 1027--1041, 1973
1973
-
[52]
S. Wang, Q. Deng, S. Feng, H. Zhang, and C. Ling. A survey on rank aggregation. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI), pages 8281--8289, 2024
2024
-
[53]
D. Wei, M. Islam, B. Schieber, and S. Basu Roj . Rank aggregation with proportionate fairnes. In Proceedings of the 2022 International Conference on Management of Data (SIGMOD '22), pages 262--275, 2022
2022
-
[54]
H. P. Young. A note on preference aggregation. Econometrica, 42 0 (6): 0 1129--1131, 1974
1974
-
[55]
H. P. Young. Condorcet's theory of voting. The American Political Science Review, 82 0 (4): 0 1231--1244, 1988
1988
-
[56]
H. P. Young and A. B. Levenglick. A consistent extension of C ondorcet's election principle. SIAM Journal on Applied Mathematics, 35 0 (2): 0 285--300, 1978
1978
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.