Stochastic shortest path games

Stephen D. Patek, Dimitri P. Bertsekas

Research output: Contribution to journalArticlepeer-review

41 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)804-824
Number of pages21
JournalSIAM Journal on Control and Optimization
Issue number3
StatePublished - 1999
Externally publishedYes

ASJC Scopus subject areas

  • Control and Optimization
  • Applied Mathematics


Dive into the research topics of 'Stochastic shortest path games'. Together they form a unique fingerprint.

Cite this