Communication complexity of correlated equilibrium with small support

Anat Ganor, C. S. Karthik

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

We define a two-player N ×N game called the 2-cycle game, that has a unique pure Nash equilibrium which is also the only correlated equilibrium of the game. In this game, every1/poly(N)-A pproximate correlated equilibrium is concentrated on the pure Nash equilibrium. We show that the randomized communication complexity of finding any 1/poly(N)-approximate correlated equilibrium of the game is (N). For small approximation values, our lower bound answers an open question of Babichenko and Rubinstein (STOC 2017).

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018
EditorsEric Blais, Jose D. P. Rolim, David Steurer, Klaus Jansen
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Print)9783959770859
DOIs
StatePublished - Aug 1 2018
Externally publishedYes
Event21st International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2018 and the 22nd International Workshop on Randomization and Computation, RANDOM 2018 - Princeton, United States
Duration: Aug 20 2018Aug 22 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume116
ISSN (Print)1868-8969

Conference

Conference21st International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2018 and the 22nd International Workshop on Randomization and Computation, RANDOM 2018
Country/TerritoryUnited States
CityPrinceton
Period8/20/188/22/18

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Communication Complexity
  • Correlated Equilibrium
  • Nash Equilibrium

Fingerprint

Dive into the research topics of 'Communication complexity of correlated equilibrium with small support'. Together they form a unique fingerprint.

Cite this