Pith. sign in

REVIEW 1 major objections 4 minor 13 references

Distortion of Metric Voting with Bounded Randomness

T0 review · 1 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

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

Pith's one-line read This paper proves that a voting rule which picks uniformly at random from a fixed list of constant size can achieve metric distortion strictly below 3, breaking the barrier known to separate deterministic rules from randomized ones.

desk verdict A real answer to a natural question about constant-size uniform randomness breaking the distortion-3 barrier, but the advertised 'deterministically identified list' is missing a verification step; worth refereeing after a fix. read the letter →

arxiv 2602.08871 v2 pith:E2WUVZ5U submitted 2026-02-09 cs.GT cs.DMcs.DS

Ziyi Cai , D. D. Gao , Prasanna Ramakrishnan , Kangning Wang This is my paper · ORCID
classification cs.GTcs.DMcs.DS MSC 91B1491B12
keywords metricdistortionrandomizedvotingrulesboundedrandomnessMaximalLotteriesStablequasi-kernelsocialchoiceapproximateequilibrium
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 asks whether the gap between deterministic voting rules, whose metric distortion cannot be better than 3, and fully randomized rules, which can do strictly better but with arbitrary distributions, can be closed using only bounded randomness — a rule that first names a constant-size list of candidates and then picks the winner uniformly from that list. The main result is an affirmative answer: there exist absolute constants ε > 0 and k such that a rule of this form has metric distortion at most 3 − ε. The proof mixes two approximate lottery rules — an approximate Maximal Lottery and an approximate Pruned Lottery, each supported on a constant number of samples — and shows that on every biased metric, the canonical hard case for distortion, the mixture is strictly below 3. If correct, the result shows that the advantage of randomization over determinism in metric voting does not require elaborate distributions; a transparent roster of constant size already suffices.

What carries the argument

The argument runs on four objects. (1) Biased metrics: a family of hard metric spaces such that a distortion bound on them transfers to all metrics; analysis reduces to two curves, ℓ(D,t) and r(t). (2) RepApx (Representative Approximate) Maximal and Stable Lotteries: distributions supported inside an exact lottery's support and satisfying approximate equilibrium inequalities; a standard concentration inequality for empirical distributions shows a constant-size uniform sample is RepApx with positive probability. (3) Quasi-Kernel Pruning: a linear-time reduction of candidates to a small kernel that preserves near-optimal social cost. (4) The mixing theorem: a tuned convex combination of the tw

What would settle it

Enumerate all constant-size lists up to the paper's implied bound for a small election (say 10 voters, 10 candidates on a line) and compute the worst-case distortion of each uniform lottery; the theorem is false if any list produced by the construction, or every list, has distortion at least 3 in some metric. One concrete violation suffices because the bound is uniform over all metrics.

Watch

Extended reading notes

Core claim

The central claim is Theorem 7.6: for suitable constants μ, β̃, ε₁, ε₂, and k, the mixed rule — with probability μ an ε₁²-RepApx Maximal Lottery, otherwise an (ε₂, k, 1/2+β̃)-RepApx Pruned Lottery — has metric distortion strictly below 3. Corollary 7.7 adds the bounded-randomness form: the support is a constant-size multiset, and with μ rational the rule is a uniform lottery over a fixed list with repetitions. The proof splits biased metrics into two regimes — inconsistent ones, where the Approximate Maximal Lottery component beats 3 by a constant, and strongly consistent ones, where the Approximate Pruned Lottery component does the same. Two structural results carry the proof: support candi

Load-bearing premise

The load-bearing premise is that a constant-size multiset with distortion below 3−ε can be found: existence follows from the sampling theorems, but the paper's enumeration-and-stop argument assumes a way to test the distortion property without specifying it.

Editorial extensions

