New Algorithms for Approximate Nash Equilibria in Bimatrix Games

We consider the problem of computing additively approximate Nash equilibria in non-cooperative two-player games. We provide a new polynomial time algorithm that achieves an approximation guarantee of 0.36392. Our work improves the previously best known (0.38197 + ε)-approximation algorithm of Daskalakis, Mehta and Papadimitriou. First, we provide a simpler algorithm, which also achieves 0.38197. This algorithm is then tuned, improving the approximation error to 0.36392. Our method is relatively fast, as it requires solving only one linear program and it is based on using the solution of an auxiliary zero-sum game as a starting point.


Published in:
Proceedings of the 3rd International Workshop on Internet and Network Economics, 17-29
Presented at:
3rd International Workshop on Internet and Network Economics (WINE), San Diego, December 12-14, 2007
Year:
2007
Publisher:
Springer
Keywords:
Laboratories:




 Record created 2009-06-12, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)