Proportional Clustering, the $\beta$-Plurality Problem, and Metric Distortion

Jannik Peters; Leon Kellerhals

REVIEW 2 major objections 4 minor 25 references

Proportional Clustering, the $\beta$-Plurality Problem, and Metric Distortion

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper establishes that fair clustering with a single center using the Droop quota is exactly the β-plurality problem, and that pure preference rankings suffice to obtain (2+√5)-proportionally fair clusterings for any number of centers.

desk verdict A solid rank-JR result undermined by a false plurality-veto theorem and an unsupported EAR assumption. read the letter →

arxiv 2502.10068 v1 pith:S7RODBAZ submitted 2025-02-14 cs.GT

Leon Kellerhals , Jannik Peters This is my paper · ORCID

classification cs.GT MSC 68W2591B14

keywords proportionalclusteringβ-pluralitypointDroopquotametricdistortionordinalinformationrank-JRExpandingApprovalsRulemultiwinnervoting

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper's central claim is that two previously separate fairness notions are the same problem viewed through different quotas: with a single center and the Droop quota, proportional clustering is exactly the β-plurality problem, with the proportionality factor equal to 1/β. Building on that bridge, the paper proves two algorithmic facts from ordinal preference data alone. First, the plurality veto rule always selects a $(\sqrt{5}-2)$-plurality point, giving a constant-factor plurality guarantee without knowing distances. Second, any committee satisfying a rank-based fairness condition called $\ell$-rank-JR is a $(2+\sqrt{5})$-approximate $\ell$-proportional clustering; since the Expanding Approvals Rule is asserted to satisfy that condition, this closes the gap in the ordinal proportional-clustering problem at exactly $(2+\sqrt{5})$. A sympathetic reader should care because this replaces exact-distance access with preference rankings, which is the information realistically available in voting and participatory settings.

What carries the argument

The central object is the $\ell$-rank-JR condition, a fairness property for committees that depends only on preference rankings: for every rank $r$ and every group of at least $\ell$ agents all having some candidate within their top $r$, the committee must contain a winner within the top $r$ of at least one group member. This condition is what lets the proof transfer an ordinal guarantee into a metric one, because it bounds how far a committee member can be from any candidate that many agents prefer collectively. The proof machinery also includes the ratio-optimization identity $\max_{x\ge 0} \min(3+2/x, 1+2x) = 2+\sqrt{5}$, which converts pairwise distance inequalities into the final approximation factor.

What would settle it

A concrete counterexample would be a finite metric space with an ordinal preference profile where either (a) the Expanding Approvals Rule returns a committee that violates $\ell$-rank-JR for $\ell \ge n/k$, or (b) some $\ell$-rank-JR committee admits a coalition $N'$ of at least $\ell$ agents and an unchosen candidate $c$ such that every member's distance to the committee exceeds $(2+\sqrt{5})$ times their distance to $c$. Constructing either by exhaustive search over small profiles would settle the theorem.

Watch

Extended reading notes

Core claim

The discovery is a chain of equivalences and reductions. For $k=1$, a point is a $\beta$-plurality point if and only if the singleton clustering satisfies $1/\beta$-Droop proportionality, so the two research programs are literally the same question. The paper then shows that plurality veto, a rule designed for metric distortion, always returns a $(\sqrt{5}-2)$-plurality point from ordinal information alone. Finally, Theorem 5 proves that any committee satisfying $\ell$-rank-JR is $(2+\sqrt{5})$-approximate $\ell$-proportional for every $\ell > n/(k+1)$; because the Expanding Approvals Rule is stated to satisfy $\ell$-rank-JR for $\ell \geq n/k$, this yields an ordinal algorithm for proportional clustering. The proof is driven by a worst-case ratio optimization: for any unchosen candidate and any large coalition, rank-JR guarantees a committee member whose relative distances to the coalition and the candidate satisfy $\min(3+2/x, 1+2x) \le 2+\sqrt{5}$ for some nonnegative ratio $x$.

