Research map / Multi-agent systems and games / Games and equilibria
Improved Metric Distortion via Threshold Approvals
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.
Shows that deterministic mechanisms using ordinal preferences, alternative distances and per-agent threshold approval sets can beat the metric distortion barrier of 3, achieving 1+√2 for social cost and max cost in general metric spaces, with matching lower bounds in several settings.
Problem
Metric distortion of single-winner social choice under limited information: the best known deterministic distortion with ordinal preferences is 3, and the question is whether limited cardinal information can beat it for social cost and max cost objectives.
Approach
Introduces α-threshold approval sets (α-TAS) that record, per agent, all alternatives whose cost is within a factor α of the agent's top choice's cost, and designs mechanisms (α-MINISUM-TAS-DISTANCE, α-MOST-COMPACT-SET, α-ELIMINATION-WEIGHTED-MAJORITY) that exploit these sets together with ordinal and distance information to achieve distortion 1+√2 for general metrics.
Key results
- Achieves distortion 1+√2 ≈ 2.42 for social cost in general metric spaces with the (1+√2)-MINISUM-TAS-DISTANCE mechanism, breaking the barrier of 3.
- Lower bound of 1+√2 for max cost holds for any deterministic mechanism with all three information types, even on a line; the (1+√2)-MOST-COMPACT-SET mechanism matches it.
- On the line metric, social cost distortion 2√2−1 ≈ 1.83 is tight for ORD∩DIST∩TAS, achieved by α-ELIMINATION-WEIGHTED-MAJORITY.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add α-threshold approval sets to the available information, with alternative distances | Social-cost mechanisms in general metric spaces · General metric spaces | distortion: 3 -> 1 + √2 | Helped |
| Add α-threshold approval sets and ordinal preferences | Social-cost mechanisms · Line metric | distortion: 3 -> 2√2 − 1 | Helped |
| Use α-TAS and alternative distances without ordinal preferences | (1+√2)-MINISUM-TAS-DISTANCE · Line metric, social cost | distortion: 3 -> 2 | Helped |
| Add α-threshold approval sets to the available information | Maximum-cost mechanisms in general metric spaces · General metric spaces | distortion: 3 -> 1 + √2 | Helped |
| Use α-TAS and ordinal preferences | Maximum-cost mechanisms · Line metric | distortion: 3 -> 1 + √2 | Helped |
| Use α-TAS and alternative distances | Maximum-cost mechanisms · Line metric | distortion: 3 -> 1 + √2 | Helped |
| Replace the maximum-cost objective with social cost while keeping α-MINISUM-TAS-DISTANCE | α-MINISUM-TAS-DISTANCE · Line metric, maximum cost | distortion: 3 -> 1 + √2 | Helped |
| Use only α-TAS and no ordinal preferences or alternative distances | Social-cost mechanisms · General metric spaces | distortion: 1 + √2 -> Θ(n) | Hurt |
Surprising findings
- The social-cost mechanism (1+√2)-MINISUM-TAS-DISTANCE does not use ordinal preferences at all, yet matches the 1+√2 lower bound for DIST∩TAS.
- For the max cost objective, the natural DIST∩TAS analogue of the line mechanism yields counterexamples with distortion 3 in general metrics.
Limitations
- Social cost gap in general metrics: upper bound 1+√2 versus lower bound 2 for mechanisms with all three information types.
- Open whether 1+√2 is achievable with ORD∩TAS in general metrics; the line-specific mechanisms do not extend to general metrics.
- Results are for deterministic mechanisms only; randomization is left open.
Experimental setup
Metrics: distortion (social cost) distortion (max cost)
Baselines: PLURALITY MATCHING PLURALITY VETO ANY-APPROVED
Builds on: metric distortion (Anshelevich et al. 2018) PLURALITY VETO (Kizilkaya and Kempe 2022) Abramowitz, Anshelevich, and Zhu 2019 cardinal threshold mechanism
Closest papers by meaning
- Every Bit Helps: Achieving the Optimal Distortion with a Few Queries (AAAI 2025 · similarity 0.90)
- Can a Few Decide for Many? The Metric Distortion of Sortition (ICML 2024 · similarity 0.90)
- Constant-Factor Distortion Mechanisms for k-Committee Election (AAAI 2025 · similarity 0.88)
- Low-Distortion Clustering with Ordinal and Limited Cardinal Information (AAAI 2024 · similarity 0.87)
- On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries (AAAI 2025 · similarity 0.87)
- Independence of Irrelevant Alternatives under the Lens of Pairwise Distortion (AAAI 2024 · similarity 0.87)
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.