TY - GEN

T1 - Approximately strategyproof tournament rules

T2 - 11th Innovations in Theoretical Computer Science Conference, ITCS 2020

AU - Schvartzman, Ariel

AU - Weinberg, S. Matthew

AU - Zlatin, Eitan

AU - Zuo, Albert

N1 - Funding Information:
Funding S. Matthew Weinberg: This work is supported by the National Science Foundation, under grant CNS-0435060, grant CCR-0325197 and grant EN-CS-0329609.
Publisher Copyright:
© Ariel Schvartzman, S. Matthew Weinberg, Eitan Zlatin, and Albert Zuo.

PY - 2020/1

Y1 - 2020/1

N2 - 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 n2 matches. Prior work defines a tournament rule to be k-SNM-α if no set of ≤ k teams can fix the ≤ k2 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) ≥ 2kk−−11 for all k, and [22] 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 [22], 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).

AB - 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 n2 matches. Prior work defines a tournament rule to be k-SNM-α if no set of ≤ k teams can fix the ≤ k2 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) ≥ 2kk−−11 for all k, and [22] 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 [22], 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).

KW - Cover-consistence

KW - Non-manipulability

KW - Strategyproof-ness

KW - Tournament design

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

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

U2 - 10.4230/LIPIcs.ITCS.2020.3

DO - 10.4230/LIPIcs.ITCS.2020.3

M3 - Conference contribution

AN - SCOPUS:85078061700

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 11th Innovations in Theoretical Computer Science Conference, ITCS 2020

A2 - Vidick, Thomas

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Y2 - 12 January 2020 through 14 January 2020

ER -