Source-linked AI summary
Robust Lottery Compression for Metric Voting: A Transfer Principle for Bounded Randomness
Jianhao Jia, Bo Peng
TL;DR
The paper studies whether bounded-randomness voting can match strong welfare guarantees despite using only short, uniform candidate lists. It develops a robustness-based compression method and a robustification step for Mixed Integrated Veto. The resulting rules approach distortion 5/2 with O(ε−3) entries, while 164 entries already achieve distortion below 3.
Problem
The paper asks whether bounded randomness can preserve the substantially stronger guarantees of unrestricted randomized voting, rather than only crossing the deterministic distortion barrier.
Method
The paper compresses lotteries whose supported candidates have bounded deterministic distortion and robustifies Mixed Integrated Veto before applying compression.
Results
O(ε−3) entries suffice for distortion 5/2 + ε, and 164 entries suffice for distortion strictly below 3.
Takeaways & Limitations
Bounded randomness approaches the current best unrestricted upper benchmark 5/2 with list size independent of the numbers of voters and candidates.
Takeaways & Limitations
The result does not establish equality between bounded and unrestricted optimal distortion, and direct compression requires control of supported candidates’ deterministic distortion.
Abstract
from arXiv · showhide
We study metric distortion in randomized social choice under bounded randomness: on every preference profile, the voting rule must deterministically identify a multiset of $K$ candidates and then select a uniformly random entry. Previous work showed that this restricted model can beat the optimal deterministic distortion of $3$. We show that it can in fact approach the current best unrestricted upper benchmark of $5/2$. For every integer $K\ge 802$, there exists a bounded-randomness rule with distortion at most $\frac{5}{2} +3\left(\fracπ{8K}\right)^{1/3} +2\sqrt{\fracπ{8K}}$. Consequently, $O(\varepsilon^{-3})$ entries suffice for distortion $5/2+\varepsilon$, independently of the numbers of voters and candidates. We also show that $164$ entries already achieve distortion strictly below $3$, giving $2\le N^\star\le 164$ for the minimum list size needed to break the deterministic barrier. Our main technical contribution is a dimension-free compression theorem: if a lottery has distortion at most $ρ$ and every candidate in its support has deterministic distortion at most $H$, then it admits a uniform $K$-entry approximation with distortion at most $ρ+(H+1)\sqrt{π/(8K)}$. Thus, lotteries whose possible outcomes are already well behaved incur only $O(K^{-1/2})$ compression loss. Mixed Integrated Veto does not satisfy this support condition, so we first remove early-eliminated outcomes, trading $O(τ^2)$ distortion loss for an $O(1/τ)$ bound on the deterministic distortion of every supported candidate. Balancing this repair cost against compression yields the $O(K^{-1/3})$ convergence rate.
1 Introduction
The paper asks whether short, uniform candidate lists can retain randomized voting’s welfare advantages. It proves that bounded randomness approaches distortion 5/2, while 164 entries already suffice to beat distortion 3.
- Model: Bounded randomness represents a lottery by a deterministically identified K-entry multiset and uniformly selects one entry, independently of voter and candidate counts.Repetitions encode unequal probabilities through multiplicity.
- Motivation: Randomized voting can improve on the optimal deterministic distortion of 3, but short uniform lists may constrain supported outcomes and probabilities.The paper frames whether this simplicity is compatible with the strongest known randomized guarantees.
- Compression principle: The compression theorem converts a low-distortion lottery with uniformly bounded supported-candidate distortion into a uniform K-entry lottery with O(K−1/2) loss.Its bound is independent of the numbers of voters and candidates.
- Robustification: Mixed Integrated Veto requires robustification before compression because its support can contain candidates of arbitrarily large deterministic distortion.The repair incurs O(τ^2) loss and yields the O(K−1/3) rate.
- Finite lists: 164 entries suffice for distortion strictly below 3, establishing 2 ≤ N⋆ ≤164 without resolving whether N⋆ =2.The same repeated-entry interpretation transfers the result to committee selection, but not directly to distinct-member committees.
2 Preliminaries
This section defines metric distortion and introduces Maximal Lotteries and Integrated Veto as ingredients in randomized voting and compression analysis.
- A preference profile consists of voters’ strict rankings over candidates, while a lottery is a probability distribution over candidates.
- Metric distortion compares a rule’s expected social cost with the minimum social cost over all metrics consistent with the observed rankings.
- Proposition 2.1 converts subset-based loss inequalities into a distortion guarantee of at most 1 + 2λ.
- A Maximal Lottery is an equilibrium strategy of the symmetric zero-sum Condorcet game.
- Every candidate supported by a Maximal Lottery has deterministic metric distortion bounded by 4 + .
- Integrated Veto continuously removes candidates through voter vetoes, with each candidate’s score decreasing at its veto rate until elimination.
3 Robustifying Mixed Integrated Veto
The paper robustifies Mixed Integrated Veto by deleting early-eliminated outcomes, obtaining bounded support distortion while controlling the removed probability mass.
- Integrated Veto may assign positive probability to candidates with unbounded deterministic distortion, preventing direct uniform-support compression.
- Candidates surviving until time τ have deterministic metric distortion at most 1 + 2/τ.
- τ^2 is an upper bound on the Integrated-Veto probability assigned to candidates eliminated before threshold time τ.
- The repaired source lottery retains surviving Integrated-Veto mass and combines it with a full Maximal Lottery before normalization.
- The support of the repaired lottery is bounded using the surviving Integrated-Veto candidates and the Maximal Lottery’s support guarantee.
- Direct empirical sampling from Mixed Integrated Veto cannot be justified by a uniform support bound.
4 Uniform-support compression for robust lotteries
The section develops a reusable compression theorem for robust lotteries and applies it conditionally to bounded-randomness voting rules. Direct compression loses O(K^-1/2), while robustifying lotteries with poor support guarantees yields the slower O(K^-1/3) rate.
- Compression construction: A K-element multiset sampled from a lottery’s support can approximate its one-sided prefix probabilities with controlled discrepancy.The construction samples candidates independently with replacement and uses the interval representation and one-sided Kolmogorov–Smirnov statistic.
- Compression construction: Lemma 4.2 gives a finite-sample K-entry approximation whose prefix-length error is bounded uniformly over every nonempty proper candidate subset.The resulting uniform lottery is supported on the original lottery’s support.
- Uniform-support compression: If a source lottery has distortion at most ρ and every supported candidate has deterministic distortion at most H, prefix discrepancy δ increases distortion by at most (H+1)δ.The support-wise bound limits the threshold range over which certificate error can accumulate.
- Uniform-support compression: Theorem 4.4 provides uniform K-entry approximations with compression loss O(K^-1/2) for fixed H, independently of the numbers of voters and candidates.The theorem also includes a sharper finite-sample bound based on the exact expectation from Lemma 4.2.
- Transfer principle: Corollary 4.5 transfers robust lottery guarantees to deterministic bounded-randomness rules by selecting a qualifying multiset under fixed tie-breaking.The required list size depends on the target accuracy rather than the profile dimensions.
- Transfer principle: Direct compression preserves the 2.75271 benchmark with O(ε^-2) list entries, whereas robustifying Mixed Integrated Veto before compression yields the O(K^-1/3) exponent.The slower rate comes from an O(τ^2) robustification loss and an O(1/τ) support-wise distortion bound, not from the compression theorem itself.
5 Proof of the main theorems
The proofs combine robustification, uniform-support compression, and exact finite-sample estimates to establish the main bounded-randomness guarantees. They also give an explicit 164-entry construction below distortion 3 and polynomial-time computability for fixed accuracy.
- Main theorem: The main parameter choice yields distortion at most 5/2 + ε, with the resulting list-size bound scaling as O(ε^-3).The algebra uses τ to balance robustification and compression terms.
- Main theorem: Theorem 5.1 combines the robustified source lottery with Uniform-Support Compression to bound distortion for every τ ∈ (0,1] and positive integer K.The multiset is deterministically identified for each preference profile.
- Computational aspects: For every fixed ε, the rule can be computed in |C|^O(K) poly(|V|,|C|) time by enumerating K-element multisets.Maximal Lottery computation uses linear programming, and the Integrated Veto trajectory has at most |C| phases.
- The list size 164: Smirnov’s exact finite-sample expectation supplies the numerical estimate needed for the explicit 164-entry bound.The estimate is obtained by integrating the exact tail formula and evaluating the resulting finite rational sum.
- The list size 164: A uniformly random entry from a deterministically identified 164-element multiset has distortion strictly below 3, implying 2 ≤ N⋆ ≤ 164.The comparison is exact and does not require floating-point approximation.
6 Discussion
The discussion identifies support-wise robustness as the condition enabling benchmark-preserving compression and distinguishes finite-list separation from asymptotic optimality. It also records open questions about list sizes, constructions, and committee extensions.
- Discussion: Support-wise deterministic distortion is the key condition for compressing a lottery while preserving its benchmark up to O(K^-1/2).This gives 2.75271 + O(K^-1/2) for the rule of Charikar et al.
- Discussion: Mixed Integrated Veto lacks this condition, so truncation incurs O(τ^2) distortion loss and produces an O(1/τ) support bound.Balancing the repair and compression terms yields 5/2 + O(K^-1/3), or O(ε^-3) entries for distortion 5/2 + ε.
- Discussion: The results imply ρ_BR ≤ 5/2 but do not establish equality with the unrestricted optimum, which may be below 5/2.The discussion separates the smallest list beating 3, benchmark-preservation rates, and asymptotically optimal bounded-randomness distortion.
- Open questions: Open questions include whether N⋆ = 2, whether a fixed finite list reaches 5/2, and whether more efficient constructions or distinct-winner committee guarantees exist.The current committee interpretation applies to repeated seats, not directly to committees whose members must be distinct.
AI-Use Disclosure
The paper discloses that ChatGPT helped explore the robustification idea and assisted with proof exposition, while the authors developed, formalized, verified, and assumed responsibility for the mathematics.
- Authorship and novelty: The authors state that the Uniform-Support Compression Theorem and its application to the 2.75271 rule were developed by them.The disclosure attributes the central contribution and direct application to the authors.
- AI assistance: ChatGPT suggested first robustifying the source lottery by removing poorly guaranteed outcomes before compression.The authors subsequently developed, formalized, and verified the resulting construction and analysis.
- AI assistance: ChatGPT also assisted with organizing arguments and drafting and revising proof exposition, while the authors independently checked all mathematical content.The authors take full responsibility for the paper’s content.