Load-bearing premise

The sole unproved step needed for the main algorithm is the remark that the Expanding Approvals Rule always produces a committee satisfying the rank-based fairness condition for quotas at least $n/k$; if that remark is false for some preference profile, the paper's ordinal $(2+\sqrt{5})$-proportionality guarantee does not follow from Theorem 5.

Editorial extensions

If this is right

For $k=1$, any improvement in $\beta$-plurality bounds immediately improves Droop proportional clustering, and any lower-bound example transfers as well.
Plurality veto gives a purely ordinal method to find a point that no alternative beats by a factor better than $1/(\sqrt{5}-2)=2+\sqrt{5}$, i.e., constant-factor Condorcet fairness from rankings only.
Every $\beta$-plurality point has metric distortion at most $2/\beta+1$, so $\beta$-plurality guarantees translate directly into social-cost guarantees; this generalizes the known distortion-3 bound for Condorcet winners.
The rank-JR theorem applies to every quota $\ell>n/(k+1)$, so the $(2+\sqrt{5})$ proportionality guarantee is not tied to the Hare quota and covers Droop-style thresholds.
Combined with the asserted EAR property, this gives an ordinal algorithm matching the known lower bound, so the approximation factor $(2+\sqrt{5})$ is the best possible among ordinal rules.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

One can read Theorem 5 as a template: any future rule, not necessarily EAR, that supplies $\ell$-rank-JR inherits the same $(2+\sqrt{5})$ guarantee; this decouples the approximation proof from the algorithmic rule.
The $k=1$ equivalence suggests a strategy for proportional clustering: settle tighter bounds for the simpler plurality problem first, then try to lift them to multiple centers; the paper's authors explicitly float this possibility as an open direction.
The core-approximation result (Theorem 6) hints that ordinal information may also suffice for $q$-core guarantees in committee selection and sortition, but the paper does not provide an explicit ordinal rule for that setting; testing this would require a rank-PJR rule with an ordinal implementation.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper has one genuinely useful result and one broken headline claim. The equivalence between Droop proportional clustering for k=1 and β-plurality points (Theorem 2) is simple, correct, and worth having. The distortion bound for β-plurality points (Theorem 3) is a clean generalization of the known Condorcet-winner bound. And the rank-JR to (2+√5)-approximate proportionality proof (Theorem 5) looks right, and it is a real step toward the Kalaycı et al. open question — provided the unproven remark that Expanding Approvals satisfies ℓ-rank-JR for ℓ ≥ n/k is true. That remark is load-bearing and currently has no proof or citation.

The problem is Theorem 4. As stated, the Plurality Veto rule selects the last point whose score is decremented, which with standard tie-breaking is the highest-plurality candidate. The theorem claims that point is always a (√5−2)-plurality point. The stress-test counterexample is valid: put 40 agents at 0, six candidates r_1..r_6 at 1+γ_t with 10 agents each, and one candidate q at 0.9. Scores are p=40, r_t=10, q=0. The r's get decremented to zero first, then p, so p wins. But the 60 agents near 1+γ_t all prefer q over p by a factor larger than 1/(√5−2), so p is not a (√5−2)-plurality point. The proof's step 'd(i,p) ≤ d(i,r)' for the agent that decrements r is unjustified; nothing in the rule implies that metric inequality. Since this false theorem is advertised in the abstract, the paper cannot be accepted as is.

Also worth flagging: the paper's resolution of the open question depends on the EAR rank-JR remark, which is asserted without proof. That is a fragile premise; it should be either proved or cited to a published result.

Overall, the core idea — connecting Droop proportionality to β-plurality and using rank-JR for ordinal proportional clustering — is sound and likely correct. But the false plurality-veto claim needs to be removed or fixed, and the EAR remark needs support. This deserves a serious referee, but the current version is not publishable. I'd suggest the authors revise and resubmit; the referee time is justified by Theorem 5.

Referee Report

2 major / 4 minor

