CS Paper Radar

Metric Distortion of Social Welfare Functions

Fatih Erdem Kizilkaya, Aaryaman Aggarwal, Evi Micha

cs.GT cs.MA ·submitted 2026-08-22 06:04 UTC · v1

Abstract

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

Comment
11 pages, 1 table

Closest papers

Nearest neighbours by meaning across the whole index.

The Distortion of Threshold Approval Multiwinner Voting

cs.GT ·2026-10-09 ·Mohamad Latifian, Marzieh Nilipour, Alexandros A. Voudouris
similarity 0.78
Abstract

We study multiwinner voting with $n$ voters and $m$ candidates, where the goal is to select a committee of size $k$. Voters have unit-sum cardinal utilities but report only coarse information induced by $t$ utility thresholds. In particular, each voter partitions the candidates into approval sets, with the utilities of all candidates in the same set lying between the same pair of consecutive thresholds. We model the utility of each voter for a committee as a normalized monotone symmetric norm, capturing, among others, additive welfare, best-representative utility, top-$r$ welfare, $\ell_p$ welfare, and normalized non-increasing ordered weighted averages. We design a deterministic rule with distortion at most $2(2m)^{1/t}$ and a randomized rule with distortion at most $2\min\{m^{1/(t+1)},m/k\}$. These guarantees hold for every committee size $k$ and every norm in our framework. Consequently, a single threshold yields distortion $O(m)$ for deterministic rules and $O(\sqrt{m})$ for randomized rules, while $O(\log m)$ thresholds suffice for constant distortion. We complement these results with norm-dependent lower bounds that asymptotically match our upper bounds for constant committee sizes, including the single-winner case.

0.18

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.77
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.33

Regularizing the Veto Core

cs.GT ·2026-10-19 ·M. August Rossi
theory similarity 0.77
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

Improved Metric Distortion Bounds for Deterministic Weighted-Tournament Voting Rules

cs.GT ·2026-08-15 ·Hau Chan, Jianan Lin, Chenhao Wang
theory similarity 0.76
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

Best-of-Both Worlds Proportionality in Structured Committee Elections

cs.GT ·2026-10-20 ·Dimitris Avramidis, Mark de Berg, Ulrike Schmidt-Kraepelin
similarity 0.72
Abstract

We study randomized committee elections with additive preferences, where we seek best-of-both-worlds proportionality. That is, we strive for strong guarantees for the selection probabilities ex ante and each realized committee ex post. We focus on structured preferences and introduce antichain single-peakedness, a restricted domain generalizing single-peaked additive preferences as well as several well-studied approval domains. Our approach first computes a fractional committee and then decomposes it through a rounding rule called systematic rounding. Among profile-oblivious rounding rules, we characterize systematic rounding as the unique rule satisfying natural quota guarantees, and thereby the only promising rule for our two-step approach. We show that ex-ante core stability is incompatible with ex-post justified representation $JR$, even under single-peaked preferences. However, applying systematic rounding to certain fractional allocations that form so-called Lindahl equilibria yields ex-ante core stability and ex-post core stability up to one. Alternatively, we retain exact ex-post proportionality and approximate the ex-ante core using two parameters: $α$ raises the utility gain required for a deviation, while $β$ reduces the coalition's proportional share. We establish the tight threshold $αβ$=2. Below it, ex-post JR is incompatible even under single-peaked preferences; at and above it, adapting a fractional rule called BestRepresentative [Pierczyński and Skowron, 2022] and applying systematic rounding to its output yields ex-ante $α, β$-fractional core stability and ex-post PJR under antichain single-peaked preferences.

0.07

A Constant Metric Distortion Protocol for Approval Voting Given Plurality Polls

cs.GT ·2026-08-28 ·Fabian Frank, Jannik Peters
similarity 0.71
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.40

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

cs.GT ·2026-08-27 ·Jianhao Jia, Bo Peng
benchmarktheory similarity 0.71
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.38

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

cs.GT cs.AIcs.DMcs.DS ·2026-10-17 ·Gabriel Chen, Yu Cheng, Alice Wang
similarity 0.70
Abstract · SOSA'27

We consider the metric distortion framework for voting, where $n$ voters and $m$ candidates are embedded in an unknown metric space. A voting rule selects a candidate using only voters' ordinal preferences, and its distortion is the worst-case ratio between the social cost of the selected candidate and the minimum social cost. We study how round complexity trades off against total communication in deterministic voting protocols with low distortion. Deterministic rules can achieve the optimal distortion of $3$ in one round by eliciting complete rankings using $Θ(nm\log m)$ bits, while a direct sequential implementation of PluralityVeto achieves the same distortion using only $O(n\log m)$ bits but requires $Θ(n)$ rounds. Our main result is TreePluralityVeto, a deterministic voting protocol that, for every $r\ge 2$, achieves distortion at most $2r-1$ using at most $r$ rounds and $O(n\log m+n s^{1/(r-1)}\log s)$ bits of total communication, where $s = \min\{n, m\}$. The protocol runs PluralityVeto on a hierarchical partition of the voters, collecting restricted rankings in parallel at each level. The branching factor controls the tradeoff between rounds and communication, and a matching-based analysis shows that each level increases the distortion bound by at most $2$.

0.19