Description:
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(s):
Sergiu Hart, Center of Rationality, Dept. of Economics, Dept. of Mathematics, The Hebrew University of Jerusalem
|
