CS Paper Radar

Improved Metric Distortion Bounds for Deterministic Weighted-Tournament Voting Rules

Hau Chan, Jianan Lin, Chenhao Wang

cs.GT ·submitted 2026-08-15 14:13 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Improving Randomized Metric Distortion to 2.1441

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

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.76
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

Metric Distortion of Social Welfare Functions

cs.GT cs.MA ·2026-08-22 ·Fatih Erdem Kizilkaya, Aaryaman Aggarwal, Evi Micha
similarity 0.76
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

A Constant Metric Distortion Protocol for Approval Voting Given Plurality Polls

cs.GT ·2026-08-28 ·Fabian Frank, Jannik Peters
similarity 0.74
Abstract

Approval voting is a simple and well-regarded voting rule: voters submit approval ballots (subsets of the candidates) and the candidate receiving the most approvals wins. One major limitation of approval voting is that it is not clear which candidates voters should approve if they have an underlying strict order over the candidates. In this paper, we initiate the study of approval voting under a simple kind of information: plurality polls. That is, we assume that for each candidate we know the share of voters who rank this candidate as their top choice. Using these plurality polls, we suggest a simple protocol parameterized by a fraction $k \in (0,1)$: every voter should approve the smallest prefix of their preference list containing the first choices of at least a fraction $k$ of the voters. We evaluate this protocol via the framework of metric distortion and show that for the optimal choice of $k$, this rule achieves a metric distortion of $2 + \sqrt{5} \simeq 4.236$. The proof techniques we use for this statement also show that the Bucklin voting rule has a metric distortion of at most $5$. Finally, we evaluate the robustness of our protocol to noise and show that the upper bounds obtained for our protocol are tight.

0.42

Distortion in Online Voting

cs.GT ·2026-11-19 ·MohammadHossein Ghasemi, Masoud Seddighin, Saeed Seddighin
theory similarity 0.72
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

Regularizing the Veto Core

cs.GT ·2026-10-19 ·M. August Rossi
theory similarity 0.71
Abstract

The metric distortion framework asks voting rules to elect a candidate close to the voters using only their rankings. SimultaneousPluralityVeto elects from the plurality veto core and achieves the optimal worst-case distortion of 3, but it is not Pareto-efficient: it can declare a tie between two candidates even when every voter prefers one of them. Removing Pareto-dominated candidates afterward would break the convexity of tied winner sets. We instead introduce regularization, which adds a small $\varepsilon$ to every candidate's weight, restoring Pareto-efficiency. To study its effect on distortion, we introduce the rank score veto core, whose candidate weights come from a positional scoring vector $\mathbf{s}$, and prove that its distortion lies in $[1 + 2(||\mathbf{s}|| - s_m),\, 1 + 2||\mathbf{s}||]$; we conjecture that the lower bound is tight. A fixed $\varepsilon$ can increase distortion, but letting $\varepsilon$ depend on the number of voters preserves the distortion guarantee of the original veto core. Regularized SimultaneousPluralityVeto thus has optimal distortion, is Pareto-efficient, and has convex tied winner sets, resolving an open question of Kızılkaya and Kempe.

0.15

Proportionality in Elections under Feasibility Constraints and Ranked Ballots: The Solid Coalition Refinement Rule

cs.GT ·2026-11-06 ·Grzegorz Kwacz, Georgios Papasotiropoulos, Piotr Skowron
similarity 0.69
Abstract

We study elections with ranked ballots and general feasibility constraints, which indicate which sets of candidates are allowed as outcomes. We introduce the first proportionality axiom for this general setting and show that it extends the established notions from specific models that fit our general framework. We extend the Solid Coalition Refinement (SCR) rule to general constraints and prove that it satisfies our axiom exactly for matroid constraints. Although the naive implementation of SCR involves a step that is computationally intractable for weak orders, we show that in practical cases it can be implemented in polynomial time or efficiently in FPT time. We also illustrate limitations of this rule for approval ballots and provide its first empirical evaluation.

0.08