Abstract
In this work we present a simple quadratic formulation for the problem of computing Nash equilibria in symmetric bimatrix games, inspired by the well-known formulation of Mangasarian and Stone [26]. We exploit our formulation to shed light to the approximability of NE points. First we observe that any KKT point of this formulation (and indeed, any quadratic program) is also a stationary point, and vice versa. We then prove that any KKT point of the proposed formulation (is not necessarily itself, but) indicates a \(\left(<\frac{1}{3}\right)-\)NE point, which is polynomially tractable, given as input the KKT point. We continue by proposing an algorithm for constructing an \(\left(\frac{1}{3}+\delta\right)-\)NE point for any δ > 0, in time polynomial in the size of the game and quasi-linear in \(\frac{1}{\delta}\), exploiting Ye’s algorithm for approximating KKT points of QPs [34]. This is (to our knowledge) the first polynomial time algorithm that constructs ε −NE points for symmetric bimatrix games for any ε close to \(\frac{1}{3}\). We extend our main result to (asymmetric) win lose games, as well as to games with maximum aggregate payoff either at most 1, or at least \(\frac{5}{3}\). To achieve this, we use a generalization of the Brown & von Neumann symmetrization technique [6] to the case of non-zero-sum games, which we prove that is approximation preserving. Finally, we present our experimental analysis of the proposed approximation and other quite interesting approximations for NE points in symmetric bimatrix games.
This work has been partially supported by the ICT Programme of the EU under contract number 258885 (SPITFIRE).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Addario-Berry, L., Olver, N., Vetta, A.: A polynomial time algorithm for finding nash equilibria in planar win-lose games. Journal of Graph Algorithms and Applications 11(1), 309–319 (2007)
Adsul, B., Garg, J., Mehta, R., Sohoni, M.: Rank-1 bimatrix games: A homeomorphism and a polynomial time algorithm. In: Proc. of 43rd ACM Symp. on Th. of Comp., STOC 2011 (2011)
Althöfer, I.: On sparse approximations to randomized strategies and convex combinations. Linear Algebra and Applications 199, 339–355 (1994)
Bertsekas, D.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (2003)
Bosse, H., Byrka, J., Markakis, E.: New algorithms for approximate nash equilibria in bimatrix games. In: Deng, X., Graham, F.C. (eds.) WINE 2007. LNCS, vol. 4858, pp. 17–29. Springer, Heidelberg (2007)
Brown, G.W., von Neumann, J.: Solutions of games by differential equations. Annals of Mathematical Studies 24, 73–79 (1950)
Burer, S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Mathematical Programming 120, 479–495 (2009)
Chen, X., Deng, X.: Settling the complexity of 2-player nash equilibrium. In: Proc. of 47th IEEE Symp. on Found. of Comp. Sci. (FOCS 2006), pp. 261–272. IEEE Comp. Soc. Press, Los Alamitos (2006)
Chen, X., Deng, X., Teng, S.H.: Computing nash equilibria: Approximation and smoothed complexity. In: Proc. of 47th IEEE Symp. on Found. of Comp. Sci. (FOCS 2006), pp. 603–612. IEEE Comp. Soc. Press, Los Alamitos (2006)
Codenotti, B., Leoncini, M., Resta, G.: Efficient computation of nash equilibria for very sparse win-lose bimatrix games. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 232–243. Springer, Heidelberg (2006)
Conitzer, V., Sandholm, T.: Complexity results about nash equilibria. In: Proc. of 18th Int. Joint Conf. on Art. Intel. (IJCAI 2003), pp. 765–771. Morgan Kaufmann, San Francisco (2003)
Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a nash equilibrium. SIAM Journal on Computing 39(1), 195–259 (2009)
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)
Daskalakis, C., Mehta, A., Papadimitriou, C.H.: Progress in approximate nash equilibrium. In: Proc. of 8th ACM Conf. on El. Comm. (EC 2007), pp. 355–358 (2007)
Daskalakis, C., Papadimitriou, C.H.: Three player games are hard. Technical Report TR05-139, Electr. Coll. on Comp. Compl., ECCC (2005)
Gale, D., Kuhn, H.W., Tucker, A.W.: On symmetric games. Contributions to Game Theory 1, 81–87 (1950)
Gilboa, I., Zemel, E.: Nash and correlated equilibria: Some complexity considerations. Games & Econ. Behavior 1, 80–93 (1989)
Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 1.21 (February 2011), http://cvxr.com/cvx
Kannan, R., Theobald, T.: Games of fixed rank: A hierarchy of bimatrix games. Economic Theory 42, 157–173 (2010)
Kontogiannis, S., Panagopoulou, P., Spirakis, P.: Polynomial algorithms for approximating nash equilibria of bimatrix games. In: Spirakis, P.G., Mavronicolas, M., Kontogiannis, S.C. (eds.) WINE 2006. LNCS, vol. 4286, pp. 286–296. Springer, Heidelberg (2006)
Kontogiannis, S., Spirakis, P.: Exploiting concavity in bimatrix games: New polynomially tractable subclasses. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX 2010. LNCS, vol. 6302. Springer, Heidelberg (2010), http://www.cs.uoi.gr/~kontog/pubs/approx10paper-full.pdf
Kontogiannis, S., Spirakis, P.: Well supported approximate equilibria in bimatrix games. ALGORITHMICA 57, 653–667 (2010)
Lee, G.M., Tam, N.N., Yen, N.D.: Quadratic Programming and Affine Variational Inequalities – A Qualitative Study. Nonconvex Optimization and its Applications. Springer, Heidelberg (2005)
Lemke, C.E., Howson Jr., J.T.: Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics 12, 413–423 (1964)
Lipton, R., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: Proc. of 4th ACM Conf. on El. Comm (EC 2003), pp. 36–41. ACM, New York (2003)
Mangasarian, O.L., Stone, H.: Two-person nonzero-sum games and quadratic programming. Journal of Mathematical Analysis and Applications 9(3), 348–355 (1964)
Morgenstern, O., von Neumann, J.: The Theory of Games and Economic Behavior. Princeton University Press, Princeton (1947)
Moulin, H., Vial, J.P.: Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved upon. Int. Journal of Game Theory 7(3/4), 201–221 (1978)
Savani, R., von Stengel, B.: Exponentially many steps for finding a nash equilibrium in a bimatrix game. In: Proc. of 45th IEEE Symp. on Found. of Comp. Sci. (FOCS 2004), pp. 258–267 (2004)
Sherali, H.D., Adams, W.P.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer Academic Publishers, Dordrecht (1998)
Sturm, J.F.: Using SeDuMi 1.02, a matlab toolbox for optimization over symmetric cones. Optimization Methods and Software 11-12, 625–653 (1999)
Tsaknakis, H., Spirakis, P.: An optimization approach for approximate nash equilibria. In: Deng, X., Graham, F.C. (eds.) WINE 2007. LNCS, vol. 4858, pp. 42–56. Springer, Heidelberg (2007)
Tsaknakis, H., Spirakis, P.: A graph spectral approach for computing approximate nash equilibria. In: Saberi, A. (ed.) WINE 2010. LNCS, vol. 6484, pp. 378–390. Springer, Heidelberg (2010)
Ye, Y.: On the complexity of approximating a kkt point of quadratic programming. Mathematical Programming 80, 195–211 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kontogiannis, S., Spirakis, P. (2011). Approximability of Symmetric Bimatrix Games and Related Experiments. In: Pardalos, P.M., Rebennack, S. (eds) Experimental Algorithms. SEA 2011. Lecture Notes in Computer Science, vol 6630. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-20662-7_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-20662-7_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-20661-0
Online ISBN: 978-3-642-20662-7
eBook Packages: Computer ScienceComputer Science (R0)