Convergence and Approximation in Games



Vahab S. Mirrokni
Microsoft Research, Theory Group

Monday  Feb. 5, 2007
4:00 PM, 5130 Upson Hall


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.