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 -