Pith. sign in

REVIEW 3 major objections 5 minor 18 references

Metric Distortion for Tournament Voting and Beyond

T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read Deterministic tournament rules cannot reach distortion 3; the optimal constant lies between 3.1128 and 3.9312, and moving from pairwise to k-wise preference data restores near-3 or sub-3 performance.

desk verdict The deterministic tournament bounds are the real result; the randomized k-tournament claim is conditional on an unproved lemma. read the letter →

arxiv 2505.13630 v1 pith:UND7QOZM submitted 2025-05-19 cs.GT

Moses Charikar , Prasanna Ramakrishnan , Zihan Tan , Kangning Wang This is my paper · ORCID
classification cs.GT MSC 91B1291B1405C20
keywords metricdistortiontournamentrulesk-tournamentsocialchoicestablelotteriesbiasedframeworkUnblanketedSetdeterministicvoting
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

This paper asks how much social cost a voting rule must sacrifice when it sees only aggregate pairwise preferences instead of full rankings, and what can be gained by seeing slightly more. It establishes that deterministic tournament rules—rules that use only the share of voters preferring each candidate to each other—cannot achieve the distortion 3 available to deterministic ranked rules or randomized tournament rules; the optimal constant lies between 3.1128 and 3.9312. It then introduces k-tournament rules, which receive the fraction of voters ranking each k-tuple in each order, and shows that deterministic such rules approach distortion 3 as k grows, while a randomized 3-tournament rule drops strictly below 3, a level previously out of reach for pairwise-only rules. A sympathetic reader should care because metric distortion measures worst-case welfare loss from coarse preference information, and pinning down the floor for each information class says exactly how much extra querying is worth.

What carries the argument

The engine is the biased metric framework, which reduces worst-case distortion to an integral inequality over "stacked blocks" representing voter distances; for tournaments, the paper extracts local graph conditions from this inequality. The new deterministic rule is built on blanketing, a strengthening of the classical covering condition, and the proof that an unblanketed candidate always exists uses a cycle argument. For k-tournaments, the central objects are stable k-lotteries—distributions over candidates that beat any other distribution with probability $1-\frac{1}{k+1}$ in a voter's eyes—together with the stability-representation lemma, which bounds how much probability a stable lottery can place on a set $J$ when many voters rank an outside candidate $i$ above all of $J$.

What would settle it

Take the 5-candidate tournament matrix from Section 4.3 and solve the exact integral condition for the best possible deterministic tournament rule; if the optimum is below 3.1128, the lower bound is false, and if the preference profiles in the tables fail to reproduce the matrix exactly, the construction is invalid.

Watch

Extended reading notes

Core claim

The paper's central claim is that the metric distortion of deterministic tournament rules is not 3 but a non-integral constant in the interval $[3.1128, 3.9312]$. The lower bound is established by a 5-candidate election with a deliberately asymmetric tournament graph and exponentially increasing vote margins, for which every candidate has worst-case distortion at least $3.1128$; the upper bound comes from the Unblanketed Set rule, which always selects a candidate not "blanketed" by another and guarantees distortion at most $1+2\lambda\approx 3.9312$, where $\lambda$ solves $\lambda^3-\lambda^2-1=0$. The paper then defines k-tournament rules and proves that deterministic such rules can approach distortion 3 as k grows, while a randomized rule using 3-way preference data achieves distortion strictly below 3.

Load-bearing premise

The claim that randomized rules with three-way preference data beat distortion 3 depends on a lemma the paper borrows from an earlier work and proves only by sketch; if that lemma is wrong as stated, that particular separation result is unsupported.

Editorial extensions

If this is right

  • If Theorem 1.1 is right, every deterministic rule that sees only pairwise vote shares has worst-case distortion above 3.1128, so the Condorcet-style distortion-3 guarantee is unattainable in this class.
  • The Unblanketed Set rule, if its analysis holds, improves the best deterministic tournament upper bound from $2+\sqrt{5}\approx 4.236$ to about $3.93$.
  • If Simultaneous Lottery Veto's bound holds, collecting favorite and least-favorite preferences over k-tuples lets a deterministic rule approach distortion 3 without full rankings.
  • If Pruned Double Lotteries' bound holds, randomizing over stable lotteries after quasi-kernel pruning yields distortion below 3 with k=3, separating randomized tournament rules from randomized 3-tournament rules.
  • The stability-representation lemma, if correct, is a reusable bridge between committee-selection algorithms and voting rules.

