On the existence of good stationary strategies for nonleavable stochastic games

This paper discusses the problem regarding the existence of optimal or nearly optimal stationary strategies for a player engaged in a nonleavable stochastic game. It is known that, for these games, player I need not have an -optimal stationary strategy even when the state space of the game is finite. On the contrary, we show that uniformly -optimal stationary strategies are available to player II for nonleavable stochastic games with finite state space. Our methods will also yield sufficient conditions for the existence of optimal and -optimal stationary strategies for player II for games with countably infinite state space. With the purpose of introducing and explaining the main results of the paper, special consideration is given to a particular class of nonleavable games whose utility is equal to the indicator of a subset of the state space of the game.     

Almost Stationary ∈-Equilibria in Zero-Sum Stochastic Games

We show the existence of almost stationary -equilibria, for all > 0, in zero-sum stochastic games with finite state and action spaces. These are -equilibria with the property that, if neither player deviates, then stationary strategies are played forever with probability almost 1. The proof is based on the construction of specific stationary strategy pairs, with corresponding rewards equal to the value, which can be supplemented with history-dependent -optimal strategies, with small > 0, in order to obtain almost stationary -equilibria.     

General sum games with joint chance constraints

We consider an $n$-player non-cooperative game with continuous strategy sets. The strategy set of each player contains a set of stochastic linear constraints. We model the stochastic linear constraints of each player as a joint chance constraint. We assume that the row vectors of a matrix defining the stochastic constraints of each player are independent and each row vector follows a multivariate normal distribution. Under certain conditions, we show the existence of a Nash equilibrium for this game.     

Simulation accuracy of stationary Gaussian stochastic processes inL 2(0,T)

Models of stationary Gaussian stochastic processes with discrete and continuous spectra are constructed. Simulation of stationary Gaussian processes with a continuous spectrum is considered for the following cases: when the covariance function of the stochastic process is expandable in a Fourier series with positive coefficients; when the spectrum of the stationary Gaussian stochastic process is concentrated on the interval [0, ]; and in the general case. The stationary Gaussian process is simulated with prescribed reliability and accuracy in L²(0, T).Kiev University. Translated from Vychislitel'naya i Prikladnaya Matematika, No. 75, pp. 108–115, 1991.     

Ordered field property for stochastic games when the player who controls transitions changes from state to state

In this paper, we consider a zero-sum stochastic game with finitely many states restricted by the assumption that the probability transitions from a given state are functions of the actions of only one of the players. However, the player who thus controls the transitions in the given state will not be the same in every state. Further, we assume that all payoffs and all transition probabilities specifying the law of motion are rational numbers. We then show that the values of both a -discounted game, for rational , and of a Cesaro-average game are in the field of rational numbers. In addition, both games possess optimal stationary strategies which have only rational components. Our results and their proofs form an extension of the results and techniques which were recently developed by Parthasarathy and Raghavan (Ref. 1).The author wishes to thank Professor T. E. S. Raghavan for introducing him to this problem and for discussing stochastic games with him on many occasions. This research was supported in part by AFOSR Grant No. 78–3495B.     

Zero-sum Markov games and worst-case optimal control of queueing systems

Zero-sum stochastic games model situations where two persons, called players, control some dynamic system, and both have opposite objectives. One player wishes typically to minimize a cost which has to be paid to the other player. Such a game may also be used to model problems with a single controller who has only partial information on the system: the dynamic of the system may depend on some parameter that is unknown to the controller, and may vary in time in an unpredictable way. A worst-case criterion may be considered, where the unknown parameter is assumed to be chosen by nature (called player 1), and the objective of the controller (player 2) is then to design a policy that guarantees the best performance under worst-case behaviour of nature. The purpose of this paper is to present a survey of stochastic games in queues, where both tools and applications are considered. The first part is devoted to the tools. We present some existing tools for solving finite horizon and infinite horizon discounted Markov games with unbounded cost, and develop new ones that are typically applicable in queueing problems. We then present some new tools and theory of expected average cost stochastic games with unbounded cost. In the second part of the paper we present a survey on existing results on worst-case control of queues, and illustrate the structural properties of best policies of the controller, worst-case policies of nature, and of the value function. Using the theory developed in the first part of the paper, we extend some of the above results, which were known to hold for finite horizon costs or for the discounted cost, to the expected average cost.     

