Individual Representation in Approval-Based Committee Voting

M. Brill, J. Israel, E. Micha, J. Peters
AAAI 2022
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.

Experiments:

Election type Culture Candidates Voters Instances Parameters
Approval Urn Model {50} {100} 500 None
Approval Candidate Interval (CI) {50} {100} 500 None
Approval Mallows {50} {100} 500 None
Approval Voter Interval (VI) {50} {100} 500 None
Approval Impartial Culture {50} {100} 500 None
Approval Euclidean 2D {50} {100} 500 None