TY - GEN
T1 - Approximately strategyproof tournament rules in the probabilistic setting
AU - Ding, Kimberly
AU - Matthew Weinberg, S.
N1 - Publisher Copyright:
© Kimberly Ding and S. Matthew Weinberg.
PY - 2021/2/1
Y1 - 2021/2/1
N2 - We consider the manipulability of tournament rules which map the results of (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) [14, 15]. 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 [14] 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ε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.
AB - We consider the manipulability of tournament rules which map the results of (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) [14, 15]. 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 [14] 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ε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.
KW - Incentive compatibility
KW - Recursive analysis
KW - Social choice theory
KW - Tournaments
UR - http://www.scopus.com/inward/record.url?scp=85115234892&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85115234892&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITCS.2021.14
DO - 10.4230/LIPIcs.ITCS.2021.14
M3 - Conference contribution
AN - SCOPUS:85115234892
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 12th Innovations in Theoretical Computer Science Conference, ITCS 2021
A2 - Lee, James R.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 12th Innovations in Theoretical Computer Science Conference, ITCS 2021
Y2 - 6 January 2021 through 8 January 2021
ER -