Research map / Learning theory and algorithms / Submodular and game algorithms
Metric Distortion of Line-up Elections: The Right Person for the Right Job
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.
Studies metric distortion for line-up elections (choosing and assigning candidates to positions in a metric space) under different information regimes, giving deterministic mechanisms with constant distortion bounds.
Problem
Selecting candidates and assigning them to distinct positions to minimize total voter cost (voter-candidate plus candidate-position distances) when the mechanism knows only limited ordinal or location information rather than exact distances.
Approach
Combines social-choice committee selection with matching: an iterative plurality-veto election over positions, and serial dictatorship over position preferences, with charging arguments that bound the joint loss from wrong matchings and wrong candidate sets; also uses known candidate-position locations to get distortion 3 without voter information.
Key results
- Iterative election with plurality veto achieves distortion 7 for general line-up elections (m,l), improved from a bound of 9.
- Serial dictatorship using position preferences achieves distortion 5 for (m,l) and 3 - 1/2^(m-2) for (m,m).
- With candidate and position locations known, a deterministic mechanism achieves distortion 3 for (m,l), and with voter preferences the (2,1) case achieves 5/3 and the (2,1) voter-preference case achieves 2 (tight).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use iterative election with plurality veto instead of a per-position election bound of 3 | Line-up elections with ordinal voter preferences · (m, ℓ) | distortion upper bound: 9 -> 7 | Helped |
| Use serial dictatorship with ordinal position preferences rather than ordinal voter preferences | Line-up elections · (m, ℓ) | distortion upper bound: 7 -> 5 | Helped |
| Use serial dictatorship with ordinal position preferences rather than ordinal voter preferences | Line-up elections · (m, m) | distortion upper bound: 3 -> $3-\frac{1}{2 ^{m-2}}$ | Helped |
| Add ordinal position preferences to ordinal voter preferences | Line-up elections · (2, 1) | distortion upper bound: 3 -> 2 | Helped |
| Add exact candidate and position locations to ordinal voter preferences | Line-up elections · (2, 1) | distortion upper bound: 3 -> $\frac{5}{3}$ | Helped |
| Add exact candidate and position locations to ordinal voter preferences | Line-up elections · (m, 1) | distortion upper bound: 3 -> $\frac{25}{9}$ | Helped |
| Add exact candidate and position locations to the available information | Line-up elections · (m, ℓ) | distortion upper bound: 7 -> 3 | Helped |
| Use candidate-position locations to choose a minimum candidate-position-cost matching | Line-up elections · (m, m) | distortion upper bound: 3 -> 1 | Helped |
Surprising findings
- Knowing only ordinal position preferences yields better distortion than knowing full ordinal voter preferences for the (m,m) and (m,l) settings, beating the best known distortion for standard single-winner elections in the (m,m) case.
Limitations
- Requires all voters, candidates and positions to lie in a common metric space; with multiple arbitrary metric spaces the bounds degrade to the exponential matching bound.
- Analysis covers only deterministic mechanisms; randomized mechanisms are left to future work.
- Lower bounds are shown for specific small instances (e.g., 2 candidates), not all settings are tight.
Experimental setup
Metrics: distortion
Baselines: plurality veto serial dictatorship
Builds on: plurality veto serial dictatorship for metric bipartite matching metric distortion of single-winner elections line-up elections (Boehmer et al.)
Closest papers by meaning
- On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries (AAAI 2025 · similarity 0.92)
- Tight Bounds on the Distortion of Randomized and Deterministic Distributed Voting (NeurIPS 2025 · similarity 0.89)
- Constant-Factor Distortion Mechanisms for k-Committee Election (AAAI 2025 · similarity 0.87)
- Improved Metric Distortion via Threshold Approvals (AAAI 2024 · similarity 0.87)
- Proportional Representation in Metric Spaces and Low-Distortion Committee Selection (AAAI 2024 · similarity 0.87)
- The Distortion of Public-Spirited Participatory Budgeting (AAAI 2025 · similarity 0.86)
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.