2026-07-22T21:03:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11228 2024-03-06T10:47:44Z ddc:004 open_access

Single-Elimination Brackets Fail to Approximate Copeland Winner Hulett, Reyna Voting theory mechanism design query complexity approximation Single-elimination (SE) brackets appear commonly in both sports tournaments and the voting theory literature. In certain tournament models, they have been shown to select the unambiguously-strongest competitor with optimum probability. By contrast, we reevaluate SE brackets through the lens of approximation, where the goal is to select a winner who would beat the most other competitors in a round robin (i.e., maximize the Copeland score), and find them lacking. Our primary result establishes the approximation ratio of a randomly-seeded SE bracket is 2^{- Theta(sqrt{log n})}; this is underwhelming considering a 1/2 ratio is achieved by choosing a winner uniformly at random. We also establish that a generalized version of the SE bracket performs nearly as poorly, with an approximation ratio of 2^{- Omega(sqrt[4]{log n})}, addressing a decade-old open question in the voting tree literature. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Reyna Hulett 2019 Is Part Of LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2019.13 urn:nbn:de:0030-drops-112283 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.13 eng https://creativecommons.org/licenses/by/3.0/legalcode