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

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 s...

Full description

Saved in:
Bibliographic Details
Published in:Journal of applied logic 2015-12, Vol.13 (4), p.557-581
Main Authors: Mattei, Nicholas, Goldsmith, Judy, Klapper, Andrew, Mundhenk, Martin
Format: Article
Language:English
Subjects:
Bribery
Computational social choice
Ranking
Tournaments
Uncertainty
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1570-8683
1570-8691
DOI:10.1016/j.jal.2015.03.004