Stochastic Shortest Path Games.
We consider dynamic, two-player, zero-sum games where the "minimizing" player seeks to drive an underlying finite-state dynamic system to a special terminal state along a least expected cost path. The "maximizer" seeks to interfere with the minimizer's progress so as to maximize the expected total cost. We consider, for the first time, undiscounted finite-state problems, with compact action spaces, and transition costs that are not strictly positive. We admit that there are policies for the minimizer which permit the maximizer to prolong the game indefinitely. Under assumptions which generalize deterministic shortest path problems, we establish (i) the existence of a real-valued equilibrium cost vector achievable with stationary policies for the opposing players and (ii) the convergence of value iteration and policy iteration to the unique solution of Bellman's equation.
Introduction
. This paper develops basic theory relating to stochastic shortest
path games. These are two-player, zero-sum, games where the minimizing player
seeks to drive an underlying finite-state dynamic system to a special terminal state
along a least expected cost path. The maximizer seeks to interfere with the mini-
mizer's progress so as to maximize the expected total cost. In actual play, the players
implement actions simultaneously at each stage, with full knowledge of the state of
the system but without knowledge of each other's current decision.
Games of this type have been studied for some time. The field was initiated by
Shapley in his classical paper [7]. In Shapley's games, two players are successively
faced with matrix-games (in mixed strategies) where both the immediate cost and
transition probabilities to new matrix-games are influenced by the stagewise decisions
of the players. In this formulation, the state of the system is the matrix-game currently
being played. It is assumed that this set of states is finite and that there is a non-zero
minimal probability that, at any stage, the game will transition to a terminal state,
ending the sequence of rewards and payoffs. It turns out that this is equivalent to
an infinite-horizon game with discounted additive cost. The analysis of such games
is straightforward, the main results being (i) the existence and characterization of a
unique real-valued equilibrium cost vector achievable in stationary randomized policies
and (ii) the convergence of value iteration and policy iteration to the equilibrium cost.
Since Shapley's work, game theorists have actively studied extensions to the
discounted-cost model. In [4], Kushner and Chamberlain consider undiscounted, pur-
suit/evasion, stochastic games where there is a terminal state corresponding to the
evader being "caught." The state space is assumed to be finite (with
one of which is the terminal state). Making some regularity assumptions on the transition
probabilities and cost functions, they consider pure strategies over compact
action spaces. In addition, they assume that either,
Supported by the National Science Foundation Grant 9300494-DMI and an Office of Naval Re-search
fellowship.
y Department of Systems Engineering, School of Engineering and Applied Science, University of
Virginia, Olsson Hall, Charlottesville, Virginia, 22903 (sdp5f@virginia.edu)
z Massachusetts Institute of Technology, Laboratory for Information and Decision Systems, Room
Cambridge, MA 02139(dimitrib@mit.edu)
S. D. PATEK AND D. P. BERTSEKAS
1. The n-stage probability transition matrix [P (-)] n (from non-terminal states
to non-terminal states) is a "uniform contraction" in the stationary policy
pairs (-) of the two players. (That is, for some ffl ? 0, [P (-)] n has
row-sums less than stationary policy pairs (-).) Or,
2. The transition costs (to the pursuer) are uniformly bounded below by
and there exists a stationary policy ~
- for the pursuer that makes [P (~-)] n
a uniform contraction under all stationary policies for the evader.
They show that there exists an equilibrium cost vector for the game which can be
found through value iteration. In [10], van der Wal considers a special case of Kushner
and Chamberlain's games. Under more restrictive assumptions about the pursuer's
ability to catch the evader, he gives error bounds for the updates in value iteration.
In [3], Kumar and Shiau give a detailed analysis of stochastic games with very
mild assumptions about the state space and control constraint sets. For the case of
nonnegative additive cost (with no discounting), they establish the existence of an
extended real equilibrium cost vector in non-Markov randomized policies (where for
both players the best mixed action can depend on all of the past states and controls,
as well as the current state). They show that the minimizing player can achieve the
equilibrium using a stationary Markov randomized policy and that, in case the state
space is finite, the maximizing player can play ffl-optimally using stationary randomized
policies.
Other researchers have studied so-called "non-terminating" stochastic games (also
sometimes called "undiscounted" stochastic games), where the costs are not discounted
but are averaged instead. Such average-cost games have a rich mathematical
structure which has been extensively covered in the literature [13, 5].
In this paper, we consider undiscounted additive cost games without averaging.
We admit that there are policies for the minimizer which allow the maximizer to
prolong the game indefinitely at infinite cost to the minimizer. We do not assume
nonnegativity of cost, as in [4] and [3]. We make alternative assumptions which
guarantee that, at least under optimal policies, the terminal state is reached with
probability one. Our results imply the results of Shapley [7], as well as those of
Kushner and Chamberlain [4]. Because of our assumptions relating to termination,
we are able to derive stronger conclusions than those made by Kumar and Shiau [3]
for the case of a finite state space. Note that because we do not assume nonnegativity
of the costs, the analysis is much more complicated than the corresponding analysis of
Kushner and Chamberlain [4]. Our formal assumptions generalize (to the case of two-
players) those for stochastic shortest path problems [2]. Because of this, we refer to
our class of games as "stochastic shortest path games." Our games are characterized
by either (i) inevitable termination (under all policies) or (ii) an incentive for the
minimizer to drive the system to termination in a finite expected number of stages.
We shall see that the results of [2] are essential in developing our present theory.
In Section 2 we give a precise mathematical formulation for stochastic shortest
path games. In Section 3, we relate our general formulation to Shapley's original
games [7]. We develop our main results in Section 4. This is where we show that
stochastic shortest path games have an equilibrium solution which can be characterized
by the unique solution to Bellman's equation. We also prove the convergence
of value iteration and policy iteration to the equilibrium cost. In Section 5, we give
an example of pursuit and evasion, illustrating our main results. Finally, in the Appendix
we collect some well known results about dynamic games which are crucial to
our development.
2. Mathematical Formulation. Let S denote a finite state space, with elements
labeled n. For each i 2 S, define U(i) and V (i) to be the sets of
actions available to the minimizer and maximizer at state i, respectively. These are
collectively referred to as control constraint sets. The probability of transitioning from
v). The expected cost
(to the minimizer) of transitioning from i 2 S under u 2 U(i) and v 2 V (i) is denoted
We denote the sets of one-stage policies for the minimizing and maximizing players
as M and N respectively, where
The sets of policies for the minimizing and maximizing players are denoted by -
M and
Given denote the transition probability matrix
that results when - and - are in effect. That is
Let c(-) denote the vector whose components are c i (-(i); -(i)). That is
Given two allowable opposing policies,
M and
N , we formally define the resulting cost (to the minimizer) to be
where
Note that h t
-M ;-N can be interpreted loosely as the expected t-stage cost vector under
the policies -M and -N .
In establishing our main results the definitions and assumptions in the following
paragraphs will be helpful. We say that a policy for the minimizer
is stationary if - k. When this is the case and no confusion can arise, we
use - to denote the corresponding policy -M , and we refer to -M as the stationary
policy -. Similar definitions hold for stationary policies of the maximizer.
The state 1 2 S has special importance. We shall refer to it as the terminal
state. This state is assumed to be absorbing and cost-free, that is p 11 (u;
and c 1 (u;
M and
4 S. D. PATEK AND D. P. BERTSEKAS
N be an arbitrary pair of policies. We say that the corresponding
Markov chain terminates with probability one if the following limit satisfies
lim
(The limit above exists because the sequence (for each i 2 S) is monotonically non-decreasing
and bounded above.) We shall refer to a pair of policies (- M ; -N ) as
terminating with probability one if the corresponding Markov chain terminates with
probability one; otherwise, we refer to the pair as prolonging.
A stationary policy - 2 M for the minimizer is said to be proper if the pair
(-N ) is terminating with probability one for all -N 2 -
N . A stationary policy - is
improper if it is not proper. If - is improper then there is a policy for the maximizer
N under which there is a positive probability that the game will never end from
some initial state. The designation of proper (or improper) applies only to stationary
policies for the minimizer.
It is convenient to define the set 0g. This is the space (of
cost vectors) over which our main results hold. We denote by 0 the zero vector in
. Let 1X denote the vector (0; . It is useful to define the following
operators on X .
sup
~
~
The suprema and infima in the above are taken componentwise. We use the notation
- (x) to denote the t-fold composition of T - applied to x 2 X . Similar definitions
hold for T t
- (x), and ~
In the Appendix, we collect (and prove
for completeness) some well-known results about these "T "-operators: monotonicity
(Lemma A.1) and continuity (Lemma A.3).
The following are our standing assumptions.
Assumption SSP The following are true:
1. There exists at least one proper policy for the minimizer.
2. If a pair of policies (- M ; -N ) is prolonging, then the expected cost to the
minimizer is infinite for at least one initial state. That is, there is a state i
for which lim t!1 [h t
Assumption R (Regularity) The following are true:
1. The control constraint sets are compact. That is, for each i 2 S, U(i) and
V (i) are compact subsets of metric spaces. (This implies that M and N are
compact.)
2. The functions are continuous with respect to (u; v) 2 U(i) \Theta V (i),
and the functions c i (u; v) are
(a) lower-semicontinuous with respect to u 2 U(i) (with
(b) upper-semicontinuous with respect to v 2 V (i) (with u 2 U(i) fixed).
(The Weierstrass theorem implies that the supremum and infimum in the
definitions of the operators T- and ~
T - are always achieved by elements of N
and M , respectively. That is, for every x 2 X, there exists - 2 N such that
X. Similarly, for every x 2 X, there exists
that ~
3. For all x 2 X, the infimum and supremum in the definitions of the operators T
and ~
are achieved by elements of M and N . That is, for every x 2 X, there
exists
4. For each x 2 X, we have T
Note that part 4 of Assumption R is satisfied under conditions for which a minimax
theorem can be used to interchange "inf" and "sup". In particular, this part, as well
as the entire Assumption R, is satisfied if:
1. the sets U(i) and V (i) are nonempty, convex, and compact subsets of Euclidean
spaces,
2. the functions are bilinear of the form u is a real
matrix of dimension commensurate with U(i) and V (i),
3. the functions c i (u; v) are
(a) convex and lower semi-continuous as functions of u 2 U(i) with v fixed
in V (i), and
(b) concave and upper semi-continuous as functions of
in U(i).
This follows from the Sion-Kakutani theorem (see [8], p.232 or [6], p. 397). We will
show in Section 3 that dynamic games with "mixed" strategies over finite underlying
action spaces satisfy this assumption.
To verify that a stationary policy - 2 M is proper, we need only check whether
(-) is terminating with probability one for all stationary policies - 2 N for the
maximizer. Furthermore, if - 2 M is improper, then we can always find a stationary
policy - 2 N for the maximizer which is prolonging when paired with -. This is
shown in the following lemma:
Lemma 2.1. If - 2 M is such that (-) terminates with probability one for all
Proof. The proof uses the analysis of [2]. Let - 2 M be a fixed policy for the
minimizer, and suppose that the pair (-) is terminating with probability one for
all stationary policies of the maximizer - 2 N . With - fixed, the maximizer is faced
with a stochastic shortest path problem of the type considered in [2]. (The maximizer
has no improper policies (against -).) Now modify the problem such that the costs
of transitioning from nonterminal states are all set to one but all of the transition
probabilities are left unchanged. The assumptions of [2] remain satisfied, so the
optimal expected cost for the maximizer in the new problem is bounded, even over
nonstationary policies. Thus, the maximum expected number of stages to termination
under - is finite. This is true for both the modified problem and the original version
of the game. This implies that - is proper. Q.E.D.
One of the objectives of this paper is to show that under Assumptions SSP and
R there exist policies -
M and -
N such that
x(-
Such a cost vector x   4
N ) is called the equilibrium cost vector (or value)
of the stochastic shortest path game. The policies -
M and -
N form an equilibrium
6 S. D. PATEK AND D. P. BERTSEKAS
solution. Since this is a zero-sum game, we know that the equilibrium cost (if it
exists) is unique. Another objective of this paper is to show that the equilibrium cost
vector is characterized as the unique solution to Bellman's equation, with stationary
equilibrium policies for the opposing players. After these results are established,
we proceed to show that value iteration and policy iteration converge to the unique
solution of Bellman's equation.
3. Connection to Shapley's Stochastic Games. The mathematical formulation
of the preceding section includes as a special case the stochastic games of Shapley.
To see this, assume that the number of actions available to either player at any state
is finite. As before, the players implement underlying actions simultaneously at each
stage, with full knowledge of the state of the system but without knowledge of each
other's current decision. However, the players are now allowed to randomize their
decisions in formulating a policy so as to keep their opponents from adapting to a deterministic
policy. That is, in considering what to do at each state, the players choose
probability distributions over underlying control sets rather than specific underlying
control actions. In other words, the players use randomized or "mixed" policies.
For each i 2 S, define A(i) and B(i) to be the finite sets of underlying actions
to the minimizer and maximizer, respectively. These are the physical controls the
players may ultimately implement at state i. Let jA(i)j and jB(i)j denote the numbers
of elements in each set of actions. We define the players' ``control constraint sets'' for
the game as
Thus, U(i) is the set of probability distributions over control actions A(i) available to
the minimizer from state i 2 S. Similarly, V (i) is the set of probability distributions
over underlying control actions B(i) available to the maximizer from state i 2 S. Here
the functions are respectively of the form
where the functions p ij and g ij denote the transition probabilities and costs of the
underlying two-player Markov Decision Process. Since the sets U(i) and V (i) are
polyhedral and the functions c i (u; v) and p ij (u; v) are bilinear for all i and j (and
continuous) as functions of (u; v) 2 U(i) \Theta V (i), it is clear that Assumption R is satis-
fied. (Parts 3 and 4 are satisfied thanks to the Minimax Theorem of von Neumann.)
4. Main Results. We now develop our main results; namely, the existence and
characterization of a unique equilibrium cost vector, the convergence of value iteration,
and the convergence of policy iteration. In Sections 4.1 and 4.2, we characterize
optimal solutions for the maximizer and minimizer, respectively, for the case where
the opposing player fixes a policy. After we lay this groundwork, we consider the
game proper in Section 4.3.
4.1. The Case Where the Minimizer's Policy is Fixed. Consider the policy
M . The cost of -M is defined by
The Appendix shows that, with our assumptions on c and P , the maximum in (4.1)
is attained for every t (see Lemma A.5). The cost of a stationary policy - for the
minimizer is denoted x(-) and is computed according to equation (4.1) where
Given a vector w 2 R n whose elements are positive, the corresponding weighted
sup-norm, denoted k \Delta k w
1 , is defined by
The next lemma follows from the theory of one-player stochastic shortest paths.
Lemma 4.1. Assume that all stationary policies for the minimizer are proper.
The operator T is a contraction mapping on the set
respect to a weighted sup-norm. Moreover, if - 2 M is proper, then T - is a contraction
mapping with respect to a weighted sup-norm.
Proof. We will show first the result about T for the case that all stationary policies
are proper. Our strategy is to identify a vector of weights w and to show that this
set of weights is one for which T is a contraction with respect to k \Delta k w
1 .
Let us define a new one-player stochastic shortest path problem of the type considered
in [2]. This problem is defined such that the transition probabilities remain
unchanged and the transition costs are all set equal to -1 for all states other than the
terminal state. The important difference is that the maximizer and minimizer "work
together" in the sense that the decision space (for the single player of the new prob-
lem) is over -
M \Theta -
N . This is a stochastic shortest path problem where all stationary
policies are proper. Using the results of [2], there is an optimal cost vector ~
which can be achieved using a stationary policy (~-; ~
M \Theta -
N . Note that, since
the transition costs from all non-terminal states are set to -1 in the new stochastic
shortest path problem, we have ~
1. Moreover, from Bellman's
equation we have
~
Also, for all
~
Thus, for all
. Since the ~
we have that fl 2 [0; 1).
Now define
. Note that w is a vector in R n whose elements
are all strictly positive.
8 S. D. PATEK AND D. P. BERTSEKAS
Let us now resume consideration of the original stochastic shortest path game.
Let x and -
x be any two elements of X such that
be such
that be such that T
Thus,
Using this, we see that for all i
where the last inequality follows from (4.2). Thus, we get
Using similar arguments, we may show that,
Combining the preceding inequalities, we see that kT
we have that T is a contraction over X with respect to k \Delta k w
1 .
Now suppose - 2 M is proper. By viewing T - as the "T "-operator in a new game
where U(i) j f-(i)g, we have the desired result. Q.E.D.
Lemma 4.2. Given a proper policy -, the following are true.
1. The cost x(-) of - is the unique fixed point of T - in
2.
3. We have T t
linear convergence.
Proof. An induction argument (cf. Appendix Lemma A.5) easily shows that
where 0 is the zero vector in X . Thus, using preceding lemma and the definition of
x(-), we have
where ~
x- is the unique fixed point of the contraction mapping T - within X , proving
statement 1.
Consider the following infinite-horizon stochastic shortest path problem for the
maximizer:
sup
lim inf
This problem is covered by the theory developed in [2] since the fact that - is proper
implies that termination is inevitable under all policies in the maximizer's problem.
The optimal cost of this problem is sup -N2 -
according to the theory
of [2], it is equal to the limit of the successive approximation method applied to this
problem, which is lim t!1 T t+1
- (0) and is also the unique fixed point of T - within X .
This proves statement 2.
Finally, the linear convergence of T t+1
- (0) follows from the contraction property
of
Lemma 4.3. If x - T - (x) for some x 2 X, then - is proper.
Proof. To reach a contradiction, suppose - is improper. According to Assumption
SSP and Lemma 2.1, there exists a stationary maximizer's policy -
such that
(-) is prolonging and results in unbounded expected cost from some initial state
when played against -.
Let x be an element in X such that x - T - (x). Then, applying T- to x, we have
that
where the second inequality follows from the definition of T - . From the monotonicity
of
-)c(-
where the last inequality follows again from the definition of T - . Proceeding induc-
tively, using the same steps, we have that for all t
On the other hand, because the policy - results in infinite expected cost (from
some initial state) when played against -, some subsequence of
must have a coordinate that tends to infinity. (The term involving x remains bounded
because it is just x multiplied by the product of stochastic matrices.) This contradicts
the above inequality. Thus, - must be proper. Q.E.D.
S. D. PATEK AND D. P. BERTSEKAS
4.2. The Case Where the Maximizer's Policy is Fixed. By Assumption
SSP there exists a proper policy for the minimizer. Thus, it is impossible that a single
policy for the maximizer prolongs the game for all policies of the minimizer. Let us
define ~
x(-N ) to be the cost of the policy -N 2 -
~
min
:g. The cost of a stationary policy - for the minimizer is
denoted ~
x(-) and is computed according to equation (4.3) where
Lemma 4.4. For any - 2 N , the following are true.
1. The cost ~
x(-) of - is the unique fixed point of ~
2. ~
3. We have ~
x(-) for all x 2 X. If for all - 2 M , the pair (-)
terminates with probability one, then the convergence is linear.
Proof. This follows directly from the theory of (one-player) stochastic shortest
path problems. Q.E.D.
4.3. Main Results for the Game. We now establish the main results of the
paper: the existence and characterization of a unique equilibrium solution, the convergence
of value iteration, and the convergence of policy iteration.
Proposition 4.5. The operator T has a unique fixed point x   on X.
Proof. We begin by showing that T has at most one fixed point in X . Suppose
x and x 0 are both fixed points of T in X . We can select
that we have that -
and - 0 are proper. Lemma 4.2 implies that
necessarily optimal with respect to x in applying the T operator, we have from the
monotonicity of T that
have that x - lim t!1 T t
Similarly, x 0 - x, which implies that
that T has at most one fixed point in X .
To establish the existence of a fixed point, fix a proper policy - 2 M for the
minimizer. (One exists thanks to Assumption SSP.) By Lemma 4.2, we have that
Similarly, by fixing a stationary policy
for the maximizer, we obtain from Lemma 4.4 that ~
~
x(- ~
now claim that ~
x(- x(-). To see this, note that,
for every -M 2 -
N , and t ? 0,
and
where we have used the notation defined in (2.2). Thus, for any -N 2 -
N and for any
min
~
~
-M
By taking the limit inferior of both sides with respect to t, we see that ~ x(-N
for all -N 2 -
N and -M 2 -
M . In particular, ~ x(- x(-).
Using the monotonicity of T we have that
~
Again from the monotonicity of T , we obtain for all t ? 1 that
Thus, the sequence fT t (~x(-))g converges to a vector x 1 2 X . From the continuity
of T , we have that x Thus, T has a fixed point in X . Q.E.D.
Proposition 4.6. The unique fixed point x  is the equilibrium cost of
the stochastic shortest path game. There exist stationary policies -   2 M and -   2 N
which achieve the equilibrium. Moreover, if x 2 X, are such that
1.
2.
3. x(-N
Proof. That there exists a unique fixed point x  from the preceding
proposition. Let -   2 M be such that x
be such that x
(Such policies exist thanks to Assumption
R.) By Lemma 4.3, we have that -   is proper. Thus, by Lemma 4.2, we
have that x
Similarly, by Lemma 4.4, we have that
Combining these results we obtain
sup
Since in general we have
sup
(a statement of the Minimax Inequality), we obtain the desired result:
sup
Q.E.D.
Lemma 4.1 implies that, when all stationary policies for the minimizer are proper,
the iteration x converges linearly to the equilibrium cost x   for all
This follows from the contraction mapping principle. In the following proposition, we
extend this result to the case where not all stationary policies for the minimizer are
proper.
Proposition 4.7. For every x 2 X, there holds,
lim
where x   is the unique equilibrium cost vector.
Proof. The uniqueness and existence of a fixed point for T was established in
Proposition 4.5. Let x   be the unique fixed point, and let -   2 M (proper) be such
that T (x   Our objective is to show that T t
\Delta be the vector with coordinates,
ae 0; if
S. D. PATEK AND D. P. BERTSEKAS
where ffi is some scalar. Let x \Delta be the unique vector in X satisfying T -
\Delta. (Such a vector exists because -   is proper, making the operator
a contraction.) Note that
Thus, x \Delta is the minimax cost of the fixed policy -   with the immediate transition
cost c(-   ; \Delta) replaced with c(-   \Delta. We have that
Thus, from the monotonicity of T -   we have that for all t ? 0
By taking the limit as t ! 1, we see that x(-   ) - x \Delta . (This is also implied by our
interpretation of x \Delta above.)
Now using the monotonicity of T and the fact that x
Proceeding inductively, we get
Hence, fT t (x \Delta )g is a monotonically decreasing sequence bounded below which converges
to some ~ x 2 X . By continuity of the operator T , we must have that ~
By the uniqueness of the fixed point of T , we have that ~
We now examine the convergence of the operator T t applied to x   \Gamma \Delta. Note
that,
where the first inequality follows from the fact that P (-
and - 2 N . Once again monotonicity of T prevails, implying that T t (x   \Gamma \Delta) is
monotonically increasing and bounded above. From the continuity of T we have that
We saw earlier that x . Then, from the
monotonicity of T -
Thus, for any x 2 X we can find ffi ? 0 such that x  . By the
monotonicity of T , we then have,
Taking limits, we see that lim t!1 T t
Proposition 4.8. Given a proper stationary policy - we have that
where x   is the unique equilibrium cost vector and f- k g is a sequence of policies
(generated by policy iteration) such that T (x(- k
Proof. Choose
implies that such an initial proper policy - 0 exists.) We have
proper. By the monotonicity of T - 1 and
Lemma 4.2, we have that for all t
Thus,
Applying this argument iteratively, we construct a sequence f- k g of proper policies
such that,
monotonically decreasing and bounded below by x   , we have that
the entire sequence converges to some vector x 1 . From (4.6) and the continuity of
T , we have that x is the unique fixed point of T on X , we have
that x(- k
5. An Example of Pursuit and Evasion. Consider the following two-player
game, played around a table with four corners. One player, the pursuer (who is
actually the minimizer), is attempting to "catch" in minimum time the other player,
the evader (who is the maximizer). The game evolves in stages where, in each stage,
both players implement actions simultaneously. When the players are across from
one another, they each decide (independently) whether to stay where they are, move
one corner clockwise, or move one corner counter-clockwise. When the two players
are adjacent to one another, they each decide (independently) whether to stay where
they are, move toward the other's current location, or move away from the other's
current location. The pursuer catches the evader only by arranging to land on the
same corner of the table as the evader. (The possibility exists that, when they are
adjacent, they can both move toward each other's current location. This does not
result in the evader being caught "in mid-air".) The evader is slower than the pursuer
in the sense that, when the evader decides to change location, he succeeds in doing
so only with probability the evader will wind up
not moving at all.) Thus, the pursuer can ultimately catch the evader, provided he
implements an appropriate policy (such as "always move toward the present location
of the evader"). On the other hand, there exist policies for the pursuer (such as
"always stay put") which allow the maximizer to prolong the game indefinitely. This
results in infinite cost (i.e. infinite capture time) to the pursuer.
This game fits into our framework for stochastic shortest path games. As described
above there are three states: evader caught (state 1), players adjacent to one
another (state 2), and players across from one another (state 3). Thus, 3g.
Once the evader is caught, the game is over, so state 1 serves as the terminal state,
which is zero cost and absorbing.
In state two, when the players are adjacent, the players may move toward the
other's location (action 1), stay where they are (action 2), or move away from the
other's location (action 3). Thus, 3g. From the description of
the problem given above, it is not hard to see that
14 S. D. PATEK AND D. P. BERTSEKAS
The expected transition cost functions c 2 (u; v) take on the value of one for all u 2 U(2)
and
In state three (when the players are on opposite corners of the table), the players
may move clockwise toward the other's current location (action 1), stay where they
are (action 2), or move counter-clockwise toward the other's location (action 3). Thus,
3g. It is not hard to see that
The expected transition cost functions c 3 (u; v) take on the value of one for all u 2 U(3)
and
We will show that the equilibrium value of this stochastic shortest path game is
given by
and that equilibrium randomized strategies for the two players are given by -   2 M
and -   2 N such that
are nonnegative, and
any probability vector forms an equilibrium strategy for
the evader. In other words, as long as the evader chooses not to remain at his current
location (when the two players are adjacent), any mixed decision (at state 2) for the
evader is optimal. The pursuer does not have the same flexibility; his optimal mixed
decision is deterministic: always move toward the evader. On the other hand, any
probability vector u 2 U(3) such that u forms an equilibrium strategy for the
pursuer. In other words, as long as the pursuer decides to not stay at his current
location (when the two players are across from one another), any mixed decision for
the pursuer (at state 3) is optimal. This time, it is the evader's strategy which is
inflexible. His optimal action is to stay at his current location. Thus, when both
players play optimally, the game will always transition from state
one stage. Happily, the equilibrium cost reflects this: x
.
To verify that these are indeed equilibrium policies, we will show that x
(Notice that the policy -   corresponds to one where the
pursuer always decides to move in the direction of the current location of the evader.
This policy is clearly proper. The desired result follows from Corollary 4.6.)
Let us first consider the case where the two players are adjacent (i.e. state 2).
Let a general cost-to-go vector be given as (Shortly, we shall
consider the case where suggested above.) To evaluate the second element
of T (x), we must compute
min
v2V (2)
where the matrix G 2 (x) is computed as
In other words, the second element of T (x) is evaluated as the value of the matrix
game (in mixed strategies) defined by G 2 (x). It is well known that the equilibrium
cost and equilibrium strategies for a matrix game are characterized as the optimal
value and solutions to a particular linear program and it's dual [12]. In particular,[T (x)] 2
subject to G 2 (x)-v -
subject to G 2 (x)-v -
where e is the vector of all ones in R 3 , and v   is an equilibrium strategy for the
maximizer in the matrix-game. We shall refer to the linear program above as the
"primal" problem. The dual of the primal problem characterizes equilibrium strategies
for the minimizer of the matrix game:
subject to G 2
Now consider G 2 (x   ) and define
It is straightforward to verify that - v   is feasible for the primal linear program and that
u   is feasible for the dual problem. Moreover, the primal cost corresponding to - v   is
exactly just as the dual value of - u   is also exactly 1 \Gamma p. Thus, we have found
a primal/dual feasible pair for which the primal cost equals the dual value. Then,
according to the duality theorem of linear programming, -
are primal/dual
optimal, and the optimal values of the primal and dual problems equal
is exactly 1
x  . This verifies that x
and that -   (2) and -   (2) form an
equilibrium pair of mixed decisions at state 2 2 S.
Let us now consider the case where the two players are across from one another
(i.e. state 3). To evaluate the third element of T (x) for general x 2 X , we must
compute
min
where G 3 (x) is a matrix computed as
S. D. PATEK AND D. P. BERTSEKAS
Thus the third element of T (x) is evaluated as the value of the matrix game defined
by G 3 (x). As before, the solution to this matrix game can be computed by solving a
primal/dual pair of linear programs:
subject to G 3 (x)-v - e; -
subject to G 3
Now consider the primal and dual problems given by G 3 (x   ). Define
(0;
Again, it is straightforward to verify that - v and - u form a feasible primal/dual pair
where the primal cost of - v equals the dual value of -
u. Thus, by the duality theorem,
v and - u are primal/dual optimal. This time the optimal cost works out to be 1\Gammap
which is exactly 1
x  . This verifies that x
an equilibrium pair of mixed decisions at state 3 2 S.

Acknowledgments

. Our proof of Lemma 4.1 was inspired by an argument by
John Tsitsiklis for a similar result in one-player stochastic shortest path problems. We
would like to thank our anonymous SIAM reviewers who, through their persistence,
have helped us to find the shortest path to establishing our results.



--R

Parallel and Distributed Computation: Numerical Methods
Analysis of Stochastic Shortest Path Problems
Zero Sum Dynamic Games
Finite State

Convex Analysis

Convexity and Optimization in Finite Dimensions I
Stationary Markov Decision Problems in Time Proportional to Log(H)
Mathematical Centre Tracts 139
Theory of Games and Economic Behavior.
Game Theory

--TR
game theory;stochastic games;stochastic shortest paths;optimization;dynamic programming