All reports by Author Spyros Kontogiannis:

__
TR06-081
| 19th May 2006
__

Spyros Kontogiannis, Panagiota Panagopoulou, Paul Spirakis#### Polynomial Algorithms for Approximating Nash Equilibria of Bimatrix Games

Spyros Kontogiannis, Panagiota Panagopoulou, Paul Spirakis

We focus on the problem of computing an $\epsilon$-Nash equilibrium of a bimatrix game, when $\epsilon$ is an absolute constant.

We present a simple algorithm for computing a $\frac{3}{4}$-Nash equilibrium for any bimatrix game in strongly polynomial time and

we next show how to extend this algorithm so as to ...
more >>>