Deterministic n-person shortest path and terminal games on symmetric digraphs have Nash equilibria in pure stationary strategies

International Journal of Game Theory. 2024. Vol. 53. P. 449–473.

Boros E., Franciosa P. G., Gurvich V., Vyalyi M.

We prove that a deterministic n-person shortest path game has a Nash equlibrium in
pure and stationary strategies if it is edge-symmetric (that is (u, v) is a move when-
ever (v, u) is, apart from moves entering terminal vertices) and the length of every
move is positive for each player. Both conditions are essential, though it remains an
open problem whether there exists a NE-free 2-person non-edge-symmetric game
with positive lengths. We provide examples for NE-free 2-person edge-symmetric
games that are not positive. We also consider the special case of terminal games
(shortest path games in which only terminal moves have nonzero length, possibly
negative) and prove that edge-symmetric n-person terminal games always have Nash
equilibria in pure and stationary strategies. Furthermore, we prove that an edge-
symmetric 2-person terminal game has a uniform (subgame perfect) Nash equilib-
rium, provided any infinite play is worse than any of the terminals for both players.

Keywords: Nash equilibrium, n-Person deterministic graphical games, Shortest path games, Terminal games

Publication based on the results of: Mathematical methods and algorithms in information theory, computational complexity, formal languages, and combinatorial matrix theory (2024)