A note on two-person zero-sum communicating stochastic games

For undiscounted two-person zero-sum communicating stochastic games with finite state and action spaces, a solution procedure is proposed that exploits the communication property, i.e., working with irreducible games over restricted strategy spaces. The proposed procedure gives the value of the communicating game with an arbitrarily small error when the value is independent of the initial state.     

Average stochastic games for continuous-time jump processes

We consider nonzero-sum games for continuous-time jump processes with unbounded transition rates under expected average payoff criterion. The state and action spaces are Borel spaces and reward rates are unbounded. We introduce an approximating sequence of stochastic game models with extended state space, for which the uniform exponential ergodicity is obtained. Moreover, we prove the existence of a stationary almost Markov Nash equilibrium by introducing auxiliary static game models. Finally, a cash flow model is employed to illustrate the results.     

Existence of nash equilibria for constrained stochastic games

In this paper, we consider constrained noncooperative N-person stochastic games with discounted cost criteria. The state space is assumed to be countable and the action sets are compact metric spaces. We present three main results. The first concerns the sensitivity or approximation of constrained games. The second shows the existence of Nash equilibria for constrained games with a finite state space (and compact actions space), and, finally, in the third one we extend that existence result to a class of constrained games which can be “approximated” by constrained games with finitely many states and compact action spaces. Our results are illustrated with two examples on queueing systems, which clearly show some important differences between constrained and unconstrained games.Mathematics Subject Classification (2000): Primary: 91A15. 91A10; Secondary: 90C40     

Stochastic Games with Average Payoff Criterion

We study two-person stochastic games on a Polish state and compact action spaces and with average payoff criterion under a certain ergodicity condition. For the zero-sum game we establish the existence of a value and stationary optimal strategies for both players. For the nonzero-sum case the existence of Nash equilibrium in stationary strategies is established under certain separability conditions. Accepted 9 January 1997     

An operator solution of stochastic games

A class of zero-sum, two-person stochastic games is shown to have a value which can be calculated by transfinite iteration of an operator. The games considered have a countable state space, finite action spaces for each player, and a payoff sufficiently general to include classical stochastic games as well as Blackwell’s infiniteG _δ games of imperfect information. Research supported by National Science Foundation Grants DMS-8801085 and DMS-8911548.     

Existence of equilibrium stationary strategies in discounted noncooperative stochastic games with uncountable state space

This paper considers discounted noncooperative stochastic games with uncountable state space and compact metric action spaces. We assume that the transition law is absolutely continuous with respect to some probability measure defined on the state space. We prove, under certain additional continuity and integrability conditions, that such games have -equilibrium stationary strategies for each >0. To prove this fact, we provide a method for approximating the original game by a sequence of finite or countable state games. The main result of this paper answers partially a question raised by Parthasarathy in Ref. 1.     

On stochastic games

In this paper, we consider the stochastic games of Shapley, when the state and action spaces are all infinite. We prove that, under certain conditions, the stochastic game has a value and that both players have optimal strategies.Part of this research was supported by NSF grant. The authors are indebted to L. S. Shapley for the useful discussions on this and related topics. The authors thank the referee for pointing out an ambiguity in the formulation of Lemma 2.4 in an earlier draft of this article.     

Denumerable state stochastic games with limiting average payoff

We study stochastic games with countable state space, compact action spaces, and limiting average payoff. ForN-person games, the existence of an equilibrium in stationary strategies is established under a certain Liapunov stability condition. For two-person zero-sum games, the existence of a value and optimal strategies for both players are established under the same stability condition.The authors wish to thank Prof. T. Parthasarathy for pointing out an error in an earlier version of this paper. M. K. Ghosh wishes to thank Prof. A. Arapostathis and Prof. S. I. Marcus for their hospitality and support.     

On stochastic games,II

In this paper, we consider positive stochastic games, when the state and action spaces are all infinite. We prove that, under certain conditions, the positive stochastic game has a value and that the maximizing player has an -optimal stationary strategy and the minimizing player has an optimal stationary strategy.The authors are grateful to Professor David Blackwell and the referee for some useful comments.     

Two-person zero-sum stochastic games

