×

zbMATH — the first resource for mathematics

On computational search for Nash equilibrium in hexamatrix games. (English) Zbl 1336.91010
Summary: The problem of numerical finding of a Nash equilibrium in a 3-player polymatrix game is considered. Such a game can be completely described by six matrices, and it turns out to be equivalent to the solving a nonconvex optimization problem with a bilinear structure in the objective function. Special methods of local and global search for the optimization problem are proposed and investigated. The results of computational solution of the test game are presented and analyzed.

MSC:
91A06 \(n\)-person games, \(n>2\)
91A10 Noncooperative games
91-08 Computational methods for problems pertaining to game theory, economics, and finance
90C26 Nonconvex programming, global optimization
Software:
Matlab
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Von Neumann, J., Morgenstern, O.: Theory of games and economic behavior. Princeton University Press (1944) · Zbl 0063.05930
[2] Owen, G.: Game Theory. Academic Press, UK (1995) · Zbl 1284.91004
[3] Pang, J-S, Three modeling paradigms in mathematical programming, Math. Program. Ser. B., 125, 297-323, (2010) · Zbl 1202.90254
[4] Panicucci, B; Pappalardo, M; Passacantando, M, On solving generalized Nash equilibrium problems via optimization, Optim. Lett., 3, 419-435, (2009) · Zbl 1187.91011
[5] Facchinei, F; Sagratella, S, On the computation of all solutions of jointly convex generalized Nash equilibrium problems, Optim. Lett., 5, 531-547, (2011) · Zbl 1259.91009
[6] Altangerel, L; Battur, G, Perturbation approach to generalized Nash equilibrium problems with shared constraints, Optim. Lett., 6, 1379-1391, (2012) · Zbl 1259.91005
[7] Orlov, AV; Strekalovsky, AS, Numerical search for equilibria in bimatrix games, Comput. Math. Math. Phys., 45, 947-960, (2005)
[8] Lemke, CE; Howson, JJ, Equilibrium points of bimatrix games, J. Soc. Ind. Appl. Math., 12, 413-423, (1964) · Zbl 0128.14804
[9] Audet, C; Belhaiza, S; Hansen, P, Enumeration of all the extreme equilibria in game theory: bimatrix and polymatrix games, J. Optim. Theory Appl., 129, 349-372, (2006) · Zbl 1122.91009
[10] Strekalovsky, A.S., Orlov, A.V.: Bimatrix Games and Bilinear Programming (in Russian). FizMatLit, Moscow (2007)
[11] Vasilyev, I.L., Klimentova, K.B., Orlov, A.V.: A parallel search of equilibrium points in bimatrix games (in Russian). Numer. Methods Prog. 8:233-243 (2007). Accessed 28 July 2014. http://num-meth.srcc.msu.ru/english/index.html · Zbl 0205.49002
[12] Yanovskaya, EB, Equilibrium points in polymatrix games (in Russian), Latv. Math. Collect., 8, 381-384, (1968) · Zbl 0205.49002
[13] Strekalovsky, AS; Enkhbat, R, Polymatrix games and optimization problems, Autom. Remote Control., 75, 632-645, (2014) · Zbl 1297.91012
[14] Mills, H, Equilibrium points in finite games, J. Soc. Ind. Appl. Math., 8, 397-402, (1960) · Zbl 0099.15201
[15] Strekalovsky, A.S.: Elements of nonconvex optimization (in Russian). Nauka, Novosibirsk (2003)
[16] Strekalovsky, AS, On the minimization of the difference of convex functions on a feasible set, Comput. Math. Math. Phys., 43, 380-390, (2003)
[17] Strekalovsky, AS; Rassias, TM (ed.); Floudas, CA (ed.); Butenko, S (ed.), On solving optimization problems with hidden nonconvex structures, 465-502, (2014), New York · Zbl 1335.90075
[18] Strekalovsky, A.S., Orlov, A.V.: A new approach to nonconvex optimization. Numer. Methods Prog, 8:160-176 (2007). Accessed 28 July 2014. http://num-meth.srcc.msu.ru/english/index.html
[19] Nash, JF, Equilibrium points in \(n\)-person games, Proc. Nat. Acad. Sci. USA, 36, 48-49, (1950) · Zbl 0036.01104
[20] Horst, R., Tuy, H.: Global optimization. Deterministic approaches. Springer, Berlin (1993) · Zbl 0704.90057
[21] Sergeyev, Ya. D., Kvasov, D.E.: Diagonal global optimization methods (in Russian). FizMatLit, Moscow (2008)
[22] Sergeyev, Ya.D., Strongin, R.G., Lera, D.: Introduction to global optimization exploiting space-filling curves. Springer, New York (2013) · Zbl 1278.90005
[23] Nocedal, J., Wright, S.J.: Numerical optimization. Springer, New York (2000) · Zbl 0930.65067
[24] Vasilyev, F.P.: Optimization methods (in Russian). Factorial Press, Moscow (2002)
[25] Bazaraa, M.S., Shetty, C.M.: Nonlinear programming. Theory and algorithms. Wiley, New York (1979) · Zbl 0476.90035
[26] Orlov, AV, Numerical solution of bilinear programming problems comput, Math. Math. Phys., 48, 225-241, (2008) · Zbl 1224.90171
[27] Strekalovsky, AS; Orlov, AV; Malyshev, AV, On computational search for optimistic solutions in bilevel problems, J. Glob. Optim., 48, 159-172, (2010) · Zbl 1202.90219
[28] Strekalovsky, AS; Orlov, AV; Malyshev, AV, Numerical solution of a class of bilevel programming problems, Numer. Anal. Appl., 3, 165-173, (2010)
[29] Strekalovsky, AS; Orlov, AV; Malyshev, AV, Local search in a quadratic-linear bilevel programming problem, Numer. Anal. Appl., 3, 59-70, (2010)
[30] Wets, RJ-B, On the continuity of the value of a linear program and of related polyhedral-valued multifunctions. mathematical programming essays in honor of george B. Dantzig part I, Math. Program. Studies, 24, 14-29, (1985) · Zbl 0578.90080
[31] Polyak, RA; Costa, J; Neyshabouri, S, Dual fast projected gradient method for quadratic programming, Optim. Lett., 7, 631-645, (2013) · Zbl 1292.90224
[32] MATLAB—The language of technical computing. http://www.mathworks.com/products/matlab/. Accessed 28 July 2014 · Zbl 0128.14804
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.