Probabilistic Possible Winner Determination

We study the computational complexity of the counting version of the POSSIBLE-WINNER problem for elections. In the POSSIBLE-WINNER problem we are given a profile of voters, each with a partial preference order, and ask if there are linear extensions of the votes such that a designated candidate wins. We also analyze a special case of POSSIBLE-WINNER, the MANIPULATION problem. We provide polynomial-time algorithms for counting manipulations in a class of scoring protocols and in several other voting rules. We show #Phardness of the counting variant of POSSIBLE-WINNER for plurality and veto and give a simple yet general and practically useful randomized algorithm for a variant of POSSIBLE- WINNER for all voting rules for which a winner can be computed in polynomial time.

Authors

• Yoram Bachrach Meta FAIR
• Nadja Betzler
• Piotr Faliszewski AGH University of Krakow

Keywords

No keywords are indexed for this paper.