PaperlayerView exact revision on arXiv

Source-linked AI summary

Stable Voting Rules on the Edge of Optimal Metric Distortion

Ziyi Cai, Moses Charikar, Jabari Hastings, Prasanna Ramakrishnan, Kangning Wang, Qilin Ye

arXiv:2609.08259v1cs.GT

TL;DR

Social choice theory offers limited guidance on which voting rules are better or where to find promising ones. This paper uses stable lotteries to construct a single-winner randomized rule, achieving distortion at most 2.13713 against a lower bound of 2.11264.

  • Problem

    Classical impossibility results say what voting rules cannot achieve, but offer less guidance on which rules are better or where to find promising ideas.

    Source: §1 · p. 1

  • Method

    The paper adapts stable lotteries from committee selection to choose a single winner by drawing once from their equilibrium distribution.

    Source: §1.1 · p. 4

  • Results

    2.13713 is the distortion upper bound for the randomized voting rule, within a hair of the 2.11264 lower bound.

    Source: §1.1 · p. 4

  • Takeaways & Limitations

    A single cleanly defined distribution, without mixing voting rules, breaks the barrier of 3 and answers a question posed by Charikar et al. (2024).

    Source: §1.1 · p. 4

    The bound leaves a gap between 2.11264 and 2.13713, while the lower-bound election is particular and unnatural.

    Source: §7 · p. 30

Abstract

from arXiv · show

We prove the existence of a randomized voting rule with metric distortion at most $2.13713$, within $0.025$ of the lower bound of $2.11264$. Our rule comes from a generalization of stable $k$-lotteries developed in the context of committee selection. In contrast to prior work, our rule samples from a single distribution derived from a zero-sum game, without mixing between voting rules. Our result also gives sharp distortion bounds for stable $k$-lotteries, and in particular shows that stable $2$-lotteries have distortion $7/3$, despite only relying on aggregate preferences over triples of candidates.

1 Introduction

Metric distortion asks whether ordinal preferences alone can guide a voting rule to a candidate with near-optimal social cost across every consistent metric. The paper generalizes stable lotteries to obtain a randomized rule with distortion at most 2.13713, near the lower bound of 2.11264.

1 Introduction

  • The metric-distortion problem asks for a candidate with approximately optimal average cost using only ordinal preferences, with guarantees over consistent metric spaces.Distortion is the worst-case approximation factor for a voting rule.Source: §1 · p. 2
  • 2.11264 is the lower bound for randomized rules, while prior independent results reached 2.5 by equally mixing a veto-based rule with maximal lotteries.Earlier work had achieved an upper bound of 2.75271 using a different mixture.Source: §1 · p. 3

1.1 Our contributions and technical overview

  • 2.13713 is the distortion upper bound for the paper’s randomized voting rule.The authors place it within a hair of the 2.11264 lower bound.Source: §1.1 · p. 4
  • 7/3 is the tight distortion bound for stable 2- and 3-lotteries, and stable 2-lotteries need only aggregate preferences over candidate triples.The bound has a matching lower bound; a stable 2-lottery is a 3-tournament rule.Source: §1.1 · p. 4
  • The rule uses a single distribution from the g-stable-lottery family rather than mixing voting rules.The family generalizes stable k-lotteries through an activation function g.Source: §1.1 · p. 4
  • A potential function corrects individual voter contributions, while stationarity of g-stable lotteries lets those corrections cancel when averaged over voters.The authors use a computer search over g and an auxiliary function W to choose a distortion bound.Source: §1.1 · p. 5

1.2 Concurrent work

  • Concurrent work reported a 2.3282 bound, then a revised 2.1441 bound for random-size stable lotteries alone.The revised proof parallels the paper’s potential-function analysis.Source: §1.2 · p. 5

2 Preliminaries and notation

The preliminaries set up elections as voter rankings over candidates and define lotteries as distributions over candidates. They describe how rankings and metric distances relate in the distortion framework.

2 Preliminaries and notation

  • An election consists of voters, candidates, and a total ranking of candidates for each voter.The notation uses V for voters and C for candidates.Source: §2 · pp. 5–6
  • A lottery D assigns probability mass to candidates, and a voter’s rank line places candidate intervals in preference order with widths equal to their probability masses.Sampling from D can be represented as a uniform draw on the rank line followed by selecting the candidate whose interval contains it.Source: §2 · p. 6, Figure 2
  • The metric framework uses distances satisfying symmetry and the triangle inequality, with rankings consistent when preferred candidates are no farther from a voter.The passages also introduce social cost and an optimal candidate.Source: §2 · pp. 6–7

3 Voting rules in equilibrium

The section develops voting rules as equilibrium distributions, progressing from maximal lotteries to stable and g-stable lotteries. A suitable g-stable lottery achieves distortion at most 2.13713, while stable k-lotteries have a tight bound of 7/3 for k = 2 and k = 3.

Maximal lotteries

  • A maximal lottery is an equilibrium distribution in the Condorcet game, where two players choose candidates and a random voter selects their favorite.A random candidate drawn from a maximal lottery beats each candidate for a majority of voters in expectation.Source: §3 · pp. 7–8

Stationarity

  • For maximal lotteries, resampling two candidates and returning a random voter’s favorite preserves the distribution.This stationarity property motivates the analogous resampling properties used in the distortion analysis.Source: §3 · p. 8
  • For stable k-lotteries, asking a random voter to choose their favorite among k + 1 independent draws likewise reproduces the original lottery.This extends the corresponding stationarity property of maximal lotteries.Source: §3 · pp. 8–9

g-stable lotteries

  • A g-stable lottery minimizes a minimax objective based on an increasing function g of an attacker’s rank against a lottery.The function g generalizes the rank power r^k used for stable k-lotteries.Source: §3 · p. 10

Stationarity

  • For a g-stable lottery, sampling a voter uniformly and then a rank with density proportional to g reproduces the lottery’s distribution.For g(r) = r^k, this is equivalent to asking a voter to choose their favorite among k + 1 independent draws.Source: §3 · p. 11

g-stable lotteries

  • The broader g-stable family extends from maximal lotteries to stable k-lotteries and allows a continuous range of rank priorities.The choice of g controls how much attention the rule pays to different parts of a voter’s ranking.Source: §3 · pp. 7, 11, 12
  • 2.13713: a g-stable lottery achieves distortion at most this amount in every election for a continuous, non-decreasing g with g(0) = 0 and g(1) = 1.The rule is selected from a general family of g-stable lotteries.Source: §3 · p. 12

4 Biased metrics

The biased metric framework reduces worst-case distortion analysis to a family of metrics parameterized by candidates’ distances to an optimal candidate. A rank-line visualization relates these parameters to a running minimum used in the analysis.

Biased metric framework

  • The biased metric framework reduces worst-case metric distortion analysis to metrics parameterized by candidate distances from an optimal candidate.The transformation fixes distances to the optimum, then minimizes voter-to-optimum distances and maximizes voter-to-other-candidate distances.Source: §4 · p. 12, Figure 3 · p. 13

Distortion characterization

  • The framework characterizes distortion bounds by an equivalent condition over functions ρ assigning zero to an optimal candidate.The theorem states that a distribution has a bound for all consistent metrics if and only if the corresponding condition holds for all such ρ.Source: §4 · p. 14

Rank-line visualization

  • For a voter’s rank line, each candidate occupies an interval of width D(b), with a box of height ρ(b) above it.The resulting function ρv maps each rank to the ρ value of the candidate occupying that rank.Source: §4 · p. 14, Figure 4 · p. 14
  • The shaded area under the running minimum of ρv represents the voter’s contribution to the left side of Equation (11).The figure caption identifies the hatched area under the running minimum as E.Source: §4 · p. 14, Figure 4 · p. 14

5 Warm-up: Distortion of stable k-lotteries

The section bounds distortion for stable k-lotteries and develops a potential-based comparison for analyzing a voter's favorite among k+1 samples. It gives a distortion bound of 7/3 for stable 2- and 3-lotteries.

5 Warm-up: Distortion of stable k-lotteries

  • Stable k-lotteries have distortion at most 1 + 2λ_k; for k=2 and k=3, the bound is 7/3 ≈ 2.333.Theorem 6 gives the general bound; the section identifies the special-case value for k=2 and k=3.Source: §5 · p. 15
  • A voter-specific offset based on an increasing potential can be used because its expected contribution averages to zero across voters under a stable k-lottery.The potential is chosen to depend on ρ and the distribution D, not on an individual voter's preferences.Source: §5 · pp. 16, 18
  • The potential argument first assumes D assigns positive probability to a candidate with ρ=0, then removes this condition by mixing a stable k-lottery with a point mass at the optimal candidate.The zero-ρ support condition arises from the chosen potential; the mixture lets the lemma apply before taking a limit.Source: §5 · pp. 16, 20
  • The proof compares an ordinary draw from D with the voter's favorite among k+1 draws, inserting the sample with the smallest ρ-value as an intermediate candidate.The intermediate candidate shares the sample with the voter's favorite, while its ρ-value can be related to an ordinary draw.Source: §5 · p. 16

6 Generalizing to g-stable lotteries

This section generalizes the stable k-lottery proof to g-stable lotteries, defining rank-based draws and bounding distortion through functions g and W. It formulates an optimization over these functions and presents a heuristic-search pair with a 2.137129167 distortion guarantee, whose constraints are verified using exact arithmetic.

Step 1. Defining the analogues of b, ˆbv, and b for a general g

  • Drawing ranks with density g(r)/τ defines voter-preference and ρ-ordered candidates, while averaging the voter-specific draw recovers D.For g(r) = r^k, τ = 1/(k + 1), recovering the stable k-lottery draws.Source: §6 · pp. 21–22

