Approximately Strategyproof Tournament Rules with Multiple Prizes

Emily Dale, Jessica Fielding, Hari Ramakrishnan, Sacheth Sathyanarayanan, S. Matthew Weinberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the manipulability of tournament rules which take the results of (n2) pairwise matches and select a ranking over the teams. Prior work designs simple tournament rules such that no pair of teams can manipulate the outcome of their match to improve their probability of being ranked first 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) [15,16]. We initiate the consideration of teams who may manipulate their match to improve their ranking (not necessarily to reach first). Specifically, teams compete for a monetary prize, and the ith ranked team takes home $p_i$ in prize money (pi ≥ pi+1 for all i). In this language, prior work designs tournament rules such that no pair of teams can manipulate the outcome of their match to improve their (collective) expected prize money by more than 1/3, when the price vector is 1,0,⋯, 0›. We design a simple tournament rule (that we call Nested Randomized King of the Hill) such that: a) no pair of teams can improve their collective expected prize money by more than 1/3 for any prize vector in [0,1]n, and b) no set of any teams can gain any prize money for the uniform prize vector with pi:=(n-i)/(n-1).

Original languageEnglish (US)
Title of host publicationEC 2022 - Proceedings of the 23rd ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Pages1082-1100
Number of pages19
ISBN (Electronic)9781450391504
DOIs
StatePublished - Jul 12 2022
Event23rd ACM Conference on Economics and Computation, EC 2022 - Boulder, United States
Duration: Jul 11 2022Jul 15 2022

Publication series

NameEC 2022 - Proceedings of the 23rd ACM Conference on Economics and Computation

Conference

Conference23rd ACM Conference on Economics and Computation, EC 2022
Country/TerritoryUnited States
CityBoulder
Period7/11/227/15/22

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Economics and Econometrics
  • Computational Mathematics
  • Statistics and Probability

Keywords

  • incentive compatibility
  • quick sort
  • tournament rules
  • voting theory

Fingerprint

Dive into the research topics of 'Approximately Strategyproof Tournament Rules with Multiple Prizes'. Together they form a unique fingerprint.

Cite this