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

DOI10.1016/j.jal.2015.03.004zbMath1422.91225MaRDI 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

uncertainty; ranking; tournaments; computational social choice; bribery

Mathematics Subject Classification ID

91B12: Voting theory

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

91B14: Social choice

Related Items

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

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