Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > APPROXIMATE EQUILIBRIA:
Reports tagged with approximate equilibria:
TR06-081 | 19th May 2006
Spyros Kontogiannis, Panagiota Panagopoulou, Paul Spirakis

Polynomial Algorithms for Approximating Nash Equilibria of Bimatrix Games

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 >>>




ISSN 1433-8092 | Imprint