1 Search Results for "Ding, Kimberly"

Document
DOI: 10.4230/LIPIcs.ITCS.2021.14
Approximately Strategyproof Tournament Rules in the Probabilistic Setting

Authors: Kimberly Ding and S. Matthew Weinberg

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
We consider the manipulability of tournament rules which map the results of binom(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) [Jon Schneider et al., 2017; Ariel Schvartzman et al., 2020]. 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 [Jon Schneider et al., 2017] 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ε²/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.
Cite as

Kimberly Ding and S. Matthew Weinberg. Approximately Strategyproof Tournament Rules in the Probabilistic Setting. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ding_et_al:LIPIcs.ITCS.2021.14,
  author =	{Ding, Kimberly and Weinberg, S. Matthew},
  title =	{{Approximately Strategyproof Tournament Rules in the Probabilistic Setting}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{14:1--14:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.14},
  URN =		{urn:nbn:de:0030-drops-135532},
  doi =		{10.4230/LIPIcs.ITCS.2021.14},
  annote =	{Keywords: Tournaments, Incentive Compatibility, Recursive Analysis, Social Choice Theory}
}
  • Refine by Author
  • 1 Ding, Kimberly
  • 1 Weinberg, S. Matthew

  • Refine by Classification
  • 1 Theory of computation → Algorithmic game theory

  • Refine by Keyword
  • 1 Incentive Compatibility
  • 1 Recursive Analysis
  • 1 Social Choice Theory
  • 1 Tournaments

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact