Document Open Access Logo

Single-Elimination Brackets Fail to Approximate Copeland Winner

Author Reyna Hulett

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.13.pdf
  • Filesize: 473 kB
  • 20 pages

Document Identifiers

Author Details

Reyna Hulett
  • Department of Computer Science, Stanford University, CA, USA

Funding

Supported in part by an NSF Graduate Research Fellowship under grant DGE-1656518.

Acknowledgements

I want to thank Benjamin Plaut and Mary Wootters for many helpful discussions.

Cite As Get BibTex

Reyna Hulett. Single-Elimination Brackets Fail to Approximate Copeland Winner. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.13

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Solution concepts in game theory
  • Mathematics of computing → Approximation algorithms
Keywords
  • Voting theory
  • mechanism design
  • query complexity
  • approximation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Micah Adler, Peter Gemmell, Mor Harchol-Balter, Richard M. Karp, and Claire Kenyon. Selection in the Presence of Noise: The Design of Playoff Systems. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '94, pages 564-572. Society for Industrial and Applied Mathematics, 1994. URL: http://dl.acm.org/citation.cfm?id=314464.314650.
  2. Haris Aziz, Serge Gaspers, Simon Mackenzie, Nicholas Mattei, Paul Stursberg, and Toby Walsh. Fixing a Balanced Knockout Tournament. In Proceedings of the 28th AAAI Conference on Artificial Intelligence, AAAI'14, pages 552-558. AAAI Press, 2014. URL: http://dl.acm.org/citation.cfm?id=2893873.2893960.
  3. Ramachandran Balasubramanian, Venkatesh Raman, and G Srinivasaragavan. Finding Scores in Tournaments. Journal of Algorithms, 24(2):380-394, 1997. URL: https://doi.org/10.1006/jagm.1997.0865.
  4. Palash Dey. Query Complexity of Tournament Solutions. Proceedings of the 31st AAAI Conference on Artificial Intelligence, pages 2992-2998, 2017. URL: https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14180.
  5. Felix Fischer, Ariel D. Procaccia, and Alex Samorodnitsky. On Voting Caterpillars: Approximating Maximum Degree in a Tournament by Binary Trees. In Ulle Endriss and Paul W. Goldberg, editors, Proceedings of the 2nd International Workshop on Computational Social Choice, pages 253-264, 2008. Google Scholar
  6. Felix Fischer, Ariel D. Procaccia, and Alex Samorodnitsky. A New Perspective on Implementation by Voting Trees. Random Structures & Algorithms, 39(1):59-82, 2011. URL: https://doi.org/10.1002/rsa.20336.
  7. Dishant Goyal, Varunkumar Jayapaul, and Venkatesh Raman. Elusiveness of Finding Degrees. In Daya Gaur and N.S. Narayanaswamy, editors, Algorithms and Discrete Applied Mathematics, pages 242-253, Cham, 2017. Springer International Publishing. Google Scholar
  8. Sean Horan. Implementation of Majority Voting Rules, 2013. Google Scholar
  9. Michael Kim, Warut Suksompong, and Virginia Vassilevska Williams. Who Can Win a Single-Elimination Tournament? SIAM Journal on Discrete Mathematics, 31(3):1751-1764, 2017. URL: https://doi.org/10.1137/16M1061783.
  10. Michael Kim and Virginia Vassilevska Williams. Fixing Tournaments for Kings, Chokers, and More. Proceedings of the 24th International Joint Conference on Artificial Intelligence, pages 561-567, 2015. URL: https://www.ijcai.org/Proceedings/15/Papers/085.pdf.
  11. Justin Kruger and Stéphane Airiau. Refinements and Randomised Versions of Some Tournament Solutions. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, AAMAS '17, pages 1584-1586. IFAAMS, 2017. URL: http://dl.acm.org/citation.cfm?id=3091125.3091370.
  12. Willi Maurer. On Most Effective Tournament Plans With Fewer Games than Competitors. The Annals of Statistics, 3(3):717-727, 1975. URL: http://www.jstor.org/stable/2958441.
  13. Ariel D. Procaccia. A Note on the Query Complexity of the Condorcet Winner Problem. Information Processing Letters, 108(6):390-393, 2008. URL: https://doi.org/10.1016/j.ipl.2008.07.012.
  14. Dmitry Ryvkin. The Predictive Power of Noisy Elimination Tournaments. CERGE-EI Working Papers wp252, The Center for Economic Research and Graduate Education - Economics Institute, Prague, March 2005. URL: https://doi.org/10.2139/ssrn.849225.
  15. Sanjay Srivastava and Michael A. Trick. Sophisticated Voting Rules: the Case of Two Tournaments. Social Choice and Welfare, 13(3):275-289, June 1996. URL: https://doi.org/10.1007/BF00179232.
  16. Isabelle Stanton and Virginia Vassilevska Williams. Manipulating Single-Elimination Tournaments in the Braverman-Mossel Model. In Ulle Endriss Edith Elkind and Jérôme Lang, editors, Proceedings of the IJCAI-2011 Workshop on Social Choice and AI, pages 87-92, 2011. Google Scholar
  17. Isabelle Stanton and Virginia Vassilevska Williams. Manipulating Stochastically Generated Single-Elimination Tournaments for Nearly All Players. In Ning Chen, Edith Elkind, and Elias Koutsoupias, editors, Internet and Network Economics, pages 326-337, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. Google Scholar
  18. Isabelle Stanton and Virginia Vassilevska Williams. Rigging Tournament Brackets for Weaker Players. In Toby Walsh, editor, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, pages 357-364. IJCAI/AAAI, 2011. URL: https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-069.
  19. Virginia Vassilevska Williams. Fixing a Tournament. In Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI'10, pages 895-900. AAAI Press, 2010. URL: http://dl.acm.org/citation.cfm?id=2898607.2898751.
  20. Thuc Vu, Alon Altman, and Yoav Shoham. On the Agenda Control Problem for Knockout Tournaments. In Ulle Endriss and Paul W. Goldberg, editors, Proceedings of the 2nd International Workshop on Computational Social Choice, pages 415-426, 2008. Google Scholar
  21. Thuc Vu and Yoav Shoham. Fair Seeding in Knockout Tournaments. ACM Transactions on Intelligent Systems and Technology, 3(1):9:1-9:17, October 2011. URL: https://doi.org/10.1145/2036264.2036273.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact