All reports by Author haralampos tsaknakis:

__
TR07-067
| 22nd May 2007
__

Paul Spirakis, haralampos tsaknakis#### Computing 1/3-approximate Nash equilibria of bimatrix games in polynomial time.

Revisions: 2

Paul Spirakis, haralampos tsaknakis

In this paper we propose a methodology for determining approximate Nash equilibria of non-cooperative bimatrix games and, based on that, we provide a polynomial time algorithm that computes $\frac{1}{3} + \frac{1}{p(n)} $ -approximate equilibria, where $p(n)$ is a polynomial controlled by our algorithm and proportional to its running time. The ... more >>>