PaperlayerView exact revision on arXiv

Source-linked AI summary

Improving Randomized Metric Distortion to 2.3282

Nisarg Shah

arXiv:2608.29308v1cs.GTcs.AI

TL;DR

For m ⩾4 candidates, the optimal randomized metric distortion remains open. This work abstracts voter profiles into an infinite-dimensional linear program and proves a randomized voting rule with distortion at most 11641/5000 = 2.3282.

  • Problem

    For m ⩾4 candidates, determining the optimal randomized metric distortion remains open, including whether its limit equals the asymptotic lower bound 2.1126.

  • Method

    The analysis abstracts the profile into an infinite-dimensional linear program and verifies candidate dual feasibility using rational arithmetic after heuristic numerical searches.

  • Results

    11641/5000 = 2.3282 is the proven upper bound for randomized metric distortion.

  • Takeaways & Limitations

    The 2.3282 bound improves the preceding 2.4924 bound obtained using a mixture of (IV + ML)/2 and SL2.

  • Takeaways & Limitations

    The analysis relies on a sufficient, rather than necessary, condition and uses heuristic searches and grid-based checks requiring separate exact verification.

Abstract

from arXiv · show

In metric social choice, each voter ranks a set of $m$ candidates by her distance to them in an unknown metric space. The cost of a candidate is its average distance to the voters. A randomized voting rule must use only the rankings to choose a lottery over candidates. Its distortion is the worst-case ratio between the expected cost under the lottery it returns and the cost of the best candidate. Charikar, Ramakrishnan, Wang, and Wu [JACM 2024] prove an upper bound of $2.753$, establishing a constant separation from deterministic rules, for which the best achievable distortion is $3$. Independently, Frank [arXiv:2608.17863] and Ye [arXiv:2608.21202] improve the bound to $2.5$, using an equal mixture of maximal lottery and Integrated Veto. The existing arguments do not yield a better bound with any mixture of these rules. We break this barrier with a new ingredient, a random-size stable lottery. Let $D$ be a random variable over the domain of positive integers. A random-size stable lottery $\mathrm{RSL}_D$ guarantees that the probability of a random voter preferring any fixed candidate $c$ to her favorite of $D$ i.i.d. draws from $\mathrm{RSL}_D$ is at most $\mathbb{E}[1/(D+1)]$, where the probability also averages over $D$. When $D=k$ deterministically, this reduces to the stable $k$-lottery of Charikar, Ramakrishnan, Tan, and Wang [EC 2025]; the case $k=1$ is precisely a maximal lottery. Their minimax argument for a fixed $k$ easily generalizes to a random $D$. Our main contribution is to show how stability with respect to a random $D$ can be used to bound distortion. By mixing a suitably chosen random-size stable lottery with Integrated Veto, we get distortion at most $11641/5000=2.3282$. The proof combines infinite-dimensional conic linear-programming duality, heuristic nonlinear optimization, and exact rational verification via the Bernstein basis.

1 Introduction

Metric social choice seeks ranking-only voting rules that minimize worst-case distortion, with randomized rules improving on the deterministic barrier of 3. This work introduces random-size stable lotteries and combines one with Integrated Veto to achieve distortion 2.3282.

  • 1 Introduction: Metric distortion compares a rule’s expected social cost with the minimum candidate cost over all consistent metrics.Voters and candidates occupy a common metric space, but the rule observes only voter rankings.
  • 1 Introduction: 2.5 was the previous upper bound, obtained by equally mixing maximal lottery and Integrated Veto, but reweighting these rules cannot improve the existing analysis.Their equal mixture reaches loss ratio 3/4 at q = 1/2 and q = 1, and shifting the weight raises one of those values.
  • 1 Introduction: 2.3282 is the achieved distortion bound: mixing Integrated Veto with a distribution D⋆ supported on 1, 12, and 13 cancels opposing loss-bound slopes.The mixture keeps the loss ratio at most 0.6641, and Proposition 1 converts this to 1 + 2(0.6641) = 2.3282.
  • 1 Introduction: Random-size stable lotteries generalize stable k-lotteries by drawing the number of lottery samples from a positive-integer-valued random variable D.When D = k deterministically, the construction recovers SLk; D must be realized after one lottery is chosen, rather than by mixing separately chosen SLk lotteries.
  • 1 Introduction: The rule’s key guarantee bounds the probability that a random voter prefers any fixed candidate to her favorite among D independent draws by E[1/(D+1)].Tie-breaking is essential when draws equal the reference candidate, requiring integration over the random label.

