Document Open Access Logo

Approximately Strategyproof Tournament Rules: On Large Manipulating Sets and Cover-Consistence

Authors Ariel Schvartzman, S. Matthew Weinberg, Eitan Zlatin, Albert Zuo

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.3.pdf
  • Filesize: 0.8 MB
  • 25 pages

Document Identifiers

Author Details

Ariel Schvartzman
  • Department of Computer Science, Princeton University, NJ, USA
S. Matthew Weinberg
  • Department of Computer Science, Princeton University, NJ, USA
Eitan Zlatin
  • Department of Computer Science, Princeton University, NJ, USA
Albert Zuo
  • Computer Science Department, Stanford University, CA, USA

Funding

  • Weinberg, S. Matthew: This work is supported by the National Science Foundation, under grant CNS-0435060, grant CCR-0325197 and grant EN-CS-0329609.

Acknowledgements

The authors are extremely grateful to Mikhail Khodak and Jon Schneider, who contributed both with many helpful discussions as well as code to help test the non-manipulability of tournament rules. The authors would also like to thank the anonymous reviewers for their feedback on extensions, clarifications and relevant references unknown to the authors.

Cite AsGet BibTex

Ariel Schvartzman, S. Matthew Weinberg, Eitan Zlatin, and Albert Zuo. Approximately Strategyproof Tournament Rules: On Large Manipulating Sets and Cover-Consistence. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 3:1-3:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.3

Abstract

We consider the manipulability of tournament rules, in which n teams play a round robin tournament and a winner is (possibly randomly) selected based on the outcome of all binom{n}{2} matches. Prior work defines a tournament rule to be k-SNM-α if no set of ≤ k teams can fix the ≤ binom{k}{2} matches among them to increase their probability of winning by >α and asks: for each k, what is the minimum α(k) such that a Condorcet-consistent (i.e. always selects a Condorcet winner when one exists) k-SNM-α(k) tournament rule exists? A simple example witnesses that α(k) ≥ (k-1)/(2k-1) for all k, and [Jon Schneider et al., 2017] conjectures that this is tight (and prove it is tight for k=2). Our first result refutes this conjecture: there exists a sufficiently large k such that no Condorcet-consistent tournament rule is k-SNM-1/2. Our second result leverages similar machinery to design a new tournament rule which is k-SNM-2/3 for all k (and this is the first tournament rule which is k-SNM-(<1) for all k). Our final result extends prior work, which proves that single-elimination bracket with random seeding is 2-SNM-1/3 [Jon Schneider et al., 2017], in a different direction by seeking a stronger notion of fairness than Condorcet-consistence. We design a new tournament rule, which we call Randomized-King-of-the-Hill, which is 2-SNM-1/3 and cover-consistent (the winner is an uncovered team with probability 1).

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic mechanism design
Keywords
  • Tournament design
  • Non-manipulability
  • Cover-consistence
  • Strategyproofness

Metrics

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

Related Versions

References

  1. Alon Altman and Robert Kleinberg. Nonmanipulable Randomized Tournament Selections. In AAAI Conference on Artificial Intelligence, 2010. URL: https://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. Kenneth J. Arrow. A Difficulty in the Concept of Social Welfare. Journal of Political Economy, 58(4):328-346, 1950. URL: http://www.jstor.org/stable/1828886.
  4. 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.
  5. Florian Brandl, Felix Brandt, and Hans Georg Seedig. Consistent Probabilistic Social Choice. CoRR, abs/1503.00694, 2015. URL: http://arxiv.org/abs/1503.00694.
  6. 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
  7. Laszlo Csato. European qualifiers 2018 FIFA World Cup qualification can be manipulated, 2017. URL: https://mpra.ub.uni-muenchen.de/id/eprint/83437.
  8. P. C. Fishburn. Probabilistic Social Choice Based on Simple Voting Comparisons. The Review of Economic Studies, 51(4):683-692, October 1984. URL: https://doi.org/10.2307/2297786.
  9. Peter C. Fishburn. Condorcet Social Choice Functions. SIAM Journal on Applied Mathematics, 33(3):469-489, 1977. URL: https://doi.org/10.1137/0133030.
  10. 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.
  11. Allan Gibbard. Manipulation of voting schemes: a general result. Econometrica, 41(4):587-601, 1973. Google Scholar
  12. Allan Gibbard. Manipulation of Schemes that Mix Voting with Chance. Econometrica, 45(3):665-681, 1977. URL: http://www.jstor.org/stable/1911681.
  13. Olivier Hudry. A note on "Banks winners in tournaments are difficult to recognize" by G. J. Woeginger. Social Choice and Welfare, 23(1):113-114, August 2004. URL: https://doi.org/10.1007/s00355-003-0241-y.
  14. 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.
  15. 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.
  16. 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.
  17. 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.
  18. Stephen B. Maurer. The King Chicken Theorems. Mathematics Magazine, 53(2):67-80, 1980. URL: http://www.jstor.org/stable/2689952.
  19. 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.
  20. 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.
  21. Mark Allen Satterthwaite. Strategy-proofness and Arrow’s conditions: Existence and Correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10(2):187-217, 1975. Google Scholar
  22. 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.
  23. 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.
  24. 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.
  25. 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.
  26. Gerhard J. Woeginger. Banks winners in tournaments are difficult to recognize. Social Choice and Welfare, 20(3):523-528, June 2003. URL: https://doi.org/10.1007/s003550200197.
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 Imprint Privacy Contact