Stationary,completely mixed and symmetric optimal and equilibrium strategies in stochastic games

In this paper, we address various types of two-person stochastic games—both zero-sum and nonzero-sum, discounted and undiscounted. In particular, we address different aspects of stochastic games, namely: (1) When is a two-person stochastic game completely mixed? (2) Can we identify classes of undiscounted zero-sum stochastic games that have stationary optimal strategies? (3) When does a two-person stochastic game possess symmetric optimal/equilibrium strategies? Firstly, we provide some necessary and some sufficient conditions under which certain classes of discounted and undiscounted stochastic games are completely mixed. In particular, we show that, if a discounted zero-sum switching control stochastic game with symmetric payoff matrices has a completely mixed stationary optimal strategy, then the stochastic game is completely mixed if and only if the matrix games restricted to states are all completely mixed. Secondly, we identify certain classes of undiscounted zero-sum stochastic games that have stationary optima under specific conditions for individual payoff matrices and transition probabilities. Thirdly, we provide sufficient conditions for discounted as well as certain classes of undiscounted stochastic games to have symmetric optimal/equilibrium strategies—namely, transitions are symmetric and the payoff matrices of one player are the transpose of those of the other. We also provide a sufficient condition for the stochastic game to have a symmetric pure strategy equilibrium. We also provide examples to show the sharpness of our results.     

Nonzero-sum stochastic games with unbounded costs: Discounted and average cost cases

We treat non-cooperative stochastic games with countable state space and with finitely many players each having finitely many moves available in a given state. As a function of the current state and move vector, each player incurs a nonnegative cost. Assumptions are given for the expected discounted cost game to have a Nash equilibrium randomized stationary strategy. These conditions hold for bounded costs, thereby generalizing Parthasarathy (1973) and Federgruen (1978). Assumptions are given for the long-run average expected cost game to have a Nash equilibrium randomized stationary strategy, under which each player has constant average cost. A flow control example illustrates the results. This paper complements the treatment of the zero-sum case in Sennott (1993a).     

Periodic Solution and Stationary Distribution of Stochastic Predator–Prey Models with Higher-Order Perturbation

In this paper, two stochastic predator–prey models with general functional response and higher-order perturbation are proposed and investigated. For the nonautonomous periodic case of the system, by using Khasminskii’s theory of periodic solution, we show that the system admits a nontrivial positive T-periodic solution. For the system disturbed by both white and telegraph noises, sufficient conditions for positive recurrence and the existence of an ergodic stationary distribution to the solutions are established. The existence of stationary distribution implies stochastic weak stability to some extent.     

A pursuit-evasion differential game with noisy measurements of the evader's bearing from the pursuer

A stochastic pursuit-evasion differential game involving two players, E and P, moving in the plane is considered. It is assumed that player E (the evader) has complete observation of the position and velocity of player P, whereas player P (the pursuer) can measure the distanced (P, E) between P and E but receives noise-corrupted measurements of the bearing of E from P. Three cases are dealt with: (a) using the noise-corrupted measurements of , player P applies the proportional navigation guidance law; (b) P has complete observation ofd (P, E) and (this case is treated for the sake of completeness); (c) using the noise-corrupted measurements of , P applies an erroneous line-of sight guidance law. For each of the cases, sufficient conditions on optimal strategies are derived. In each of the cases, these conditions require the solution of a nonlinear partial differential equation on a in ². Finally, optimal strategies are computed by solving the corresponding equations numerically.     

Discrete Spectrum of Nonstationary Stochastic Processes on Groups

Vector-valued, asymptotically stationary stochastic processes on -compact locally compact abelian groups are studied. For such processes, we introduce a stationary spectral measure and show that it is discrete if and only if the asymptotically stationary covariance function is almost periodic. Using an almost periodic Fourier transform we recover the discrete part of the spectral measure and construct a natural, consistent estimator for the latter from samples of the process.     

Semi-markov strategies in stochastic games

