RECORD
Individual Representation in Approval-Based Committee Voting
Computer Science and Game Theory · Submitted 9 Dec 2021
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We show that checking whether an IR outcome exists is computationally intractable, and we verify that all common approval-based voting rules may fail to provide IR even in cases where this is possible.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
When selecting multiple candidates based on approval preferences of agents, the proportional representation of agents' opinions is an important and well-studied desideratum. Existing criteria for evaluating the representativeness of outcomes focus on groups of agents and demand that sufficiently large and cohesive groups are ''represented'' in the sense that candidates approved by some group members are selected. Crucially, these criteria say nothing about the representation of individual agents, even if these agents are members of groups that deserve representation. In this paper, we formalize the concept of individual representation (IR) and explore to which extent, and under which circumstances, it can be achieved. We show that checking whether an IR outcome exists is computationally intractable, and we verify that all common approval-based voting rules may fail to provide IR even in cases where this is possible. We then focus on domain restrictions and establish an interesting contrast between ''voter interval'' and ''candidate interval'' preferences. This contrast can also be observed in our experimental results, where we analyze the attainability of IR for realistic preference profiles.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | When selecting multiple candidates based on approval preferences of agents, the proportional representation of agents' opinions is an important and well-studied desideratum. | background 1.00 | 0.03 | 0.02 | asserted 1.00 |
| s1 | Existing criteria for evaluating the representativeness of outcomes focus on groups of agents and demand that sufficiently large and cohesive groups are ''represented'' in the sense that candidates approved by some group members are selected. | background 0.99 | 0.03 | 0.03 | asserted 1.00 |
| s2 | Crucially, these criteria say nothing about the representation of individual agents, even if these agents are members of groups that deserve representation. | gap 1.00 | 0.06 | 0.06 | asserted 1.00 |
| s3 | In this paper, we formalize the concept of individual representation (IR) and explore to which extent, and under which circumstances, it can be achieved. | contribution 1.00 | 0.83 | 0.09 | asserted 0.68 |
| s4 | We show that checking whether an IR outcome exists is computationally intractable, and we verify that all common approval-based voting rules may fail to provide IR even in cases where this is possible. | result 0.99 | 0.96 | 0.44 | asserted 0.99 |
| s5 | We then focus on domain restrictions and establish an interesting contrast between ''voter interval'' and ''candidate interval'' preferences. | contribution 0.90 | 0.80 | 0.07 | asserted 0.98 |
| s6 | This contrast can also be observed in our experimental results, where we analyze the attainability of IR for realistic preference profiles. | result 0.65 | 0.94 | 0.08 | asserted 0.92 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
When selecting multiple candidates based on approval preferences of agents, the proportional representation of agents' opinions is an important and well-studied desideratum. Existing criteria for evaluating the representativeness of outcomes focus on groups of agents and demand that sufficiently large and cohesive groups are ''represented'' in the sense that candidates approved by some group members are selected. Crucially, these criteria say nothing about the representation of individual agents, even if these agents are members of groups that deserve representation. In this paper, we formalize the concept of individual representation (IR) and explore to which extent, and under which circumstances, it can be achieved. We show that checking whether an IR outcome exists is computationally intractable, and we verify that all common approval-based voting rules may fail to provide IR even in cases where this is possible. We then focus on domain restrictions and establish an interesting contrast between ''voter interval'' and ''candidate interval'' preferences. This contrast can also be observed in our experimental results, where we analyze the attainability of IR for realistic preference profiles.
Human review
How the literature uses it
What this paper does with the arXiv papers it cites
What it cites · 3 sentences without a confident label
Cites as background 1 paper
-
[For the common rules defined in this paper, we refer the reader to the survey [ref] .]
Multi-Winner Voting with Approval Preferences · ABC Rules Violating IR · 0.95
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.