On some approaches to searching the Nash equilibrium in concave games

Andrey V. Chernov

Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 9 (2017) no. 2, pp. 62-104.

Résumé

The subject of the paper is finite-dimensional concave games id est noncooperative $n$-person games with objective functionals concave with respect to “their own” variables. For such games we investigate the problem of designing numerical algorithms for searching the Nash equilibrium with convergence guaranteed without additional requirements concerning objective functionals such as convexity in “strange” variables or another similar hypotheses (in the sense of weak convexity, quasiconvexity and so on). We describe two approaches. The first one being obvious enough is based on usage of the Hooke–Jeeves method for minimization a residual function and presented as a “standard for comparison” in the sense of efficiency of numerical solution for possible alternative methods. The second one (to some extent) can be regarded as “a cross between” the relaxation algorithm and the Hooke–Jeeves method of configurations (but with considering specific character of the function being minimized). Its justification (at this moment for the case of one-dimensional sets of players strategies but with general enough requirements to objective functionals) is a main result of the paper. Moreover, we present results of numerical experiments with their discussion. We give the comparison with other algorithms which are known at present.

Détail

Keywords: finite-dimensional concave game, Nash equilibrium, searching algorithm.

Bibliographie

[1] Aleeva S. R., Yakubovich E. O., “Ravnovesnoe programmirovanie i ego primenenie dlya nakhozhdeniya ravnovesiya po Neshu”, Vestnik Chelyabinskogo gos. un-ta. Ser. Matematika. Mekhanika. Informatika, 28(319):16 (2013), 6–20

[2] Antipin A. S., Gradientnyi i ekstragradientnyi podkhody v bilineinom ravnovesnom programmirovanii, VTs im. A.A. Dorodnitsyna RAN, M., 2002

[3] Belenkii V. Z., Volkonskii V. A., Iterativnye metody v teorii igr i programmirovanii, Nauka, M., 1974

[4] Boldyrev V. I., “Metod kusochno-lineinoi approksimatsii dlya resheniya zadach optimalnogo upravleniya”, Differents. uravneniya i protsessy upravleniya, 2004, no. 1, 28–123

[5] Buzinov A. A., Metody otsechenii v lineinom optimalnom bystrodeistvii, Dis. \ldots kand. fiz.-mat. nauk, YarGU, Yaroslavl, 2000; Наука, М., 1985

[6] Vasin A. A., Morozov V. V., Teoriya igr i modeli matematicheskoi ekonomiki, MAKS Press, M., 2005

[7] Vasin A. A., Krasnoschekov P. S., Morozov V. V., Issledovanie operatsii, ITs «Akademiya», M., 2008

[8] Vorobev N. N., Teoriya igr dlya ekonomistov-kibernetikov, Nauka, M., 1985

[9] Goldshtein A. L., Optimizatsiya v srede MATLAB, Izd-vo PNIPU, Perm, 2015

[10] Evtushenko Yu. G., Metody resheniya ekstremalnykh zadach i ikh primenenie v sistemakh optimizatsii, Nauka, M., 1982

[11] Evtushenko Yu. G., Optimizatsiya i bystroe avtomaticheskoe differentsirovanie, VTs im. A. A. Dorodnitsyna RAN, M., 2013

[12] Elsakov S. M., Shiryaev V. I., “Odnorodnye algoritmy mnogoekstremalnoi optimizatsii dlya tselevykh funktsii so znachitelnym vremenem vychisleniya znacheniya”, Vychislitelnye metody i programmirovanie, 12 (2011), 48–69

[13] Kantorovich L. V., Akilov G. P., Funktsionalnyi analiz, Nauka, M., 1984

[14] Levin A. Yu., “Ob odnom algoritme minimizatsii vypuklykh funktsii”, Dokl. AN SSSR, 160:6 (1965), 1244–1247 | Zbl

[15] Minarchenko I. M., “Lokalnyi poisk v kvadratichnoi igre dvukh lits”, Izvestiya Irkutskogo gos. un-ta. Ser. Matem., 18 (2016), 60–73 | Zbl

[16] Nenakhov E. I., “Ob odnom algoritme otyskaniya reshenii sistemy lineinykh neravenstv”, Teoriya optimalnikh rishen, 2005, no. 4, 42–48

[17] Pisaruk N. N., Vvedenie v teoriyu igr, BGU, Minsk, 2015

[18] Piyavskii S. A., “Odin algoritm otyskaniya absolyutnogo ekstremuma funktsii”, Zhurnal vychisl. matem. i matem. fiz., 12:12 (1972), 57–67

[19] Posypkin M. A., “Parallelnyi evristicheskii algoritm globalnoi optimizatsii”, Trudy ISA RAN, 32 (2008), 166–179

