Fixing Tournaments for Kings, Chokers, and More
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 561-566.
Abstract
We study the tournament fixing problem (TFP), which asks whether a tournament organizer can rig a single-elimination (SE) tournament such that their favorite player wins, simply by adjusting the initial seeding. Prior results give two perspectives of TFP: on the one hand, deciding whether an arbitrary player can win any SE tournament is known to be NP-complete; on the other hand, there are a number of known conditions, under which a player is guaranteed to win some SE tournament. We extend and connect both these lines of work. We show that for a number of structured variants of the problem, where our player is seemingly strong, deciding whether the player can win any tournament is still NP-complete. Dual to this hardness result, we characterize a new set of sufficient conditions for a player to win a tournament. Further, we give an improved exact algorithm for deciding whether a player can win a tournament.
@inproceedings{ijcai2015p85,
title = {Fixing Tournaments for Kings, Chokers, and More},
author = {Kim, Michael P. and Williams, Virginia Vassilevska},
booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-15}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Qiang Yang and Michael Wooldridge},
pages = {561--566},
year = {2015},
month = {7},
note = {Main Track},
url = {https://ijcai.org/proceedings/2015/85},
}
TY - CPAPER TI - Fixing Tournaments for Kings, Chokers, and More AU - Kim, Michael P. AU - Williams, Virginia Vassilevska T2 - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15 PB - International Joint Conferences on Artificial Intelligence PY - 2015 SP - 561 EP - 566 UR - https://ijcai.org/proceedings/2015/85 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