Reading between the lines

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

  • The paper's use of a half-integral biased metric for one candidate suggests that the conjecture that $(0,1,2,3)$-metrics are the only hard cases may be too restrictive; similar metrics might improve known lower bounds for randomized voting rules.
  • Because the k-tournament rules need only each voter's top and bottom choice within a k-set rather than a full ranking, the results suggest that RLHF-style preference elicitation can use cheaper top-and-bottom queries and still capture much of the benefit of k-wise data.
  • Closing the deterministic tournament gap likely requires avoiding the block-sliding obstruction the paper identifies: a multi-candidate version of its shifting argument would imply Ranked Pairs has distortion 3, which is known to be false, so new upper-bound rules probably need a different mechanism.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper studies metric distortion in social choice, focusing on tournament rules (which observe pairwise aggregate preferences) and a new class of k-tournament rules (which observe aggregate preferences over k-tuples). The main claims are: (i) the optimal metric distortion of deterministic tournament rules lies between 3.1128 and 3.9312, established via a new deterministic rule called Unblanketed Set and a 5-candidate lower-bound instance (Theorems 1.1, 4.9, 4.10); (ii) a deterministic k-tournament rule, Simultaneous Lottery Veto, achieves distortion 3 + O((log k / k)^{1/4}) (Theorem 5.13); and (iii) a randomized k-tournament rule, Pruned Double Lotteries, achieves distortion strictly below 3, even for 3-tournament rules (Theorems 1.2 and 5.14). The proofs use the biased-metric integral framework of Charikar and Ramakrishnan and Charikar et al., a block-sliding argument for the deterministic upper bound, and stable k-lotteries from committee selection. The deterministic results are developed in detail; the randomized k-tournament result depends on a lemma that is only sketched and delegated to prior work.

Significance. If the deterministic bounds are correct, they resolve a long-standing question by showing that no deterministic tournament rule can achieve distortion 3, while also improving the upper bound from 2+sqrt(5) to 3.9312. This is a substantive contribution to the metric distortion literature. The introduction of k-tournament rules is a natural and potentially useful generalization, with motivation from RLHF and from the theory of k-wise comparison queries. The deterministic proofs are largely self-contained and include explicit constructions: the stability-representation lemma (Lemma 5.6), the existence and defensive properties of stable k-lotteries (Theorems 5.4 and 5.5), and the subtle block-shifting argument for Lemma 4.2 are all given in full. The randomized claim of distortion below 3 for 3-tournament rules would be a striking separation if fully supported, but as written its proof lacks a complete formal derivation of the key reduction, which tempers the significance of that part of the paper.

major comments (3)
  1. [Section 5.4, Lemma 5.15 and Theorem 5.14] The proof of Theorem 5.14 for arbitrary preference profiles, and hence the randomized claim in Theorem 1.2 and in the abstract, rests entirely on Lemma 5.15. This lemma is stated as 'implicit in [CRWW24]' and is followed by a proof sketch whose final sentence refers the reader to [CRWW24] for formal execution. No specific statement in [CRWW24] is cited that directly implies Lemma 5.15 as written, namely that stable k-lotteries for all k >= 2 can be combined with quasi-kernel pruning and a stable 1-lottery to give distortion below 3 with parameters independent of k. The sketch's two-case discussion does not quantify the (alpha,beta)-consistency threshold or the resulting constants r, r', mu, and theta. This gap is load-bearing: the direct analysis in the proof of Theorem 5.14 (using Lemma 5.16 and the stability-representation lemma) only establishes the desired lambda < 1 bound for theta-regular profiles, and the step from theta-regular profiles to general profiles is exactly Lemma 5.15. Please provide a complete proof of Lemma 5.15 or a precise citation to a statement in [CRWW24] that covers the needed parameter range for all k >= 2.
  2. [Section 4.3, Tables 1 and 2] The lower bound of Theorem 4.10 requires the listed preference profiles to realize the tournament margins and to satisfy the exact equalities used in the integral computations, e.g., 1 - plu(j*-1) = s_{j*-2 > j*-1} for j* = 1,2,3,4, and s_{2 > 0} = s_{3 > 0} = s_{4 > 0} = s_{2,3,4 > 0} = beta for j* = 0. The text says these conditions are 'indeed satisfied' and that the profiles are 'optimal,' but it does not show the algebra or provide checking code. Because Theorem 4.10 is a central contribution, the verification should be included, either as an exact arithmetic derivation or as a reproducible auxiliary file. Without this, the lower-bound claim is not fully checkable as written.
  3. [Section 5.3, Theorem 5.13] The proof of Theorem 5.13 is concise but appears to rely on an implicit re-use of the quasi-kernel pruning property for sets J that may contain pruned candidates. In the chain of inequalities after applying Lemma 5.6, the argument uses that s_{i > J} <= theta for every candidate i in the quasi-kernel and every subset J disjoint from {i}, but it is not stated explicitly whether the partition J is restricted to the pruned set C-hat. Since the inequality 's_{i > J} <= theta' is only justified for pairs both inside the quasi-kernel, the proof should clarify how subsets containing non-quasi-kernel candidates are handled. This is likely fixable and does not undermine the asymptotic claim, but it should be made explicit.
