Geodesic
On the Existence of Stationary Nash Equilibria for Mean Payoff Games on Graphs
Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 2 (2023), pp. 41-51 
Dmitrii Lozovanu; Stefan Pickl. On the Existence of Stationary Nash Equilibria for Mean Payoff Games on Graphs. Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 2 (2023), pp. 41-51. http://geodesic.mathdoc.fr/item/BASM_2023_2_a4/
@article{BASM_2023_2_a4,
     author = {Dmitrii Lozovanu and Stefan Pickl},
     title = {On the {Existence} of {Stationary} {Nash} {Equilibria} for {Mean} {Payoff} {Games} on {Graphs}},
     journal = {Buletinul Academiei de \c{S}tiin\c{t}e a Republicii Moldova. Matematica},
     pages = {41--51},
     year = {2023},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/BASM_2023_2_a4/}
}
TY  - JOUR
AU  - Dmitrii Lozovanu
AU  - Stefan Pickl
TI  - On the Existence of Stationary Nash Equilibria for Mean Payoff Games on Graphs
JO  - Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica
PY  - 2023
SP  - 41
EP  - 51
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/BASM_2023_2_a4/
LA  - ru
ID  - BASM_2023_2_a4
ER  - 
%0 Journal Article
%A Dmitrii Lozovanu
%A Stefan Pickl
%T On the Existence of Stationary Nash Equilibria for Mean Payoff Games on Graphs
%J Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica
%D 2023
%P 41-51
%N 2
%U http://geodesic.mathdoc.fr/item/BASM_2023_2_a4/
%G ru
%F BASM_2023_2_a4

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper we extend the classical concept of positional strategies for a mean payoff game to a general mixed stationary strategy approach, and prove the existence of mixed stationary Nash equilibria for an arbitrary $m$-player mean payoff game on graphs. Traditionally, a positional strategy represents a pure stationary strategy in a classical mean payoff game, where a Nash equilibrium in pure stationary strategies in general may not exist. Based on a constructive proof of the existence of specific equilibria for an $m$-player mean payoff game we propose a new approach for determining the optimal mixed stationary strategies. Additionally we characterize and extend the general problem of the existence of pure stationary Nash equilibria for some special classes of mean payoff games.

[1] Alpern S., “Cycles in extensive form perfect information games”, J. Math. Anal. Appl., 159 (1991), 1–17 | DOI | MR | Zbl

[2] Dasgupta P., Maskin E., “The existence of an equilibrium in discontinuous economic games”, The Review of Economic Studies, 53 (1986), 1–26 | DOI | MR | Zbl

[3] Ehrenfeucht A., Mycielski J., “Positional strategies for mean payoff games”, Int. J. Game Theory, 8 (1979), 109–113 | DOI | MR | Zbl

[4] Flesch J., Thuijsman F., Vrieze K., “Cyclic Markov equilibria in stochastic games”, International Journal of Game Theory, 26 (1997), 303–314 | DOI | MR | Zbl

[5] Gurvich V., Karzanov A., Khachiyan L., “Cyclic games and an algorithm to find minimax cycle means in directed graphs”, USSR Comput. Math. Math. Phis., 28 (1988), 85–91 | DOI | MR | Zbl

[6] Karzanov A., Lebedev V., “Cyclic games with prohibitions”, Mathematical Programming, 60 (1993), 277–293 | DOI | MR | Zbl

[7] Lozovanu D., “Pure and mixed stationary equilibria for average stochastic games”, Static amd Dynamic Game Theory: Foundations and Applications, Chapter 8, eds. Petrosyan L., Mazalov V., Zenkevich N., Springer, 2019, 131–155 | DOI | MR

[8] Lozovanu D., “Stationary Nash equilibria for average stochastic positional games”, Static amd Dynamic Game Theory: Foundations and Applications, Chapter 9, eds. Petrosyan L., Mazalov V., Zenkevich N., Springer, 2018, 139–163 | DOI | MR

[9] Lozovanu D., Pickl S., “Determining the optimal strategies for zero-sum average stochastic positional games”, Electronic Notes in Discrete Mathematics, 55 (2016), 155–159 | DOI | Zbl

[10] Lozovanu D., Pickl S., “Nash equilibria conditions for cyclic games with $m$ players”, Electronic Notes in Discrete Mathematics, 28 (2006), 85–91 | MR

[11] Zwick U., Paterson M., “The complexity of mean payoffs on graphs”, Theoretical Computer Science, 158 (1996), 343–359 | DOI | MR | Zbl