2 Preliminaries

This section formalizes metric distortion and introduces Integrated Veto and maximal lotteries as the ingredients behind the previous 2.5 bound. It also explains why mixtures of these rules cannot improve that bound.

  • Metric social choice: Metric distortion compares a lottery’s expected social cost with the minimum candidate cost over metrics consistent with voters’ rankings.Randomized rules see only rankings, while voter costs arise from distances in a common metric space.
  • Candidate-set analysis: A lottery satisfying ℓ(P, I) ≤ κq(I) for every nonempty proper candidate subset guarantees distortion at most 1 + 2κ.The quantities q(I) and ℓ(P, I) reduce the metric analysis to ranking-based inequalities.
  • Integrated Veto: Integrated Veto assigns each candidate twice the area under its score trajectory, with score changes when exhausted candidates cause voters to switch veto targets.The normalization follows because the total score is 1 − t and its area over time is 1/2.
  • Integrated Veto and maximal lotteries: 2.5 is obtained by equally mixing Integrated Veto and maximal lottery, using ℓ(IV, I) ≤ q(I)^2 and ℓ(ML, I) ≤ min {q(I), 1/2}.Both unequal mixtures and the existing analysis fail to improve the 2.5 guarantee.

3 Random-Size Stable Lotteries

This section defines random-size stable lotteries by randomizing the number of independent draws in the stability comparison. It proves existence for every positive-integer draw distribution and recovers maximal lotteries and stable k-lotteries as special cases.

  • Definition and motivation: Random-size stable lotteries extend stable k-lotteries by choosing the number of independent draws from a positive-integer-valued random variable D.The construction is proved directly rather than by mixing separately chosen stable k-lotteries.
  • Computation and limitation: Random-size stable lotteries can be approximated with a standard multiplicative-weights algorithm, while averaging stable k-lotteries fails because mixture draws create uncontrolled cross terms.The approximation guarantee is deferred to the appendix, and the cross-term obstruction is demonstrated there.
  • Random sample size: The random draw count is represented by the probability-generating function ϕ(t) = E[t^D], with ∫_0^1 ϕ(t)dt = E[1/(D + 1)].Random-label tie-breaking corrects the comparison when the challenger and sampled lottery can draw the same candidate.
  • Special cases: For D = 1, random-size stability is precisely maximal-lottery stability; deterministic D = k recovers stable k-lotteries.The generalization preserves these established special cases.
  • Existence: For every finite preference profile and every distribution D, a random-size stable lottery exists and satisfies the stability inequality for every challenger.The proof extends the fixed-size minimax argument using convexity and exchangeability.

4 From Random-Size Stability to Loss Ratio

This section converts random-size stability into a profile-independent optimization problem that upper-bounds loss on every candidate subset. The resulting program captures the distribution of D through its full probability-generating function.

  • Reduction to loss: The analysis seeks to bound ℓ(RSL_D, I) using only the draw distribution D and q(I), thereby abstracting away the rest of the preference profile.This reduction is designed for use with the distortion implication based on loss ratios.
  • Infinite-dimensional program: Lemma 2 represents every profile by a scalar x and probability measures η and ξ, then maximizes the resulting loss over all feasible triples.The measures encode voter-level comparisons inside and outside the candidate subset I.
  • Stability constraints: The constraints arise from applying random-size stability to a representative candidate in I, to the inside lottery, and to the reversed comparison.The resulting conditions are labeled (C1)–(C3).
  • Direct upper bound: The loss is bounded by (1 − p_D)x, where p_D = E[1/(D + 1)], yielding constraint (C3).This bound follows by combining reverse comparison with the decomposition of RSL_D across I and its complement.
  • Linear-program formulation: Fixing x makes the objective and constraints linear in η and ξ, allowing a linear program over probability measures; relaxing profile realizability preserves an upper bound.The relaxed program may include measure pairs that do not arise from any preference profile.

