Source-linked AI summary
Distortion in Social Choice Problems: The First 15 Years and Beyond
Elliot Anshelevich, Aris Filos-Ratsikas, Nisarg Shah, Alexandros A. Voudouris
TL;DR
Ordinal rankings leave out utility intensity, making utilitarian welfare difficult to optimize. This survey synthesizes 15 years of distortion research across social-choice settings, including bounds on deterministic rules such as Plurality's O(m^2) distortion in normalized social choice, which is best possible.
Problem
Ordinal preference rankings omit utility intensity, making it challenging to optimize utilitarian social welfare, defined as the sum of individual utilities.
Source: §1 · p. 1Method
The paper surveys significant distortion results from 15 years of work across elections, metric preferences, committee selection, participatory budgeting, and matching.
Source: §1 · p. 2Results
In normalized social choice, Plurality has distortion O(m^2), best possible among deterministic voting rules.
Source: §2 · p. 3Takeaways & Limitations
The survey highlights open problems and promising ongoing and future directions in distortion research.
Source: §1 · p. 2The voting rule is given ordinal rankings, while agents' values are private and may be unknown even to the agents themselves.
Source: §2 · p. 2
Abstract
from arXiv · showhide
The notion of distortion in social choice problems has been defined to measure the loss in efficiency -- typically measured by the utilitarian social welfare, the sum of utilities of the participating agents -- due to having access only to limited information about the preferences of the agents. We survey the most significant results of the literature on distortion from the past 15 years, and highlight important open problems and the most promising avenues of ongoing and future work.
1 Introduction
Ordinal rankings omit utility intensity, making it difficult to optimize utilitarian social welfare; the section motivates distortion as a way to study the worst-case loss from this limited information. It introduces a survey of 15 years of results, open problems, and future directions across social-choice settings.
1 Introduction
- With tied ordinal preferences, choosing a winner can yield social welfare n/4 when the alternative has welfare 3n/4, a factor of 3 below optimal.The rankings alone cannot distinguish the two alternatives in the example.Source: §1 · pp. 1–2
- Distortion measures the worst-case deterioration in a cardinal objective, such as utilitarian welfare, when decisions use limited preference information, especially ordinal rankings.The research asks which social choice functions achieve the best possible distortion for a given cardinal objective.Source: §1 · p. 2
- The survey reviews significant results, open problems, and future directions across elections, metric preferences, committee selection, participatory budgeting, and matching.The literature spans economics, computation, and artificial intelligence.Source: §1 · p. 2
2 Normalized Social Choice
In normalized single-winner social choice, rules choose from rankings rather than agents’ private values, and distortion measures the resulting worst-case welfare loss. The section surveys tight deterministic and improved randomized bounds, then reviews extensions beyond single-winner elections.
2 Normalized Social Choice
- The normalized setting assumes each agent’s values across alternatives sum to one, while the rule receives rankings because cardinal values are private.Distortion is the worst-case ratio of the maximum social welfare to the welfare of the selected alternative.Source: §2 · pp. 2–3
- Plurality has distortion O(m^2), the best possible among deterministic rules; the upper and lower bounds are illustrated by the proof and its Figure 1 instance.The upper bound follows from unit-sum values, while the lower-bound instance gives selectable alternatives welfare n/(m(m −2)) against n/4 for the blue alternative.Source: §2 · p. 3, Figure 1 · p. 4
- A simpler randomized rule mixes uniform selection with a harmonic-score lottery for O(√m log m), while a more involved rule achieves O(√m log* m), settling single-winner bounds.The survey notes that randomized rules overcome sharp impossibility results for deterministic rules.Source: §2 · pp. 3–4
Beyond the single-winner setting
- Extensions cover selecting committees, participatory budgeting under a budget constraint, and randomized rules that output rankings of alternatives.The survey reports almost tight committee bounds, tight bounds for several budgeting input types, and qualitatively similar randomized bounds for rankings.Source: Beyond the single-winner setting · p. 4
3 Metric Social Choice
Metric restrictions permit constant-distortion voting despite a deterministic lower bound of 3, and later work examined randomized rules, limited ordinal inputs, and other metric settings. The section also surveys performance bounds and open directions across these variants.
3 Metric Social Choice
- Agents and alternatives lie in a metric space, where social cost sums distances; Copeland achieves distortion 5 [Anshelevich et al., 2015].The example in Figure 2 establishes a deterministic lower bound of 3.Source: §3 · pp. 4–5, Figure 2 · p. 5
- The plurality-matching rule resolves the conjecture that deterministic metric distortion can reach the example’s lower bound of 3 [Gkatzelis et al., 2020].The rule selects an alternative whose integral domination graph has a perfect matching.Source: §3 · p. 5, Figure 2 · p. 5
- Ranked Pairs has distortion Θ(√m), while Munagala and Wang’s rule achieves 4.236; positional scoring rules have distortion Ω(√log m) [Skowron and Elkind, 2017; Goel et al., 2017; Kempe, 2020b; Munagala and Wang, 2019].Single Transferable Vote has distortion between Ω(√log m) and O(log m) [Skowron and Elkind, 2017].Source: §3 · p. 5
Randomized Rules
- Random Dictatorship has distortion 3 − 2/n, while any randomized rule has distortion at least 2, even on a line [Anshelevich and Postl, 2017].The rule of Kempe [2020a] has distortion 3 − 2/m; the section also reports a tight bound of 2 for the line metric and almost 1.218 for median graphs [Feldman et al., 2016; Fain et al., 2017].Source: Randomized Rules · p. 6
Limited Ordinal Information
- For top-k rankings with k < m/2, distortion is at least 3 − 2/⌊m/k⌋, and a randomized agreement rule is almost optimal when m is not too large [Gross et al., 2017].The rule asks random agents for their favorite alternatives until two agree.Source: Limited Ordinal Information · p. 6
- With constant pairwise-comparison sample complexity, Random Referee achieves constant squared distortion; no rule using only top-k rankings for constant k has sublinear squared distortion [Fain et al., 2019].For deterministic rules, distortion is Θ(m/k) when input consists of alternatives ranked in a given set of k positions, and is Ω(m/b) when agents submit b bits [Kempe, 2020a].Source: Limited Ordinal Information · p. 6
Other Settings
- Other variants study randomly selected alternatives, abstention, approval preferences, and committee quality based on consistency with agents’ binary-issue preferences [Cheng et al., 2017; Cheng et al., 2018; Ghodsi et al., 2021; Pierczynski and Skowron, 2019; Jaworski and Skowron, 2020].For primary voting, every rule is guaranteed to perform almost as well as under direct elections, but not vice versa [Borodin et al., 2019].Source: Other Settings · p. 7
4 Other Problems and Extensions
The survey extends distortion analysis to matching and related graph problems, and considers how truthfulness constrains the available rules. It also identifies open questions for minimum-cost metric matching and other settings.
Matching and Other Graph Problems
- Random Serial Dictatorship has distortion O(√n), best possible among ordinal-input rules for one-sided matching, while the best deterministic rule has distortion Θ(n²) [Filos-Ratsikas et al., 2014; Amanatidis et al., 2021].One-sided matching assigns n agents to n items to maximize the total value of their assigned items.Source: Matching and Other Graph Problems · p. 7
- For symmetric values satisfying the triangle inequality, deterministic rules attain distortion 2 for maximum-weight matching and maximum-TSP; randomized bounds are 1.6 and 1.88, respectively [Anshelevich and Sekar, 2016a; 2016b; Abramowitz and Anshelevich, 2018].For many facility-assignment and matching problems with public facility locations, ordinal rules have distortion at most 3 [Anshelevich and Zhu, 2018].Source: Matching and Other Graph Problems · pp. 7–8
Truthfulness and Distortion
- In one-sided matching, random serial dictatorship’s O(√n) bound is best possible among truthful mechanisms; for minimum-cost metric matching, its distortion lies between Ω(n^0.29) and O(n), leaving the best ordinal bound open [Filos-Ratsikas et al., 2014; Caragiannis et al., 2016].The open question asks for the best ordinal distortion in that metric matching setting, both with and without truthfulness.Source: Truthfulness and Distortion · p. 8
5 Generalizations of Distortion
The section broadens distortion to efficiency loss from incomplete information, including limited cardinal information, communication constraints, and distributed decisions. It surveys results and open questions for each setting.
5 Generalizations of Distortion
- Generalized distortion captures efficiency loss when information is incomplete, including cases with more than ordinal but less than full cardinal information, limited communication, or distributed decision-making.The survey presents these as avenues for further investigation.Source: §5 · pp. 8–9
Beyond Ordinal Information
- In single-winner elections, O(m) distortion needs one query per agent, O(√m) needs O(log m) queries, and constant distortion needs O(log²m) queries [Amanatidis et al., 2020].Sublinear distortion is impossible with one query per agent, and ω(log m) queries per agent are necessary for constant distortion; matching and its generalizations also exhibit similar tradeoffs [Amanatidis et al., 2020; Amanatidis et al., 2021; Ma et al., 2020]. Passion information in metric settings yields deterministic distortion 2 with two alternatives and 2 with more alternatives [Abramowitz et al., 2019].Source: Beyond Ordinal Information · p. 9
Communication complexity
- For single-winner voting, communication complexity to achieve distortion d has bounds ˜Θ(m/d) for deterministic elicitation and ˜Θ(m/d³) for randomized elicitation [Mandal et al., 2020].For multi-winner voting with k winners, the corresponding bounds are ˜Θ(m/(kd)) and ˜Θ(m/(kd³)); other settings remain an open direction [Mandal et al., 2020].Source: Communication complexity · p. 10
Distributed settings
- Distributed rules in unit-sum single-winner elections have considerably larger distortion than centralized counterparts; deterministic facility-location rules on a line have tight small-constant bounds, including under truthfulness [Filos-Ratsikas et al., 2020; Filos-Ratsikas and Voudouris, 2020].Open questions include randomized distributed rules, committees, multiple facilities, and general metric spaces.Source: Distributed settings · p. 10