Probabilistic Possible Winner Determination
Lists
Only you see this
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...