Possible Winners in Approval Voting

International audienceGiven the knowledge of the preferences of a set of voters over a set of candidates, and assuming that voters cast sincere approval ballots, what can we say about the possible (co-)winners? The outcome depends on the number of candidates each voter will approve. Whereas it is easy to know who can be a unique winner, we show that deciding whether a set of at least two candidates can be the set of co-winners is computationally hard. If, in addition, we have a probability distribution over the number of candidates approved by each voter, we obtain a probability distribution over winners; we study the shape of this probability distribution empirically, for the impartial culture assumption. We study variants of the problem where the number of candidates approved by each voter is upper and/or lower bounded. We generalize some of our results to multiwinner approval voting