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

Nicholas Mattei, Judy Goldsmith, Andrew Klapper, Martin Mundhenk

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

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 languageEnglish
Pages (from-to)557-581
Number of pages25
JournalJournal of Applied Logic
Volume13
Issue number4
DOIs
StatePublished - 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

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