Who can win a single-elimination tournament?

DOI10.1137/16M1061783MaRDI QIDQ5348496zbMATH OpenWikidataFDO

Authors Michael P. Kim, Warut Suksompong, Virginia Vassilevska Williams

Publication date 18 August 2017

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.08416

zbMATH Keywords

knockout tournamentmanipulationsingle-elimination tournamentsports scheduling

Mathematics Subject Classification ID

2-person games (91A05) Social choice (91B14)

Abstract: A single-elimination (SE) tournament is a popular way to select a winner in both 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 their 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 emph{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=Theta(lnn/n)$; prior work only had such results for $pgeqOmega(sqrtlnn/n)$. We also establish new results for significantly more general generative models.

Recommendations

• Optimal seedings in elimination tournaments
• Designing fair 8- and 16-team knockout tournaments
• Fixing balanced knockout and double elimination tournaments
• Condorcet-consistent and approximately strategyproof tournament rules
• Comparing Draws for Single Elimination Tournaments

Cites work

• Choosing from a large tournament
• Fixing balanced knockout and double elimination tournaments
• Noisy sorting without resampling
• On the complexity of bribery and manipulation in tournaments with uncertain information
• The bipartisan set of a tournament game
• Tournament solutions
• Tournament solutions and majority voting

Cited in

(16)

• Margin of victory for tournament solutions
• Controlling sub-tournaments: easy or hard problem? Theoretical vs. practical analysis
• Tennis manipulation: can we help Serena Williams win another tournament? Or can we control a knockout tournament with reasonable complexity?
• Comparing Draws for Single Elimination Tournaments
• Condorcet-consistent and approximately strategyproof tournament rules
• scientific article; zbMATH DE number 842027 (Why is no real title available?)
• Knockout-tournament procedures for large-scale ranking and selection in parallel computing environments
• Single-Elimination Brackets Fail to Approximate Copeland Winner.
• Robust bounds on choosing from large tournaments
• Robust bounds on choosing from large tournaments
• Fixing knockout tournaments with seeds
• How can an elimination tournament favor a weaker player?
• Query complexity of tournament solutions
• Tight bounds on 3-team manipulations in randomized death match
• Voting profiles admitting all candidates as knockout winners
• Winning is not the only metric: the complexity of control manipulation in knockout tournaments for a redefined goal

This page was built for publication: Who can win a single-elimination tournament?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5348496)