Summary. The paper connects two lines of work: proportional clustering with the Droop quota and the β-plurality problem. It proves an equivalence for k=1 (Theorem 2), gives a distortion bound for β-plurality points (Theorem 3), and makes two algorithmic claims: that Plurality Veto selects a (√5−2)-plurality point using only ordinal information (Theorem 4), and that any committee satisfying ℓ-rank-JR is (2+√5)-approximately ℓ-proportional, which together with an asserted property of the Expanding Approvals Rule would resolve an open question of Kalaycı et al. (Theorem 5). An appendix extends the rank-based approach to a core notion.

Significance. If the algorithmic claims were correct, the paper would make a valuable contribution: it would give an ordinal voting rule with a constant plurality guarantee and resolve an open question in ordinal proportional clustering. The simple equivalence in Theorem 2 is correct and nicely bridges two literatures, and the conditional Theorem 5 is a useful structural statement. However, the central Theorem 4 is false as stated, and the resolution of the open question rests on an unproved, load-bearing assertion about the Expanding Approvals Rule. The paper's headline results are therefore not established, and the current version cannot be accepted.

major comments (2)

[Section 4, Theorem 4]
[Section 5, remark before Theorem 5] The claim that 'an outcome returned by EAR satisfies ℓ-rank-JR with ℓ ≥ n/k' is stated as a remark with no proof and no citation. This property is exactly what is needed to turn the conditional Theorem 5 into an actual ordinal algorithm achieving (2+√5)-proportionality, thereby resolving the open question of Kalaycı et al. The cited references do not establish it: Aziz and Lee predate the rank-JR notion, and Brill and Peters do not state this quota version for EAR. Without a proof of this property, the paper's main contribution to the open question is conditional only. This is a load-bearing gap, not a presentation issue.

minor comments (4)

[Section 5, Definition of ℓ-rank-JR] The definition of ℓ-rank-JR contains a variable error: 'for each j ∈ N′' should be 'for each i ∈ N′' with 'rank(i,c) ≤ r', or equivalently the condition should read 'rank(j,c) ≤ r for each j ∈ N′'. As written, the quantifier is ambiguous and the proof of Theorem 5 silently reinterprets the axiom.
[Section 3, Theorem 3 proof] The proof of Theorem 3 skips the justification that ∑_{N\N′} d(q,p) ≤ ∑_{N′} d(q,p), which follows from |N\N′| ≤ |N′| and d(q,p) ≥ 0. The step as written is confusing and should be spelled out.
[Section 5, Theorem 5 proof] In the proof of Theorem 5, the agent j obtained from the rank-JR axiom is said to belong to N, whereas the axiom as stated guarantees an agent in N′; since N′ ⊆ N this is harmless, but it should be stated consistently to avoid confusion.
[Throughout] There are several typos and formatting issues, e.g., 'asgents' in Section 2.1, 'D roop' in the abstract, and the footnote 'Droop quota' spacing. These should be cleaned up in a revision.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's derivations are definitional equivalences and triangle-inequality bounds, and its load-bearing EAR rank-JR premise is an external assumption rather than a self-referential input.

full rationale

The paper's derivation chain is not circular. Theorem 2 proves an equivalence between β-plurality points and 1/β-Droop proportional clusterings for k = 1 by unpacking both definitions; this is a genuine connection theorem, not a fitted or renamed quantity. Theorem 3 and Theorem 5 derive distortion and proportionality bounds from their respective assumptions (β-plurality, ℓ-rank-JR) via triangle-inequality manipulations, and no parameter is fitted to data or renamed as a prediction. Theorem 4 rests on properties of PluralityVeto; even if its proof contains an unjustified metric inequality, that is a correctness concern, not circularity. The main algorithmic claim relies on the Section 5 remark that EAR satisfies ℓ-rank-JR with ℓ ≥ n/k; this premise is asserted without proof, but it is an external input assumption rather than a conclusion derived from itself, so it does not make the argument circular. The self-citations, including Kellerhals and Peters [2024], are contextual and not load-bearing; the appendix proof of Theorem 6 is self-contained. No equation reduces by construction to its own input, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no fitted parameters or invented entities. The central bound is derived from standard metric axioms. The most fragile input is the unproved EAR rank-JR property, which is essential to the main open-question result. The plurality veto proof also silently assumes a tie-breaking rule that the paper does not define.

