Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR07-067 | 23rd August 2007 00:00

An Optimization Approach for Approximate Nash Equilibria.

RSS-Feed




Revision #2
Authors: Paul Spirakis, haralambos tsaknakis
Accepted on: 23rd August 2007 00:00
Downloads: 1297
Keywords: 


Abstract:

In this paper we propose a new methodology for determining approximate
Nash equilibria of non-cooperative bimatrix games and, based on that, we
provide an efficient algorithm that computes 0.3393-approximate
equilibria, the best approximation till now. The methodology is based
on the formulation of an appropriate function of pairs of mixed
strategies reflecting the maximum deviation of the players' payoffs
from the best payoff each player could achieve given the strategy
chosen by the other. We then seek to minimize such a function using
descent procedures. As it is unlikely to be able to find global
minima in polynomial time, given the recently proven intractability
of the problem, we concentrate on the computation of stationary points
and prove that they can be approximated arbitrarily close in
polynomial time and that they have the above mentioned approximation
property. Our result provides the best epsilon till now for
polynomially computable epsilon-approximate Nash equilibria of
bimatrix games. Furthermore, our methodology for computing
approximate Nash equilibria has not been used by others.


Revision #1 to TR07-067 | 24th July 2007 00:00

An Optimization Approach for Approximate Nash Equilibria.





Revision #1
Authors: Paul Spirakis, haralambos tsaknakis
Accepted on: 24th July 2007 00:00
Downloads: 1488
Keywords: 


Abstract:

In this paper we propose a new methodology for determining approximate Nash equilibria of non-cooperative bimatrix games and , based on that , we provide an efficient algorithm that computes 0.3393-approximate equilibria, the best approximation till now. The methodology is based on the formulation of an appropriate function of pairs of mixed strategies reflecting the maximum deviation of the players' payoffs from the best payoff each player could achieve given the strategy chosen by the other. We then seek to minimise such a function using descent procedures. As it is unlikely to be able to find global minima in polynomial time, given the recently proven intractability of the problem , we concentrate on the computation of stationary points and prove that they can be approximated arbitrarily close in polynomial time and that they have the above mentioned approximation property. Our result provides the best epsilon till now for polynomially computable epsilon-approximate Nash equilibria of bimatrix games. Furthermore, our methodology for computing approximate Nash equilibria has not been used by others.


Paper:

TR07-067 | 22nd May 2007 00:00

Computing 1/3-approximate Nash equilibria of bimatrix games in polynomial time.





TR07-067
Authors: Paul Spirakis, haralampos tsaknakis
Publication: 23rd July 2007 17:33
Downloads: 1197
Keywords: 


Abstract:

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 methodology is based on the formulation of an appropriate function of pairs of mixed strategies reflecting the maximum deviation of the players' payoffs from the best payoff each player could achieve given the strategy chosen by the other. We then seek to minimize such a function using descent procedures. As it is unlikely to be able to find global minima in polynomial time, gievn the recently proved intractability of the problem, we concentrate on the computation of local minima and prove that they can be approximated arbitrarily close in polynomial time and that they have the above mentioned approximation property. Our result provides the best $\epsilon$ till now for polynomially computable $\epsilon$-approximate Nash equilibria of bimatrix games.



ISSN 1433-8092 | Imprint