ECCC-Report TR06-081https://eccc.weizmann.ac.il/report/2006/081Comments and Revisions published for TR06-081en-usSun, 25 Jun 2006 20:01:12 +0300
Paper TR06-081
| Polynomial Algorithms for Approximating Nash Equilibria of Bimatrix Games |
Spyros Kontogiannis,
Panagiota Panagopoulou,
Paul Spirakis
https://eccc.weizmann.ac.il/report/2006/081We 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 obtain a (potentially stronger) parameterized approximation.
Namely, we present an algorithm that computes a $\frac{2+\lambda+\epsilon}{4}$-Nash equilibrium for any $\epsilon$, where $\lambda$
is the minimum, among all Nash equilibria, expected payoff of either player. The suggested algorithm runs in time polynomial in $\frac{1}{\epsilon}$ and the number of strategies available to the players.
Sun, 25 Jun 2006 20:01:12 +0300https://eccc.weizmann.ac.il/report/2006/081