首页    期刊浏览 2024年11月05日 星期二
登录注册

文章基本信息

  • 标题:Approximately Strategyproof Tournament Rules: On Large Manipulating Sets and Cover-Consistence
  • 本地全文:下载
  • 作者:Ariel Schvartzman ; S. Matthew Weinberg ; Eitan Zlatin
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2020
  • 卷号:151
  • 页码:1-25
  • DOI:10.4230/LIPIcs.ITCS.2020.3
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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 binom{n}{2} matches. Prior work defines a tournament rule to be k-SNM-α if no set of ≤ k teams can fix the ≤ binom{k}{2} 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) ≥ (k-1)/(2k-1) for all k, and [Jon Schneider et al., 2017] 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 [Jon Schneider et al., 2017], 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).
  • 关键词:Tournament design; Non-manipulability; Cover-consistence; Strategyproofness
国家哲学社会科学文献中心版权所有