A Nash equilibrium of a noncooperative game is a pair of strategies such that no player has an incentive to unilaterally deviate from his current strategy. Recent results (e.g. Daskalakis, Goldberg, Papadimitriou '06 and Chen, Deng, Teng '06) indicate that polynomial time algorithms for finding an exact Nash equilibrium are unlikely to exist.
In this talk we will consider the question of computing approximate Nash equilibrium strategies in bimatrix games. In particular, given a bimatrix game where the entries of both payoff matrices are in the interval [0,1], we will say that a pair of strategies is an epsilon Nash equilibrium if no player can gain more than epsilon by deviating. I will first summarize the existing results on the complexity of this problem. Then I will present a new polynomial time approximation algorithm that achieves an improved approximation guarantee of epsilon = 0.36.
This is joint work with Jaroslaw Byrka and Hartwig Bosse
No previous knowledge on game theory is required.
Dr Vangelis Markakis
Vangelis Markakis is currently a postdoctoral fellow at the Center for Mathematics and Computer Science (CWI), in Amsterdam. He completed his PhD degree in August 2005 at the Georgia Institute of Technology, under the supervision of Richard Lipton. Before that, he received his BS degree from the National Technical University of Athens. His research interests lie mainly in the area of design and analysis of algorithms, and especially approximation algorithms, with a focus on applications that arise in the context of game theoretic environments.