Zero-sum risk-sensitive stochastic games on a countable state space

Infinite horizon discounted-cost and ergodic-cost risk-sensitive zero-sum stochastic games for controlled Markov chains with countably many states are analyzed. Upper and lower values for these games are established. The existence of value and saddle-point equilibria in the class of Markov strategies is proved for the discounted-cost game. The existence of value and saddle-point equilibria in the class of stationary strategies is proved under the uniform ergodicity condition for the ergodic-cost game. The value of the ergodic-cost game happens to be the product of the inverse of the risk-sensitivity factor and the logarithm of the common Perron–Frobenius eigenvalue of the associated controlled nonlinear kernels.     

Existence of Value and Saddle Point in Infinite-Dimensional Differential Games

We study two-player zero-sum differential games of finite duration in a Hilbert space. Following the Berkovitz notion of strategies, we prove the existence of value and saddle-point equilibrium. We characterize the value as the unique viscosity solution of the associated Hamilton–Jacobi–Isaacs equation using dynamic programming inequalities.     

On saddle-point optimality in differential games

A family of two-person, zero-sum differential games in which the admissible strategies are Borel measurable is defined, and two types of saddle-point conditions are introduced as optimality criteria. In one, saddle-point candidates are compared at each point of the state space with all playable pairs at that point; and, in the other, they are compared only with strategy pairs playable on the entire state space. As a theorem, these two types of optimality are shown to be equivalent for the defined family of games. Also, it is shown that a certain closure property is sufficient for this equivalence. A game having admissible strategies everywhere constant, in which the two types of saddle-point candidates are not equivalent, is discussed.This paper is based on research supported by ONR.     

Linear-quadratic,two-person,zero-sum differential games: Necessary and sufficient conditions

We consider linear-quadratic, two-person, zero-sum perfect information differential games, possibly with a linear target set. We show a necessary and sufficient condition for the existence of a saddle point, within a wide class of causal strategies (including, but not restricted to, pure state feedbacks). The main result is that, when they exist, the optimal strategies are pure feedbacks, given by the classical formulas suitably extended, and that existence may be obtained even in the presence of a conjugate point within the time interval, provided it is of a special type that we calleven.The partial support of the Trieste Unit of the GNAS, Italian CNR, is gratefully acknowledged.     

Zero-sum games with incompletely defined payoff

It is shown that a saddle-point solution exists in a two-person, zero-sum game whose payoff is given by a matrix which is not completely defined. On the other hand, we show that such games do not always have a value, so that a saddle-point solution is not necessarily an optimal solution.This work was supported by the Centre d'Etudes Atomiques, Saclay, France.     

Construction of Approximate Saddle-Point Strategies for Differential Games in a Hilbert Space

Two-person zero-sum infinite-dimensional differential games with strategies and payoff as in Berkovitz (SIAM J. Control Optim. 23: 173–196, 1985) are studied. Using Yosida type approximations of the infinitesimal generator (of the unbounded dynamics) by bounded linear operators, we prove convergence theorems for the approximate value functions. This is used to construct approximate saddle-point strategies in feedback form. A.J. Shaiju: NBHM Postdoctoral Fellow and the financial support from NBHM is gratefully acknowledged.     

Vector linear programming in zero-sum multicriteria matrix games

In this paper, a multiple-objective linear problem is derived from a zero-sum multicriteria matrix game. It is shown that the set of efficient solutions of this problem coincides with the set of Paretooptimal security strategies (POSS) for one of the players in the original game. This approach emphasizes the existing similarities between the scalar and multicriteria matrix games, because in both cases linear programming can be used to solve the problems. It also leads to different scalarizations which are alternative ways to obtain the set of all POSS. The concept of ideal strategy for a player is introduced, and it is established that a pair of Pareto saddle-point strategies exists if both players have ideal strategies. Several examples are included to illustrate the results in the paper.     

On the saddle-point solution of a class of stochastic differential games

This paper deals with the saddle-point solution of a class of stochastic differential games described by linear state dynamics and quadratic objective functionals. The information structure of the problem is such that both players have access to a common noisy linear measurement of the state and they are permitted to utilize only this information in constructing their controls. The saddle-point solution of such differential game problems has been discussed earlier in Ref. 1, but the conclusions arrived there are incorrect, as is explicitly shown in this paper. We extensively discuss the role of information structure on the saddle-point solution of such stochastic games (specifically within the context of an illustrative discrete-time example) and then obtain the saddle-point solution of the problem originally formulated by employing an indirect approach.This work was done while the author was on sabbatical leave at Twente University of Technology, Department of Applied Mathematics, Enschede, Holland, from Applied Mathematics Division, Marmara Scientific and Industrial Research Institute, Gebze, Kocaeli, Turkey.     

Sequential Linear-Quadratic Method for Differential Games with Air Combat Applications

