Research map / Learning theory and algorithms / Submodular and game algorithms
Completing Priceable Committees: Utilitarian and Representation Guarantees for Proportional Multiwinner Voting
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 completing affordable committees (a weakening of priceability, including MES and GJCR outputs) with AV or CC yields optimal-type utilitarian (2/sqrt(k) - 1/k) and representation (3/4) guarantees, including under EJR+.
Problem
Utilitarian welfare and coverage guarantees achievable by proportional multiwinner voting rules that are non-exhaustive and must be completed to full committees, under demanding proportionality axioms such as EJR+ and FJR.
Approach
Defines affordable committees (payment systems satisfying only constraints C1-C4 of priceability) and proves that any affordable committee completed with AV, CC, seq-CC, or maximin support achieves specific utilitarian/representation guarantees; the EJR+ implies representativeness link yields strong bounds for MES and GJCR.
Key results
- Any affordable committee completed with CC achieves a representation guarantee of 3/4, and any affordable committee completed with seq-CC achieves 1-1/e.
- GJCR completed with AV achieves a utilitarian guarantee of exactly 2/sqrt(k) - 1/k, answering an open question of Elkind et al. (2022).
- For any c<1, there are exhaustive affordable committees satisfying EJR with utilitarian ratio O(1/k^(1-c)), so EJR alone is insufficient for strong utilitarian guarantees.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Complete GJCR with Approval Voting | GJCR · Approval-based multiwinner voting | utilitarian guarantee: \frac{2}{\sqrt{k}} - \frac{1}{k} | Helped |
| Complete MES with Approval Voting | MES · Approval-based multiwinner voting | utilitarian guarantee: \frac{2}{\sqrt{k}} - \frac{2}{k} | Helped |
| Complete an affordable committee with Chamberlin--Courant | Affordable committee · Approval-based multiwinner voting | representation guarantee: \frac{3}{4} | Helped |
| Complete an affordable committee with sequential Chamberlin--Courant | Affordable committee · Approval-based multiwinner voting | representation guarantee: 1-\frac{1}{e} | Helped |
| Complete an affordable EJR+ committee with Approval Voting | Affordable EJR+ committee · Approval-based multiwinner voting | utilitarian guarantee: \frac{1}{4\sqrt{k}} - \frac{1}{2k} | Helped |
| Use GJCR completed with AV instead of the asymptotic-only guarantee previously known | GJCR · Approval-based multiwinner voting | utilitarian guarantee: \frac{2}{\sqrt{k}} - \frac{1}{k} | Helped |
| Require EJR+ rather than EJR for the affordable committee | Affordable proportional committees · Approval-based multiwinner voting | utilitarian ratio: \mathcal{O}(\frac{1}{k ^ {1-c}}) | Mixed |
| Complete MES by varying the budget, then use AV | MES · Approval-based multiwinner voting | utilitarian guarantee: \frac{2}{\sqrt{k}} - \frac{2}{k} | Helped |
| Complete MES by perturbation instead of using AV | MES · Approval-based multiwinner voting | utilitarian guarantee: \Theta(\frac{1}{k}) | Hurt |
| Complete MES by perturbation | MES · Approval-based multiwinner voting | representation guarantee: \frac{1}{2} | Helped |
| Complete an affordable committee with the maximin support rule | Affordable committee · Approval-based multiwinner voting | maximin support approximation: \frac{1}{2} | Helped |
| Use the combined completion strategy that adds high-approval candidates and CC | GJCR · Approval-based multiwinner voting | utilitarian guarantee: \frac{2}{\sqrt{k}} - \frac{1}{k} | Helped |
Surprising findings
- EJR alone (as satisfied by GreedyEJR, even when exhaustive) cannot give strong utilitarian guarantees, unlike EJR+.
- MES completed by perturbation has utilitarian guarantee only Theta(1/k), and MES completed by varying the budget has representation guarantee only 1/k.
Limitations
- Results are for approval-based multiwinner voting with utility defined as number of approved committee members.
- Affordability is incompatible with exhaustiveness in general, so completion steps are required.
Experimental setup
Metrics: utilitarian guarantee representation guarantee approximation ratio
Baselines: Method of Equal Shares GreedyEJR Phragmén's sequential rule Approval Voting Chamberlin-Courant seq-CC
Builds on: priceability Method of Equal Shares Greedy Justified Candidate Rule GreedyEJR EJR+
Closest papers by meaning
- The Price of Justified Representation (AAAI 2022 · similarity 0.92)
- Reconfiguring Proportional Committees (AAAI 2026 · similarity 0.90)
- Maintaining Proportional Committees with Dynamic Candidate Sets (ICML 2025 · similarity 0.89)
- Proportional Justified Representation (AAAI 2017 · similarity 0.88)
- Approval-Based Apportionment (AAAI 2020 · similarity 0.88)
- Welfare Maximization in Perpetual Voting (Student Abstract) (AAAI 2024 · 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.