5 A Rule with Distortion at Most 2.3282

The section establishes a certified loss bound for a selected random-size stable lottery and combines it with Integrated Veto to obtain metric distortion at most 2.3282.

  • Certification: 49 parametric dual tuples and 50 candidate bounds are used to certify feasibility across the relevant (q, x) domain.The verification reduces to polynomial nonnegativity checks over one- or two-variable domains.
  • Loss bound: gD⋆(q) ⩽ q(a − bq) for all q ∈[0, 1], yielding ℓ(RSLD⋆, I) ⩽ q(I) · (a − b · q(I)).This bound holds for every profile, every random-size stable lottery RSLD⋆, and every nonempty proper I ⊊ C.
  • Mixing rules: The target form T(q) = q(a − bq) makes the RSLD⋆ loss-ratio bound linearly decreasing in q(I).Integrated Veto supplies a linearly increasing bound, allowing the two slopes to cancel when the rules are mixed.
  • Certification: The proof uses heuristic numerical search to identify candidates, followed by exact rational verification of the final dual certificates.The search itself is not exact and uses nonlinear separation, numerical LP solving, and a grid over (q, x).

6 Discussion

The discussion places the 2.3282 result within an ongoing search for optimal randomized metric distortion and identifies unresolved limitations in the rule, distribution, and analysis.

  • Remaining avenues: The draw-distribution search suggests that alternatives to D⋆ may yield only modest improvement, but this conclusion depends on a conjectured bimodal support structure.Among support size four, the best identified distribution placed positive mass only on 1, 12, and 13.
  • Remaining avenues: The analysis relies on Proposition 1 as a sufficient but not necessary condition, leaving room for a stronger joint analysis of Integrated Veto and random-size stable lotteries.The discussion also considers tighter loss envelopes and retaining more profile constraints.
  • Remaining avenues: It remains unknown whether mixtures of Integrated Veto, maximal lottery, and random-size stable lotteries can reach optimal distortion or require a fundamentally new rule.The known lower bound is approximately 2.1126.
  • Open problem: For m ⩾ 4 candidates, the optimal randomized metric distortion remains open, including whether its limit equals the asymptotic lower bound 2.1126.The paper therefore does not settle the gap between its upper bound and the known lower bound.
  • Autonomous search: The bound improved from 2.4924 with stable 2-lottery to 2.4662 after unequal weighting of Integrated Veto and maximal lottery.A subsequent generalization to random-size stable lotteries culminated in the 2.3282 bound.
  • Verification scope: The authors manually verified only the final bound and its corresponding mathematical claims, not all intermediate results.The intermediate improvements arose through a rapid autonomous search process.

AI Disclosure

The appendix contrasts random-size stability with related committee lotteries and shows, through an example, why separately stable lotteries cannot simply be mixed. It also discloses AI assistance while retaining author responsibility.

  • The authors state that OpenAI Codex and Claude Opus 5 aided the proofs and exposition, while the author verified the mathematics and retains responsibility for errors.
  • Random-size stability differs from stable lotteries over committees because its committees use independent draws from one lottery and compare voters’ favorite members.
  • For D uniform on {1, 2}, the averaged lottery violates the target bound: 21/50 > 5/12 = E[1/(D + 1)].The failure arises from cross terms created by repeated draws from the mixture; choosing P_D after observing D is a different requirement.

A.2 Computing a random-size stable lottery