minor comments (5)
  1. [Section 4.1, proof of Lemma 4.2] In the last paragraph of the proof, 'Thus, g_v(1) = 1 as claimed' should be 'g_v(t) = 1' to match the preceding sentence.
  2. [Section 4.1, proof of Corollary 4.5] The notation 'i*, k* in I' should read 'i*, k in I' to be consistent with the statement of the corollary.
  3. [Sections 5.4 and Abstract] The parameter k is overloaded: in Theorem 5.14 the rule is called a (k+1)-tournament rule, while the abstract and Theorem 1.2 refer to a randomized 3-tournament rule. This is not an error, but the correspondence (set the stable-lottery size to 2 for a 3-tournament rule) should be stated explicitly to avoid confusion.
  4. [Section 4.3, Theorem 4.10] The matrix and tables give decimal values rounded to a few digits, while the derivation uses exact symbolic parameters beta and lambda. Please state the precision of the decimal approximations and confirm that the profile weights in Tables 1 and 2 sum to 1 within the stated precision.
  5. [Abstract and Introduction] The phrase 'which had been a longstanding barrier even for the larger class of ranked voting rules' could be misread as claiming that breaking distortion 3 for ranked voting rules is new. Since [CRWW24] already achieved distortion below 3 for randomized ranked voting rules, please rephrase to make clear that the barrier here is specifically for k-tournament rules.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: deterministic bounds are explicit profile constructions and sufficient-condition derivations; the Lemma 5.15 delegation to CRWW24 is a completeness gap, not circularity.

full rationale

No circularity found. The deterministic lower bound (Theorem 4.10) is an explicit 5-candidate adversarial tournament with concrete preference profiles (Tables 1 and 2), and the proof verifies the required biased-metric inequalities directly rather than fitting them to the target 3.1128. The Unblanketed Set upper bound (Theorem 4.9) is a genuine derivation: Lemma 4.2 proves a sufficient integral condition, Corollary 4.5 translates it into graph conditions, and Lemma 4.8 proves an unblanketed candidate always exists; choosing lambda as the root of x^3 - x^2 - 1 is an optimization, not an import of the conclusion. For k-tournaments, the stability-representation lemma (Lemma 5.6) is proved in-text via Lemmas 5.4, 5.5, and 5.7, and the Simultaneous Lottery Veto analysis follows from Corollary 3.3 and Observation 5.12. The randomized claim (Theorem 5.14) has the same shape: the theta-regular profile analysis is carried out in-text (Lemma 5.16 and the small-k/large-k cases). The only caveat is Lemma 5.15, stated as 'implicit in [CRWW24]' with a proof sketch and formal execution delegated to that reference. This is a load-bearing self-citation and a possible completeness gap, and if Lemma 5.15 were false or unavailable, Theorem 5.14 would be unsupported. That is a correctness/support concern, not circularity: the cited framework is prior work, not an assumption of the distortion claim being proved, and no equation in the paper reduces by construction to a fitted parameter or to the target bound.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The new mathematical constructs, such as k-tournament rules and the voting rules Unblanketed Set, Simultaneous Lottery Veto, and Pruned Double Lotteries, are algorithmic or definitional contributions rather than postulated entities with independent falsifiable handles. The free parameters listed are explicit constants chosen to optimize bounds, not hidden fudge factors. The primary assumption beyond standard math is the biased-metric framework from prior work, and the unproven Lemma 5.15.

free parameters (3)
  • beta (lower bound) = ~0.60696
    Chosen with lambda to optimize the 5-candidate lower-bound construction; beta = 2/(1+lambda^2+lambda^3), set to satisfy the tournament realizability inequality with equality.
  • lambda (lower bound) = ~1.056439
    Root of 2*lambda^5 + lambda^4 + lambda^3 - lambda - 4 = 0, chosen to maximize the lower bound distortion 1+2*lambda in Theorem 4.10.
  • alpha, beta (Unblanketed Set) = alpha = 1/lambda ~ 0.68233, beta = 2 - lambda ~ 0.53443
    Tuning parameters of the Unblanketed Set rule, chosen to minimize the proven distortion bound in Theorem 4.9; explicit and not hidden.
