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 ε till now for polynomially computable ε-approximate Nash equilibria of bimatrix games. Furthermore, our methodology for computing approximate Nash equilibria has not been used by others.
This work has been partially supported by the IST 6th Framework Programme of the European Union under contract 001907 DELIS.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Boss, H., Byrka, J., Markakis, E.: New Algorithms for Approximate Nash Equilibria in Bimatrix Games. In: this volume of WINE (2007)
Chen, X., Deng, X.: Settling the complexity of 2-player Nash equilibrium. In: Proc. of the 47th IEEE Symp. on Foundations of Comp. Sci (FOCS 2006), pp. 261–272. IEEE Computer Society Press, Los Alamitos (2006)
Daskalakis, C., Mehta, A., Papadimitriou, C.: Progress in approximate Nash Equilibria. In: Proc. of the 8th ACM Conf. on Electronic Commerce (EC 2007), ACM Press, New York (2007)
Daskalakis, C., Mehta, A., Papadimitriou, C.: A note on approximate Nash equilibria. In: Spirakis, P.G., Mavronicolas, M., Kontogiannis, S.C. (eds.) WINE 2006. LNCS, vol. 4286, pp. 297–306. Springer, Heidelberg (2006)
Kontogiannis, S., Panagopoulou, P., Spirakis, P.G.: Polynomial algorithms for approximating Nash equilibria in bimatrix games. In: Spirakis, P.G., Mavronicolas, M., Kontogiannis, S.C. (eds.) WINE 2006. LNCS, vol. 4286, pp. 282–296. Springer, Heidelberg (2006)
Chen, X., Deng, X., Teng, S.: Computing Nash Equilibria: Approximation and smoothed complexity. In: Proc. of the 47th IEEE Symp. on Foundations of Comp. Sci (FOCS 2006), pp. 603–612. IEEE Press, New York (2006)
Kontogiannis, S., Spirakis, P.G.: Efficient algorithms for constant well supported approximate equilibria of bimatrix games. In: ICALP 2007 (2007)
Bellare, M., Rogaway, P.: The complexity of approximating a nonlinear program. Mathematical Programming 69, 429–441 (1995)
Sandholm, T., Gilpin, A., Conitzer, V.: Mixed-integer Programming Methods for Finding Nash Equilibria. In: Proceedings of the 20th National Conference on Artificial Intelligence (AAAI 2005), pp. 495–501 (2005)
Tsaknakis, H., Spirakis, P.G.: An Optimization Approach for Approximate Nash Equilibria. In: the Electronic Colloqium on Computational Complexity (ECCC), as a Technical Report with number TR07067
Ye, Y.: A fully polynomial time approximation algorithm for computing a stationary point of the general linear complementarity problem. Mathematics of Operations Research 18(2), 334–345 (1993)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tsaknakis, H., Spirakis, P.G. (2007). An Optimization Approach for Approximate Nash Equilibria. In: Deng, X., Graham, F.C. (eds) Internet and Network Economics. WINE 2007. Lecture Notes in Computer Science, vol 4858. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77105-0_8
Download citation
DOI: https://doi.org/10.1007/978-3-540-77105-0_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77104-3
Online ISBN: 978-3-540-77105-0
eBook Packages: Computer ScienceComputer Science (R0)