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

DOI10.1016/j.jal.2015.03.004zbMath1422.91225OpenAlexW1978717786MaRDI QIDQ901143

Nicholas Mattei, Martin Mundhenk, Andrew Klapper, Judy Goldsmith

Publication date: 23 December 2015

Published in: Journal of Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jal.2015.03.004

zbMATH Keywords

uncertaintyrankingtournamentscomputational social choicebribery

Mathematics Subject Classification ID

Voting theory (91B12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Social choice (91B14)

Related Items (8)

Tennis manipulation: can we help Serena Williams win another tournament? Or can we control a knockout tournament with reasonable complexity? ⋮ The complexity of priced control in elections ⋮ The complexity of probabilistic lobbying ⋮ The number of parties and decision-making in legislatures ⋮ Who Can Win a Single-Elimination Tournament? ⋮ Fixing balanced knockout and double elimination tournaments ⋮ Margin of victory for tournament solutions ⋮ Controlling sub-tournaments: easy or hard problem? Theoretical vs. practical analysis

Uses Software

• PrefLib

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Evaluation and decision models with multiple criteria. Stepping stones for the analyst.
• Choosing from a tournament
• How hard is it to control an election?
• Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions
• Tournament solutions and majority voting
• The complexity of probabilistic lobbying
• On the evaluation of election outcomes under uncertainty
• The computational difficulty of manipulating an election
• The computational complexity of the elimination problem in generalized sports competitions
• Determining Possible and Necessary Winners Given Partial Orders
• Complexity of finite-horizon Markov decision process problems
• When are elections with few candidates hard to manipulate?
• Manipulating Tournaments in Cup and Round Robin Competitions
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• How Hard Is Bribery in Elections?
• Manipulation of Voting Schemes: A General Result
• Reducibility among Combinatorial Problems
• The structure and complexity of sports elimination numbers

This page was built for publication: On the complexity of bribery and manipulation in tournaments with uncertain information