Dynamics and Equilibria: Communication Complexity and Adaptive Heuristics

Part 1: “The Communication Complexity of Uncoupled Nash Equilibrium Procedures”, by Sergiu Hart and Yishay Mansour

http://www.ma.huji.ac.il/hart/abs/comcom.html

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. These lower bounds are exponential in the number of players. We then show that, in contrast, the communication complexity of reaching a correlated equilibrium is polynomial in the number of players.

Part 2: “Adaptive Heuristics” (Econometrica 2005)

http://www.ma.huji.ac.il/hart/abs/heurist.html

We exhibit a large class of simple rules of behavior, which we call adaptive heuristics, and show that they generate rational behavior in the long run. These adaptive heuristics are based on natural regret measures, and may be viewed as a bridge between rational and behavioral viewpoints.

The results presented here, taken together, establish a solid connection between the dynamic approach of adaptive heuristics and the static approach of correlated equilibria.

Speaker Details

Sergiu Hart’s Web site: http://www.ma.huji.ac.il/hart/index.html?#cv

Date:
Speakers:
Sergiu Hart
Affiliation:
The Hebrew University of Jerusalem
    • Portrait of Jeff Running

      Jeff Running