Randomized metric distortion improved to 2.3282
A randomized voting rule built on a new random-size stable lottery achieves metric distortion 2.3282, past a 2.5 barrier that existing arguments could not cross.
- Lab
- Independent
- Model
- GPT-5.6 Sol; Claude Opus 5.0
- Field
- Computer science
- Date
- 2026-08-29
- Human collaborators
- Nisarg Shah
Sources
Original work
Independent commentary
What was found
In metric social choice each voter ranks candidates by distance in an unknown metric space, a candidate's cost is its average distance to voters, and a randomized rule's distortion is the worst-case ratio between the expected cost of its lottery and that of the best candidate. Charikar, Ramakrishnan, Wang and Wu proved an upper bound of 2.753, and Frank and Ye independently improved it to 2.5 using an equal mixture of maximal lottery and Integrated Veto; existing arguments yield nothing better from any mixture of those two rules. The paper breaks that barrier with a new ingredient, a random-size stable lottery, reaching 2.3282.
Novelty check
The baseline chain is named and dated in the paper: 2.753 from Charikar, Ramakrishnan, Wang and Wu in JACM 2024, then 2.5 independently by Frank (arXiv:2608.17863) and Ye (arXiv:2608.21202) weeks before this work. The paper also states why 2.5 was a barrier rather than merely the current best, namely that no mixture of the two rules involved yields a better bound, which is what the new lottery is introduced to get past. No stronger bound appears.
Caveats and known objections
A preprint days old at entry, unrefereed, not formalized, with no independent check on record, and vibemathed records it as a partial result since the optimal distortion remains unknown. Autonomy is graded ai-led on a disclosure that describes the model producing the key ideas under human guidance: all proofs in the document were obtained using GPT-5.6 Sol with guidance from the author, who verified them for correctness and expanded and simplified the exposition with the aid of GPT-5.6 Sol and Claude Opus 5. The author records two specific steps where the model autonomously identified the ingredient to add, first a stable lottery and then a lottery whose existence it proved by a minimax argument.
Also recorded at
vibemathedimproving-randomized-metric-distortion-to-2-3282
Nothing mechanically. It is a parallel listing of the same result, carrying its own verification label rather than an independent check.
Nobody outside the lab has checked this yet.
Reading the primary source closely enough to say whether it supports the claim counts as a check, and you are credited on the entry.
Or on GitHub: submit a check challenge the grade send a correction or send a pull request
Flag this for triage
Signals order the review queue and nothing else. They are never published, and they never move a grade: that takes a citation.
Entry history (1 event)
- AddedEntered the registry graded Author verified and AI-led.
Entries are never deleted. A grade that does not hold up is downgraded on the record, with the reason beside it.
Graded author verified for verification and ai-led for autonomy. What these mean.
Cite this entry
whataifound.org. (2026). Randomized metric distortion improved to 2.3282. whataifound.org: A Registry of AI Scientific and Mathematical Discoveries. https://whataifound.org/finding/2026-08-29-metric-distortion-23282BibTeX
@misc{whataifound-independent-2026-23282,
title = {Randomized metric distortion improved to 2.3282},
author = {{whataifound.org}},
year = {2026},
howpublished = {whataifound.org: A Registry of AI Scientific and Mathematical Discoveries},
note = {Result by Independent. Verification: Author verified. Autonomy: AI-led.},
url = {https://whataifound.org/finding/2026-08-29-metric-distortion-23282}
}