publication . Preprint . Part of book or chapter of book . 2009

Manipulating Tournaments in Cup and Round Robin Competitions

Tyrel Russell; Toby Walsh;
Open Access English
  • Published: 08 Nov 2009
Abstract
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.
Subjects
ACM Computing Classification System: ComputerApplications_COMPUTERSINOTHERSYSTEMS
free text keywords: Computer Science - Artificial Intelligence, Computer Science - Computer Science and Game Theory, Computer Science - Multiagent Systems, I.2.4, Throwing, Time complexity, Artificial intelligence, business.industry, business, Mathematics, Polynomial
Download fromView all 2 versions
http://arxiv.org/pdf/0911.1582...
Part of book or chapter of book
Provider: UnpayWall
http://www.springerlink.com/in...
Part of book or chapter of book
Provider: Crossref

1. A. Altman, A. D. Procaccia, and M. Tennenholtz. Nonmanipulable Selections from a Tournament. In Proc. of 21st Intl. Joint Conf. on AI 2009.

2. J. J. Bartholdi, C. A. Tovey, and M. A. Trick. The computational difficulty of manipulating an election. Social Choice and Welfare, 6:227-241, 1989. [OpenAIRE]

3. V. Conitzer, T. Sandholm, and J. Lang. When are elections with few candidates hard to manipulate? JACM, 54:1-33, 2007.

4. P. Faliszewski, E. Hemaspaandra, and H. Schnoor. Copeland voting: Ties matter. In Proc. of the 7th Int. Conf. on Autonomous Agents and Multiagent Systems, 2008.

5. D. Gusfield and C. E. Martel. The structure and complexity of sports elimination numbers. Algorithmica, 32:73-86, 2002. [OpenAIRE]

6. N. Hazon, P. E. Dunne, S. Kraus, and M. Wooldridge. How to Rig Elections and Competitions. In Proc. of 2nd Int. Workshop on Computational Social Choice, 2008.

7. W. Kern and D. Paulusma. The computational complexity of the elimination problem in generalized sports competitions. Discrete Optimization, 1:205-214, 2004. [OpenAIRE]

8. J. Lang, M. S. Pini, F. Rossi, K. B. Venable, and T. Walsh. Winner Determination in Sequential Majority Voting. In Proc. of the 20th Int. Joint Conf. on AI, 2007.

9. S. T. McCormick. Fast algorithms for parametric scheduling come from extensions to parametric maximum flow. Operations Research, 47:744-756, 1999.

10. M. S. Pini, F. Rossi, K. B. Venable, and T. Walsh. Dealing with incomplete agents' preferences and an uncertain agenda in group decision making via sequential majority voting. In Proc. of the 11th Int. Conf. on Principles of Knowledge Representation and Reasoning, 2008.

11. P. Tang, Y. Shoham, and F. Lin. Team Competition. In Proc. of 8th Intl. Conf. on Autonomous Agents and Multiagent Systems, 2009.

12. T. Vu, A. Altman, and Y. Shoham. On the Complexity of Schedule Control Problems for Knockout Tournaments. In Proc. of 8th Intl. Conf. on Autonomous Agents and Multiagent Systems, 2009.

13. T. Walsh Where are the really hard manipulation problems? The phase transition in manipulating the veto rule. In Proc. of 21st Intl. Joint Conf. on AI 2009.

Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Preprint . Part of book or chapter of book . 2009

Manipulating Tournaments in Cup and Round Robin Competitions

Tyrel Russell; Toby Walsh;