Convergence and Approximation in Games
Vahab S. Mirrokni
Microsoft Research, Theory Group
Abstract: I will survey recent results on convergence to approximate solutions in games. For potential games in which a sequence of best-responses converge to a pure Nash equilibrium, we study the speed of convergence to efficient solutions in three classes of congestion games, selfish scheduling games, and cut games. For non-potential games, we introduce sink equilibria based on the convergence of the best-response moves of players and study the properties of this equilibrium concept.