Approval-Based Committee Voting under Incomplete Information

Approval-based committee (ABC) voting represents a well-studied multiwinner election setting, where a subset of candidates of a predetermined size, a so-called committee, needs to be chosen based on the approval preferences of a set of voters [23]. Traditionally, ABC voting is studied in the context where we know, for each voter and each candidate, whether the voter approves the candidate or not. In this paper, we investigate the situation where the approval information is incomplete. Specifically, we assume that each voter is associated with a set of approved candidates, a set of disapproved candidates, and a set of candidates where the voter's stand is unknown, hereafter referred to as the unknown candidates. Moreover, we may have (partial) ordinal information on voters' preferences among the unknown candidates, restricting the "valid" completions of voters' approval sets. When the number of candidates is large, unknown candidates are likely to exist because voters are not aware of or not familiar with, and therefore cannot evaluate, all candidates. In particular, this holds in scenarios where candidates join the election over time, and voter preferences over new candidates have not been elicited [16].