Step 3. Repeating the calculation that chose Φ

  • For 0 < p < 1, Φ′(t) is well defined because nondecreasing g with g(0) = 0 and g(1) = 1 has a strictly smaller average on [0, p] than on [0, 1], so α(p) > 0.When g(r) = r^k, τ = 1/(k + 1), G(p) = p^(k + 1)/(k + 1), α(p) = τ(1 - p^k), and Φ′(t) = 1/(1 - p^k).Source: §6 · p. 23

Step 4. Comparing ˆbv with b

  • For 0 < p < 1, Lemma 5 bounds K_v(S) by Γ_z(p, q), placing the residual S-interval length at the right of [q, z] to maximize its contribution under nondecreasing g.The resulting bound also gives γ_v(S) ≤ Γ_z(p, q).Source: §6 · pp. 24, 26

Step 5. Putting the bounds together

  • Threshold intervals (q_t, z_t] contain rank r exactly for L_v(r) ≤ t < U_v(r), enabling Tonelli’s theorem to turn a pointwise bound into the general-g analogue of the distortion bound.The construction handles p_t = 0 and p_t = 1 separately before establishing the bound for every t.Source: §6 · pp. 26–28

Step 6. Choosing g and W

  • The passage says a requirement is imposed so that γv(St) ≤ W(zt) − W(qt) also holds in the boundary case pt = 1.Source: §6 · p. 28

6 Generalizing to g-stable lotteries

  • 2.137129167 is the distortion guarantee from a heuristic-search pair (g, W) satisfying Equation (30), with both functions piecewise linear on 385 grid points.Proposition 7 bounds the distortion of every g-stable lottery for pairs satisfying Equation (30).Source: §6 · p. 29
  • Verification checks affine slack at all 385 grid points and certifies the other constraint over tetrahedra using nonnegative degree-three Bernstein coefficients, exact rational arithmetic, and recursive subdivision.On each tetrahedron, the relevant polynomial has degree at most three and is represented by 20 Bernstein coefficients.Source: §6 · pp. 29–30

7 Discussion

The discussion situates g-stable lotteries among voting rules used across several collective-choice settings and highlights the unresolved gap to the randomized distortion lower bound. It identifies reducing randomness and preference information as future directions, and discloses how AI assisted the authors’ work.

7 Discussion

  • Stable lotteries have supported results across distortion, committee selection, and deterministic objectives, and this paper extends that family’s reach to metric distortion.The authors suggest that g-stable lotteries may be worth considering early in new voting problems.Source: §7 · p. 30
  • The remaining gap is between 2.11264 and 2.13713; the authors find it surprising that g-stable lotteries already come so close to the lower bound.They describe the lower-bound election as particular and unnatural, and say they would find an exact match by a natural rule hard to believe if the bound is tight.Source: §7 · p. 30
  • The authors identify reducing randomness and preference information as open directions for metric-distortion research.They note that breaking the barrier of 3 opened questions in both directions.Source: §7 · p. 31

AI Disclosure

  • AI helped prove and simplify the stable-lottery bounds and improve the final search; the authors wrote the final text, with AI assistance in copyediting and figure production.GPT-6 Astra improved the final search from 2.13742 to 2.13713.Source: AI Disclosure · p. 31

A A matching lower bound for stable k-lotteries

For every integer k > 1, the stable k-lottery distortion bound is tight. A symmetric election and a consistent metric provide the matching lower bound.

A A matching lower bound for stable k-lotteries

  • For every integer k > 1, the supremum distortion of stable k-lotteries is exactly 1 + 2λ_k.The constructed election’s distortion approaches this bound as m grows, matching Theorem 6’s upper bound.Source: A A matching lower bound for stable… · pp. 36–37
  • The construction partitions voters into V0 and V1, with every permutation of U equally represented in both groups, and uses D uniform over U.V1 ranks a⋆ between the first m − t and remaining candidates in each permutation.Source: A A matching lower bound for stable… · p. 36
  • The uniform lottery D over U is stable because every candidate is preferred to all k draws with probability 1/(k + 1).The construction makes this probability equal for a⋆ and every candidate in U.Source: A A matching lower bound for stable… · p. 36
  • In the biased metric, a⋆ is optimal, while the uniform lottery over U has higher social cost.Voters in V0 are colocated with a⋆; voters in V1 are at distance 1 from a⋆ and candidates ranked above it, and distance 3 from the rest.Source: A A matching lower bound for stable… · pp. 36–37

B Parameters of a good (g, W) pair

Table 1 gives a good (g, W) pair found by heuristic search, specified on a grid and linearly interpolated between grid points.

B Parameters of a good (g, W) pair

  • Table 1 reports a good (g, W) pair obtained by heuristic search.The pair is specified at 385 grid points, indexed from 0 through 384.Source: Table 1 · p. 38
  • At each grid point i/384, the table sets g(i/384) = A_i/10^12 and W(i/384) = B_i/10^12.Source: Table 1 · p. 38
  • The tabulated g and W values are interpolated linearly between consecutive grid points.Source: Table 1 · p. 38
Loading 2609.08259v1…