Skip to main content
SpringerLink
Log in

Formulating an n-person noncooperative game as a tensor complementarity problem

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

In this paper, we consider a class of n-person noncooperative games, where the utility function of every player is given by a homogeneous polynomial defined by the payoff tensor of that player, which is a natural extension of the bimatrix game where the utility function of every player is given by a quadratic form defined by the payoff matrix of that player. We will call such a problem the multilinear game. We reformulate the multilinear game as a tensor complementarity problem, a generalization of the linear complementarity problem; and show that finding a Nash equilibrium point of the multilinear game is equivalent to finding a solution of the resulted tensor complementarity problem. Especially, we present an explicit relationship between the solutions of the multilinear game and the tensor complementarity problem, which builds a bridge between these two classes of problems. We also apply a smoothing-type algorithm to solve the resulted tensor complementarity problem and give some preliminary numerical results for solving the multilinear games.

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. Aumann, R.J., Hart, S.: Handbook of Game Theory with Economic Applications, vol. 1, 2nd edn. Elsevier, Amsterdam (1992)

    MATH  Google Scholar 

  2. Bai, X.L., Huang, Z.H., Wang, Y.: Global uniqueness and solvability for tensor complementarity problems. J. Optim. Theory Appl. 170(1), 72–84 (2016)

  3. Basar, T., Olsder, G.J.: Dynamic Noncooperative Game Theory, 2nd edn. Academic Press, San Diego (1995)

    MATH  Google Scholar 

  4. Bomze, I.M.: Non-cooperative two-person games in biology: a classification. Int. J. Game Theory 15(1), 31–57 (1986)

    Article  MATH  Google Scholar 

  5. Burke, J., Xu, S.: A non-interior predictor-corrector path following algorithm for the monotone linear complementarity problem. Math. Program. 87, 113–130 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  6. Che, M., Qi, L., Wei, Y.: Positive definite tensors to nonlinear complementarity problems. J. Optim. Theory Appl. 168, 475–487 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  7. Chen, B., Harker, P.T.: A non-interior-point continuation method for linear complementarity problem. SIAM J. Matrix Anal. Appl. 14, 1168–1190 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  8. Chen, X., Qi, L., Sun, D.: Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities. Math. Comput. 67, 519–540 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  9. Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. Academic Press, Boston (1992)

    MATH  Google Scholar 

  10. Ding, W.Y., Luo, Z.Y., Qi, L.: \(P\)-tensors, \(P_{0}\)-tensors, and tensor complementarity problem. (2015). arXiv:1507.06731v1

  11. Facchinei, F., Kanzow, C.: Generalized Nash equilibrium problems. Ann. Oper. Res. 175, 177–211 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  12. Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003)

    MATH  Google Scholar 

  13. Ferris, M.C., Pang, J.-S.: Engineering and economic applications of complementarity problems. SIAM Rev. 39, 669–713 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  14. Fukushima, M., Lin, G.H.: Smoothing methods for mathematical programs with equilibrium constraints. In: Proceedings of the ICKS’04, IEEE Computer Society, pp. 206–213 (2004)

  15. Fukushima, M., Luo, Z.-Q., Tseng, P.: Smoothing functions for second-order-cone complementarity problems. SIAM J. Optim. 12, 436–460 (2001)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  17. Gowda, M.S., Luo, Z.Y., Qi, L., Xiu, N.H.: \(Z\)-tensors and complementarity problems. (2015). arXiv:1510.07933v1

  18. Gowda, M.S., Sznajder, R.: A generalization of the Nash equilibrium theorem on bimatrix games. Int. J. Game theory 25, 1–12 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  19. Han, J.Y., Xiu, N.H., Qi, H.D.: Nonlinear Complementarity Theory and Algorithm. Shanghai Science and Technology Press, Shanghai (2006). (in Chinese)

    Google Scholar 

  20. Hayashi, S., Yamashita, N., Fukushima, M.: Robust Nash equilibria and second-order cone complementarity problems. J. Nonlinear Convex Anal. 6, 283–296 (2005)

    MathSciNet  MATH  Google Scholar 

  21. Howson Jr., J.T.: Equilibria of polymatrix games. Manag. Sci. 18(5), 312–318 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  22. Hu, M., Fukushima, M.: Existence, uniqueness, and computation of robust Nash equilibrium in a class of multi-leader-follower games. SIAM J. Optim 23, 894–916 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  23. Huang, Z.H.: Locating a maximally complementary solution of the monotone NCP by using non-interior-point smoothing algorithms. Math. Method Oper. Res. 61(1), 41–55 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  24. Huang, Z.H., Ni, T.: Smoothing algorithms for complementarity problems over symmetric cones. Comput. Optim. Appl. 45, 557–579 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  25. Huang, Z.H., Suo, Y.Y., Wang, J.: On \(Q\)-tensors. (2015). arXiv:1509.03088v1

  26. Isac, G.: Topological Methods in Complementarity Theory. Kluwer Academic Publishers, Dordrecht (2000)

    Book  MATH  Google Scholar 

  27. Kim, T., Jeon, Y.: Stationary perfect equilibria of an \(n\)-person noncooperative bargaining game and cooperative solution concepts. Eur. J. Oper. Res. 194, 922–932 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  28. Kolda, T.G., Bader, B.W.: Tensor decompositions and applications. SIAM Rev. 51, 455–500 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  29. Lemke, C.E., Howson Jr., J.T.: Equilibrium points of bimatrix games. SIAM J. Appl. Math. 12(2), 413–423 (1964)

    Article  MathSciNet  MATH  Google Scholar 

  30. Li, P., Lin, G.H.: Solving a class of generalized Nash equilibrium problems. J. Math. Res. Appl. 33(3), 372–378 (2013)

    MathSciNet  MATH  Google Scholar 

  31. Luo, Z.Y., Qi, L., Xiu, N.H.: The sparsest solutions to \(Z\)-tensor complementarity problems. Optim. Lett. (2016). doi:10.1007/s11590-016-1013-9

  32. Mangasarian, O.L., Stone, H.: Two-person nonzero-sum games and quadratic programming. J. Math. Anal. Appl. 9, 348–355 (1964)

    Article  MathSciNet  MATH  Google Scholar 

  33. Myerson, R.B.: Nash equilibrium and the history of economic theory. J. Econ. Lit. 37, 1067–1082 (1999)

    Article  Google Scholar 

  34. Nash, J.F.: Equilibrium points in \(N\)-person games. Proc. Natl. Acad. Sci. USA 36, 48–49 (1950)

    Article  MathSciNet  MATH  Google Scholar 

  35. Nash, J.F.: Non-cooperative games. Ann. Math. 54, 286–295 (1951)

    Article  MathSciNet  MATH  Google Scholar 

  36. Osborne, M.J., Rubinstein, A.: A Course in Game Theory. The MIT Press, London (1994)

    MATH  Google Scholar 

  37. Qi, L.: Eigenvalue of a real supersymmetric tensor. J. Symb. Comput. 40, 1302–1324 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  38. Qi, L., Sun, D., Zhou, G.: A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems. Math. Program. 87, 1–35 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  39. Song, Y., Qi, L.: Properties of some classes of structured tensors. J. Optim. Theory Appl. 165, 854–873 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  40. Song, Y., Qi, L.: Tensor complementarity problem and semi-positive tensors. J. Optim. Theory Appl. 169(3), 1069–1078 (2016)

  41. Song, Y., Qi, L.: Properties of tensor complementarity problem and some classes of structured tensors. (2014). arXiv:1412.0113v2

  42. Song, Y., Qi, L.: Error bound of \(P\)-tensor nonlinear complementarity problem. (2015). arXiv:1508.02005v2

  43. Song, Y., Yu, G.H.: Properties of solution set of tensor complementarity problem. J. Optim. Theory Appl. 170(1), 85–96 (2016)

  44. Wang, Y., Huang, Z.H., Bai, X.L.: Exceptionally regular tensors and tensor complementarity problems. Optim. Method Softw. 31(4), 815–828 (2016)

  45. Weibull, J.W.: Evolutionary Game Theory. The MIT Press, London (1996)

    MATH  Google Scholar 

  46. Yuan, Y.X.: A trust region algorithm for Nash equilibrium problems. Pac. J. Optim. 7(1), 125–138 (2011)

    MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The authors are very grateful to the editor and the two anonymous referees for their valuable suggestions and comments, which have considerably improve the presentation of this paper. The first author’s work was supported by the National Natural Science Foundation of China (Grant No. 11431002) and the second author’s work was supported by the Hong Kong Research Grant Council (Grant No. PolyU 502111, 501212, 501913 and 15302114).

Author information

Authors and Affiliations

  1. Department of Mathematics, School of Science, Tianjin University, Tianjin, 300072, People’s Republic of China

    Zheng-Hai Huang

  2. The Center for Applied Mathematics, Tianjin University, Tianjin, People’s Republic of China

    Zheng-Hai Huang

  3. Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, People’s Republic of China

    Liqun Qi

Authors
  1. Zheng-Hai Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Liqun Qi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zheng-Hai Huang.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Huang, ZH., Qi, L. Formulating an n-person noncooperative game as a tensor complementarity problem. Comput Optim Appl 66, 557–576 (2017). https://doi.org/10.1007/s10589-016-9872-7

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-016-9872-7

Keywords

Search

Navigation