Improving Randomized Metric Distortion to 2.1441

Nisarg Shah

cs.GTAug 29, 2026

Improving Randomized Metric Distortion to 2.1441

Authors: Nisarg Shah

Organizations: University of Toronto

Abstract

In metric social choice, voters rank candidates by their distances in an unknown metric space. A voting rule uses these rankings to select a candidate or a lottery over candidates, aiming to minimize the average distance to voters. Distortion measures the worst-case approximation ratio. While the best distortion of deterministic rules is $3$ , prior work pins down the best distortion of randomized rules to $[2.1126,2.5]$ . We improve the upper bound to $2.1441$ , closing over $90\%$ of this gap. The proof introduces random-size stable lotteries, proves their existence, and derives the new bound through a potential argument. All the proofs were obtained using GPT-5.6-Sol with significant guidance from the author, who verified them and simplified the exposition.

Figures & tables

Panel of Figure 1 — Figure 1: Two metrics consistent with the reported rankings, which show a lower bound of $3$ for deterministic rules and $2$ for randomized rules.

Upper bounds
$3$	optimal deterministic rule	[ 17 ]
$2.753$	a mixture of maximal lottery and RaDiUS	[ 9 ]
$2.5$	the equal mixture of maximal lottery and Integrated Veto	[ 15 , 34 ]
$2.1441$	a random-size stable lottery rule	this paper
Lower bounds
$2.0631$	an example with $m=7$	[ 32 ]

Table 1: Randomized metric distortion bounds from our work and prior work.

Panel of Figure 2 — Figure 2: The $P$ -mass arranged from voter $v$ ’s least- to most-preferred candidate.

Panel of Figure 3 — Figure 3: The example continues Figure 2 . At the threshold shown, $H(t)=\left\{c_{5},c_{4}\right\}$ , so the marked probability is $p(t)=P(c_{5})+P(c_{4})$ . The scan for voter $v$ passes $c_{5}$ and stops at the unmarked candidate $c_{2}$ , giving the lower cutoff $a_{v}(t)=P(c_{5})$ . The displayed upper cutoff $A_{v}(t)$ is deliberately nonminimal: it lies to the right of both marked blocks. Panel (b) keeps the forced interval $[0,a]$ and moves the remaining marked length $p-a$ as far right as the upper cutoff $A$ permits.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Check in the proof	Checker routine	Polynomial in the checker
The probabilities are positive and sum to one, and the distortion bound is $1+2C_{0}$	exact_parameter_checks	probability_mass_identity and its reverse, probability_0_positive through probability_3_positive , and distortion_identity and its reverse
$\phi(t_{0})<\mu$ and $\phi^{\prime}(t_{0})>1-\mu$	threshold_checks	activation_below_mean and threshold_derivative
Equation 5.2 on $[0,t_{0}]$	boundary_inequality	boundary_polynomial
Monotonicity of the second branch of $W$ on $[t_{0},1]$	potential_monotonicity	potential_derivative , a direct polynomial check of the conclusion also obtained from convexity in Verification 3
$a\leqslant p\leqslant t_{0}\leqslant A$	internal_cell_001	cell_001
$a\leqslant t_{0}\leqslant p\leqslant A$	internal_cell_011	cell_011

Appendix

Table 5

Social Choice Theory

Social choice theory studies how individual preferences can be combined into collective decisions, fair allocations, and representative outcomes.

See all 52 papers

Metric Distortion of Social Welfare Functions
Aug 22, 2026Fatih Erdem Kizilkaya, Aaryaman Aggarwal, Evi MichaSocial Choice Theory Rank Aggregation
University of Southern California · Indian Institute of Technology Kanpur
Tree Plurality Veto: Voting in Few Rounds with Efficient Communication and Low Metric Distortion
Oct 17, 2026Gabriel Chen, Yu Cheng, Alice WangSocial Choice Theory Communication Complexity
Brown University.
Smooth Partial Lotteries for Stable Randomized Selection
May 19, 2026Alexander Goldberg, Giulia Fanti, Nihar B. ShahAlgorithmic Stability Algorithmic Fairness
Carnegie Mellon University

Aug 22, 2026J/K move · Enter open · S save

Metric Distortion of Social Welfare Functions

Fatih Erdem Kizilkaya, Aaryaman Aggarwal, Evi Micha

University of Southern California · Indian Institute of Technology Kanpur

Social Choice Theory Rank Aggregation

Open paper AskPDF arXiv

Metric distortion has primarily been studied for social choice functions, which select a single winner from ordinal preferences. We extend this framework to social welfare functions, which output a ranking of

m

candidates. We associate each voter

v

with a monotone weight vector

\mathbf{w}_v = (w_{v1},\ldots,w_{vm})

, specifying the importance of the

i

-th position for voter

v

, and define the cost of a ranking as the position-weighted sum of their distances to the ranked candidates. This model generalizes both single-winner voting and committee selection. We consider three information regimes. First, we study the setting where the positional weight vectors are known. A natural approach recursively applies a single-winner rule with distortion

β

to construct the ranking one position at a time. We show that this yields distortion at most

3β

in general. This gap is not merely an artifact of the analysis: we show that no analysis based solely on per-round guarantees can certify a bound better than

2β

. By exploiting structural properties specific to Fractional Veto of Kizilkaya and Kempe, we show that its recursive extension achieves the optimal distortion of 3. Second, when all voters share the same unknown weight vector, recursively applying any social choice function with distortion

β

achieves distortion at most

1+(β-1)\text{range}(\mathbf{w})

, where

\text{range}(\mathbf{w})=(w_1-w_m)/w_1

denotes the normalized range of the common weight vector

\mathbf{w}

. Finally, we study unknown heterogeneous weights. Without further assumptions, every rule has unbounded distortion. We therefore consider two natural normalizations: unit-sum, where each voter distributes one unit of value across the ranking, and unit-top, where every voter assigns unit value to the first position. Under both models, we show that the optimal distortion is

Θ(m)

Abstract

Social Choice Theory

Explore similar work

Metric Distortion of Social Welfare Functions

Tree Plurality Veto: Voting in Few Rounds with Efficient Communication and Low Metric Distortion

Smooth Partial Lotteries for Stable Randomized Selection