assumptions (4)

standard math Triangle inequality in metric spaces
Used in proofs of Theorems 3, 4, 5, and 7.
domain assumption Agents and candidates are points in a common metric space; each agent has a sincere distance ranking over candidates
Standard model for metric distortion; stated in Sections 2 and 3.
domain assumption Plurality veto proceeds by decrementing the lowest positive score, with tie-breaking left unspecified
Definition in Section 4; the unspecified tie-breaking is load-bearing for Theorem 4 and is not justified.
ad hoc to paper EAR satisfies ℓ-rank-JR with ℓ ≥ n/k
Stated as a remark in Section 5 without proof or citation; the open-question result relies on it.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Proportional Clustering, the $\beta$-Plurality Problem, and Metric Distortion." pith.science (2026). https://pith.science/paper/S7RODBAZ

@misc{pith2026250210068,
  author       = {Pith},
  title        = {Pith review of: Proportional Clustering, the $\beta$-Plurality Problem, and Metric Distortion},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/S7RODBAZ}},
  note         = {Machine review of arXiv:2502.10068}
}

abstract

We show that the proportional clustering problem using the Droop quota for $k = 1$ is equivalent to the $\beta$-plurality problem. We also show that the Plurality Veto rule can be used to select ($\sqrt{5} - 2$)-plurality points using only ordinal information about the metric space and resolve an open question of Kalayci et al. (AAAI 2024) by proving that $(2+\sqrt{5})$-proportionally fair clusterings can be found using purely ordinal information.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 22 canonical work pages

[1]

Anshelevich, O

E. Anshelevich, O. Bhardwaj, E. Elkind, J. Postl, and P. Skowron. Approximating optimal social choice under metric preferences. Artificial Intelligence, 264: 0 27--51, 2018

work page 2018
[2]

Aronov, M

B. Aronov, M. de Berg, J. Gudmundsson, and M. Horton. On beta -plurality points in spatial voting games. ACM Transactions on Algorithms , 17 0 (3): 0 1--21, 2021

work page 2021
[3]

Aziz and B

H. Aziz and B. E. Lee. The expanding approvals rule: improving proportional representation and monotonicity. Social Choice and Welfare, 54: 0 1--45, 2020

work page 2020
[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, B. E. Lee, S. Morota Chu , and J. Vollen. Proportionally representative clustering. In Proceedings of the 20th International Conference on Web and Internet Economics (WINE), 2024. Forthcoming

work page 2024
[6]

D. Black. On the rationale of group decision-making. Journal of Political Economy, 56 0 (1): 0 23--34, 1948

work page 1948
[7]

Brill and J

M. Brill and J. Peters. Robust and verifiable proportionality axioms for multiwinner voting. In Proceedings of the 24th ACM Conference on Economics and Computation (ACM-EC), page 301. ACM Press, 2023. Full version arXiv:2302.01989 [cs.GT]

arXiv 2023
[8]

Caragiannis, E

I. Caragiannis, E. Micha, and N. Shah. Proportional fairness in non-centroid clustering. In Proceedings of the 38th Conference on Neural Information Processing Systems (NeurIPS), 2024. Forthcoming

work page 2024

Show all 25 references

[9]

X. Chen, B. Fain, L. Lyu, and K. Munagala. Proportionally fair clustering. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 1032--1041, 2019

2019
[10]

A. Downs. An economic theory of political action in a democracy. The Journal of Political Economy, 65 0 (2): 0 135--150, 1957

1957
[11]

H. R. Droop. On methods of electing representatives. Journal of the Statistical Society of London, 44 0 (2): 0 141--202, 1881
[12]

Ebadian and E

S. Ebadian and E. Micha. Boosting sortition via proportional representation. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2025. Forthcoming

2025
[13]

Enelow and M

J. Enelow and M. Hinisch. On plott's pairwise symmetry condition for majority rule equilibrium. Public Choice, 40 0 (3): 0 317--321, 1983

1983
[14]

Filtser and O

A. Filtser and O. Filtser. Plurality in spatial voting games with constant . Discrete & Computational Geometry, pages 1--16, 2024

2024
[15]

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
[16]

Y. H. Kalaycı, D. Kempe, and V. Kher. Proportional representation in metric spaces and low-distortion committee selection. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 9815--9823. AAAI Press, 2024

2024
[17]

Kellerhals and J

L. Kellerhals and J. Peters. Proportional fairness in clustering: A social choice perspective. In Proceedings of the 38th Conference on Neural Information Processing Systems (NeurIPS), pages 111299--111317, 2024

2024
[18]

F. E. Kızılkaya and D. Kempe. P lurality V eto: A simple voting rule achieving optimal metric distortion. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), pages 349 -- 355, 2022

2022
[19]

F. E. Kızılkaya 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. ACM Press, 2023

2023
[20]

Lassota, A

A. Lassota, A. Vetta, and B. von Stengel. The condorcet dimension of metric spaces. Technical report, arXiv:2410.09201 [cs.GT], 2024

2024 arXiv
[21]

Masa r \' k, G

T. Masa r \' 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. ACM Press, 2024

2024
[22]

McCune and A

D. McCune and A. Graham-Squire. Monotonicity anomalies in scottish local government elections. Social Choice and Welfare, 63 0 (1): 0 69--101, 2024

2024
[23]

Micha and N

E. Micha and N. Shah. Proportionally fair clustering revisited. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP), pages 85:1--85:16, 2020

2020
[24]

Peters and P

D. Peters and P. Skowron. Proportionality and the limits of welfarism. In Proceedings of the 21st ACM Conference on Economics and Computation (ACM-EC), pages 793--794. ACM Press, 2020

2020
[25]

N. Tideman. The single transferable vote. Journal of Economic Perspectives, 9 0 (1): 0 27--38, 1995

1995

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Anshelevich, O

E. Anshelevich, O. Bhardwaj, E. Elkind, J. Postl, and P. Skowron. Approximating optimal social choice under metric preferences. Artificial Intelligence, 264: 0 27--51, 2018

work page 2018

[2] [2]

Aronov, M

B. Aronov, M. de Berg, J. Gudmundsson, and M. Horton. On beta -plurality points in spatial voting games. ACM Transactions on Algorithms , 17 0 (3): 0 1--21, 2021

work page 2021

[3] [3]

Aziz and B

H. Aziz and B. E. Lee. The expanding approvals rule: improving proportional representation and monotonicity. Social Choice and Welfare, 54: 0 1--45, 2020

work page 2020

[4] [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] [5]

H. Aziz, B. E. Lee, S. Morota Chu , and J. Vollen. Proportionally representative clustering. In Proceedings of the 20th International Conference on Web and Internet Economics (WINE), 2024. Forthcoming

work page 2024

[6] [6]

D. Black. On the rationale of group decision-making. Journal of Political Economy, 56 0 (1): 0 23--34, 1948

work page 1948

[7] [7]

Brill and J

M. Brill and J. Peters. Robust and verifiable proportionality axioms for multiwinner voting. In Proceedings of the 24th ACM Conference on Economics and Computation (ACM-EC), page 301. ACM Press, 2023. Full version arXiv:2302.01989 [cs.GT]

arXiv 2023

[8] [8]

Caragiannis, E

I. Caragiannis, E. Micha, and N. Shah. Proportional fairness in non-centroid clustering. In Proceedings of the 38th Conference on Neural Information Processing Systems (NeurIPS), 2024. Forthcoming

work page 2024