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
ABSTRACT
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