TY - GEN
T1 - Communication complexity of correlated equilibrium with small support
AU - Ganor, Anat
AU - Karthik, C. S.
N1 - Funding Information:
The research leading to these results has received funding from the Israel Science Foundation (grant number 552/16) and the I-CORE Program of the planning and budgeting committee and The Israel Science Foundation (grant number 4/11). 2 This work was supported by Irit Dinur’s ERC-CoG grant 772839 and ISF-UGC grant 1399/14.
Publisher Copyright:
© 2018 Aditya Bhaskara and Srivatsan Kumar.
PY - 2018/8/1
Y1 - 2018/8/1
N2 - 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).
AB - 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).
KW - Communication Complexity
KW - Correlated Equilibrium
KW - Nash Equilibrium
UR - http://www.scopus.com/inward/record.url?scp=85052456853&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85052456853&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.APPROX-RANDOM.2018.12
DO - 10.4230/LIPIcs.APPROX-RANDOM.2018.12
M3 - Conference contribution
AN - SCOPUS:85052456853
SN - 9783959770859
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018
A2 - Blais, Eric
A2 - Rolim, Jose D. P.
A2 - Steurer, David
A2 - Jansen, Klaus
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 21st International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2018 and the 22nd International Workshop on Randomization and Computation, RANDOM 2018
Y2 - 20 August 2018 through 22 August 2018
ER -