If this is right

  • Any metric space: a uniform lottery over a constant-size list achieves distortion strictly below 3, so the optimal distortion constant for bounded randomness matches that of unrestricted randomized rules.
  • Transparency: because the rule is a fixed roster with uniform probabilities, it is easy to publish and audit, addressing a common objection to randomized voting.
  • Robustness: the support bound implies that every realized winner of the mixed rule has distortion at most 4+√17, so no single realization is catastrophic.
  • Multi-winner connection: for any sufficiently large committee size, the same technique yields a deterministic committee selection rule with distortion below 3 when seats can be repeated.
  • Open question: the paper conjectures that two options (N = 2) already suffice to break the barrier, an order of magnitude smaller than the current constants.

Reading between the lines

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

  • An implication the paper leaves implicit: the enumeration-and-stop procedure presumes a test for the distortion property; if the RepApx conditions are used as the test, the rule becomes fully constructive and polynomial-time.
  • The constants are far from tight; the same framework may support a much smaller list, and the paper's conjecture that two options suffice is a concrete target.
  • The multi-winner connection could yield a practical deterministic committee rule with distortion below 3; this is testable by simulation on random metrics.
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

1 major / 4 minor

Summary. The paper studies metric distortion in single-winner voting and asks whether the known randomized improvement below the deterministic barrier of 3 can be achieved with only 'bounded randomness': a rule that selects a winner uniformly from a constant-size list of candidates. The main formal result, Theorem 7.6, constructs a mixture of an ε1^2-RepApx Maximal Lottery and an (ε2,k,1/2+β~)-RepApx Pruned Lottery, with explicit parameters, whose metric distortion is strictly below 3. Corollary 7.7 states that the resulting rule has support size at most a constant independent of n and m. The proof develops several structural results: deterministic distortion of every candidate in the Maximal-Lottery support (Theorem 4.1), distortion of approximate Maximal Lotteries (Theorem 5.1), existence of small-support approximate Stable Lotteries via a DKW-based sampling argument (Theorem 3.4), and distortion bounds for approximate Pruned Lotteries under regular profiles and under strongly consistent biased metrics (Lemmas 6.3, 6.4, 7.5). The biased-metric framework of [CR22, CRWW24] is used throughout.

Significance. If the result holds, it is a significant step: it shows that the 3-distortion barrier for deterministic rules can be broken using randomness of a very restricted, interpretable form — a uniform lottery over a constant-size list. The structural results on the support of Maximal Lotteries and on small-support approximate Maximal/Stable Lotteries are likely to be of independent interest. The paper contains detailed proofs, and the main inequalities are derived in the body or appendices. The main caveat is that the advertised algorithmic 'deterministically identified list' part is not fully justified as written; however, the gap is local and reparable within the paper's framework.

major comments (1)
  1. [Section 1.1 (final paragraph) and Corollary 7.7] The paper claims a deterministic polynomial-time algorithm that enumerates multisets and 'stop[s] if the induced distribution achieves a metric distortion of less than 3−ε'. No finite decision procedure for this predicate is supplied. Theorem 2.8 characterizes distortion as an integral inequality over all biased metrics, which is not an algorithmic test, and Theorems 3.3–3.4 only establish existence of a good multiset with positive probability. Since the abstract and Section 1.1 promise a 'deterministically identified list', this gap is load-bearing for the advertised constructive claim. The gap is reparable: rather than testing exact distortion, enumerate constant-size multisets and test the RepApx conditions from Definitions 3.1 and 3.2, which are finite and polynomial-time checkable once an exact ML/Stable-Lottery support is computed; by Theorems 3.3 and 3.4 some multiset of the guara
minor comments (4)
  1. [Lemma 6.3 / Claim A.1] The constraint displayed as λ/(θ(1−θ)) should be λ(1−θ)/θ. The closed-form expression for λ(θ,k,ε) and the algebra in Claim A.1 (where f1(p*) = p* gives λ = p* · θ/(1−θ)) show that the intended first threshold is (λ/θ)(1−θ). As printed, the text is ambiguous and the sufficiency argument in Lemma 6.3 is incorrect under the literal reading. Please rewrite the formula unambiguously.
  2. [Section 3.4, proof of Theorem 3.4] The step from the expectation bound (4) to 'there is a positive probability ... for all candidates a' uses the inequality max_a avg_v d_{v,a} ≤ avg_v max_a d_{v,a}. This is true and standard, but it is not stated; adding one sentence would make the probabilistic inference transparent.
  3. [Section 5, first paragraph] The text refers to 'ε2-RegApx Maximal Lotteries'; the intended term is 'RepApx'.
  4. [Section 1.1, committee-selection implication] The sentence about committee selection says the result implies existence of a deterministic committee rule with distortion strictly less than 3 when candidates may occupy multiple seats. This is only a corollary of the existential support-size statement, not of the algorithmic enumeration claim, and it may be worth stating as such.

Circularity Check

1 steps flagged · score 4.0 of 10

Core distortion theorem is independent, but the 'deterministically identified list' is asserted via an unstated oracle: the enumeration stops on the target predicate 'distortion < 3−ε' with no finite test supplied.

  1. self definitional [Section 1.1, 'Our Results' (paragraph beginning 'To obtain a deterministic polynomial-time algorithm')]
    "To obtain a deterministic polynomial-time algorithm to find such a distribution, we can enumerate all multisets (from small to large) of the candidates and stop if the induced distribution achieves a metric distortion of less than 3−ε. Its running time is guaranteed to be polynomial since, according to our main result, there exists a multiset of constant size with an induced metric distortion of less than 3−ε."

    The stopping predicate is the theorem's own conclusion: 'the induced distribution achieves a metric distortion of less than 3−ε.' No finite decision procedure for this predicate is given; Theorem 2.8 only recasts distortion as an integral inequality over all biased metrics, which is not a finite test. Thus the proposed enumeration is not a derived algorithm unless one already has an oracle for the target guarantee. A finite verifiable substitute would be to check the RepApx conditions in Definitions 3.1/3.2, but the paper never states that these conditions are the stopping test. Consequently, the advertised 'deterministically identified list' is not established by the proof; it is assumed to be recognizable.

full rationale

The main distortion theorem is not circular. Definitions 3.1/3.2 define RepApx lotteries through approximate equilibria without assuming any distortion bound. The proof chain — biased-metric characterization (Theorem 2.8), distortion of approximate Maximal Lotteries (Theorem 5.1), distortion of approximate Stable Lotteries among regular profiles (Lemma 6.3), and the mixing argument (Theorem 7.6) — reduces upper bounds to verified inequalities and does not fit any parameter to the target quantity. The support-size corollary follows from sampling existence theorems, not from the distortion claim itself. The paper does lean heavily on prior work by overlapping authors, especially [CRW26, Theorem 1] for constant-support approximate Maximal Lotteries and [CRWW24, CRTW25] for the biased-metric machinery. These are parameter-free external theorems with stated assumptions that do not include the present target result, so under the independence-support rule they count as ordinary external dependence rather than circularity. The one concrete self-referential step is in Section 1.1, where the claimed deterministic identification of the constant-size list uses 'distortion < 3−ε' as the stopping test without supplying a finite way to evaluate that predicate. This affects the algorithmic 'deterministically identified list' part of the advertised contribution, but not the independent existence of a constant-support rule with distortion below 3. The gap is reparable by testing the finite RepApx conditions instead of exact distortion, but the manuscript does not say this. Score 4 reflects this partial self-definitional identification step while recognizing that the central distortion claim has independent content.

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

The main theorem introduces hand-chosen constants mu, alpha, beta~, epsilon1, epsilon2, and k, all selected to make inequalities in Appendix B strict; none are fitted to data. The structural assumptions are standard or imported from prior work; the most load-bearing unproved input is CRW26's Theorem 3.3.

