TY - GEN

T1 - Approximately Strategyproof Tournament Rules with Multiple Prizes

AU - Dale, Emily

AU - Fielding, Jessica

AU - Ramakrishnan, Hari

AU - Sathyanarayanan, Sacheth

AU - Weinberg, S. Matthew

N1 - Publisher Copyright:
© 2022 Owner/Author.

PY - 2022/7/12

Y1 - 2022/7/12

N2 - 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).

AB - 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).

KW - incentive compatibility

KW - quick sort

KW - tournament rules

KW - voting theory

UR - http://www.scopus.com/inward/record.url?scp=85135002428&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85135002428&partnerID=8YFLogxK

U2 - 10.1145/3490486.3538242

DO - 10.1145/3490486.3538242

M3 - Conference contribution

AN - SCOPUS:85135002428

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

SP - 1082

EP - 1100

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

PB - Association for Computing Machinery, Inc

T2 - 23rd ACM Conference on Economics and Computation, EC 2022

Y2 - 11 July 2022 through 15 July 2022

ER -