@inproceedings{e285093e009847d0a372ad2cf08fa3ca,
title = "New algorithms for approximate Nash equilibria in bimatrix games",
abstract = "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¿+¿e)-approximation algorithm of Daskalakis, Mehta and Papadimitriou [6]. 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. The first author was supported by NWO. The second and third author were supported by the EU Marie Curie Research Training Network, contract numbers MRTN-CT-2003-504438-ADONET and MRTN-CT-2004-504438-ADONET respectively.",
author = "H. Bosse and J. Byrka and E. Markakis",
year = "2007",
doi = "10.1007/978-3-540-77105-0_6",
language = "English",
isbn = "978-3-540-77104-3",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "17--29",
editor = "X. Deng and F.C. Graham",
booktitle = "Proceedings of the 3rd International Workshop on Internet and Network Economics (WINE 2007) 12-14 December 2007, San Diego, California, USA",
address = "Germany",
note = "conference; WINE 2007, San Diego, California, USA; 2007-12-12; 2007-12-14 ; Conference date: 12-12-2007 Through 14-12-2007",
}