Deterministic n-person shortest path and terminal games on symmetric digraphs have Nash equilibria in pure stationary strategies
share
We prove that a deterministic n-person shortest path game has a Nash equlibrium in pure and stationary strategies, provided that the game is symmetric (that is (u,v) is a move whenever (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-symmetric game with positive lengths. We provide examples for NE-free 2-person 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 symmetric n-person terminal games always have Nash equilibria in pure and stationary strategies. Furthermore, we prove that a symmetric 2-person terminal game has a uniform (sub-game perfect) Nash equilibrium, provided any infinite play is worse than any of the terminals for both players.
READ FULL TEXT