Research map / Learning theory and algorithms / Submodular and game algorithms
On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries
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 deterministic k-committee election with 1-Euclidean (line) preferences under ordinal input plus few distance queries, giving distortion lower/upper bounds for k=2 and query-distortion trade-offs for k>=3.
Problem
Metric distortion of k-committee election where each voter's cost is distance to nearest elected candidate, with voters and candidates on the real line, only ordinal rankings available, and few distance queries allowed.
Approach
Shows that without queries distortion is unbounded for k>=3; with about k-3 queries it remains unbounded, while a greedy k-center-style rule using 6(k-3)+3 candidate-distance queries achieves distortion 5n, and a coreset-style hierarchical partitioning with O(k log n) queries achieves constant distortion by exploiting line structure and voter rankings to locate furthest candidates.
Key results
- For k=2 and m=3 the best deterministic distortion is 3; for m>=4 it is at least n-1 and at most n+1.
- For k>=3, any deterministic rule using at most k-3 distance queries has unbounded distortion in n, m and k.
- A greedy rule with at most 6(k-3)+3 distance queries achieves distortion at most 5n for social cost and 5 for egalitarian cost.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use at most k-3 distance queries | Any deterministic k-committee election rule · k≥3, m≥2(k-1), social cost | distortion | Hurt |
| Use at most k-3 distance queries | Any deterministic k-committee election rule · k≥3, m≥2(k-1), egalitarian cost | distortion | Hurt |
| Add greedy selection using at most 6k-15 candidate distance queries | Deterministic k-committee election · k-committee election, social cost | distortion: unbounded -> 5n | Helped |
| Add greedy selection using at most 6k-15 candidate distance queries | Deterministic k-committee election · k-committee election, egalitarian cost | distortion: unbounded -> 5 | Helped |
| Reconstruct the candidate axis with m-1 candidate distance queries and optimize the candidate-restricted instance | Deterministic k-committee election · k-committee election, social cost | distortion: unbounded -> 3 | Helped |
| Reconstruct the candidate axis with m-1 candidate distance queries and optimize the candidate-restricted instance | Deterministic k-committee election · k-committee election, egalitarian cost | distortion: unbounded -> 3 | Helped |
| Select representative candidates by hierarchical partitioning | k-committee election · k-committee election, social cost | distortion: unbounded -> 5 | Helped |
| Elect the two extreme active candidates instead of using an optimal committee | Deterministic k=2 rule · k=2, m≥4, social cost | distortion: 2n-2 | Hurt |
| Choose the median candidate in each cluster induced by the two extreme candidates | Deterministic k=2 rule · k=2, social cost | distortion: 2n-2 -> n+1 | Helped |
| Use the tailored deterministic rule for three candidates | Deterministic k=2 rule · k=2, m=3, social cost | distortion: 3 | Helped |
Surprising findings
- Distortion is unbounded for any deterministic rule using k-3 or fewer distance queries, even on the real line.
- Electing the two extreme candidates for k=2 can have distortion as large as 2n-3, showing extreme candidates are not generally good.
Limitations
- Results restricted to 1-Euclidean (real line) preferences.
- Upper bound for k>=3 is O(n) with O(k) queries and constant with O(k log n) queries; gap to lower bound remains in query counts.
- Focus on deterministic rules only.
Experimental setup
Metrics: distortion number of distance queries
Baselines: Polar-Opposites Copeland
Builds on: metric distortion k-center greedy algorithm Polar-Opposites
Closest papers by meaning
- Constant-Factor Distortion Mechanisms for k-Committee Election (AAAI 2025 · similarity 0.92)
- On the Distortion of Voting With Multiple Representative Candidates (AAAI 2018 · similarity 0.92)
- Metric Distortion of Line-up Elections: The Right Person for the Right Job (AAAI 2025 · similarity 0.92)
- Tight Bounds on the Distortion of Randomized and Deterministic Distributed Voting (NeurIPS 2025 · similarity 0.90)
- Maintaining Proportional Committees with Dynamic Candidate Sets (ICML 2025 · similarity 0.87)
- Improved Metric Distortion via Threshold Approvals (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.