Research map / Learning theory and algorithms / Submodular and game algorithms
The Price of Justified Representation
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 |
|---|---|---|---|
| Impose JR while maximizing social welfare | Approval-based multiwinner committees · Approval elections, committee size k | social welfare price: √k/2 | Hurt |
| Impose JR while maximizing coverage | Approval-based multiwinner committees · Approval elections, committee size k | coverage: coverage price = 1 | No clear effect |
| Impose EJR while maximizing coverage | Approval-based multiwinner committees · Approval elections, committee size k | coverage: coverage price = 4/3 | Hurt |
| Use a JR committee selection policy balancing welfare and coverage | Approval-based multiwinner committees · Approval elections, sufficiently large k | coverage: coverage price ≤ 4/3+ε; welfare price ≤ (1/β)(1+√k) | Mixed |
| Use greedy rather than optimal coverage selection in the second stage | JR committee selection · Approval elections, sufficiently large k | coverage: 1/(1-(1/e)^(1 - 2/√k - 1/k)) | Hurt |
| Use GreedyCC with any second-stage selection rule | JR committee selection · Constructed approval election | social welfare: Θ(k√k) to Θ(k) | Hurt |
| Use the polynomial-time greedy coverage algorithm | JR-constrained social-welfare maximization · Approval elections, n = k | social welfare: at least sw_JR(I)/2 | Helped |
| Exploit 1D-VCR interval structure | JR-constrained social-welfare maximization · 1D-VCR preferences | social welfare | Helped |
Closest papers by meaning
- Completing Priceable Committees: Utilitarian and Representation Guarantees for Proportional Multiwinner Voting (AAAI 2024 · similarity 0.92)
- On the Complexity of Extended and Proportional Justified Representation (AAAI 2018 · similarity 0.92)
- Maintaining Proportional Committees with Dynamic Candidate Sets (ICML 2025 · similarity 0.88)
- Proportional Aggregation of Preferences for Sequential Decision Making (AAAI 2024 · similarity 0.88)
- Participation Incentives in Approval-Based Committee Elections (AAAI 2024 · similarity 0.86)
- Verifying Proportionality in Temporal Voting (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.