Probabilistic copeland tournaments

Sam Saarinen, Judy Goldsmith, Craig Tovey

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationAAMAS 2015 - Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems
EditorsRafael H. Bordini, Pinar Yolum, Edith Elkind, Gerhard Weiss
Pages1851-1852
Number of pages2
ISBN (Electronic)9781450337717
StatePublished - 2015
Event14th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015 - Istanbul, Turkey
Duration: May 4 2015May 8 2015

Publication series

NameProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Volume3
ISSN (Print)1548-8403
ISSN (Electronic)1558-2914

Conference

Conference14th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015
Country/TerritoryTurkey
CityIstanbul
Period5/4/155/8/15

Bibliographical note

Publisher Copyright:
Copyright © 2015, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.

Funding

FundersFunder number
National Science Foundation (NSF)CCF-1215985, CMMI1335301

    ASJC Scopus subject areas

    • Artificial Intelligence
    • Software
    • Control and Systems Engineering

    Fingerprint

    Dive into the research topics of 'Probabilistic copeland tournaments'. Together they form a unique fingerprint.

    Cite this