TY - JOUR

T1 - A three-person deterministic graphical game without Nash equilibria

AU - Boros, Endre

AU - Gurvich, Vladimir

AU - Milanič, Martin

AU - Oudalov, Vladimir

AU - Vičič, Jernej

N1 - Funding Information:
The first author thanks the National Science Foundation for partial support (Grant and IIS-1161476). The second author was partially funded by the Russian Academic Excellence Project ‘5-100’. The work of the third author is supported in part by the Slovenian Research Agency (I 0-0035, research program P 1-0285, research projects N1-0032, J1-6720, and J1-7051). The work for this paper was done in the framework of bilateral projects between Slovenia and the USA, partially financed by the Slovenian Research Agency (BI-US/16-17-027 and BI-US/16-17-030).
Publisher Copyright:
© 2018 Elsevier B.V.

PY - 2018/7/10

Y1 - 2018/7/10

N2 - We give an example of a three-person deterministic graphical game that has no Nash equilibrium in pure stationary strategies. The game has seven positions, four outcomes (a unique cycle and three terminal positions), and its normal form is of size 2×2×4 only. Thus, the example strengthens significantly the one obtained in 2014 by Gurvich and Oudalov; the latter has four players, five terminals, and normal form of size 2×4×6×8. Furthermore, our example is minimal with respect to the number of players. Somewhat similar examples were known since 1975, but they were not related to deterministic graphical games. The small size of our example allows us to verify that it has no Nash equilibrium not only in pure but also in independently mixed (so-called behavioral) strategies. For independently mixed strategies two distinct effective payoffs can be considered: along with the classical Markovian evaluation, we also consider a priori evaluation, which may be a better fit for playing in behavioral strategies. We show that in both cases Nash equilibria may fail to exist.

AB - We give an example of a three-person deterministic graphical game that has no Nash equilibrium in pure stationary strategies. The game has seven positions, four outcomes (a unique cycle and three terminal positions), and its normal form is of size 2×2×4 only. Thus, the example strengthens significantly the one obtained in 2014 by Gurvich and Oudalov; the latter has four players, five terminals, and normal form of size 2×4×6×8. Furthermore, our example is minimal with respect to the number of players. Somewhat similar examples were known since 1975, but they were not related to deterministic graphical games. The small size of our example allows us to verify that it has no Nash equilibrium not only in pure but also in independently mixed (so-called behavioral) strategies. For independently mixed strategies two distinct effective payoffs can be considered: along with the classical Markovian evaluation, we also consider a priori evaluation, which may be a better fit for playing in behavioral strategies. We show that in both cases Nash equilibria may fail to exist.

KW - Deterministic graphical multi-person game

KW - Directed cycle

KW - Nash equilibrium

KW - Perfect information

KW - Pure stationary strategy

KW - Terminal position

UR - http://www.scopus.com/inward/record.url?scp=85044313924&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85044313924&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2018.01.008

DO - 10.1016/j.dam.2018.01.008

M3 - Article

AN - SCOPUS:85044313924

SN - 0166-218X

VL - 243

SP - 21

EP - 38

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -