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 -