Who Can Win a Single-Elimination Tournament?
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 adjustin...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Society for Industrial & Applied Mathematics (SIAM)
2020
|
| Online Access: | https://hdl.handle.net/1721.1/125608 |
| _version_ | 1811080024188518400 |
|---|---|
| author | Kim, Michael P. Suksompong, Warut Williams, Virginia Vassilevska |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Kim, Michael P. Suksompong, Warut Williams, Virginia Vassilevska |
| author_sort | Kim, Michael P. |
| collection | MIT |
| description | 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 |
| first_indexed | 2024-09-23T11:24:29Z |
| format | Article |
| id | mit-1721.1/125608 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:24:29Z |
| publishDate | 2020 |
| publisher | Society for Industrial & Applied Mathematics (SIAM) |
| record_format | dspace |
| spelling | mit-1721.1/1256082022-10-01T03:24:03Z Who Can Win a Single-Elimination Tournament? Kim, Michael P. Suksompong, Warut Williams, Virginia Vassilevska Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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 NSF (Grant CCF-1417238) NSF (Grant CCF-1528078) NSF (Grant CCF-1514339) BSF (Grant BSF:2012338) 2020-06-02T14:32:14Z 2020-06-02T14:32:14Z 2017-08 2016-02 2019-07-09T13:17:13Z Article http://purl.org/eprint/type/JournalArticle 0895-4801 1095-7146 https://hdl.handle.net/1721.1/125608 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. en https://dx.doi.org/10.1137/16m1061783 SIAM Journal on Discrete Mathematics 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. application/pdf Society for Industrial & Applied Mathematics (SIAM) SIAM |
| spellingShingle | Kim, Michael P. Suksompong, Warut Williams, Virginia Vassilevska Who Can Win a Single-Elimination Tournament? |
| title | Who Can Win a Single-Elimination Tournament? |
| title_full | Who Can Win a Single-Elimination Tournament? |
| title_fullStr | Who Can Win a Single-Elimination Tournament? |
| title_full_unstemmed | Who Can Win a Single-Elimination Tournament? |
| title_short | Who Can Win a Single-Elimination Tournament? |
| title_sort | who can win a single elimination tournament |
| url | https://hdl.handle.net/1721.1/125608 |
| work_keys_str_mv | AT kimmichaelp whocanwinasingleeliminationtournament AT suksompongwarut whocanwinasingleeliminationtournament AT williamsvirginiavassilevska whocanwinasingleeliminationtournament |