For a stochastic game with countable state and action spaces we prove, that solutions in the game where all players are restricted to semi-markov strategies are solutions for the unrestricted game. In addition we show, that if all players, except for one, fix a stationary strategy, then the best the remaining player can do, is solving a markov decision problem, corresponding to the fixed stationary strategies.     

Zero-Sum Ergodic Semi-Markov Games with Weakly Continuous Transition Probabilities

Zero-sum ergodic semi-Markov games with weakly continuous transition probabilities and lower semicontinuous, possibly unbounded, payoff functions are studied. Two payoff criteria are considered: the ratio average and the time average. The main result concerns the existence of a lower semicontinuous solution to the optimality equation and its proof is based on a fixed-point argument. Moreover, it is shown that the ratio average as well as the time average payoff stochastic games have the same value. In addition, one player possesses an ε-optimal stationary strategy (ε>0), whereas the other has an optimal stationary strategy. A. Jaśkiewicz is on leave from Institute of Mathematics and Computer Science, Wrocław University of Technology. This work is supported by MNiSW Grant 1 P03A 01030.     

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.     

Existence theorems for games of survival

A two-person, zero-sum differential game of survival with general type phase constraints is investigated. The dynamics of both players is governed by a system of differential inclusions. Player II can choose any strategy in the Varaiya-Lin sense, while player I can select any lower -strategy (Ref. 1, p. 400). The existence of a value and an optimal strategy for player II is proved under the assumptions that the set of all player II's trajectories is compact in the Banach space of all continuous mappings and that some capturability condition is fulfilled.     

Stationary solutions of SPDEs and infinite horizon BDSDEs with non-Lipschitz coefficients

We prove a general theorem that the -valued solution of an infinite horizon backward doubly stochastic differential equation, if exists, gives the stationary solution of the corresponding stochastic partial differential equation. We prove the existence and uniqueness of the -valued solutions for backward doubly stochastic differential equations on finite and infinite horizon with linear growth without assuming Lipschitz conditions, but under the monotonicity condition. Therefore the solution of finite horizon problem gives the solution of the initial value problem of the corresponding stochastic partial differential equations, and the solution of the infinite horizon problem gives the stationary solution of the SPDEs according to our general result.     

Stationary solutions of SPDEs and infinite horizon BDSDEs

In this paper we study the existence of stationary solutions for stochastic partial differential equations. We establish a new connection between valued solutions of backward doubly stochastic differential equations (BDSDEs) on infinite horizon and the stationary solutions of the SPDEs. Moreover, we prove the existence and uniqueness of the solutions of BDSDEs on both finite and infinite horizons, so obtain the solutions of initial value problems and the stationary solutions (independent of any initial value) of SPDEs. The connection of the weak solutions of SPDEs and BDSDEs has independent interests in the areas of both SPDEs and BSDEs.     

Asymptotic Expansion of M ‐Estimator Over Wiener Space

In this paper we consider an Mestimator defined as a solution of a given estimating function. Sufficient conditions of existence of an Mestimator and its stochastic expansion are presented. In the case where the underlying probability space is a Wiener space and the leading term of the stochastic expansion is a martingale, asymptotic expansions of its distribution function are obtained with the aid of Malliavin calculus. Applications to a stationary ergodic diffusion model are also discussed.     

Markov Games with Several Ergodic Classes

We consider Markov games of the general form characterized by the property that, for all stationary strategies of players, the set of game states is partitioned into several ergodic sets and a transient set, which may vary depending on the strategies of players. As a criterion, we choose the mean payoff of the first player per unit time. It is proved that the general Markov game with a finite set of states and decisions of both players has a value, and both players have -optimal stationary strategies. The correctness of this statement is demonstrated on the well-known Blackwell's example (Big Match).     

A utilization of properties of the discrete-time Riccati equation in stochastic realization theory

The problem of generating families of wide-sense, stochastic realizations of a discrete-time stationary stochastic process is considered. To do this, it is known that a Riccati equation has to be solved. In this paper, the non-Riccati algorithm of Lindquist and Kailath is used to generate families of realizations, the state covariances of which are totally ordered. Finally, the property of constant directions which the discrete-time Riccati equation enjoys is utilized to obtain families of realizations, the state covariances of which have the same value in certain directions.