Two-person zero-sum stochastic games with finite state and action spaces are considered. The expected average payoff criterion is introduced. In the special case of single controller games it is shown that the optimal stationary policies and the value of the game can be obtained from the optimal solutions to a pair of dual programs. For multichain structures, a decomposition algorithm is given which produces such optimal stationary policies for both players. In the case of both players controlling the transitions, a generalized game is obtained, the solution of which gives the optimal policies.     

Forward–Backward Stochastic Differential Games and Stochastic Control under Model Uncertainty

We study optimal stochastic control problems with jumps under model uncertainty. We rewrite such problems as stochastic differential games of forward–backward stochastic differential equations. We prove general stochastic maximum principles for such games, both in the zero-sum case (finding conditions for saddle points) and for the nonzero sum games (finding conditions for Nash equilibria). We then apply these results to study robust optimal portfolio-consumption problems with penalty. We establish a connection between market viability under model uncertainty and equivalent martingale measures. In the case with entropic penalty, we prove a general reduction theorem, stating that a optimal portfolio-consumption problem under model uncertainty can be reduced to a classical portfolio-consumption problem under model certainty, with a change in the utility function, and we relate this to risk sensitive control. In particular, this result shows that model uncertainty increases the Arrow–Pratt risk aversion index.     

Perfect equilibria in stochastic games

We examine stochastic games with finite state and action spaces. For the -discounted case, as well as for the irreducible limiting average case, we show the existence of trembling-hand perfect equilibria and give characterizations of those equilibria. In the final section, we give an example which illustrates that the existence of stationary limiting average equilibria in a nonirreducible stochastic game does not imply the existence of a perfect limiting average equilibrium.Support was provided by the Netherlands Organization for Scientific Research NWO via the Netherlands Foundation for Mathematics SMC, Project 10-64-10.     

A policy iteration algorithm for zero-sum stochastic games with mean payoff

We give a policy iteration algorithm to solve zero-sum stochastic games with finite state and action spaces and perfect information, when the value is defined in terms of the mean payoff per turn. This algorithm does not require any irreducibility assumption on the Markov chains determined by the strategies of the players. It is based on a discrete nonlinear analogue of the notion of reduction of a super-harmonic function. To cite this article: J. Cochet-Terrasson, S. Gaubert, C. R. Acad. Sci. Paris, Ser. I 343 (2006).     

Noncooperative stochastic games under a n-stage local contraction assumption

We consider a class of noncooperative stochastic games with general state and action spaces and with a state dependent discount factor. The expected time duration between any two stages of the game is not bounded away from zero, so that the usual N-stage contraction assumption, uniform over all admissible strategies, does not hold. We propose milder sufficient regularity conditions, allowing strategies that give rise with probability one to any number of simultaneous stages. We give sufficient conditions for the existence of equilibrium and ∈-equilibrium stationary strategies in the sense of Nash. In the two-player zero-sum case, when an equilibrium strategy exists, the value of the game is the unique fixed point of a specific functional operator and can be computed by dynamic programming.     

Fictitious play applied to sequences of games and discounted stochastic games

In this paper, we show that the iterative method of Brown and Robinson, for solving a matrix game, is also applicable to a converging sequence of matrices, where the players choose at staget a row and a column of thet-th matrix in the sequence. As an application of this result, we describe a new solution method for discounted stochastic games with finite state and action spaces.     

Stochastic games with non-observable actions

We examine n-player stochastic games. These are dynamic games where a play evolves in stages along a finite set of states; at each stage players independently have to choose actions in the present state and these choices determine a stage payoff to each player as well as a transition to a new state where actions have to be chosen at the next stage. For each player the infinite sequence of his stage payoffs is evaluated by taking the limiting average. Normally stochastic games are examined under the condition of full monitoring, i.e. at any stage each player observes the present state and the actions chosen by all players. This paper is a first attempt towards understanding under what circumstances equilibria could exist in n-player stochastic games without full monitoring. We demonstrate the non-existence of -equilibria in n-player stochastic games, with respect to the average reward, when at each stage each player is able to observe the present state, his own action, his own payoff, and the payoffs of the other players, but is unable to observe the actions of them. For this purpose, we present and examine a counterexample with 3 players. If we further drop the assumption that the players can observe the payoffs of the others, then counterexamples already exist in games with only 2 players.