How Long to Equilibrium?
The Communication Complexity of Uncoupled Equilibrium Procedures
Sergiu Hart and Yishay Mansour
Abstract
We study the question of how long it takes players to reach a Nash
equilibrium in "uncoupled" setups, where each player initially
knows only his own payoff function. We derive lower bounds on the
number of bits that need to be transmitted in order to reach a
Nash equilibrium, and thus also on the required number of steps.
Specifically, we show lower bounds that are exponential in the
number of players in each one of the following cases: (1) reaching
a pure Nash equilibrium; (2) reaching a pure Nash equilibrium in a
Bayesian setting; and (3) reaching a mixed Nash equilibrium.
We then show that, in
contrast, the communication complexity of reaching a correlated equilibrium
is polynomial in the number of players.
-
The 39th ACM Symposium on Theory of Computing (STOC)
(2007), 345-353
[extended abstract:
"The Communication Complexity of Uncoupled Nash Equilibrium
Procedures"]
- Games and Economic Behavior 69 (2010), 1, 107-126
- Simple Adaptive Strategies: From
Regret-Matching to Uncoupled Dynamics, Sergiu Hart and
Andreu Mas-Colell, World Scientific (2013),
Chapter 10, 215-249
Related papers:
Video:
Presentation: