NEAR-OPTIMAL COMMUNICATION LOWER BOUNDS FOR APPROXIMATE NASH EQUILIBRIA

被引：0
作者：
Goos, Mika [1 ]
Rubinstein, Aviad [2 ]
机构：
[1] Ecole Polytech Fed Lausanne, CH-1015 Lausanne, Switzerland
[2] Stanford Univ, Comp Sci, Stanford, CA 94305 USA
来源：
SIAM JOURNAL ON COMPUTING | 2023年 / 52卷 / 06期
关键词：
communication complexity; game theory; Nash equilibrium; COMPLEXITY;
D O I：
10.1137/19M1242069
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We prove an N2-o(1) lower bound on the randomized communication complexity of finding an epsilon-approximate Nash equilibrium (for constant epsilon > 0) in a two-player N x N game.
引用
收藏
页码：316 / 348
页数：33
相关论文
共 46 条
[1]   ON SPARSE APPROXIMATIONS TO RANDOMIZED STRATEGIES AND CONVEX COMBINATIONS [J].
ALTHOFER, I .
LINEAR ALGEBRA AND ITS APPLICATIONS, 1994, 199 :339-355
[2]  
Babichenko Y, 2020, P FOCS
[3]   The Communication Complexity of Local Search [J].
Babichenko, Yakov ;
Dobzinski, Shahar ;
Nisan, Noam .
PROCEEDINGS OF THE 51ST ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '19), 2019, :650-661
[4]   Communication Complexity of Approximate Nash Equilibria [J].
Babichenko, Yakov ;
Rubinstein, Aviad .
STOC'17: PROCEEDINGS OF THE 49TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2017, :878-889
[5]   Query Complexity of Approximate Nash Equilibria [J].
Babichenko, Yakov .
JOURNAL OF THE ACM, 2016, 63 (04)
[6]   Completely uncoupled dynamics and Nash equilibria [J].
Babichenko, Yakov .
GAMES AND ECONOMIC BEHAVIOR, 2012, 76 (01) :1-14
[7]  
Blum A, 2007, J MACH LEARN RES, V8, P1307
[8]   New algorithms for approximate Nash equilibria in bimatrix games [J].
Bosse, Hartwig ;
Byrka, Jaroslaw ;
Markakis, Evangelos .
THEORETICAL COMPUTER SCIENCE, 2010, 411 (01) :164-173
[9]  
Brown G.W., 1951, ACTIVITY ANAL PRODUC
[10]  
Chen X., 2017, LIPIcs, V67, P1, DOI [10.4230/LIPIcs.ITCS.2017.57, DOI 10.4230/LIPICS.ITCS.2017.57]
12345