assumptions (5)
  • domain assumption Biased metric framework: Theorem 3.2 of CRWW24 characterizes worst-case distortion via integrals over biased metrics.
    Both the upper and lower bounds in Section 4 and the k-tournament analyses in Section 5 rely on this characterization as a black box.
  • standard math Existence of stable k-lotteries with i.i.d. sampling (Theorem 5.5, following CJMW20).
    Used in the definitions and analyses of Simultaneous Lottery Veto and Pruned Double Lotteries.
  • standard math Existence of quasi-kernels in directed graphs (CL74, Cro15).
    Used in quasi-kernel pruning in Section 5.3.
  • domain assumption Lemma 5.15 is 'implicit in CRWW24' and is not fully proven here.
    Theorem 5.14's conclusion depends on this lemma; the paper provides only a proof sketch and refers to CRWW24 for formal execution.
  • standard math Concentration inequalities (Chernoff, Holder, Jensen).
    Used in the proof of the stability-representation lemma (Lemma 5.6).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Metric Distortion for Tournament Voting and Beyond." pith.science (2026). https://pith.science/paper/UND7QOZM

@misc{pith2026250513630,
  author       = {Pith},
  title        = {Pith review of: Metric Distortion for Tournament Voting and Beyond},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UND7QOZM}},
  note         = {Machine review of arXiv:2505.13630}
}
abstract

In the well-studied metric distortion problem in social choice, we have voters and candidates located in a shared metric space, and the objective is to design a voting rule that selects a candidate with minimal total distance to the voters. However, the voting rule has limited information about the distances in the metric, such as each voter's ordinal rankings of the candidates in order of distances. The central question is whether we can design rules that, for any election and underlying metric space, select a candidate whose total cost deviates from the optimal by only a small factor, referred to as the distortion. A long line of work resolved the optimal distortion of deterministic rules, and recent work resolved the optimal distortion of randomized (weighted) tournament rules, which only use the aggregate preferences between pairs of candidates. In both cases, simple rules achieve the optimal distortion of $3$. Can we achieve the best of both worlds: a deterministic tournament rule matching the lower bound of $3$? Prior to our work, the best rules have distortion $2 + \sqrt{5} \approx 4.2361$. In this work, we establish a lower bound of $3.1128$ on the distortion of any deterministic tournament rule, even when there are only 5 candidates, and improve the upper bound with a novel rule guaranteeing distortion $3.9312$. We then generalize tournament rules to the class of $k$-tournament rules which obtain the aggregate preferences between $k$-tuples of candidates. We show that there is a family of deterministic $k$-tournament rules that achieves distortion approaching $3$ as $k$ grows. Finally, we show that even with $k = 3$, a randomized $k$-tournament rule can achieve distortion less than $3$, which had been a longstanding barrier even for the larger class of ranked voting rules.

Figures

Figures reproduced from arXiv: 2505.13630 by the authors.