This appendix develops computation and consequences for random-size stable lotteries, including an iterative approximation algorithm, bounds for repeated draws, and support reduction. The guarantees extend to infinite-support D when expectations can be evaluated sufficiently accurately.

  • For finite-support D, Proposition 2 gives a computable lottery satisfying the random-size stability guarantee for every positive integer N.The procedure uses multiplicative weights with the comparison quantities g_t,c = E_D Pr_v[c ≻_v P_D].
  • The algorithm runs in O(Nnms log(dmax + 1)) arithmetic operations and exponential evaluations, obtaining additive error ε in O(nms log(dmax + 1) log(m)/ε^2) time.
  • For infinite-support D, the iteration guarantee remains valid when required expectations are evaluated to sufficient precision, but runtime depends on evaluation cost.
  • Theorem 3 bounds the probability that an independent R-draw lottery B beats the random-size stable lottery, with deterministic R = r yielding 1 − (1 − E[1/(D + 1)])^r.
  • Random-size stable lotteries admit approximation by lotteries supported on at most s candidates, although the resulting additive error is too coarse for the main distortion proof.

A.3 A calculation with cumulative distributions

The appendix uses cumulative-distribution identities to relate committees formed from A and P, then derives probability bounds and a finite-support approximation result for random-size stable lotteries.

  • The cumulative-distribution calculation uses uniformity of the transformed variable Y conditional on every voter and an identity whose equality case is A = P.
  • For each integer d, the committee comparisons satisfy Pr_v[A ≻_v P^d] = E[U^d] and Pr_v[A^d ≻_v P] = d E[U Y^(d−1)].The identities use a voter-specific cumulative-distribution representation and the density of the best of d independent A-draws.
  • Lemma 7 relates the averaged probabilities of A defeating P^D and A^D defeating P through the distribution of D.The formulas are obtained by summing the fixed-d identities over D.
  • If E_D Pr_v[A ≻_v P_D] ≤ E[1/(D + 1)], then E_D Pr_v[A^D ≻_v P] ≤ 1 − E[1/(D + 1)], and the inequality extends to arbitrary D by truncation.
  • Sampling s candidates from RSL_D and applying the Dvoretzky–Kiefer–Wolfowitz inequality yields an empirical lottery with support at most s that simultaneously controls all candidates.The same sampled candidates are used for every voter, and the common cumulative-distribution error avoids a factor depending on |C|.

A.6 An extension to signed coefficients

The signed-coefficient extension characterizes a threshold for weighted candidate comparisons, but signed coefficients fall outside the probability and convexity conditions used for the distortion results. The appendix also documents the exact dual verification framework.

  • A.6 An extension to signed coefficients: Every finite profile admits a lottery whose maximum weighted comparison is bounded by the integral threshold, and this threshold is exact.For every lottery, some candidate attains at least the threshold in the maximum comparison.
  • A.6 An extension to signed coefficients: The proof uses continuity, an exchangeability identity, and a fixed point of the correspondence mapping lotteries to lotteries supported on maximizing candidates.
  • A.6 An extension to signed coefficients: Signed coefficients do not define probabilities and may destroy convexity, so the minimax proof and the union-bound consequences used for distortion do not apply.The distortion results therefore use nonnegative coefficients summing to one.
  • B.2 Exact Dual Families and Candidate Bounds: The exact verification constructs 49 parametrized dual solutions and checks 50 candidate bounds across the relevant continuous domain.The candidate families and bounds are recorded in Tables 3 and 4, with feasibility restricted to stated x ranges.
  • B.2 Exact Dual Families and Candidate Bounds: The verification uses the D⋆-specific functions and handles endpoint feasibility separately before covering every relevant (q, x) with candidate bounds.

B.3 Exact Polynomials for Dual Feasibility

This section constructs parametrized dual tuples and verifies their feasibility by reducing pointwise inequalities to polynomial nonnegativity on specified domains.

  • The exact-polynomial setup represents rational expressions as numerator-denominator pairs with positive denominators on relative interiors.This convention provides an implicit specification of the polynomials checked by the program.
  • Dual families 1 and 2: Dual families 1 and 2 use domains X_j = [x_j, 1] × [0, 1] and six polynomial families whose nonnegativity is verified on those domains.The construction sets x_1 = 0, x_2 = 1/5, and a_1 = 423239/106.
  • Dual family 3: For dual family 3, sign conditions imply λ_3 ⩾ 0 and µ_3 > 0, reducing the first inequality to endpoint checks and the second to convexity.The second pointwise difference vanishes at b_1 = 0 and has nonnegative derivative there.
  • Dual families 4–49: For families 4–49, nonnegative polynomial conditions imply S_j(x) ⩾ 1 and 0 < θ_j(x) ⩽ 1, establishing both pointwise inequalities by convexity.At x = 1, feasibility follows from the limiting tuple and the tangent-line inequality for the convex polynomial f.

