Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-081 | 19th May 2006 00:00

Polynomial Algorithms for Approximating Nash Equilibria of Bimatrix Games

RSS-Feed




TR06-081
Authors: Spyros Kontogiannis, Panagiota Panagopoulou, Paul Spirakis
Publication: 25th June 2006 20:01
Downloads: 3356
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint