Randomized metric distortion
The smallest distortion achievable by a randomized voting rule that sees only rankings: the worst-case ratio between the expected cost of the lottery it returns and the cost of the best candidate.
- steps
- 2
- by AI
- 1
- since
- 2024
The line is the frontier over time. Filled dots are steps that moved it; muted dots are results that did not. Orange dots are catalog entries, results with AI in the loop. Hollow dots are candidates under review and never move the line. Grey dots along the bottom edge are results from before the quantity had a number, placed there because they have no value on this axis. Dots that would overlap are nudged sideways a few pixels. Hover a dot for its value and attribution.
About this frontier
Voters rank candidates by distance in an unknown metric space, and a rule sees only the rankings. For deterministic rules the best achievable distortion is exactly 3. Randomized rules do better, and how much better was open: the upper bound fell three times in 2026 alone, from 2.753 to 2.5 to 2.3282, against a known lower bound of about 2.1126 that nobody has reached.
Every step, newest first
| Date | Value | Who | Model | Status | Source |
|---|---|---|---|---|---|
| Aug 2026 | Two independent preprints the same month, both by an equal mixture of maximal lottery and Integrated Veto. The existing arguments could not be pushed past this with any mixture of those rules. | Frank, and independently Ye | – | historical | source ↗ |
| 29 Aug 2026 | best Breaks the barrier the previous two ran into, with a random-size stable lottery. Closes about 44% of the remaining gap to the lower bound. | GPT-5.6 Sol and Claude Opus 5.0, with Shah | GPT-5.6 Sol; Claude Opus 5.0 | AI step unreviewed | entry |
| 2024 | JACM 2024. The first constant separation from deterministic rules, which are stuck at exactly 3. | Charikar, Ramakrishnan, Wang and Wu | – | historical | source ↗ |
The values and their attributions are as stated in Shah's paper (arXiv:2608.29308), which names Charikar, Ramakrishnan, Wang and Wu for 2.753 and Frank and Ye independently for 2.5, with links to both preprints. The deterministic bound of 3 is context rather than a row: it is a different class of rule and is exactly achievable, not a record anybody is pushing.
Changelog1 change
- Curatoradded this entry