Probabilistic Possible Winner Determination

Yoram Bachrach, Nadja Betzler, Piotr Faliszewski

Abstract

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 #P-hardness 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.
BibTeX
@inproceedings{bachrach2010probabilistic,
  author = {Yoram Bachrach and Nadja Betzler and Piotr Faliszewski},
  title = {{Probabilistic Possible Winner Determination}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7609},
}

Loading related content...

Figure