[20] Sergeev Ya. D., Kvasov D. E., Diagonalnye metody globalnoi optimizatsii, Fizmatlit, M., 2008

[21] Strongin R. G., Chislennye metody v mnogoekstremalnykh zadachakh, Nauka, M., 1978

[22] Chernov A. V., “O suschestvovanii ravnovesiya po Neshu v differentsialnoi igre, svyazannoi s ellipticheskimi uravneniyami: monotonnyi sluchai”, Matem. teoriya igr i ee prilozheniya, 7:3 (2015), 48–78

[23] Chirkina D. N., “Obzor metoda relaksatsii dlya poiska tochek ravnovesiya po Neshu v nepreryvnykh nekooperativnykh igrakh mnogikh lits”, Materialy XVI Mezhdunarodnoi molodezhnoi konf. «Naukoemkie tekhnologii i intellektualnye sistemy–2014», Sektsiya 1: «Intellektualnye sistemy», MGTU im. N. E. Baumana, M., 2014, 37–40

[24] Shvedov I. A., Kompaktnyi kurs matematicheskogo analiza, v. 2, Differentsialnoe ischislenie funktsii mnogikh peremennykh, NGU, Novosibirsk, 2003

[25] Shor N. Z., Metody minimizatsii nedifferentsiruemykh funktsii i ikh prilozheniya, Naukova dumka, Kiev, 1979

[26] Başar T., “Relaxation techniques and asynchronous algorithms for online computation of non-cooperative equilibria”, J. of Economic Dynamics and Control, 11:4 (1987), 531–549 | DOI | MR | Zbl

[27] Dreves A., Facchinei F., Kanzow C., Sagratella S., “On the solution of the KKT conditions of generalized Nash equilibrium problems”, SIAM J. Optim., 21:3 (2011), 1082–1108 | DOI | MR | Zbl

[28] Facchinei F., Kanzow C., “Generalized Nash equilibrium problems”, Ann. Oper. Res., 175 (2010), 177–211 | DOI | MR | Zbl

[29] Facchinei F., Lampariello L., “Partial penalization for the solution of generalized Nash equilibrium problems”, J. Global Optim., 50:1 (2011), 39–57 | DOI | MR | Zbl

[30] Facchinei F., Pang J. S., Finite-dimensional variational inequalities and complementarity problems, Springer, New York, 2003 | MR

[31] Facchinei F., Pang J.-S., “Exact penalty functions for generalized Nash problems”, Large-Scale Nonlinear Optimization, Nonconvex Optimization and Its Applications, 83, 2006, 115–126 | DOI | MR | Zbl

[32] Fukushima M., “Restricted Generalized Nash Equilibria and Controlled Penalty Algorithm”, Computational Management Science, 8:3 (2011), 201–218 | DOI | MR | Zbl

[33] von Heusinger A., Kanzow C., “Methods for Generalized Nash Equilibrium Problems with Inexact Line Search”, J. Optim. Theory Appl., 2009, no. 143, 159–183 | MR | Zbl

[34] Izmailov A. F., Solodov M. V., “On error bounds and Newton-type methods for generalized Nash equilibrium problems”, Comput. Optim. Appl., 59:1–2 (2014), 201–218 | DOI | MR | Zbl

[35] Kanzow C., Steck D., “Augmented Lagrangian Methods for the Solution of Generalized Nash Equilibrium Problems”, SIAM J. Optim., 26:4 (2016), 2034–2058 | DOI | MR | Zbl

[36] Krawczyk J. B., Uryasev S., “Relaxation Algorithms to Find Nash Equilibria with Economic Applications”, Environmental Modeling and Assessment, 2000, no. 5, 63–73 | DOI

[37] Nikaido H., Isoda K., “Note on Noncooperative Convex Games”, Pacific J. of Mathematics, 5:5 (1955), 807–815 | DOI | MR

[38] Pang J. S., Fukushima M., “Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games”, Computational Management Science, 2:1 (2005), 21–56 | DOI | MR | Zbl

[39] Rosen J. B., “Existence and Uniqueness of Equilibrium Points for Concave $n$-Person Games”, Econometrica, 33:3 (1965), 520–534 | DOI | MR | Zbl

[40] Stoer J., Bulirsch R., Introduction to numerical analysis, Springer, New York, 2002 | MR | Zbl

[41] Uryas'ev S., Rubinstein R. Y., “On relaxation algorithms in computation of noncooperative equilibria”, IEEE Transactions on Automatic Control, 39:6 (1994), 1263–1267 | DOI | MR | Zbl

[42] Zhang L. P., Han J. Y., “Unconstrained optimization reformulations of equilibrium problems”, Acta Mathematica Sinica, English Series, 25:3 (2009), 343–354 | DOI | MR | Zbl