New Algorithms for Approximate Nash Equilibria in Bimatrix GamesReportar como inadecuado




New Algorithms for Approximate Nash Equilibria in Bimatrix Games - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Presented at: 3rd International Workshop on Internet and Network Economics (WINE), San Diego, December 12-14, 2007 Published in: Proceedings of the 3rd International Workshop on Internet and Network Economics, p. 17-29 Series: Lecture Notes in Computer Science 4858 Springer, 2007

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.

Keywords: Noncooperative Games ; Nash Equilibria ; Additive Approximation Reference DISOPT-CONF-2009-004





Autor: Bosse, Hartwig; Byrka, Jaroslaw; Markakis, Evangelos

Fuente: https://infoscience.epfl.ch/record/138776?ln=en







Documentos relacionados