B.4 Polynomial Verification and Proof of Lemma 5

The proof of Lemma 5 certifies a global loss bound by covering the relevant state space with polynomial inequalities and verifying feasible dual upper bounds exactly.

  • 44 polynomial gaps convert candidate dual upper bounds into polynomial nonnegativity conditions with rational coefficients.The displayed factors serve as positive common denominators on the interiors where the corresponding tuples are used.
  • The Bernstein-basis test proves nonnegativity because each basis function is nonnegative and the polynomial is a convex combination of its coefficients.The coefficients are computed using exact rational arithmetic.
  • A finite disjunction is verified recursively: accepted boxes have one eligible polynomial with nonnegative Bernstein coefficients, while unresolved boxes are subdivided at rational midpoints.The procedure is sufficient for accepted boxes but is not guaranteed to terminate.
  • For every relevant (q, x), either the direct bound (1 − p)x ⩽ T(q) holds or an eligible feasible dual tuple satisfies U(q, x; z_j) ⩽ T(q).This establishes the sufficient condition in Lemma 4, and the loss bound then follows from Lemma 2.
  • Discretized finite LP values generally underestimate the exact infinite-dimensional program, so numerical dual tuples do not certify the original constraints without full pointwise verification.Restricting measures and omitting dual constraints both can decrease the discretized common value.

B.6 Numerical Search and Rationalization

The numerical search identifies candidate lottery distributions, active dual patterns, and mixture parameters, while exact rationalization—not numerical proximity—supplies the proof guarantee.

  • The numerical objective is an estimate rather than an upper bound, and heuristic failure to find violations does not prove dual feasibility.Floating-point tolerances can also leave returned tuples slightly infeasible.
  • The optimized mixture assigned β = 0, so the remaining constraints combine Integrated Veto and the random-size stable lottery.The endpoint constraints include β + γΛ_D ⩽ Ccut and α + β/2 + γρ_D ⩽ Ccut.
  • The search optimized probability masses continuously over selected finite supports of positive integer degrees, including supports containing degree 1.The masses were parameterized by normalized unconstrained log ratios and optimized with differential_evolution.
  • From numerical dual solutions to explicit tuples: Numerical dual solutions revealed active constraints that were converted into explicit rational dual families z_1 through z_49.The families arise from endpoint, tangency, and interior active-state conditions.
  • From numerical dual solutions to explicit tuples: 49 rational active values t = 15/100, 16/100, …, 60/100 generate z_4, z_5, …, z_49, but only the exact coverage proof establishes sufficiency.The numerical pattern itself is not the proof.
  • Rationalization: The best candidate used an Integrated Veto weight of approximately 0.1588198 and was replaced by rational probabilities, mixture weight, active value, and tangency points.The resulting rational target came from the outer LP relations a = Ccut/γ and b = α/γ.

B.7 Reproducing the Computer-Assisted Checks

The computer-assisted checks are reproducible from the repository using an exact verifier that reconstructs the proof polynomials and confirms all required nonnegativity conditions.

  • The repository contains the README, exact verifier, checked-in rational candidate, and numerical search code.The verifier uses only the Python standard library.
  • The verifier can run with the built-in candidate or with the checked-in candidate.json file.Both commands invoke verify_distortion.py.
  • All polynomial nonnegativity checks passed.
  • Successful completion verifies dual feasibility on the stated domains and that an eligible bound applies at every relevant (q, x).The numerical discovery output becomes part of the proof only after exact verification of the rationalized candidate.
Loading 2608.29308v1…