A Computational Method for Solving N-Person Game
The nonzero sum n-person game has been considered. It is well known that the game can be reduced to a global optimization problem [5 7 14]. By extending Mills’ result , we derive global optimality conditions for a Nash equilibrium. In order to solve the problem numerically, we apply the Curvilinear Multistart Algorithm [2 3] developed for finding global solutions in nonconvex optimization problems. The proposed algorithm was tested on three and four person games. Also, for the test purpose, we have considered competitions of 3 companies at the bread market of Ulaanbaatar as the three person game and solved numerically.
1. Strekalovsky A.S. Global Optimality Conditions for Nonconvex Optimization. Journal of Global Optimization, 1998, vol. 12, pp. 415-434.
2. Enkhbat R., Tungalag N., Gornov A., Anikin A. The Curvilinear Search Algorithm for Solving Three-Person Game. Proc. DOOR 2016. CEUR-WS, 2016, vol. 1623. p. 574-583. URL: http://ceur-ws.org/Vol-1623/paperme4.pdf.
3. Gornov A., Zarodnyuk T. Computing technology for estimation of convexity degree of the multiextremal function. Machine learning and data analysis, 2014, vol. 10, no 1, pp. 1345-1353. URL: http://jmlda.org
4. Mangasarian O.L., Stone H. Two-Person Nonzero Games and Quadratic Programming. J. Mathemat. Anal. Appl., 1964, vol. 9, pp. 348-355.
5. Mills H. Equilibrium Points in Finite Games. J. Soc. Indust. Appl. Mathemat., 1960, vol. 8, no 2, pp. 397-402.
6. Von Neumann J., Morgenstern O. Theory of games and economic behavior. Princeton University Press, 1944.
7. Melvin Dresher (1981) The Mathematics of Games of Strategy. Dover Publications.
8. Vorobyev N.N. Noncooperative games. Moscow, Nauka Publ., 1984.
9. Germeyer YU.B. Introduction to Operation Reseach. Moscow, Nauka Publ., 1976.
10. Strekalovsky A.S., Orlov A.V. Bimatrix Game and Bilinear Programming. Moscow, Nauka Publ., 2007.
11. Owen G. Game Theory. Saunders, Philadelphia, 1971.
12. Gibbons R. Game Theory for Applied Economists. Princeton University Press., 1992.
13. Horst R., Tuy H. Global Optimization. Springer-Verlag, 1993.
14. Howson J.T. Equilibria of Polymatrix Games. Management Sci., 1972, vol. 18, pp. 312-318.
15. Strekalovsky A.S., Enkhbat R. Polymatrix games and optimization problems. Automation and Remote Control, 2014, vol. 75, no 4, pp. 632-645.
16. Orlov A.V., Strekalovsky A.S.,Batbileg S. On computational search for Nash equilibrium in hexamatrix games. Optimization Letters, 2014, vol. 10, no 2, pp. 369-381.
17. Problem 3.4. https://www.dropbox.com/s/137aaahvbniau9q/problem_4_data.txt.