TY - GEN
T1 - Probabilistic copeland tournaments
AU - Saarinen, Sam
AU - Goldsmith, Judy
AU - Tovey, Craig
N1 - Publisher Copyright:
Copyright © 2015, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.
PY - 2015
Y1 - 2015
N2 - We consider a probabilistic model of round-robin tournaments, or equivalently, Copeland voting, where candidates are the voters. We assume that the outcomes of each game or pairwise vote are jointly independent. In particular, we do not assume that votes arise from voters' ranked orderings of candidates. We can treat such games as pairwise preferences, without assuming any form of transitivity. We prove the #P-completeness of computing the probability of victory. As a consequence, it is #P-hani to manipulate a round-robin tournament by controlling the outcome of a subset of the games to raise the probability of winning above a particular threshhold. These results hold in the restricted case where all probabilities are zero, one half, or one.
AB - We consider a probabilistic model of round-robin tournaments, or equivalently, Copeland voting, where candidates are the voters. We assume that the outcomes of each game or pairwise vote are jointly independent. In particular, we do not assume that votes arise from voters' ranked orderings of candidates. We can treat such games as pairwise preferences, without assuming any form of transitivity. We prove the #P-completeness of computing the probability of victory. As a consequence, it is #P-hani to manipulate a round-robin tournament by controlling the outcome of a subset of the games to raise the probability of winning above a particular threshhold. These results hold in the restricted case where all probabilities are zero, one half, or one.
UR - http://www.scopus.com/inward/record.url?scp=84944703904&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84944703904&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84944703904
T3 - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
SP - 1851
EP - 1852
BT - AAMAS 2015 - Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems
A2 - Bordini, Rafael H.
A2 - Yolum, Pinar
A2 - Elkind, Edith
A2 - Weiss, Gerhard
T2 - 14th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015
Y2 - 4 May 2015 through 8 May 2015
ER -