A three-person deterministic graphical game without Nash equilibria. (English) Zbl 1391.91050
Summary: 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 \times 2 \times 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 \times 4 \times 6 \times 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.
MSC:
| 91A24 | Positional games (pursuit and evasion, etc.) |
| 91A06 | \(n\)-person games, \(n>2\) |
| 91A43 | Games involving graphs |
Keywords:
deterministic graphical multi-person game; perfect information; Nash equilibrium; directed cycle; terminal position; pure stationary strategySoftware:
JBoolReferences:
| [1] | Andersson, D.; Gurvich, V.; Hansen, T., On acyclicity of games with cycles, Discrete Appl. Math., 158, 10, 1049-1063 (2010) · Zbl 1231.91029 |
| [2] | Andersson, D.; Hansen, K. A.; Miltersen, P. B.; Sorensen, T. B., Deterministic graphical games revisited, J. Logic Comput., 22, 2, 165-178 (2012) · Zbl 1236.91039 |
| [3] | Börgers, T., Pure strategy dominance, Econometrica, 61, 423-430 (1993) · Zbl 0768.90103 |
| [4] | Boros, E.; Elbassioni, K.; Gurvich, V.; Makino, K., On Nash equilibria and improvement cycles in pure positional strategies for Chess-like and Backgammon-like \(n\)-person games, Discrete Math., 312, 4, 772-788 (2012) · Zbl 1235.91009 |
| [5] | E. Boros, V. Gurvich, On Nash-solvability in pure strategies of finite games with perfect information which may have cycles, RUTCOR Research Report, RRR-60-2001, Rutgers University; Math. Soc. Sciences 46 (2003) 207-241.; E. Boros, V. Gurvich, On Nash-solvability in pure strategies of finite games with perfect information which may have cycles, RUTCOR Research Report, RRR-60-2001, Rutgers University; Math. Soc. Sciences 46 (2003) 207-241. · Zbl 1071.91009 |
| [6] | E. Boros, V. Gurvich, Why Chess and Backgammon can be solved in pure positional uniformly optimal strategies, RUTCOR Research Report 21-2009, Rutgers University.; E. Boros, V. Gurvich, Why Chess and Backgammon can be solved in pure positional uniformly optimal strategies, RUTCOR Research Report 21-2009, Rutgers University. |
| [7] | E. Boros, V. Gurvich, K. Makino, W. Shao, Nash-solvable two-person symmetric cycle game forms, RUTCOR Research Reports, RRR-30-2007 and 20-2009, Rutgers University; Discrete Applied Math. 159 (2011) 1461-1487.; E. Boros, V. Gurvich, K. Makino, W. Shao, Nash-solvable two-person symmetric cycle game forms, RUTCOR Research Reports, RRR-30-2007 and 20-2009, Rutgers University; Discrete Applied Math. 159 (2011) 1461-1487. · Zbl 1243.05164 |
| [8] | E. Boros, V. Gurvich, E. Yamangil, Chess-like games may have no uniform Nash equilibria even in mixed strategies; Game Theory, Article ID 534875, Hindawi, 2013. http://dx.doi.org/10.1155/2013/534875; E. Boros, V. Gurvich, E. Yamangil, Chess-like games may have no uniform Nash equilibria even in mixed strategies; Game Theory, Article ID 534875, Hindawi, 2013. http://dx.doi.org/10.1155/2013/534875 · Zbl 1305.91052 |
| [9] | E. Boros, R. Rand, Terminal games with three terminals have proper Nash equilibria, RUTCOR Research Report, RRR-22-2009, Rutgers University.; E. Boros, R. Rand, Terminal games with three terminals have proper Nash equilibria, RUTCOR Research Report, RRR-22-2009, Rutgers University. |
| [10] | Crama, Y.; Hammer, P. L., Boolean Functions. Theory, Algorithms, and Applications (2011), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1237.06001 |
| [11] | Edmonds, J.; Fulkerson, D. R., Bottleneck extrema, J. Combin. Theory, 8, 299-306 (1970) · Zbl 0218.05006 |
| [12] | Ewerhart, C., Backward induction and game theoretic analysis of chess, Games Econom. Behav., 34, 123-137 (2001) |
| [13] | Gale, D., A theory of \(N\)-person games with perfect information, Proc. Natl. Acad. Sci., 39, 496-501 (1953) · Zbl 0050.14008 |
| [14] | Gillette, D., Stochastic games with zero stop probabilities, (Contributions to the Theory of Games, Vol. 3. Contributions to the Theory of Games, Vol. 3, Annals of Mathematics Studies, vol. 39 (1957), Princeton University Press: Princeton University Press Princeton, NJ), 179-187 · Zbl 0078.33001 |
| [15] | Gurvich, V., On theory of multistep games, USSR Comput. Math. Math. Phys., 13, 6, 143-161 (1973) |
| [16] | Gurvich, V., The solvability of positional games in pure strategies, USSR Comput. Math. Math. Phys., 15, 2, 74-87 (1975) · Zbl 0336.90070 |
| [17] | Gurvich, V., Equilibrium in pure strategies, Sov. Math. Doklady, 38, 3, 597-602 (1989) · Zbl 0668.90099 |
| [18] | Gurvich, V., A four-person chess-like game without Nash equilibria in pure stationary strategies, Bus. Inform., 1, 31, 68-76 (2015) |
| [19] | V. Gurvich, V. Oudalov, A four-person chess-like game without Nash equilibria in pure stationary strategies, 2014. arXiv:1411.0349; V. Gurvich, V. Oudalov, A four-person chess-like game without Nash equilibria in pure stationary strategies, 2014. arXiv:1411.0349 · Zbl 1286.91026 |
| [20] | Gurvich, V.; Oudalov, V., On Nash-solvability in pure stationary strategies of the deterministic \(n\)-person games with perfect information and mean or total effective cost, Discrete Appl. Math., 167, 131-143 (2014) · Zbl 1286.91026 |
| [21] | Kalmár, L., Zur Theorie der abstrakten Spiele, Acta Sci. Math. (Szeged), 4, 65-85 (1928-1929) · JFM 54.0096.01 |
| [22] | König, D., Über eine schlussweise aus dem endlichen ins unendliche, Acta Sci. Math. Szeged., 3, 121-130 (1927) · JFM 53.0170.04 |
| [23] | Kuhn, H., Extensive games, Proc. Natl. Acad. Sci., 36, 286-295 (1950) · Zbl 0039.13402 |
| [24] | H. Kuhn, Extensive games and the problem of information, in Contributions to the theory of games, Vol. II, Princeton 1953, pp. 193-216.; H. Kuhn, Extensive games and the problem of information, in Contributions to the theory of games, Vol. II, Princeton 1953, pp. 193-216. · Zbl 0050.14303 |
| [25] | Liggett, T. M.; Lippman, S. A., Stochastic games with perfect information and time average payoff, SIAM Rev., 11, 604-607 (1969) · Zbl 0193.19602 |
| [26] | Mine, H.; Osaki, S., Markovian Decision Processes (1970), Elsevier: Elsevier New York · Zbl 0209.51601 |
| [27] | Moulin, H., The Strategy of Social Choice (1983), North-Holland Publishing Co.: North-Holland Publishing Co. Amsterdam · Zbl 0543.90002 |
| [28] | Nash, J., Equilibrium points in \(n\)-person games, Proc. Natl. Acad. Sci., 36, 1, 48-49 (1950) · Zbl 0036.01104 |
| [29] | Nash, J., Non-cooperative games, Ann. of Math., 54, 2, 286-295 (1951) · Zbl 0045.08202 |
| [30] | Schwalbe, U.; Walker, P., Zermelo and early history of game theory, Games Econom. Behav., 34, 123-137 (2001) · Zbl 0978.91002 |
| [31] | Washburn, A. R., Deterministic graphical games, J. Math. Anal. Appl., 153, 84-96 (1990) · Zbl 0724.90098 |
| [32] | Zermelo, E., Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels, (Proc. 5th Int. Cong. Math. Cambridge 1912, Vol. II (1913), Cambridge University Press: Cambridge University Press Cambridge), 501-504 · JFM 44.0092.04 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
