Research map / Multi-agent systems and games / Games and equilibria
The Metric Distortion of Multiwinner Voting
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Set the committee cost to the q-th closest selected alternative, with q ≤ k/3 | Multiwinner metric voting · Multiwinner metric distortion | distortion: distortion is unbounded | Hurt |
| Increase q into the range k/3 < q ≤ k/2 | Multiwinner metric voting · Multiwinner metric distortion | distortion: O(n); Ω(n) | Mixed |
| Use PolarOpposites, selecting two agents' top-q sets | Multiwinner metric voting · k/3 < q ≤ k/2 | distortion: 4n+1 | Helped |
| Increase q above k/2 | Multiwinner metric voting · Multiwinner metric distortion | distortion: 3 | Helped |
| Treat every k-sized committee as an alternative and apply a single-winner rule | Multiwinner metric voting · q > k/2 | distortion: 3 | Helped |
| Use randomized dictatorship to select an agent's top-k committee | Multiwinner metric voting · q > k/2 | distortion: 3-2/n | Helped |
| Restrict the candidate committees to agents' top-k committees and apply Plurality-Matching | Multiwinner metric voting · q > k/2 | distortion: ≤ 9 | Helped |
| Use the constant-agent enumeration to include an optimal committee among the candidates | Deterministic polynomial-time multiwinner rule · q > k/2, constant n | distortion: 3 | Helped |
| Require the efficient reduction template to return polynomially many candidate committees | Deterministic polynomial-time multiwinner rule · q > k/2 | distortion: 1+2/e; 5.207 | Hurt |
Closest papers by meaning
- On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries (AAAI 2025 · similarity 0.91)
- Constant-Factor Distortion Mechanisms for k-Committee Election (AAAI 2025 · similarity 0.90)
- Maintaining Proportional Committees with Dynamic Candidate Sets (ICML 2025 · similarity 0.89)
- Improved Metric Distortion via Threshold Approvals (AAAI 2024 · similarity 0.89)
- Temporal Fairness in Multiwinner Voting (AAAI 2024 · similarity 0.89)
- Tight Bounds on the Distortion of Randomized and Deterministic Distributed Voting (NeurIPS 2025 · similarity 0.88)
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.