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: | , , |
|---|---|
| Format: | Journal article |
| Published: |
Society for Industrial and Applied Mathematics
2017
|
| _version_ | 1826289038282194944 |
|---|---|
| author | Kim, M Suksompong, W Williams, V |
| author_facet | Kim, M Suksompong, W Williams, V |
| author_sort | Kim, M |
| collection | OXFORD |
| 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. |
| first_indexed | 2024-03-07T02:22:49Z |
| format | Journal article |
| id | oxford-uuid:a4895b58-5b04-45b1-84f5-a10beb15c53c |
| institution | University of Oxford |
| last_indexed | 2024-03-07T02:22:49Z |
| publishDate | 2017 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | oxford-uuid:a4895b58-5b04-45b1-84f5-a10beb15c53c2022-03-27T02:34:28ZWho can win a single-elimination tournament?Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:a4895b58-5b04-45b1-84f5-a10beb15c53cSymplectic Elements at OxfordSociety for Industrial and Applied Mathematics2017Kim, MSuksompong, WWilliams, VA 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. |
| spellingShingle | Kim, M Suksompong, W Williams, V 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 |
| work_keys_str_mv | AT kimm whocanwinasingleeliminationtournament AT suksompongw whocanwinasingleeliminationtournament AT williamsv whocanwinasingleeliminationtournament |