Document Open Access Logo

Approximately Strategyproof Tournament Rules in the Probabilistic Setting

Authors Kimberly Ding, S. Matthew Weinberg

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2021.14.pdf
  • Filesize: 0.57 MB
  • 20 pages

Document Identifiers

Author Details

Kimberly Ding
  • Computer Science, Princeton University, NJ, USA
S. Matthew Weinberg
  • Computer Science, Princeton University, NJ, USA

Funding

  • Weinberg, S. Matthew: Supported by NSF CAREER Award CCF-1942497.

Cite As Get BibTex

Kimberly Ding and S. Matthew Weinberg. Approximately Strategyproof Tournament Rules in the Probabilistic Setting. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ITCS.2021.14

Abstract

We consider the manipulability of tournament rules which map the results of binom(n,2) pairwise matches and select a winner. Prior work designs simple tournament rules such that no pair of teams can manipulate the outcome of their match to improve their probability of winning by more than 1/3, and this is the best possible among any Condorcet-consistent tournament rule (which selects an undefeated team whenever one exists) [Jon Schneider et al., 2017; Ariel Schvartzman et al., 2020]. These lower bounds require the manipulators to know precisely the outcome of all future matches.
We take a beyond worst-case view and instead consider tournaments which are "close to uniform": the outcome of all matches are independent, and no team is believed to win any match with probability exceeding 1/2+ε. We show that Randomized Single Elimination Bracket [Jon Schneider et al., 2017] and a new tournament rule we term Randomized Death Match have the property that no pair of teams can manipulate the outcome of their match to improve their probability of winning by more than ε/3 + 2ε²/3, for all ε, and this is the best possible among any Condorcet-consistent tournament rule.
Our main technical contribution is a recursive framework to analyze the manipulability of certain forms of tournament rules. In addition to our main results, this view helps streamline previous analysis of Randomized Single Elimination Bracket, and may be of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory
Keywords
  • Tournaments
  • Incentive Compatibility
  • Recursive Analysis
  • Social Choice Theory

Metrics

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

References

  1. Alon Altman and Robert Kleinberg. Nonmanipulable randomized tournament selections. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010. AAAI Press, 2010. URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/view/1703.
  2. Alon Altman, Ariel D. Procaccia, and Moshe Tennenholtz. Nonmanipulable selections from a tournament. In Proceedings of the 21st International Joint Conference on Artifical Intelligence, IJCAI'09, pages 27-32, San Francisco, CA, USA, 2009. Morgan Kaufmann Publishers Inc. URL: http://dl.acm.org/citation.cfm?id=1661445.1661451.
  3. J. S. Banks. Sophisticated voting outcomes and agenda control. Social Choice and Welfare, 1(4):295-306, December 1985. URL: https://doi.org/10.1007/BF00649265.
  4. Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D Procaccia. Handbook of Computational Social Choice. Cambridge University Press, 2016. Google Scholar
  5. Laszlo Csato. European qualifiers 2018 FIFA world cup qualification can be manipulated, September 2017. URL: https://mpra.ub.uni-muenchen.de/id/eprint/83437.
  6. Peter C. Fishburn. Condorcet social choice functions. SIAM Journal on Applied Mathematics, 33(3):469-489, 1977. URL: https://doi.org/10.1137/0133030.
  7. David C. Fisher and Jennifer Ryan. Optimal strategies for a generalized “scissors, paper, and stone” game. The American Mathematical Monthly, 99(10):935-942, 1992. URL: https://doi.org/10.1080/00029890.1992.11995957.
  8. Michael P. Kim, Warut Suksompong, and Virginia Vassilevska Williams. Who can win a single-elimination tournament? In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA., pages 516-522, 2016. URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12194.
  9. Michael P. Kim and Virginia Vassilevska Williams. Fixing tournaments for kings, chokers, and more. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, pages 561-567, 2015. URL: http://ijcai.org/Abstract/15/085.
  10. G. Laffond, J.F. Laslier, and M. Le Breton. The bipartisan set of a tournament game. Games and Economic Behavior, 5(1):182-201, 1993. URL: https://doi.org/10.1006/game.1993.1010.
  11. J.F. Laslier. Tournament Solutions and Majority Voting. Studies in Economic Theory (Berlin, Germany), 7. Springer, 1997. URL: https://books.google.com/books?id=vYbGAAAAIAAJ.
  12. Nicholas R. Miller. A new solution set for tournaments and majority voting: Further graph-theoretical approaches to the theory of voting. American Journal of Political Science, 24(1):68-96, 1980. URL: http://www.jstor.org/stable/2110925.
  13. Marc Pauly. Can strategizing in round-robin subtournaments be avoided? Social Choice and Welfare, 43(1):29-46, 2014. URL: http://EconPapers.repec.org/RePEc:spr:sochwe:v:43:y:2014:i:1:p:29-46.
  14. Jon Schneider, Ariel Schvartzman, and S. Matthew Weinberg. Condorcet-consistent and approximately strategyproof tournament rules. In 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, pages 35:1-35:20, 2017. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.35.
  15. Ariel Schvartzman, S. Matthew Weinberg, Eitan Zlatin, and Albert Zuo. Approximately strategyproof tournament rules: On large manipulating sets and cover-consistence. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 3:1-3:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.3.
  16. Kenneth A. Shepsle and Barry R. Weingast. Uncovered sets and sophisticated voting outcomes with implications for agenda institutions. American Journal of Political Science, 28(1):49-74, 1984. URL: http://www.jstor.org/stable/2110787.
  17. Isabelle Stanton and Virginia Vassilevska Williams. Rigging tournament brackets for weaker players. In IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, pages 357-364, 2011. URL: https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-069.
  18. Virginia Vassilevska Williams. Fixing a tournament. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010, 2010. URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/view/1726.
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