Skip to main content
SpringerLink
Log in

Semidefinite programming for min–max problems and games

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

We consider two min–max problems (1) minimizing the supremum of finitely many rational functions over a compact basic semi-algebraic set and (2) solving a 2-player zero-sum polynomial game in randomized strategies with compact basic semi-algebraic sets of pure strategies. In both problems the optimal value can be approximated by solving a hierarchy of semidefinite relaxations, in the spirit of the moment approach developed in Lasserre (SIAM J Optim 11:796–817, 2001; Math Program B 112:65–92, 2008). This provides a unified approach and a class of algorithms to compute Nash equilibria and min–max strategies of several static and dynamic games. Each semidefinite relaxation can be solved in time which is polynomial in its input size and practice on a sample of experiments reveals that few relaxations are needed for a good approximation (and sometimes even for finite convergence), a behavior similar to what was observed in polynomial optimization.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ash R.: Real Analysis and Probability. Academic Press, San Diego (1972)

    Google Scholar 

  2. Aumann R.J., Shapley L.S.: Long-term competition—a game theoretic analysis. In: Megiddo, N. (eds) Essays on Game Theory, pp. 1–15. Springer-Verlag, New-York (1994)

    Chapter  Google Scholar 

  3. Borgs, C., Chayes, J., Immorlica, N., Kalai, A.T., Mirrokni, V., Papadimitriou, C.: The mith of the Folk theorem. Games Econ. Behav. (in press) (2009)

  4. Chen, X., Deng, X.: Settling the complexity of two-player Nash equilibrium. J. ACM 56 (2009)

  5. Dantzig G.B.: Linear Programming and Extenstions. Princeton University Press, Princeton (1963)

    Google Scholar 

  6. Daskalakis C., Goldberg P.W., Papadimitriou C.H.: The complexity of computing a Nash equilibrium. SIAM J. Comput. 39, 195–259 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  7. Datta R.S.: Finding all Nash equilibria of a finite game using polynomial algebra. Econ. Theory 42, 55–96 (2010)

    Article  MATH  Google Scholar 

  8. Dresher, M., Karlin, S., Shapley, L.S.: Polynomial games. In Contributions to the Theory of Games, Annals of Mathematics Studies, vol. 24, pp. 161–180. Princeton University Press, Princeton (1950)

  9. Fink A.M.: Equilibrium in a stochastic n-person game. J. Sci. Hiroshima Univ. 28, 89–93 (1964)

    MathSciNet  MATH  Google Scholar 

  10. Glicksberg I.: A further generalization of the kakutani fixed point theorem with applications to Nash equilibrium points. Proc. Amer. Math. Soc. 3, 170–174 (1952)

    MathSciNet  MATH  Google Scholar 

  11. Govindan S., Wilson R.: A global newton method to compute Nash equilibria. J. Econ. Theory 110, 65–86 (2003)

    MathSciNet  MATH  Google Scholar 

  12. Gürkan G., Pang J.S.: Approximations of Nash equilibria. Math. Program. B 117, 223–253 (2009)

    Article  MATH  Google Scholar 

  13. Henrion D., Lasserre J.B.: GloptiPoly : global optimization over polynomials with matlab and SeDuMi. ACM Trans. Math. Soft. 29, 165–194 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  14. Henrion D., Lasserre J.B., Lofberg J.: GloptiPoly 3: moments, optimization and semidefinite programming, optim. Methods Softw. 24, 761–779 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  15. Herings P.J.-J., Peeters R.: A globally convergent algorithm to compute all Nash equilibria for n-person games. Ann. Oper. Res. 137, 349–368 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  16. Herings P.J.-J., Peeters R.: Homotopy methods to compute equilibria in game theory. Econ. Theory 42, 119–156 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  17. Herings P.J.-J., van den Elzen A.H.: Computation of the Nash equilibrium selected by the tracing procedure in n-person games. Games Econ. Behav. 38, 89–117 (2002)

    Article  MATH  Google Scholar 

  18. Jibetean D., De Klerk E.: Global optimization of rational functions: an SDP approach. Math. Prog. 106, 103–109 (2006)

    Article  MathSciNet  Google Scholar 

  19. Khachiyan L.: A polynomial algorithm in linear programming. Dokl. Akad. Nauk SSSR 224, 1093–1096. English translation in Soviet Math. Dokl 20, 191–194 (1979)

    MATH  Google Scholar 

  20. Kohlberg E.: Repeated games with absorbing states. Ann. Stat. 2, 724–738 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  21. Kostreva M.M., Kinard L.A.: A differential homotopy approach for solving polynomial optimization problems and noncooperative games. Comput. Math. Appl. 21, 135–143 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  22. Laraki R.: Explicit formulas for repeated games with absorbing states. Int. J. Game Theory Spec. Issue Honor Michael Maschler 39, 53–69 (2010)

    MathSciNet  MATH  Google Scholar 

  23. Lasserre J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11, 796–817 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  24. Lasserre J.B.: Convergent SDP-relaxations in polynomial optimization with sparsity. SIAM J. Optim. 17, 822–843 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  25. Lasserre J.B.: A semidefinite programming approach to the generalized problem of moments. Math. Program. B 112, 65–92 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  26. Lasserre J.B., Laurent M., Rostalski P.: Semidefinite characterization and computation of zero-dimensional real radical ideals. Found. Comput. Math. 8, 607–647 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  27. Lasserre J.B.: Moments and sums of squares for polynomial optimization and related problems. J. Global Optim. 45, 39–61 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  28. Lemke C.E., Howson J.T.: Equilibrium points of bimatrix games. J. SIAM 12, 413–423 (1964)

    MathSciNet  MATH  Google Scholar 

  29. Lipton, R., Markakis, E.: Nash equilibria via polynomial equations. In: Proceedings of the Latin American Symposium on Theoretical Informatics, Buenos Aires, Argentina, Lecture Notes in Computer Sciences, pp. 413–422. Springer Verlag, Berlin (2004)

  30. Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: Proceedings of the 8th ACM Conference on Electronic Commerce, pp. 36–41 (2003)

  31. Loomis L.H.: On a theorem of von neumann. Proc. Nat. Acad. Sci. 32, 213–215 (1946)

    Article  MathSciNet  MATH  Google Scholar 

  32. Nash J.F.: Equilibrium points in n-person games. Proc. Nat. Acad. Sci. 36, 48–49 (1950)

    Article  MathSciNet  MATH  Google Scholar 

  33. Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V. (eds): Algorithmic Game Theory. Cambridge University Press, Cambridge (2008) (first published 2007)

    Google Scholar 

  34. Papadimitriou C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Compt. Syst. Sci. 48(3), 498–532 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  35. Papadimitriou C.H.: On the complexity of finding Nash equilibria. In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani V.V., (eds) Algorithmic Game Theory, chap. 2, Cambridge University Press, Cambridge (2008) (first published 2007)

    Google Scholar 

  36. Parrilo, P.A.: Polynomial games and sum of squares optimization. In: Proceedings of the 45th IEEE Conference on Decision and Control, pp. 2855–2860 (2006)

  37. Putinar M.: Positive polynomials on compact semi-algebraic sets. Ind. Univ. Math. J. 42, 969–984 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  38. Rosenmüller J.: On a generalization of the lemke-howson algorithm to non cooperative n-person games. SIAM J. Appl. Math. 21, 73–79 (1971)

    Article  MathSciNet  MATH  Google Scholar 

  39. Roughgarden T.: Computing equilibria: a computational complexity perspective. Econ. Theory 42, 193–236 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  40. Savani R., von Stengel B.: Hard-to-Solve bimatrix games. Econometrica 74, 397–429 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  41. Schweighofer M.: On the complexity of Schmüdgen’s positivstellensatz. J. Complex. 20, 529–543 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  42. Schweighofer M.: Optimization of polynomials on compact semialgebraic sets. SIAM J. Optim. 15, 805–825 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  43. Shah, P., Parrilo, P.A.: Polynomial stochastic games via sum of squares optimization. In: Proceedings of the 46th IEEE Conference on Decision and Control, pp. 745–750 (2007)

  44. Shapley L.S.: Stochastic games. Proc. Nat. Acad. Sci. 39, 1095–1100 (1953)

    Article  MathSciNet  MATH  Google Scholar 

  45. Stein, N., Parrilo, P.A., Ozdaglar, A.: Correlated Equilibria in Continuous Games: Characterization and Computation. arXiv:0812.4279v1 (2008)

  46. Sturmfels B.: Solving Systems of Polynomial Equations. American Mathemathical Society, Providence Rhode, Island (2002)

    MATH  Google Scholar 

  47. van den Elzen A.H., Talman A.J.J.: A procedure for finding Nash equilibria in bi-matrix games. ZOR Methods Models Oper. Res. 35, 27–43 (1991)

    Article  MATH  Google Scholar 

  48. Verschelde V.: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation. ACM Trans. Math. Softw. 25, 251–276 (1999)

    Article  MATH  Google Scholar 

  49. Waki H., Kim S., Kojima M., Muramatsu M.: Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity. SIAM J. Optim. 17, 218–242 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  50. Wilson R.: Computing equilibria of n-person games. SIAM J. Appl. Math. 21, 80–87 (1971)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. CNRS, Laboratoire d’Econométrie de l’Ecole Polytechnique, 91128, Palaiseau-Cedex, France

    R. Laraki

  2. Équipe Combinatoire et Optimisation, CNRS FRE 3232, Université Pierre et Marie Curie (Paris 6), Paris, France

    R. Laraki

  3. LAAS-CNRS and Institute of Mathematics, University of Toulouse, LAAS, 7 Avenue du Colonel Roche, 31077, Toulouse Cédex 4, France

    J. B. Lasserre

Authors
  1. R. Laraki
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. B. Lasserre
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to R. Laraki.

Additional information

We would like to thank Bernhard von Stengel and the referees for their comments. The work of J.B. Lasserre was supported by the (French) ANR under grant NT05-3-41612.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Laraki, R., Lasserre, J.B. Semidefinite programming for min–max problems and games. Math. Program. 131, 305–332 (2012). https://doi.org/10.1007/s10107-010-0353-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-010-0353-y

Keywords

Mathematics Subject Classification (2000)

Search

Navigation