5 Search Results for "Schneider, Jon"

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}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.3
Approximately Strategyproof Tournament Rules: On Large Manipulating Sets and Cover-Consistence

Authors: Ariel Schvartzman, S. Matthew Weinberg, Eitan Zlatin, and Albert Zuo

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
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).
Cite as

Ariel Schvartzman, S. Matthew Weinberg, Eitan Zlatin, and Albert Zuo. Approximately Strategyproof Tournament Rules: On Large Manipulating Sets and Cover-Consistence. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 3:1-3:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{schvartzman_et_al:LIPIcs.ITCS.2020.3,
  author =	{Schvartzman, Ariel and Weinberg, S. Matthew and Zlatin, Eitan and Zuo, Albert},
  title =	{{Approximately Strategyproof Tournament Rules: On Large Manipulating Sets and Cover-Consistence}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{3:1--3:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.3},
  URN =		{urn:nbn:de:0030-drops-116881},
  doi =		{10.4230/LIPIcs.ITCS.2020.3},
  annote =	{Keywords: Tournament design, Non-manipulability, Cover-consistence, Strategyproofness}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.36
The Space Complexity of Mirror Games

Authors: Sumegha Garg and Jon Schneider

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
We consider the following game between two players Alice and Bob, which we call the mirror game. Alice and Bob take turns saying numbers belonging to the set {1, 2, ...,N}. A player loses if they repeat a number that has already been said. Otherwise, after N turns, when all the numbers have been spoken, both players win. When N is even, Bob, who goes second, has a very simple (and memoryless) strategy to avoid losing: whenever Alice says x, respond with N+1-x. The question is: does Alice have a similarly simple strategy to win that avoids remembering all the numbers said by Bob? The answer is no. We prove a linear lower bound on the space complexity of any deterministic winning strategy of Alice. Interestingly, this follows as a consequence of the Eventown-Oddtown theorem from extremal combinatorics. We additionally demonstrate a randomized strategy for Alice that wins with high probability that requires only O~(sqrt N) space (provided that Alice has access to a random matching on K_N). We also investigate lower bounds for a generalized mirror game where Alice and Bob alternate saying 1 number and b numbers each turn (respectively). When 1+b is a prime, our linear lower bounds continue to hold, but when 1+b is composite, we show that the existence of a o(N) space strategy for Bob (when N != 0 mod (1+b)) implies the existence of exponential-sized matching vector families over Z^N_{1+b}.
Cite as

Sumegha Garg and Jon Schneider. The Space Complexity of Mirror Games. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.ITCS.2019.36,
  author =	{Garg, Sumegha and Schneider, Jon},
  title =	{{The Space Complexity of Mirror Games}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{36:1--36:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.36},
  URN =		{urn:nbn:de:0030-drops-101295},
  doi =		{10.4230/LIPIcs.ITCS.2019.36},
  annote =	{Keywords: Mirror Games, Space Complexity, Eventown-Oddtown}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2017.35
Condorcet-Consistent and Approximately Strategyproof Tournament Rules

Authors: Jon Schneider, Ariel Schvartzman, and S. Matthew Weinberg

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract
We consider the manipulability of tournament rules for round-robin tournaments of n competitors. Specifically, n competitors are competing for a prize, and a tournament rule r maps the result of all n(n-1)/2 pairwise matches (called a tournament, T) to a distribution over winners. Rule r is Condorcet-consistent if whenever i wins all n-1 of her matches, r selects i with probability 1. We consider strategic manipulation of tournaments where player j might throw their match to player i in order to increase the likelihood that one of them wins the tournament. Regardless of the reason why j chooses to do this, the potential for manipulation exists as long as Pr[r(T) = i] increases by more than Pr[r(T) = j] decreases. Unfortunately, it is known that every Condorcet-consistent rule is manipulable. In this work, we address the question of how manipulable Condorcet-consistent rules must necessarily be - by trying to minimize the difference between the increase in Pr[r(T) = i] and decrease in Pr[r(T) = j] for any potential manipulating pair. We show that every Condorcet-consistent rule is in fact 1/3-manipulable, and that selecting a winner according to a random single elimination bracket is not alpha-manipulable for any alpha > 1/3. We also show that many previously studied tournament formats are all 1/2-manipulable, and the popular class of Copeland rules (any rule that selects a player with the most wins) are all in fact 1-manipulable, the worst possible. Finally, we consider extensions to match-fixing among sets of more than two players.
Cite as

Jon Schneider, Ariel Schvartzman, and S. Matthew Weinberg. Condorcet-Consistent and Approximately Strategyproof Tournament Rules. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{schneider_et_al:LIPIcs.ITCS.2017.35,
  author =	{Schneider, Jon and Schvartzman, Ariel and Weinberg, S. Matthew},
  title =	{{Condorcet-Consistent and Approximately Strategyproof Tournament Rules}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{35:1--35:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.35},
  URN =		{urn:nbn:de:0030-drops-81605},
  doi =		{10.4230/LIPIcs.ITCS.2017.35},
  annote =	{Keywords: Tournament design, Non-manipulability, Condorcet-consistent, Strategyproofness}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.87
Information Complexity Is Computable

Authors: Mark Braverman and Jon Schneider

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
The information complexity of a function f is the minimum amount of information Alice and Bob need to exchange to compute the function f. In this paper we provide an algorithm for approximating the information complexity of an arbitrary function f to within any additive error epsilon > 0, thus resolving an open question as to whether information complexity is computable. In the process, we give the first explicit upper bound on the rate of convergence of the information complexity of f when restricted to b-bit protocols to the (unrestricted) information complexity of f.
Cite as

Mark Braverman and Jon Schneider. Information Complexity Is Computable. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 87:1-87:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{braverman_et_al:LIPIcs.ICALP.2016.87,
  author =	{Braverman, Mark and Schneider, Jon},
  title =	{{Information Complexity Is Computable}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{87:1--87:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.87},
  URN =		{urn:nbn:de:0030-drops-62203},
  doi =		{10.4230/LIPIcs.ICALP.2016.87},
  annote =	{Keywords: Communication complexity, convergence rate, information complexity}
}
  • Refine by Author
  • 3 Schneider, Jon
  • 3 Weinberg, S. Matthew
  • 2 Schvartzman, Ariel
  • 1 Braverman, Mark
  • 1 Ding, Kimberly
  • Show More...

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

  • Refine by Keyword
  • 2 Non-manipulability
  • 2 Strategyproofness
  • 2 Tournament design
  • 1 Communication complexity
  • 1 Condorcet-consistent
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 1 2016
  • 1 2017
  • 1 2019
  • 1 2020
  • 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