Abstract
Approval-Based Committee (ABC) voting traditionally assumes that voter preferences are known with certainty. However, real-world data often involves noise, historical averages, or probabilistic predictions. This paper investigates ABC voting under four distinct models of uncertainty: Joint Probability, Lottery, Candidate Probability, and Three-Valued Approval (3VA). The authors analyze the computational complexity of ensuring fairness, specifically focusing on the Justified Representation (JR) axiom and its variants. The results demonstrate that while checking for potential fairness is often tractable, finding committees that are guaranteed to be fair or calculating the exact probability of fairness is computationally demanding, typically falling into NP-hard or #P-complete categories.
Introduction
In computational social choice, Approval-Based Committee (ABC) voting is a fundamental mechanism for selecting a fixed-size committee based on voter approval. The standard assumption is that each voter provides a deterministic set of approved candidates. In practice, however, preferences may be uncertain due to noisy data, historical modeling, or representative voting for divided groups. Aziz et al., in "Approval-Based Committee Voting under Uncertainty," address this gap by formalizing how to select fair committees when voter preferences are probabilistic.
Models of Uncertainty
The authors propose four hierarchical models to capture different levels of uncertainty:
- Joint Probability Model: The most general model, providing a single probability distribution over all possible voting profiles for the entire electorate.
- Lottery Model: Each voter has an independent probability distribution over different sets of candidates they might approve.
- Candidate-Probability Model: Each voter approves each candidate independently with a specific probability ($p_{i,c}$).
- Three-Valued Approval (3VA): A simplified version where a voter approves, disapproves, or is "unknown" (effectively a 50/50 chance).
Fairness Axioms and Computational Problems
The primary fairness criterion studied is Justified Representation (JR). JR requires that if a sufficiently large group of voters agrees on at least one candidate, the elected committee must include at least one candidate approved by that group. The paper extends this to probabilistic settings by defining several key problems:
- JR-Probability: Calculating the exact probability that a given committee satisfies JR.
- IsPossJR / IsNecJR: Determining if a committee satisfies JR in at least one possible world (possibly) or all possible worlds (necessarily).
- ExistsNecJR: Determining if there exists any committee that satisfies JR in all possible worlds.
- MaxJR: Finding the committee with the highest probability of satisfying JR.
Complexity Analysis and Key Results
The researchers establish a comprehensive "complexity map" for these problems across the four models. A significant finding is that while checking if a committee might be fair (IsPossJR) is generally easy (in P) for most models, it becomes NP-complete in the Lottery model due to complex dependencies. Finding a committee that is guaranteed to be fair (ExistsNecJR) is NP-complete across all models, even with minimal uncertainty.
Furthermore, calculating the exact probability of JR (JR-Probability) is #P-complete for the Candidate-Probability model, indicating that exact computation is as hard as counting solutions to NP-complete problems. Stronger fairness notions like Proportional Justified Representation (PJR) and Extended Justified Representation (EJR) further increase complexity, often leading to coNP-hardness.
Conclusion and Future Directions
This work highlights the significant computational hurdles introduced by probabilistic realism in social choice. While the Joint Probability model allows for some polynomial-time solutions when scenarios are explicitly listed, more compact models like Candidate-Probability quickly become intractable. Future research may focus on approximation algorithms to find committees with near-optimal fairness probabilities or identifying fixed-parameter tractable (FPT) cases that remain manageable in practice. For AI systems relying on noisy preference data, these results underscore the difficulty of guaranteeing fair representation.
Summary updated