Improving Randomized Metric Distortion to 2.3282

arXiv:2608.29308v1 Announce Type: cross Abstract: In metric social choice, each voter ranks a set of m candidates by her distance to them in an unknown metric space. The cost of a candidate is its average distance to the voters. A randomized voting rule must use only the rankings to choose a lottery over candidates. Its distortion is the worst-case ratio between the expected cost under the lottery it returns and the cost of the best candidate. Charikar, Ramakrishnan, Wang, and Wu [JACM 2024] prove an upper bound of 2.753, establishing a constant separation from deterministic rules, for which the best achievable distortion is 3. Independently, Frank [arXiv:2608.17863] and Ye [arXiv:2608.21202] improve the bound to 2.5, using an equal mixture of maximal lottery and Integrated Veto. The existing arguments do not yield a better bound with any mixture of these rules. We break this barrier with a new ingredient, a random-size stable lottery. Let D be a random variable over the domain of positive integers. A random-size stable lottery RSL_D guarantees that the probability of a random voter preferring any fixed candidate c to her favorite of D i.i.d. draws from RSL_D is at most E[1/(D+1)], where the probability also averages over D. When D=k deterministically, this reduces to the stable k-lottery of Charikar, Ramakrishnan, Tan, and Wang [EC 2025]; the case k=1 is precisely a maximal lottery. Their minimax argument for a fixed k easily generalizes to a random D. Our main contribution is to show how stability with respect to a random D can be used to bound distortion. By mixing a suitably chosen random-size stable lottery with Integrated Veto, we get distortion at most 11641/5000=2.3282. The proof combines infinite-dimensional conic linear-programming duality, heuristic nonlinear optimization, and exact rational verification via the Bernstein basis.

Source: arXiv cs.AI | 2026-09-01

Related