Abstract
We study the computational complexity of bribery and manipulation schemes for sports tournaments with uncertain information. We introduce a general probabilistic model for multi-round tournaments and consider several special types of tournament: challenge (or caterpillar); cup; and round robin. In some ways, tournaments are similar to the sequential pair-wise, cup and Copeland voting rules. The complexity of bribery and manipulation are well studied for elections, usually assuming deterministic information about votes and results. We assume that for tournament entrants 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 several problems related to manipulation and bribery for the various types of tournaments. Complexities range from probabilistic log space to NPPP. 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 (from-to) | 557-581 |
Number of pages | 25 |
Journal | Journal of Applied Logic |
Volume | 13 |
Issue number | 4 |
DOIs | |
State | Published - Dec 2015 |
Bibliographical note
Publisher Copyright:© 2015 Elsevier B.V.
Keywords
- Bribery
- Computational social choice
- Ranking
- Tournaments
- Uncertainty
ASJC Scopus subject areas
- Logic
- Applied Mathematics