Research map / Learning theory and algorithms / Submodular and game algorithms
Independence of Irrelevant Alternatives under the Lens of Pairwise Distortion
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces pairwise distortion to quantify how violating IIA (using only pairwise preferences between two alternatives) costs social welfare, with average-case experiments and worst-case 1D-Euclidean bounds for pairwise voting rules.
Problem
Quantifying the social welfare loss caused by the independence of irrelevant alternatives (IIA) axiom, i.e., when a pairwise social choice between two alternatives ignores information from other alternatives' rankings.
Approach
Defines pairwise distortion, adapting voting distortion to pairwise voting rules that choose between two alternatives using full profiles; shows that IIA-satisfying pairwise majority has constant distortion, while score-based transitive rules (Borda, Copeland) can exploit irrelevant alternatives to reduce distortion on average and in the cooperative 1D-Euclidean worst case.
Key results
- Average pairwise distortion for m=2 is very close to 1 (highest about 5/2 - ln 4 ≈ 1.11 for unit-sum uniform with n=2).
- In 1D-Euclidean worst case with cooperative alternative placement, BordaPW achieves inf-pairwise distortion (m+1)/(m-1) and OddBordaPW achieves (2m-1)/(2m-3), versus 3 for pairwise majority and PluralityPW.
- Plurality pairwise rule has sup-pairwise distortion infinite for m≥3 in 1D-Euclidean, while BordaPW's sup is 2m-1; experiments show Plurality's average distortion increases with m while Borda and Copeland decrease.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use BordaPW instead of pairwise majority as the pairwise rule | Pairwise distortion on synthetic and real-data profiles · Average mean pairwise distortion as the number of alternatives m increases | average mean pairwise distortion | Helped |
| use CopelandPW instead of pairwise majority as the pairwise rule | Pairwise distortion on synthetic and real-data profiles · Average mean pairwise distortion as the number of alternatives m increases | average mean pairwise distortion | Helped |
| use PluralityPW instead of pairwise majority as the pairwise rule | Pairwise distortion on synthetic and real-data profiles · Average mean pairwise distortion as the number of alternatives m increases | average mean pairwise distortion | Hurt |
| use BordaPW instead of pairwise majority as the pairwise rule | Pairwise distortion on 1D-Euclidean uniform profiles · Average mean pairwise distortion as the number of alternatives m increases | average mean pairwise distortion | Mixed |
| place additional alternatives cooperatively and use BordaPW instead of pairwise majority | 1D-Euclidean metric pairwise distortion · Worst-case distortion with m alternatives | inf-pairwise distortion: 3 -> m+1/m−1 | Helped |
| place additional alternatives cooperatively and use OddBordaPW instead of pairwise majority | 1D-Euclidean metric pairwise distortion · Worst-case distortion with m alternatives | inf-pairwise distortion: 3 -> 2m−1/2m−3 | Helped |
| use PluralityPW instead of pairwise majority when alternative positions are adversarial | 1D-Euclidean metric pairwise distortion · Worst-case distortion with m≥3 alternatives | sup-pairwise distortion: 3 -> +∞ | Hurt |
| use k-ApprovalPW instead of pairwise majority when alternative positions are adversarial | 1D-Euclidean metric pairwise distortion · Worst-case distortion with m≥3 alternatives | sup-pairwise distortion: 3 -> +∞ | Hurt |
| use BordaPW instead of pairwise majority when alternative positions are adversarial | 1D-Euclidean metric pairwise distortion · Worst-case distortion with m alternatives | sup-pairwise distortion: 3 -> 2m −1 | Hurt |
| use OddBordaPW instead of pairwise majority when alternative positions are adversarial | 1D-Euclidean metric pairwise distortion · Worst-case distortion with m alternatives | sup-pairwise distortion: 3 -> 4m −5 | Hurt |
Surprising findings
- PluralityPW's average pairwise distortion increases with the number of alternatives, performing worse than pairwise majority.
- With the 1D-Euclidean uniform distribution, BordaPW has higher average pairwise distortion than pairwise majority.
Limitations
- Worst-case analysis restricted to 1D-Euclidean metric space; general metric spaces left to future work.
- OddBordaPW optimality conjectured only; for m≥6 it is shown not to be optimal among all pairwise rules.
- Average-case experiments use synthetic distributions and one real dataset with independent (uncorrelated) preferences.
Experimental setup
Datasets: Bars dataset (Preflib, Lesser et al. 2017)
Benchmarks: Bars dataset (Preflib) synthetic uniform, unit-sum uniform, and 2D-Euclidean profiles
Metrics: average pairwise distortion (avg) average max pairwise distortion (max) inf-pairwise distortion sup-pairwise distortion
Baselines: pairwise majority (IIA-satisfying) PluralityPW Half-approvalPW BordaPW CopelandPW
Builds on: voting distortion (Procaccia and Rosenschein 2006) metric distortion (Anshelevich et al. 2018) Arrow's impossibility theorem Half-approval average distortion (Gonczarowski et al. 2023)
Closest papers by meaning
- Worst-Case Voting When the Stakes Are High (AAAI 2022 · similarity 0.90)
- Low-Distortion Social Welfare Functions (AAAI 2019 · similarity 0.90)
- Improved Metric Distortion via Threshold Approvals (AAAI 2024 · similarity 0.87)
- Weak Strategyproofness in Randomized Social Choice (AAAI 2025 · similarity 0.86)
- Can a Few Decide for Many? The Metric Distortion of Sortition (ICML 2024 · similarity 0.85)
- Computing Voting Rules with Improvement Feedback (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.