Research map / Learning theory and algorithms / Submodular and game algorithms
Participation Incentives in Approval-Based Committee Elections
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.
Initiates the study of participation (voters never benefit from abstaining) for approval-based committee voting rules, showing ABC scoring rules satisfy group participation while most sequential rules fail it, with escape routes and NP-hardness of deciding benefit from abstention.
Problem
Whether voters have incentives to participate in approval-based committee elections, i.e., whether abstaining can benefit a voter under ABC voting rules.
Approach
Shows ABC scoring rules (incl. Thiele rules) satisfy group participation, while sequential query rules satisfying standardness, concurrence and continuity fail participation; proposes escape routes (unrepresented voters, laminar profiles) and proves NP-hardness of deciding whether a voter benefits from abstaining.
Key results
- All ABC scoring rules (including all Thiele rules) satisfy group participation.
- Every sequential query rules with standardness, concurrence and continuity fails participation for k>=3; all sequential Thiele rules except AV, sequential Phragmén and MES fail participation.
- For every sequential Thiele rule except AV, sequential Phragmén and MES, deciding whether a voter can benefit from abstention is NP-hard.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an ABC scoring rule rather than a general ABC rule | ABC voting rules · ABC elections | group participation | Helped |
| Use sequential Thiele rule other than AV | Sequential Thiele rules · ABC elections | participation | Hurt |
| Use sequential Phragmén | Sequential Phragmén · ABC elections | participation | Hurt |
| Use the method of equal shares | Method of equal shares (MES) · ABC elections | participation | Hurt |
| Restrict profiles to laminar profiles | Sequential Thiele rules · Laminar profiles | participation | Helped |
| Restrict profiles to laminar profiles | Sequential Phragmén · Laminar profiles | participation | Helped |
| Restrict profiles to laminar profiles | Method of equal shares (MES) · Laminar profiles | participation | Helped |
| Restrict attention to voters approving none of the elected candidates | Sequential Thiele rules · ABC elections | participation for unrepresented voters | Helped |
| Restrict attention to voters approving none of the elected candidates | Sequential Phragmén · ABC elections | participation for unrepresented voters | Helped |
| Restrict attention to voters approving none of the elected candidates | Method of equal shares (MES) · ABC elections | participation for unrepresented voters | Hurt |
Surprising findings
- Sequential Thiele rules, sequential Phragmén, and MES fail participation even though they are natural rules, with a voter approving one elected candidate when voting and k-1 when abstaining.
- MES even violates participation for unrepresented voters, while sequential Thiele rules and sequential Phragmén satisfy it.
Limitations
- Impossibility holds for most sequential rules, so only escape routes (unrepresented voters, laminar profiles) are positive results.
- NP-membership is unresolved; hardness stated as NP-hard rather than NP-complete for the benefit-from-abstention problem.
Experimental setup
Baselines: multiwinner approval voting sequential PAV sequential Phragmén method of equal shares
Builds on: Thiele rules Method of equal shares Sequential Phragmén Kelly's extension
Closest papers by meaning
- Refined Characterizations of Approval-Based Committee Scoring Rules (AAAI 2024 · similarity 0.92)
- Proportional Aggregation of Preferences for Sequential Decision Making (AAAI 2024 · similarity 0.88)
- Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences (NeurIPS 2026 · similarity 0.88)
- Maintaining Proportional Committees with Dynamic Candidate Sets (ICML 2025 · similarity 0.88)
- Unravelling Expressive Delegations: Complexity and Normative Analysis (AAAI 2024 · similarity 0.86)
- On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries (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.