free parameters (6)
  • k = any integer k >= 7
    Hand-chosen Stable-Lottery parameter; all subsequent constants are defined from k and the Appendix B inequalities hold for every integer k >= 7.
  • mu = 1 - L_k^2 / 2000
    Mixing probability hand-chosen so the weighted distortion inequalities in Claims B.4 and B.5 are strict.
  • alpha = L_k / 24
    Consistency parameter hand-chosen to make the strong-consistency bound exceed the epsilon1 penalty.
  • beta~ = L_k / 9
    Margin parameter in strong consistency; chosen with alpha for Claims B.4 and B.5.
  • epsilon1 = L_k^3 / 150000
    Approximation error for RepApx Maximal Lotteries; chosen small enough that 28*epsilon1 < 2*alpha*beta~.
  • epsilon2 = 1 / k
    Approximation error for RepApx Stable Lotteries; chosen so epsilon2*k = 1 and the lambda bound is controlled.
assumptions (5)
  • standard math Dvoretzky-Kiefer-Wolfowitz/Massart empirical-CDF concentration bound (Lemma 3.5).
    Used in Theorem 3.4 to convert sampling error into small-support RepApx Stable Lotteries.
  • standard math Every directed graph has a quasi-kernel (Chvatal-Lovasz).
    Used in Section 6 to define quasi-kernel pruning and bound the distance to the optimal candidate.
  • domain assumption Biased metrics are worst-case for metric distortion: Theorem 2.8 from CRWW24 characterizes distortion via the integral condition over biased metrics.
    All main bounds are proven only for biased metrics; the equivalence is imported from prior work.
  • domain assumption CRW26 Theorem 3.3: q = (1+o(1)) * pi / (8*epsilon^2) samples from a Maximal Lottery give an epsilon-RepApx Maximal Lottery with positive probability.
    Load-bearing input for constant support of the Maximal-Lottery branch; not reproven in this paper.
  • domain assumption Exact Maximal Lotteries and Stable k-Lotteries exist, are poly-time computable, and satisfy the value theorems (2.12 and 2.15).
    Used throughout Sections 4-7; cited from Bra17 and CRTW25.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Distortion of Metric Voting with Bounded Randomness." pith.science (2026). https://pith.science/paper/E2WUVZ5U

@misc{pith2026260208871,
  author       = {Pith},
  title        = {Pith review of: Distortion of Metric Voting with Bounded Randomness},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/E2WUVZ5U}},
  note         = {Machine review of arXiv:2602.08871}
}
abstract

We study the design of voting rules in the metric distortion framework. It is known that any deterministic rule suffers distortion of at least $3$, and that randomized rules can achieve distortion strictly less than $3$, often at the cost of reduced transparency and interpretability. In this work, we explore the trade-off between these paradigms by asking whether it is possible to break the distortion barrier of $3$ using only "bounded" randomness. We answer in the affirmative by presenting a voting rule that (1) achieves distortion of at most $3 - \varepsilon$ for some absolute constant $\varepsilon > 0$, and (2) selects a winner uniformly at random from a deterministically identified list of constant size. Our analysis builds on new structural results for the distortion and approximation of Maximal Lotteries and Stable Lotteries.

Figures

Figures reproduced from arXiv: 2602.08871 by the authors.

