Who Can Win a Single-Elimination Tournament?
Name
16m1061783.pdf
Description
Published version
Size
205.51 KB
Format
Adobe PDF
Checksum (MD5)
c68b8c37db006cd446c67075c2246b65
Author(s)
Kim, Michael P.
Suksompong, Warut
Williams, Virginia Vassilevska
Date Issued
August 2017
Journal
SIAM Journal on Discrete Mathematics
Publisher
Society for Industrial & Applied Mathematics (SIAM)
Citation
Kim, Michael P. et al., "Who Can Win a Single-Elimination Tournament?." SIAM Journal on Discrete Mathematics 31, 3 (August 2017): 1751–1764. © 2017 Society for Industrial and Applied Mathematics.
Version
Final published version
Abstract
A single-elimination (SE) tournament is a popular way to select a winner both in sports competitions and in elections. A natural and well-studied question is the tournament fixing problem (TFP): given the set of all pairwise match outcomes, can a tournament organizer rig an SE tournament by adjusting the initial seeding so that the organizer'fs favorite player wins? We prove new sufficient conditions on the pairwise match outcome information and the favorite player, under which there is guaranteed to be a seeding where the player wins the tournament. Our results greatly generalize previous results. We also investigate the relationship between the set of players that can win an SE tournament under some seeding (so-called SE winners) and other traditional tournament solutions. In addition, we generalize and strengthen prior work on probabilistic models for generating tournaments. For instance, we show that every player in an n player tournament generated by the Condorcet random model will be an SE winner even when the noise is as small as possible, p = Θ(lnn/n). prior work only had such results for p ≥ Ω(ln n/n). We also establish new results for significantly more general generative models. Keywords: sports scheduling; single-elimination tournament; knockout tournament; manipulation
MIT Department
Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Terms of Use
Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use.
Persistent DSpace Link
DOI of Published Version
https://dx.doi.org/10.1137/16m1061783
