Manipulating Tournaments in Cup and Round Robin Competitions

In sports competitions, teams can manipulate the result by, for instance, throwing games. We show that we can decide how to manipulate round robin and cup competitions, two of the most popular types of sporting competitions in polynomial time. In addition, we show that finding the minimal number of games that need to be thrown to manipulate the result can also be determined in polynomial time. Finally, we show that there are several different variations of standard cup competitions where manipulation remains polynomial.

• Publication year

  2009

• Venue

  Algorithmic Decision Theory

• Publication date

  2009-10-13

• Fields of study

  Mathematics, Computer Science, Engineering

• Identifiers
  DOI 10.1007/978-3-642-04428-1_3arXiv 0911.1582
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Where Are the Really Hard Manipulation Problems? The Phase Transition in Manipulating the Veto Rule

  2009cited by this paper
• On the complexity of schedule control problems for knockout tournaments

  2009influential reference
• Nonmanipulable Selections from a Tournament

  2009cited by this paper
• Hong Kong University of Science and Technology Clear Water Bay

  2009cited by this paper
• Dealing with Incomplete Agents' Preferences and an Uncertain Agenda in Group Decision Making via Sequential Majority Voting

  2008cited by this paper
• Copeland voting: ties matter

  2008cited by this paper
• How to Rig Elections and Competitions

  2008cited by this paper
• Winner Determination in Sequential Majority Voting

  2007cited by this paper
• When are elections with few candidates hard to manipulate?

  2007influential reference
• The computational complexity of the elimination problem in generalized sports competitions

  2004influential reference
• The complexity of homomorphism and constraint satisfaction problems seen from the other side

  2003cited by this paper
• The Structure and Complexity of Sports Elimination Numbers

  2001cited by this paper
• Fast algorithms for parametric scheduling come from extensions to parametric maximum flow

  1996cited by this paper
• The computational difficulty of manipulating an election

  1989cited by this paper

• Robust Value Maximization in Challenge the Champ Tournaments with Probabilistic Outcomes

  2026cites this paper
• Manipulation unraveled: A new framework to analyze the impact of tournament design on manipulation opportunities

  2025cites this paper
• Tournament Robustness via Redundancy

  2025cites this paper
• Maximizing Value in Challenge the Champ Tournaments

  2025cites this paper
• Adaptive Manipulation for Coalitions in Knockout Tournaments

  2024influential citation
• Parameterized Analysis of Bribery in Challenge the Champ Tournaments

  2024cites this paper
• Tournaments in Computational Social Choice: Recent Developments

  2021cites this paper
• A paradox of tournament seeding

  2020cites this paper
• Refining Tournament Solutions via Margin of Victory

  2019cites this paper
• Bribery in Balanced Knockout Tournaments

  2019cites this paper
• Controlling sub-tournaments: easy or hard problem?

  2019cites this paper
• Fixing balanced knockout and double elimination tournaments

  2018cites this paper
• Winning a Tournament by Any Means Necessary

  2018cites this paper
• Incentive compatible designs for FIFA and UEFA tournament qualifiers

  2018cites this paper
• Tennis manipulation: can we help serena williams win another tournament?

  2017cites this paper
• European qualifiers to the 2018 FIFA World Cup can be manipulated

  2017cites this paper
• Winning by Losing

  2017cites this paper
• Handbook of Computational Social Choice

  2016cites this paper
• Tournament solutions based on cooperative game theory

  2015cites this paper
• Can strategizing in round-robin subtournaments be avoided?

  2014cites this paper
• Implementation of Majority Voting Rules

  2013cites this paper
• The structure, efficacy, and manipulation of double-elimination tournaments

  2013cites this paper
• On the complexity of bribery and manipulation in tournaments with uncertain information

  2012cites this paper
• Graph Algorithms in the Internet Age

  2012cites this paper
• Decision making under uncertainty: theoretical and empirical results on social choice, manipulation, and bribery

  2012cites this paper
• Detecting Manipulation in Cup and Round Robin Sports Competitions

  2012cites this paper
• Decision Making under Uncertainty: Social Choice and Manipulation

  2011cites this paper
• Manipulating Stochastically Generated Single-Elimination Tournaments for Nearly All Players

  2011cites this paper
• Manipulating Single-Elimination Tournaments in the Braverman-Mossel Model

  2011cites this paper
• A Short Introduction to Preferences: Between Artificial Intelligence and Social Choice

  2011cites this paper
• Proceedings of the IJCAI-2011 Workshop on Social Choice and Artificial Intelligence

  2011cites this paper
• A Computational Study of Problems in Sports

  2010cites this paper
• Is computational complexity a barrier to manipulation?

  2010cites this paper
• Where are the hard manipulation problems?

  2010cites this paper
• Discrete Algorithms Seminar

  2009cites this paper
• Determining Possible and Necessary Winners under Common Voting Rules Given Partial Orders

  2008cites this paper