Communication complexity of approximate Nash equilibria (joint work with Aviad Rubinstein)

Location: 
Elath Hall, 2nd floor, Feldman Building, Edmond J. Safra Campus
Dates: 
Sunday, January 29, 2017 - 16:00
Lecturers: 
Yakov Babichenko
Technion
Abstract: 

For a constant ε>0, we prove a poly(N) lower bound on the (randomized) communication complexity of ε-Nash equilibrium in two-player N×N games.For n-player binary-action games we prove an exp(n) lower bound for the (randomized) communication complexity of (ε,ε)-weak approximateNash equilibrium, which is a profile of mixed actions such that at least (1-ε)-fraction of the players are ε-best replying.