Figure 1
Figure 1. The biased metric integrals as stacked blocks. Each block is annotated with its cor [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗
Figure 2
Figure 2. After sliding the blocks corresponding to voters that prefer [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗
Figure 3
Figure 3. Examples of local structures where Corollary 4.5 shows that SC(j ∗ ) ≤ (1 + 2λ) SC(i ∗ ). Proof of Corollary 4.5. We will prove that each of the conditions is sufficient one at at time, by showing that they imply the conditions of Corollary 4.3 (with the same choice of k). First, note that k = i ∗ or si ∗≻j ∗ ≤ 1 ≤ λsk≻i ∗ so the first condition is satisfied. It remains to check the second condition given (I) and (I… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Left: the cycle C. Right: the cycle Cˆ. We derive a contradiction by showing that some i ∗ cannot blanket some j ∗ , using k and ℓ as labeled. Fix a candidate k in the cycle. We claim that there exists some edge (i ∗ , j∗ ) ∈ C such that sk≻j ∗ < α and either k = i ∗ o…
Figure 5
Figure 5. Figure 5: A tournament graph where each candidate has worst-case distortion at least 3.112. [PITH_FULL_IMAGE:figures/full_fig_p021_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 12 canonical work pages

  1. [6]

    Fair allocation of indivisible public goods

    [FMS18] Brandon Fain, Kamesh Munagala, and Nisarg Shah. Fair allocation of indivisible public goods. In Proceedings of the 2018 ACM Conference on Economics and Computation (EC), pages 575–592,

    work page 2018

  2. [7]

    Krishnaswamy, and Kamesh Munagala

    34 [GKM17] Ashish Goel, Anilesh K. Krishnaswamy, and Kamesh Munagala. Metric distortion of social choice rules: Lower bounds and fairness properties. In Proceedings of the 2017 ACM Conference on Economics and Computation (EC) , pages 287–304,

    work page 2017

  3. [8]

    An analysis framework for metric voting based on LP duality

    [Kem20a] David Kempe. An analysis framework for metric voting based on LP duality. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI) , pages 2079–2086,

    work page

  4. [9]

    Communication, distortion, and randomness in metric voting

    [Kem20b] David Kempe. Communication, distortion, and randomness in metric voting. In Pro- ceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI) , pages 2087– 2094,

    work page

  5. [13]

    Improved metric distortion for deterministic social choice rules

    [MW19] Kamesh Munagala and Kangning Wang. Improved metric distortion for deterministic social choice rules. In Proceedings of the 2019 ACM Conference on Economics and Computation (EC), pages 245–262,

    work page 2019

  6. [14]

    GPT-4 technical report

    [O+23] OpenAI et al. GPT-4 technical report. CoRR, abs/2303.08774,

    arXiv

  7. [1433]

    Mapping social choice theory to RLHF

    [DF24] Jessica Dai and Eve Fleisig. Mapping social choice theory to RLHF. In ICLR 2024 Workshop on Reliable and Responsible Foundation Models ,

    work page 2024

  8. [1928]

    Su, Zhiwei Steven Wu, and Linjun Zhang

    [ZDS+24] Huiying Zhong, Zhun Deng, Weijie J. Su, Zhiwei Steven Wu, and Linjun Zhang. Provable multi-party reinforcement learning with diverse human feedback. CoRR, abs/2403.05006,

    arXiv

Show all 18 references
  1. [1960]

    and of G¨ osing, Austria (3–27 July 1962), pages 73–79,

    1962

  2. [1964]

    On voting and facility location

    [FFG16] Michal Feldman, Amos Fiat, and Iddan Golomb. On voting and facility location. In Proceedings of the 2016 ACM Conference on Economics and Computation (EC), pages 269–286,

    2016

  3. [1980]

    AI alignment and social choice: Fundamental limitations and policy implications

    [Mis23] Abhilash Mishra. AI alignment and social choice: Fundamental limitations and policy implications. CoRR, abs/2310.16048,

    arXiv

  4. [1984]

    The metric distortion of randomized social choice functions: C1 maximal lottery rules and simulations

    [FL24] Fabian Frank and Patrick Lederer. The metric distortion of randomized social choice functions: C1 maximal lottery rules and simulations. CoRR, abs/2403.18340,

    arXiv

  5. [1987]

    Llama 2: Open foundation and fine-tuned chat models

    [TMS+23] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton-Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jer...

    arXiv

  6. [2006]

    On the randomized metric distortion conjecture

    36 [PS21] Haripriya Pulyassary and Chaitanya Swamy. On the randomized metric distortion conjecture. arXiv preprint arXiv:2111.08698 ,

    arXiv

  7. [2019]

    Woodruff

    [MSW20] Debmalya Mandal, Nisarg Shah, and David P. Woodruff. Optimal communication- distortion tradeoff in voting. InProceedings of the 2020 ACM Conference on Economics and Computation (EC) , pages 795–813,

    2020

  8. [2020]

    Every directed graph has a semi-kernel

    [CL74] Vaˇ sek Chv´ atal and L´ aszl´ o Lov´ asz. Every directed graph has a semi-kernel. InHyper- graph Seminar: Ohio State University 1972 , page

    1972

  9. [2022]

    Ozdaglar

    [PLK+24] Chanwoo Park, Mingyang Liu, Dingwen Kong, Kaiqing Zhang, and Asuman E. Ozdaglar. RLHF from heterogeneous feedback via personalization and preference ag- gregation. CoRR, abs/2405.00254,

    arXiv

  10. [2024]

    Metric distortion bounds for random- ized social choice

    [CR22] Moses Charikar and Prasanna Ramakrishnan. Metric distortion bounds for random- ized social choice. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2986–3004,

    2022

Pith tools

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