On some general scheme of constructing iterative methods for searching the Nash equilibrium in concave games

Andrey V. Chernov

Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 13 (2021) no. 3, pp. 75-121.

Résumé

\language=0 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 iterative algorithms for searching the Nash equilibrium with convergence guaranteed without requirements concerning objective functionals such as smoothness and as convexity in ‘strange’ variables or another similar hypotheses (in the sense of weak convexity, quasiconvexity and so on). In fact, we prove some assertion analogous to the theorem on convergence of $M$-Fejér iterative process for the case when an operator acts in a finite-dimensional compact and nearness to an objective set is measured with the help of arbitrary continuous function. Then, on the base of this assertion we generalize and develope the approach suggested by the author formerly to searching the Nash equilibrium in concave games. The last one can be regarded as “a cross between” the relaxation algorithm and the Hooke–Jeeves method of configurations (but taking into account a specific character of the the residual function being minimized). Moreover, we present results of numerical experiments with their discussion.

Détail

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

Bibliographie

[1] M. Bazara, K. Shetti, Nelineinoe programmirovanie. Teoriya i algoritmy, Mir, M., 1982, 583 pp.

[2] V. V. Vasin, I. I. Eremin, Operatory i iteratsionnye protsessy feirovskogo tipa. Teoriya i prilozheniya, RKhD, M.–Izhevsk, 2005, 200 pp.

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

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

[5] N. N. Vorobev, Teoriya igr dlya ekonomistov-kibernetikov, Nauka, M., 1985, 272 pp.

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

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

[8] I. I. Eremin, V. D. Mazurov, Nestatsionarnye protsessy matematicheskogo programmirovaniya, Nauka, M., 1979, 288 pp.

[9] I. I. Eremin, S. V. Patsko, “Feierovskie protsessy dlya beskonechnykh sistem vypuklykh neravenstv”, Trudy IMM UrO RAN, 8, no. 1, 2002, 106–115

[10] I. I. Eremin, Feierovskie metody dlya zadach vypukloi i lineinoi optimizatsii, ITs YuUrGU, Chelyabinsk, 2009, 199 pp.

[11] I. I. Eremin, “Otobrazheniya szhatiya”, Trudy IMM UrO RAN, 15, no. 3, 2009, 106–115

[12] I. I. Eremin, L. D. Popov, “Feierovskie protsessy v teorii i praktike: obzor poslednikh rezultatov”, Izv. vuzov. Matematika, 2009, no. 1, 44–65 | Zbl

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

[14] V. V. Morozov, A. G. Sukharev, V. V. Fedorov, Issledovanie operatsii v zadachakh i uprazhneniyakh, Vysshaya shkola, M., 1986, 287 pp.

[15] N. N. Pisaruk, Vvedenie v teoriyu igr, BGU, Minsk, 2015, 256 pp.

[16] B. T. Polyak, Vvedenie v optimizatsiyu, Nauka, M., 1983, 384 pp.

[17] A. V. Chernov, “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 | Zbl

[18] A. V. Chernov, “O nekotorykh podkhodakh k poisku ravnovesiya po Neshu v vognutykh igrakh”, Matem. teoriya igr i ee prilozheniya, 9:2 (2017), 62–104 | Zbl

[19] D. N. Chirkina, “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

[20] J. Contreras, J. B. Krawczyk, J. Zuccollo, “Playing Pollution Games with Thermal Electricity Generators”, Environmental Modeling and Assessment, 23:4 (2018), 639–651 | DOI

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

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

[23] Lei Wang, Cui Liu, Hongwei Gao, Chong Lin, “Strongly strategic support of cooperative solutions for games over event trees”, Operations Research Letters, 48 (2020), 61–66 | DOI | Zbl

[24] A. B. MacKenzie, L. A. DaSilva, Game Theory for Wireless Engineers, Virginia Polytechnic Institute and State University: Morgan publishers, 2006, ix+76 pp.

[25] T. Meng, N. R. Schiff, P. B. Godfrey, M. Schapira, “PCC Proteus: Scavenger Transport And Beyond”, Annual conference of the ACM Special Interest Group on Data Communication on the applications, technologies, architectures, and protocols for computer communication (SIGCOMM-20) (August 10–14, 2020, Virtual Event, USA), ACM, New York, NY, USA, 615–631

[26] V. V. Vasin, I. I. Eremin, Operators and Iterative Processes of Fejér Type. Theory and Applications, Walter de Gruyter, Berlin–New York, 2009, xiv+155 pp.