---
title: "Fixing Tournaments for Kings, Chokers, and More"
authors:
  - "Michael P. Kim"
  - "Virginia Vassilevska Williams"
doi: ""
url: "https://ijcai.org/proceedings/2015/85"
pdf: "https://ijcai.org/proceedings/2015/0085.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "561-566"
track: "Main Track"
keywords:
---

# Fixing Tournaments for Kings, Chokers, and More

Michael P. Kim, Virginia Vassilevska Williams

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, 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.