Figure 1
Figure 1. ℓ(𝐷, 𝑡) and 𝑟(𝑡). Proof of Fact 2.6. By definition, for all voter 𝑣 we have 𝑑(𝑗, 𝑣) − 𝑑(𝑖 ∗ , 𝑣) > 𝑡 ⇐⇒ min 𝑘:𝑗⪰𝑣 𝑘 𝑥𝑘 > 𝑡 ⇐⇒ 𝑥𝑘 > 𝑡 if 𝑗 ⪰𝑣 𝑘 ⇐⇒ 𝑘 ≻𝑣 𝑗 if 𝑥𝑘 ≤ 𝑡. Therefore, voter 𝑣 prefers every candidate in 𝐼𝑡 to 𝑗, or equivalently, we have 𝐼𝑡 ≻𝑣 𝑗. □ Proof of Fact 2.7. By definition, for all voter 𝑣 we have 2𝑑(𝑖 ∗ , 𝑣) ≤ 𝑡 ⇐⇒ max 𝑖,𝑗:𝑖⪰𝑣 𝑗 (𝑥𝑖 − 𝑥𝑗) ≤ 𝑡 ⇐⇒ 𝑥𝑖 − 𝑥𝑗 ≤ 𝑡 if 𝑖 ⪰𝑣 𝑗. Since 𝑥𝑖 − 𝑥𝑗 = 0 ≤ 𝑡 always hold… view at source ↗
Figure 2
Figure 2. Partition of the interval [0, 1] induced by the preference order 𝑑 ≻𝑣 𝑐 ≻𝑣 𝑏 ≻𝑣 𝑎. The multiset is 𝑆 = {𝑎, 𝑎, 𝑏, 𝑐, 𝑐, 𝑐}. To compute Pr[𝑐 ≻𝑣 𝑆], we sample 𝑋1, . . . , 𝑋6 and 𝑍 indepen￾dently from the corresponding subintervals of [0, 1]. In this example, we have Pr[𝑐 ≻𝑣 𝑆] = Pr[max {𝑋1, . . . , 𝑋6} < 𝑍] = 1/4. 3.3 Sampling Process In this subsection, we outline a technique that allows us to equate the process of sa… view at source ↗
Figure 3
Figure 3. Pictorial illustration of ℓ(𝐷ML, 𝑡) v.s. 𝑟(𝑡), and ℓ(𝐷𝜀 2 -ML, 𝑡) v.s. 𝑟(𝑡) + 2𝜀 Case (1): Integral on 0 ≤ 𝑡 < 𝜏. When 𝑡 falls within the range [0, 𝜏), we have 𝑃(𝐼 𝑐 𝑡 ) > 𝜀. In this case, the pointwise inequality that relates ℓ(𝐷, 𝑡) to the lifted version of 𝑟(𝑡) holds. The following lemma is inspired by and generalizes its counterpart [CRWW24, Theorem 1] which is used in showing that exact (i.e., 𝜀 = 0) Maximal Lo… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Pictorial illustration of ℓ(𝐷, 𝑡) and 𝑟(𝑡) + 2𝜀 Case 1: 𝛼𝑅 ≥ 𝜏 (see Fig. 4a). Split the integral defining 𝐿(𝐷) into two parts: 0 ≤ 𝑡 < 𝛼𝑅 and 𝑡 ≥ 𝛼𝑅. We can compute, 𝐿(𝐷) = ∫ 𝛼𝑅 0 ℓ(𝐷, 𝑡) d𝑡 + ∫ ∞ 𝛼𝑅 ℓ(𝐷, 𝑡) d𝑡 ≤ ∫ 𝛼𝑅 0 ℓ(𝐷, 𝑡) d𝑡 + ∫ ∞ 𝜏 ℓ(𝐷, 𝑡) d𝑡 (𝜏 ≤ 𝛼𝑅) ≤ ∫ 𝛼𝑅 0 (…
Figure 5
Figure 5. Figure 5: Pictorial illustration of 𝑓1(𝑝), 𝑓2(𝑝), and 𝑓3(𝑝). Proof of Claim A.1. For ease of notation, let 𝑓1(𝑝) = 𝜆 𝜃 (1 − 𝜃), 𝑓2(𝑝) = 𝜆 𝜃 · [PITH_FULL_IMAGE:figures/full_fig_p043_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 3 linked inside Pith

  1. [1]

    =3+12(1−𝜇)−𝜇 1 108𝐿2 𝑘−28𝜀 1 =3+ 12 2000𝐿2 𝑘−𝜇 1 108𝐿2 𝑘− 28 150000𝐿3 𝑘 =3+𝐿 2 𝑘 12 2000−𝜇 1 108− 28 150000𝐿𝑘 ≤3+𝐿 2 𝑘 12 2000−𝜇 1 108− 28 150000·4𝑒 (𝐿𝑘≤ 1 4𝑒 for any integer𝑘>0) ≤3+𝐿 2 𝑘 12 2000− 1− 1 2000· 1 4𝑒 2! · 1 108− 28 150000·4𝑒 ! (𝜇=1− 1 2000𝐿2 𝑘≥1− 1 2000· 1 4𝑒 2 for any integer𝑘≥4) <3.(𝐿 𝑘 >0for any integer𝑘≥5) This completes the proof.□ 46

    2000

  2. [11]

    On the randomized metric distortion conjecture.CoRR, abs/2111.08698,

    [PS21] Haripriya Pulyassary and Chaitanya Swamy. On the randomized metric distortion conjecture.CoRR, abs/2111.08698,

    arXiv

  3. [1891]

    An analysis framework for metric voting based on LP duality

    [Kem20a] David Kempe. An analysis framework for metric voting based on LP duality. InThe Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, ...

    2020

  4. [1960]

    and of Gö sing, Austria (3–27 July 1962), pages 73–79,

    1962

  5. [1974]

    [CR22] Moses Charikar and Prasanna Ramakrishnan

    Springer Berlin Heidelberg. [CR22] Moses Charikar and Prasanna Ramakrishnan. Metric distortion bounds for random- ized social choice. InProceedings of the 2022 ACM-SIAM Symposium on Discrete Algo- rithms (SODA), pages 2986–3004,

    2022

  6. [1977]

    Krishnaswamy, and Kamesh Munagala

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

    2017

  7. [1980]

    40 1 1𝑝∗ 𝑓3 𝑓1 𝑓2 (a)𝑓 1 and𝑓 3 do not intersect

    A Missing Details from Proof of Lemma 6.3 Claim A.1.If 1 𝑘+1+𝜀≤ 2 𝑘 and𝑘is an integer no less than7, then the minimum𝜆that satisfies 𝑝≤max 𝜆 𝜃(1−𝜃), 𝜆 𝜃 1− 1 𝑘+1 +𝜀 𝑝−𝑘 ,∀𝑝∈[0,1] is 𝜆(𝜃,𝑘,𝜀)= 𝜃 1−𝜃 1 𝜃(𝑘+1) + 𝜀 𝜃 1/𝑘 . 40 1 1𝑝∗ 𝑓3 𝑓1 𝑓2 (a)𝑓 1 and𝑓 3 do not intersect. 1 1𝑝∗ 𝑓3𝑓1 𝑓2 (b)𝑓 1,𝑓 2, and𝑓 3 intersect at the same point. Figure 5: Pictorial illust...

    2000

  8. [1990]

    Improved metric distortion for determin- istic social choice rules

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

    2019

Show all 13 references
  1. [2008]

    On voting and facility location

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

    2016

  2. [2017]

    Compatibility of max and sum objectives for com- mittee selection andk-facility location.CoRR, abs/2507.17063,

    [HA25] Yue Han and Elliot Anshelevich. Compatibility of max and sum objectives for com- mittee selection andk-facility location.CoRR, abs/2507.17063,

    arXiv

  3. [2019]

    Deliberation via matching.CoRR, abs/2511.00986,

    [MYZ25] Kamesh Munagala, Qilin Ye, and Ian Zhang. Deliberation via matching.CoRR, abs/2511.00986,

    arXiv

  4. [2020]

    Communication, distortion, and randomness in metric voting

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

  5. [2025]

    Approximatelydom- inating sets in elections

    [CRW26] MosesCharikar,PrasannaRamakrishnan,andKangningWang. Approximatelydom- inating sets in elections. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),

    2026

Pith tools

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