Improving the Odds: Fairness in Tournament Design

Abstract

Sports tournaments are some of the most exciting events in the world. From local competitions such as high school basketball tournaments to international competitions like the FIFA World Cup, billions of people from a wide variety of backgrounds come together to compete or cheer on their favorite teams. With so much attention on these events, the study of tournament design becomes critical; the quality of a tournament format, or tournament rule can have a big impact on both tangible metrics like viewership and sponsorship, and more abstract metrics, like fairness for the competitors.

We analyze fair tournament design in two settings. We first look at fairness in the context of incentive compatibility by considering how teams should behave to maximize their chances of winning a tournament. We present a new tournament rule that improves on previously-known tradeoffs between fairness and strategyproofness.

We then consider tournament design with the goal of optimizing for fairness across all teams (as opposed to fairness for strong teams), and define the Welfare-Maximizing Bracket problem, which we conjecture to be NP-hard. We provide two approximation lower bounds, and give three linear programming relaxation heuristics for better approximations.