Abstract
This paper investigates the computational complexity of multi-winner voting systems when voter preferences are incomplete. Traditional Approval-Based Committee (ABC) voting assumes complete knowledge of voter approvals. However, real-world data often contains gaps. The authors introduce three formal models of incompleteness—Poset Approval, Three-Valued Approval (3VA), and Linear Incomplete Approval—and analyze the complexity of identifying "possible" and "necessary" winning committees under various Thiele rules. The findings reveal that while determining possible winners is often NP-complete, identifying necessary winners remains computationally tractable across all studied models.
Introduction
In Approval-Based Committee (ABC) voting, voters select a subset of candidates they approve of, and a rule is used to select a committee of size $k$. Standard models assume perfect information, but practical applications—such as job shortlisting, filtering search results, or analyzing social media data—frequently involve missing data. A voter might not have evaluated every candidate, or their internal "approval threshold" might be unknown even if their relative preferences are clear.
This research addresses the challenge of collective decision-making under such uncertainty. The primary focus is on two types of queries:
- Possible Winners: Could a specific committee win in at least one valid completion of the partial preferences?
- Necessary Winners: Must a specific committee win in every valid completion of the partial preferences?
Models of Incompleteness
The authors propose three nested models to represent varying degrees of uncertainty in voter preferences:
- Poset Approval: The most general model. Candidates are partitioned into "Approved," "Disapproved," and "Unknown." The "Unknown" set is governed by a partial order (poset), restricting how they might be classified in a complete profile.
- Three-Valued Approval (3VA): A simpler model where "Unknown" candidates have no specified order. A voter could potentially approve any subset of these candidates.
- Linear Incomplete Approval: A model where "Unknown" candidates are linearly ordered. The uncertainty lies in the "cutoff point"—the voter approves all candidates above a certain rank, but that rank is unknown.
Computational Complexity and Key Insights
The study evaluates these models against Thiele rules, a class of scoring-based ABC rules that includes Approval Voting (AV), Proportional Approval Voting (PAV), and Chamberlin–Courant (CC).
A significant finding is the "Necessary" Advantage: for all studied ABC scoring rules, determining if a committee is a necessary winner is solvable in polynomial time. This suggests that even with incomplete data, we can efficiently identify committees that are guaranteed to be optimal.
In contrast, the complexity of finding Possible Winners depends heavily on the model and the specific voting rule:
- Approval Voting (AV): Finding possible winners is easy in the 3VA model but becomes NP-complete in the Linear and Poset models.
- Chamberlin–Courant (CC): This rule shows the opposite trend, where the problem is NP-complete in 3VA but tractable in the Linear model.
- Proportional Approval Voting (PAV): This rule remains generally difficult, with NP-completeness appearing even in the Linear model for certain committee sizes.
Fairness and Representation
Beyond winning committees, the paper examines fairness axioms. A core property in multi-winner voting is Justified Representation (JR), which ensures that large enough groups of voters with similar preferences are not ignored. The researchers demonstrate that verifying whether a committee satisfies JR is computationally easy (polynomial time) even in the most complex Poset model. This is a vital result for ensuring fair outcomes in automated decision systems where data might be sparse.
Conclusion
This work provides a comprehensive map of the computational landscape for ABC voting under uncertainty. While the structure of incompleteness can make identifying potential winners difficult, the tractability of necessary winners and fairness verification offers a path forward for robust collective choice. Future research may extend these results to stronger fairness axioms like Proportional Justified Representation (PJR) or explore other forms of uncertainty, such as unknown voter participation.
Summary updated