On the complexity of bribery and manipulation in tournaments with uncertain information

Nicholas Mattei, Judy Goldsmith, Andrew Klapper

Research output: Contribution to conferencePaperpeer-review

Abstract

We study the computational complexity of optimal bribery and manipulation schemes for sports tournaments with uncertain information: cup; challenge or caterpillar; and round robin. Our results carry over to the equivalent voting rules: sequential pair-wise elections, cup, and Copeland, when the set of candidates is exactly the set of voters. This restriction creates new difficulties for most existing algorithms. The complexity of bribery and manipulation are well studied, almost always assuming deterministic information about votes and results. We assume that for candidates i and j the probability that i beats j and the costs of lowering each probability by fixed increments are known to the manipulators. We provide complexity analyses for cup, challenge, and round robin competitions ranging from polynomial time to NP PP. This shows that the introduction of uncertainty into the reasoning process drastically increases the complexity of bribery problems in some instances.

Original languageEnglish
Pages24-29
Number of pages6
StatePublished - 2012
Event2012 AAAI Fall Symposium - Arlington, VA, United States
Duration: Nov 2 2012Nov 4 2012

Conference

Conference2012 AAAI Fall Symposium
Country/TerritoryUnited States
CityArlington, VA
Period11/2/1211/4/12

ASJC Scopus subject areas

  • General Engineering

Fingerprint

Dive into the research topics of 'On the complexity of bribery and manipulation in tournaments with uncertain information'. Together they form a unique fingerprint.

Cite this