Equilibrium Selection Via Natural Learning
Cornell, Department of Computer Science
Game theory is saturated with plausible equilibrium concepts. Which is the "right" one? Arguably, the most coveted one is that of Nash equilibria. However, even if we choose to concentrate on them, the multiplicity of Nash poses a similar dilemma. Which Nash is the right one?
We explore this question from the perspective of learning theory. Can players reach Nash (and which one) while applying simple and natural learning algorithms? Our results imply exponential improvement on the performance bounds of well-known learning protocols in wide classes of games.
This is joint work with Robert Kleinberg and Eva Tardos (STOC 09).