Rigging Tournament Brackets for Weaker Players

Stanton, Isabelle; Williams, Virginia Vassilevska

doi:10.5591/978-1-57735-516-8/IJCAI11-069

Rigging Tournament Brackets for Weaker Players

Isabelle Stanton, Virginia Vassilevska Williams

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 357-363.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-069

Abstract

Consider the following problem in game manipulation. A tournament designer who has full knowledge of the match outcomes between any possible pair of players would like to create a bracket for a balanced single-elimination tournament so that their favorite player will win.Although this problem has been studied in the areas of voting and tournament manipulation, it is still unknown whether it can be solved in polynomial time.We focus on identifying several general cases for which the tournament can always be rigged efficiently so that the given player wins. We give constructive proofs that, under some natural assumptions, if a player is ranked among the top K players, then one can efficiently rig the tournament for thegiven player, even when K is as large as 19% of the players.

Isabelle Stanton, and Virginia Vassilevska Williams. 2011. Rigging Tournament Brackets for Weaker Players. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 357–363. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-069

@inproceedings{ijcai2011p69,
  title     = {Rigging Tournament Brackets for Weaker Players},
  author    = {Stanton, Isabelle and Williams, Virginia Vassilevska},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {357--363},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-069},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-069},
}

TY  - CPAPER
TI  - Rigging Tournament Brackets for Weaker Players
AU  - Stanton, Isabelle
AU  - Williams, Virginia Vassilevska
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 357
EP  - 363
DO  - 10.5591/978-1-57735-516-8/IJCAI11-069
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-069
ER  -