CS Paper Radar

Computational Aspects of Distortion

Soroush Ebadian, Aris Filos-Ratsikas, Mohamad Latifian, Nisarg Shah

cs.GT ·submitted 2026-11-03 17:44 UTC · v1
published

Abstract

The distortion framework in social choice theory allows quantifying the efficiency of (randomized) selection of an alternative based on the preferences of a set of agents. We make two fundamental contributions to this framework. First, we develop a linear-programming-based algorithm for computing the optimal randomized decision on a given instance, which is simpler and faster than the state-of-the-art solutions. For practitioners who may prefer to deploy a classical decision-making rule over the aforementioned optimal rule, we develop an algorithm based on non-convex quadratic programming for computing the exact distortion of any (and the best) randomized positional scoring rule. For a small number of alternatives, we find that the exact distortion bounds are significantly better than the asymptotic upper bounds established in prior literature and lead to different recommendations on which rules to use. These results rely on a novel characterization of the instances yielding the worst distortion, which may be of independent interest.

Comment
Paper presented at AAMAS 2024
Journal ref
Autonomous Agents and Multi-Agent Systems, 40, Article 50 (2026)
DOI
10.1007/s10458-026-09776-2

Closest papers

Nearest neighbours by meaning across the whole index.

Metric Distortion of Social Welfare Functions

cs.GT cs.MA ·2026-08-22 ·Fatih Erdem Kizilkaya, Aaryaman Aggarwal, Evi Micha
similarity 0.68
Abstract · 11 pages, 1 table

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)$.

0.43

Distortion in Online Voting

cs.GT ·2026-11-19 ·MohammadHossein Ghasemi, Masoud Seddighin, Saeed Seddighin
theory similarity 0.67
Abstract

We initiate the study of distortion in online voting, a framework that bridges computational social choice and online algorithms. In contrast to the classical offline setting, where the full election instance is known in advance, we consider a dynamic environment where a fixed set of voters is present from the beginning, but alternatives arrive sequentially over time. Upon each arrival, a mechanism must immediately and irrevocably decide whether to retain the currently selected candidate or switch to the newly arriving one, operating solely on the partial ordinal rankings induced by the underlying cardinal preferences. We provide upper and lower bounds for deterministic and randomized mechanisms under two standard cardinal preference frameworks. Utilitarian framework: For deterministic mechanisms under adversarial arrival order, we establish an $Ω(mn)$ lower bound and give an matching online algorithm with distortion at most $\frac{2}{3}m(n+\frac{1}{4})$. For randomized rules, we introduce regularity, which allows any regular, order-independent offline randomized rule to be converted into an online rule with the same expected distortion. The Harmonic voting rule satisfies this property, yielding online distortion $O(\sqrt{m\log m})$. Metric framework: For deterministic mechanisms, maintaining an alternative within a $\varphi$-weighted uncovered set guarantees distortion $2+\sqrt{5}$. We show that matching-based offline rules achieving distortion $3$ cannot be directly implemented online. We establish a lower bound of $\sqrt{13}$, even with three alternatives, and a matching upper bound for three alternatives and any number of voters. For randomized mechanisms, regularity gives an online distortion of $3-\frac{2}{n}$ via Random Dictatorship.

0.13

An improved bound for the randomized metric distortion problem

cs.GT ·2026-08-18 ·Fabian Frank
theoryhighly cited similarity 0.65
Abstract

We propose a randomized social choice rule called Mixed Integrated Veto (MIV) with metric distortion of $5/2$, improving the previous best upper bound of $2.75271$. MIV is the equal mixture of Maximal Lotteries and Integrated Veto, a new rule built on the Simultaneous Veto process of Kizilkaya and Kempe. Rather than returning the candidate surviving longest, Integrated Veto assigns each candidate probability proportional to its average score over the whole process.

0.45

Stable Voting Rules on the Edge of Optimal Metric Distortion

cs.GT ·2026-09-08 ·Ziyi Cai, Fabian Frank, Jabari Hastings, Prasanna Ramakrishnan, Kangning Wang +1 more
theory similarity 0.65
Abstract

We prove the existence of a randomized voting rule with metric distortion at most $2.1248$, within $0.013$ of the lower bound of $2.11264$. Our rule comes from a generalization of \emph{stable $k$-lotteries} developed in the context of committee selection. In contrast to prior work, our rule samples from a single distribution derived from a zero-sum game, without mixing between voting rules. Our result also gives sharp distortion bounds for stable $k$-lotteries. In particular we show that stable $2$-lotteries have distortion $7/3$, despite only relying on aggregate preferences over triples of candidates, and that stable $2$-lotteries are optimal in this class of voting rules.

0.37

Improving Randomized Metric Distortion to 2.1441

