Improving Randomized Metric Distortion to 2.3282
In metric social choice, voters rank candidates by distance in an unknown metric space, while a randomized voting rule must use only these rankings. The paper introduces random-size stable lotteries and proves that, by mixing a suitably chosen random-size stable lottery with Integrated Veto, one obtains a randomized voting rule with metric distortion at most . This improves the previous best upper bound of . The proof combines infinite-dimensional conic linear-programming duality, heuristic nonlinear optimization, and exact rational verification using polynomial nonnegativity in the Bernstein basis.
- Result
- Proved(see note)
- Status
- Partial result
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Game theory
- Posed by
- —
- Year posed
- —
- Years open
- —
- Solved
- 2026-08-29
- Model
- GPT-5.6 Sol; Claude Opus 5.0
- Vendor
- OpenAI; Anthropic
- Collaborators
- Nisarg Shah
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 18 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
The paper proves that there exists a randomized voting rule using only ordinal rankings with metric distortion at most . This improves the previous best upper bound of and closes about of the gap to the known asymptotic lower bound of approximately . It does not determine the optimal randomized metric distortion: for , the exact optimum and its asymptotic limit remain open.
What the AI did
GPT-5.6 Sol derived all mathematical proofs in the paper from research directions, literature connections, proof and search strategies, and inspiration supplied by Nisarg Shah. It autonomously introduced stable-lottery ingredients, developed progressively stronger bounds, and derived the proofs leading to . Shah then generalized one proposed lottery to random-size stable lotteries, guided the search over distributions, verified all final mathematical details, and rewrote and simplified the exposition with GPT-5.6 Sol and Claude Opus 5.
The disclosure is in the paper itself, not only in this entry: "All the proofs in this document were obtained using GPT-5.6-Sol with guidance from the author."
Verification
Unreviewed. The author states that he verified all final mathematical details; by this site's ladder an author's own check does not move the tier, however expert, and Shah is among the leading researchers on metric distortion. The bound rests, per the abstract, on an exact rational verification via polynomial nonnegativity in the Bernstein basis, which is checkable in principle but has not been re-run here. No referee and no formalization.
Source
- PaperarXiv
Submitted by VibeGene on