CSAIL Event Calendar: Previous Series

The Communication Complexity of Uncoupled Nash Equilibrium Procedures

Speaker: Yishay Mansour , Tel Aviv University
Date: September 18 2007
Time: 4:15PM to 5:15PM
Location: 32-155
Host: Ronitt Rubinfeld, MIT

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.


This is a joint work with Prof. Sergiu Hart (The Hebrew University of Jerusalem).

See other events that are part of Theory Colloquium Fall 2007

See other events happening in September 2007