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.     

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

We give a simpler, easier-to-check, version of the theorem of the paper referred to, i.e., a necessary and sufficient condition for the existence of a saddle point to the linear-quadratic two-person zero-sum perfect information differential game.     

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.     

Some thoughts on saddle-point conditions and information structures in zero-sum differential games

For a very simple two-stage, linear-quadratic, zero-sum difference game with dynamic information structure, we show that (i) there exist nonlinear saddle-point strategies which require the same existence conditions as the well-known linear, closed-loop, no-memory solution and (ii) there exist both linear and nonlinear saddle-point strategies which require more stringent conditions than the unique open-loop solution. We then discuss the implication of this result with respect to the existence of saddle points in zero-sum differential games for different information patterns.     

Perfect information two-person zero-sum markov games with imprecise transition probabilities

Based on an extension of the controlled Markov set-chain model by Kurano et al. (in J Appl Prob 35:293–302, 1998) into competitive two-player game setting, we provide a model of perfect information two-person zero-sum Markov games with imprecise transition probabilities. We define an equilibrium value for the games formulated with the model in terms of a partial order and then establish the existence of an equilibrium policy pair that achieves the equilibrium value. We further analyze finite-approximation error bounds obtained from a value iteration-type algorithm and discuss some applications of the model.     

On the existence of the stabilizing solution of generalized Riccati equations arising in zero-sum stochastic difference games: the time-varying case

In this paper, a large class of time-varying Riccati equations arising in stochastic dynamic games is considered. The problem of the existence and uniqueness of some globally defined solution, namely the bounded and stabilizing solution, is investigated. As an application of the obtained existence results, we address in a second step the problem of infinite-horizon zero-sum two players linear quadratic (LQ) dynamic game for a stochastic discrete-time dynamical system subject to both random switching of its coefficients and multiplicative noise. We show that in the solution of such an optimal control problem, a crucial role is played by the unique bounded and stabilizing solution of the considered class of generalized Riccati equations.     

Saddle-point equilibrium sequence in one class of singular infinite horizon zero-sum linear-quadratic differential games with state delays

ABSTRACT

We consider an infinite horizon zero-sum linear-quadratic differential game with state delays in the dynamics. The cost functional of this game does not contain a control cost of the minimizing player (the minimizer), meaning that the considered game is singular. For this game, definitions of the saddle-point equilibrium and the game value are proposed. These saddle-point equilibrium and game value are obtained by a regularization of the singular game. Namely, we associate this game with a new differential game for the same equation of dynamics. The cost functional in the new game is the sum of the original cost functional and an infinite horizon integral of the square of the minimizer's control with a small positive weight coefficient. This new game is regular, and it is a cheap control game. An asymptotic analysis of this cheap control game is carried out. Using this asymptotic analysis, the existence of the saddle-point equilibrium and the value of the original game is established, and their expressions are derived. Illustrative example is presented.     

Non zero-sum stochastic games in admission,service and routing control in queueing systems

The purpose of this paper is to investigate situations of non-cooperative dynamic control of queueing systems by two agents, having different objectives. The main part of the paper is devoted to analyzing a problem of an admission and a service (vacation) control. The admission controller has to decide whether to allow arrivals to occur. Once the queue empties, the server goes on vacation, and controls the vacations duration (according to the state and past history of the queue). The immediate costs for each controller are increasing in the number of customers, but no convexity assumptions are made. The controllers are shown to have a stationary equilibrium policy pair, for which each controller uses a stationary threshold type policy with randomization in at most one state. We then investigate a problem of a non-zero sum stochastic game between a router into several queues, and a second controller that allocates some extra service capacity to one of the queues. We establish the equilibrium of a policy pair for which the router uses the intuitive Join the shortest queue policy.     

A theorem of the maximin and applications to Bayesian zero-sum games

Consider a family of zero-sum games indexed by a parameter that determines each player’s payoff function and feasible strategies. Our first main result characterizes continuity assumptions on the payoffs and the constraint correspondence such that the equilibrium value and strategies depend continuously and upper hemicontinuously (respectively) on the parameter. This characterization uses two topologies in order to overcome a topological tension that arises when players’ strategy sets are infinite-dimensional. Our second main result is an application to Bayesian zero-sum games in which each player’s information is viewed as a parameter. We model each player’s information as a sub-σ-field, so that it determines her feasible strategies: those that are measurable with respect to the player’s information. We thereby characterize conditions under which the equilibrium value and strategies depend continuously and upper hemicontinuously (respectively) on each player’s information.     

Generic uniqueness of the bias vector of finite zero-sum stochastic games with perfect information

Mean-payoff zero-sum stochastic games can be studied by means of a nonlinear spectral problem. When the state space is finite, the latter consists in finding an eigenpair $(u,\lambda )$ solution of $T(u)=\lambda e+u$, where $T:{\mathbb{R}}^n\to {\mathbb{R}}^n$ is the Shapley (or dynamic programming) operator, λ is a scalar, e is the unit vector, and $u\in {\mathbb{R}}^n$. The scalar λ yields the mean payoff per time unit, and the vector u, called bias, allows one to determine optimal stationary strategies in the mean-payoff game. The existence of the eigenpair $(u,\lambda )$ is generally related to ergodicity conditions. A basic issue is to understand for which classes of games the bias vector is unique (up to an additive constant). In this paper, we consider perfect-information zero-sum stochastic games with finite state and action spaces, thinking of the transition payments as variable parameters, transition probabilities being fixed. We show that the bias vector, thought of as a function of the transition payments, is generically unique (up to an additive constant). The proof uses techniques of nonlinear Perron–Frobenius theory. As an application of our results, we obtain an explicit perturbation scheme allowing one to solve degenerate instances of stochastic games by policy iteration.     

The core of a class of non-atomic games which arise in economic applications

We study the core of a non-atomic game v which is uniformly continuous with respect to the DNA-topology and continuous at the grand coalition. Such a game has a unique DNA-continuous extension on the space B ₁ of ideal sets. We show that if the extension is concave then the core of the game v is non-empty iff is homogeneous of degree one along the diagonal of B ₁. We use this result to obtain representation theorems for the core of a non-atomic game of the form v=f^μ where μ is a finite dimensional vector of measures and f is a concave function. We also apply our results to some non-atomic games which occur in economic applications. Received May 1998/Revised version September 1998     

On games corresponding to sequencing situations with ready times

This paper considers the special class of cooperative sequencing games that arise from one-machine sequencing situations in which all jobs have equal processing times and the ready time of each job is a multiple of the processing time.By establishing relations between optimal orders of subcoalitions, it is shown that each sequencing game within this class is convex.This author is financially supported by the Dutch Organization for Scientific Research (NWO).     

Correlated equilibria of games with many players

Let G _m,n be the class of strategic games with n players, where each player has m≥2 pure strategies. We are interested in the structure of the set of correlated equilibria of games in G _m,n when n→∞. As the number of equilibrium constraints grows slower than the number of pure strategy profiles, it might be conjectured that the set of correlated equilibria becomes large. In this paper, we show that (1) the average relative measure of the set of correlated equilibria is smaller than 2⁻ⁿ; and (2) for each 1<c<m, the solution set contains c ⁿ correlated equilibria having disjoint supports with a probability going to 1 as n grows large. The proof of the second result hinges on the following inequality: Let c ₁, …, c _l be independent and symmetric random vectors in R ^k, l≥k. Then the probability that the convex hull of c ₁, …, c _l intersects R ^k ₊ is greater than or equal to . Received: December 1998/Final version: March 2000