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 language | English |
---|---|
Pages | 24-29 |
Number of pages | 6 |
State | Published - 2012 |
Event | 2012 AAAI Fall Symposium - Arlington, VA, United States Duration: Nov 2 2012 → Nov 4 2012 |
Conference
Conference | 2012 AAAI Fall Symposium |
---|---|
Country/Territory | United States |
City | Arlington, VA |
Period | 11/2/12 → 11/4/12 |
ASJC Scopus subject areas
- General Engineering