We present a numerical method for computing a local Nash (saddle-point) solution to a zero-sum differential game for a nonlinear system. Given a solution estimate to the game, we define a subproblem, which is obtained from the original problem by linearizing its system dynamics around the solution estimate and expanding its payoff function to quadratic terms around the same solution estimate. We then apply the standard Riccati equation method to the linear-quadratic subproblem and compute its saddle solution. We then update the current solution estimate by adding the computed saddle solution of the subproblem multiplied by a small positive constant (a step size) to the current solution estimate for the original game. We repeat this process and successively generate better solution estimates. Our applications of this sequential method to air combat simulations demonstrate experimentally that the solution estimates converge to a local Nash (saddle) solution of the original game.     

Markov games with incomplete information

We consider zero-sum Markov games with incomplete information. Here, the second player is never informed about the current state of the underlying Markov chain. The existence of a value and of optimal strategies for both players is shown. In particular, we present finite algorithms for computing optimal strategies for the informed and uninformed player. The algorithms are based on linear programming results.     

Zero-sum risk-sensitive stochastic games for continuous time Markov chains

We study infinite horizon discounted-cost and ergodic-cost risk-sensitive zero-sum stochastic games for controlled continuous time Markov chains on a countable state space. For the discounted-cost game, we prove the existence of value and saddle-point equilibrium in the class of Markov strategies under nominal conditions. For the ergodic-cost game, we prove the existence of values and saddle point equilibrium by studying the corresponding Hamilton-Jacobi-Isaacs equation under a certain Lyapunov condition.     

Singular linear quadratic differential games with bounds on control

A class of two-persons zero-sum differential games with the possibility of singular arcs is considered. Under some assumptions, a sufficient condition for the existence of a saddle-point solution is derived. In this approach, the properties of convexity and concavity of the performance index are used to find the sufficient condition. It is observed that, unlike total singularity, the occurrence of partially singular arcs does not cause any problems for the existence of a unique saddle-point solution.     

Statistical linear differential games: A treatment of incomplete information

A zero-sum, two-player linear differential game of fixed duration is considered in the case when the information is incomplete but a statistical structure gives both players the possibility tospy the value of an unknown parameter in the payoff. Considerations of topological vector spaces and functional analysis allow one to demonstrate, via a classical Sion's theorem, sufficient conditions for the existence of a value.The author is indebted to Professor J. Fichefet for his helpful remarks and indications.     

Zero-sum games for continuous-time Markov jump processes with risk-sensitive finite-horizon cost criterion

In this paper we study the zero-sum games for continuous-time Markov jump processes under the risk-sensitive finite-horizon cost criterion. The state space is a Borel space and the transition rates are allowed to be unbounded. Under the suitable conditions, we use a new value iteration approach to establish the existence of a solution to the risk-sensitive finite-horizon optimality equations of the players, obtain the existence of the value of the game and show the existence of saddle-point equilibria.     

连续区间策略下二人零和对策问题研究

考虑连续区间策略下的二人零和对策问题,研究其均衡策略的存在性。首先分析了完全信息下的二人零和对策问题,证明了该问题均衡策略的存在性并给出求解方法。然后进一步研究了收益函数不确定的不完全信息二人零和对策问题,在各局中人都认为对方是风险厌恶型的假设下,分析该类对策纯策略均衡的存在性,并通过研究纯策略均衡存在的充要条件给出判断并寻找纯策略均衡解的方法。最后给出一个数值算例,验证本文所提出方法的可行性。     

Risk-sensitive stochastic differential games with reflecting diffusions

We study risk-sensitive differential games for controlled reflecting diffusion processes in a bounded domain. We consider both nonzero-sum and zero-sum cases. We treat two cost evaluation criteria; namely, discounted cost and ergodic cost. Under certain assumptions we establish the existence of Nash/saddle-point equilibria for relevant cases.     

Differential games with noise-corrupted measurements

In this paper, readily computable strategies for zero-sum, linear-quadratic differential games with noise-corrupted measurements are developed. Of particular significance is the fact that the governing differential equations no longer require the solution of an often difficult nonlinear, two-point boundary-value problem, but again satisfy the separation principle of linear-quadratic optimal control. The implications of the payoff relationships are considered.In a subsequent paper, we will apply the theory developed in this paper to a detailed example of a pursuit-evasion game. We discuss a missile and an airplane system where the missile supported by its launch platform has perfect state measurements and the airplane has noise-corrupted measurements.     

A near-optimal closed-loop solution method for nonsingular zero-sum differential games

This paper presents a method for generating nearoptimal closed-loop solutions to zero-sum perfect information differential games with and without the final time explicitly specified, and with and without control constraints. This near-optimal closed-loop solution is generated by periodically updating the solution to the two-point boundary-value problem obtained by the application of the necessary conditions for a saddle-point solution. The resulting updated open-loop control is then used between updating intervals. Three examples are presented to illustrate the application of this method.     

On saddlepoints of two-person zero-sum games with applications to data verification tests

A set of sufficient conditions for the existence of saddlepoint strategies of two-person zero-sum games is given which may be described as follows: The set of pure strategies for one of the two players is a compact metric space. His opponent has a best answer to each randomized strategy. The payoff function satisfies a continuity condition concerning the weak convergence of probability measures. These conditions are neither covered by those of well known existence theorems for saddlepoints nor do they generalize them. They are applied to treat important practical problems that have not been solved before. Received November 1995/Revised version August 1998