Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5072502 | Games and Economic Behavior | 2010 | 20 Pages |
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 communication complexity of reaching a Nash equilibrium, i.e., on the number of bits that need to be transmitted, 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.
Related Topics
Social Sciences and Humanities
Economics, Econometrics and Finance
Economics and Econometrics
Authors
Sergiu Hart, Yishay Mansour,