DIMACS TR: 2002-15

On Nash-solvability in pure stationary strategies of finite games with perfect information which may have cycles

Authors: E. Boros and V. Gurvich


Let $g$ be a positional game with perfect information modelled by a directed graph $G = (V,E)$ which is finite but may have directed cycles. % an initial position $v_0 \in V(G)$, A local cost function $f(i,e)$ is given for every player $i \in I$ and for every move $e \in E$. The players are allowed only pure stationary strategies, that is the move in any position is deterministic, and may depend only on this present position, not on the preceding positions or moves. Hence, the resulting play $p$ is a directed path which begins in the initial position $v_0$ and either (i) ends in a final position or (ii) results in a simple directed cycle. Given a play $p$, for every player $i \in I$ the effective cost $f(i,p)$ is defined as the sum of all local costs along the path $f(i,p) = \sum_{e \in p} f(i,e)$ in case of (i), or as $f(i,p) = + \infty$ in case of (ii). Let us call a local cost function $f$ and the corresponding game terminal if $f(i,e) = 0$ for every player $i \in I$ and for every move $e$ which is not leading to a final position. The players wish to minimize their effective costs, thus in particular they should try to avoid cycles. A game is called Nash-solvable if it has at least one Nash equilibrium in pure stationary strategies and properly Nash-solvable if the corresponding play results in a final position, not in a cycle. It is easy to demonstrate that already zero-sum games with two players may not be solvable. Yet, Nash-solvability turns into an exciting open problem under the following simple additional condition: ($\clubsuit$) all local costs are non-negative, i.e. $f(i,e) \geq 0$ for every player $i \in I$ for every move $e \in E$, or under the seemingly weaker but in fact equivalent condition: ($\spadesuit$) $\sum_{e \in c} f(i,e) \geq 0$, for every player $i \in I$ and for every simple directed cycle $c$ in $G$.
In all examples, which we were able to analyze, games satisfying condition ($\clubsuit$) turned out to be properly Nash-solvable, yet the Nash-solvability of such games is an open problem. In this paper we prove proper Nash-solvability for the following special cases: (a) play-once games, i.e. games in which every player controls exactly one position, (b) terminal games with only 2 players, and (c) terminal games with only 2 terminal moves. We also show that in each of these cases a Nash equilibrium can be constructed in polynomial time in the size of the graph $G$.

Keywords: cycle, cyclic game, directed graph, directed cycle, directed path, effective cost, local cost, Nash equilibrium, perfect information, positional game, potentials, pure strategies, saddle point, stationary strategies, strong equilibrium, shortest path.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-15.ps.gz

DIMACS Home Page