Rigging Tournament Brackets for Weaker Players
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.
Cite
Text
Stanton and Williams. "Rigging Tournament Brackets for Weaker Players." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-069Markdown
[Stanton and Williams. "Rigging Tournament Brackets for Weaker Players." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/stanton2011ijcai-rigging/) doi:10.5591/978-1-57735-516-8/IJCAI11-069BibTeX
@inproceedings{stanton2011ijcai-rigging,
title = {{Rigging Tournament Brackets for Weaker Players}},
author = {Stanton, Isabelle and Williams, Virginia Vassilevska},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2011},
pages = {357-364},
doi = {10.5591/978-1-57735-516-8/IJCAI11-069},
url = {https://mlanthology.org/ijcai/2011/stanton2011ijcai-rigging/}
}