Mixed Integrated Veto rule hits record 2.5 metric distortion

In social choice theory, the metric distortion problem asks: given voters and candidates embedded in a metric space, how closely can a voting rule approximate the candidate nearest to the true optimum? The lower the distortion, the better the rule mirrors a perfect social planner. Until now, the tightest known upper bound for randomized rules was 2.75271. Fabian Frank's new paper, posted to arXiv on August 18, 2026, introduces Mixed Integrated Veto (MIV), a randomized social choice rule that slashes that bound to exactly 5/2 (2.5). MIV is the 50/50 mixture of two existing mechanisms: Maximal Lotteries, a well-studied rule that outputs a distribution over candidates based on pairwise majority comparisons, and Integrated Veto, a novel rule derived from the Simultaneous Veto process of Kizilkaya and Kempe.

The key insight lies in how Integrated Veto differs from its predecessor. Instead of simply declaring the candidate who survives longest in a series of veto rounds, Integrated Veto assigns each candidate a probability proportional to its average score across the entire veto process. This smoother aggregation captures more information from each round, which mathematically translates into a tighter distortion bound. The paper proves that MIV's 2.5 distortion holds for any metric space, making it a landmark improvement in computational social choice. Beyond the theoretical milestone, the result has practical implications for designing voting systems and preference aggregation algorithms—especially in contexts like multi-agent planning, recommender systems, and location-based elections where distances naturally matter. It also opens new questions: can the bound be pushed lower, or is 2.5 tight for this family of rules? Frank's work provides both a sharper tool and a fresh direction for future research.