Optimal distortion of randomized metric voting rules

An ordinal metric voting rule sees voters’ candidate rankings but not their underlying distances. How small can its worst-case expected social-cost ratio, or randomized distortion, be over all finite metric profiles?

Why it matters and what counts as progress

Why it matters: Better upper bounds narrow the gap between implementable ranking-based rules and unavoidable distortion.

What counts as progress: A randomized rule with a rigorously smaller universal ratio, or a stronger lower bound, using the same metric and social-cost model.

How the problem developed

5 Nov 2021 · Lower bound [1]
Moses Charikar and Prasanna Ramakrishnan Disproved the conjectured randomized distortion of 2, establishing lower bounds that approach 2.1126 as the number of candidates grows.
18 Aug 2026 · Upper bound [2]
Fabian Frank Introduced Mixed Integrated Veto with distortion at most 2.5, improving the previous best upper bound of 2.75271.
8 Sept 2026 · Upper bound [3]
Ziyi Cai, Moses Charikar, Jabari Hastings, Prasanna Ramakrishnan, Kangning Wang and Qilin Ye Proved a randomized rule with distortion at most 2.13713, within 0.025 of the known lower bound.

AI contribution

Improving Randomized Metric Distortion to 2.1441

Nisarg Shah

For every finite metric voting profile, Shah’s v2 random-size stable-lottery rule has distortion at most 107200742653/50000000000 = 2.14401485306. This supersedes the v1 mixed-rule bound of 2.3282.

AI involvementAI-led

ImportanceNotable

Technical verificationFormal (exact rational Bernstein-basis polynomial certificate checked by Python standard-library script + human)

Human understandingFull