cs.GT cs.AI ·2026-08-29 ·Nisarg Shah
theoryhot direction similarity 0.63
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.

0.44

Robust Lottery Compression for Metric Voting: A Transfer Principle for Bounded Randomness

cs.GT ·2026-08-27 ·Jianhao Jia, Bo Peng
benchmarktheory similarity 0.61
Abstract

We study metric distortion in randomized social choice under bounded randomness: on every preference profile, the voting rule must deterministically identify a multiset of $K$ candidates and then select a uniformly random entry. Previous work showed that this restricted model can beat the optimal deterministic distortion of $3$. We show that it can in fact approach the current best unrestricted upper benchmark of $5/2$. For every integer $K\ge 802$, there exists a bounded-randomness rule with distortion at most $\frac{5}{2} +3\left(\fracπ{8K}\right)^{1/3} +2\sqrt{\fracπ{8K}}$. Consequently, $O(\varepsilon^{-3})$ entries suffice for distortion $5/2+\varepsilon$, independently of the numbers of voters and candidates. We also show that $164$ entries already achieve distortion strictly below $3$, giving $2\le N^\star\le 164$ for the minimum list size needed to break the deterministic barrier. Our main technical contribution is a dimension-free compression theorem: if a lottery has distortion at most $ρ$ and every candidate in its support has deterministic distortion at most $H$, then it admits a uniform $K$-entry approximation with distortion at most $ρ+(H+1)\sqrt{π/(8K)}$. Thus, lotteries whose possible outcomes are already well behaved incur only $O(K^{-1/2})$ compression loss. Mixed Integrated Veto does not satisfy this support condition, so we first remove early-eliminated outcomes, trading $O(τ^2)$ distortion loss for an $O(1/τ)$ bound on the deterministic distortion of every supported candidate. Balancing this repair cost against compression yields the $O(K^{-1/3})$ convergence rate.

0.41

Improved Metric Distortion Bounds for Deterministic Weighted-Tournament Voting Rules

cs.GT ·2026-08-15 ·Hau Chan, Jianan Lin, Chenhao Wang
theory similarity 0.61
Abstract

In metric social choice, voters and candidates lie in a common but unknown metric space, voters rank candidates by distance, and a voting rule seeks to minimize total distance to the voters. Its distortion is the worst-case approximation ratio relative to the minimum possible total distance. We study weighted-tournament rules (also known as C2 rules), which observe only the fraction of voters who prefer $a$ to $b$ for each pair of candidates $a,b$. These frequencies form a weighted tournament on candidates, a compressed representation that omits voter identities and the association of comparisons with individual voters. Prior work placed the optimal distortion of deterministic C2 rules between $3.1128$ and $3.9312$ [Charikar et al., EC 2025]. We introduce the Path-Unblanketed Set rule, a polynomial-time deterministic C2 rule with distortion at most $1+2\sqrt{2}\approx3.8284$ for every finite number of candidates. For elections with no more than six candidates, we prove with computer assistance that the distortion is at most $3.3346$. Furthermore, using an exact computer-assisted certificate, we provide a lower bound of $3.1828$ for deterministic C2 rules as a byproduct.

0.32

Improved Randomized Approximations for Strategic Obnoxious Facility Location

cs.GT ·2026-09-07 ·Hau Chan, Jianan Lin, Chenhao Wang
publishedtheory similarity 0.59
Abstract · To appear in ISAAC 2026

We study randomized strategyproof mechanisms for strategic obnoxious facility location on a line segment, where agents wish the facility to be located as far away from them as possible and their utility is their distance from the facility, under the social utility and minimum utility objectives. For social utility, we propose a novel randomized mechanism that breaks the previously best known \(\frac32\)-approximation of [Cheng, Yu, and Zhang, TCS 2013], achieving an approximation ratio of at most \(1.47359\). We also raise the lower bound on the approximation ratio of randomized strategyproof mechanisms from \(\frac{2}{\sqrt{3}}\approx1.15470\) [Feigenbaum et al., JAAMAS 2020] to \(\frac{105}{88}\approx1.19318\). For minimum utility, following the profile-independent approach of [Chan, Lin and Wang, AAMAS 2026], we design a simple randomized mechanism that reduces the approximation guarantee from \(\sqrt{2n}+O(1)\) to \(\sqrt n+O(1)\), where \(n\) is the number of agents. Finally, we prove that no randomized strategyproof mechanism can achieve an asymptotic approximation ratio strictly smaller than \(2\), strengthening the previous asymptotic lower bound of \(\frac32\) [Feigenbaum et al., JAAMAS 2020]. Thus, all four bounds considered in this paper strictly improve upon the corresponding previously known results.

0.30