Guaranteed control in differential games with ellipsoidal payoff

A class of antagonistic linear differential games (DGs) in a fixed time interval with ellipsoidal payoff functional is considered. This class of DGs includes problems which assume both rigid constraints on the players' controls and requirements to minimize control expenses. Other known classes of differential games, such as linear DGs with a quadratic performance index and linear DGs with ellipsoidal terminal sets and admissible sets of controls for the players, considered in Kurzhanskii's ellipsoidal technique, are limiting cases of DGs of this class. The concept of a u-strategic function, which expresses the property of u-stability for ellipsoidal functions, is introduced. An effective algorithm is presented for computing a u-strategic function, based on Kurzhanskii's ellipsoidal technique. The main result of this paper is that a guaranteed positional strategy for player u is defined by a certain explicit formula in terms of a u-strategic function. The proof of this result is based on a viability theorem for differential equations.     

A convex programming-based algorithm for mean payoff stochastic games with perfect information

We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph \(G = (V, E)\), with local rewards \(r{:}\,E \rightarrow \mathbb {Z}\), and three types of positions: black \(V_B\), white \(V_W\), and random \(V_R\) forming a partition of V. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, even when \(|V_R|=0\). In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this short note, we show that BWR-games can be solved via convex programming in pseudo-polynomial time if the number of random positions is a constant.     

Stochastic programmed synthesis in a differential game with integral payoff

The problem of assured optimal control of a system subjected to infinite interference is formalized as a positional differential game /1/ in the typical case of integral index of the transient quality, and is solved by the method of stochastic program synthesis /2/, which is further developed in the present paper. An important feature here is the functional nature of the ancilliary stochastic construction considered that enables us to calculate the value of the game as the quality of a properly designed programmed stochastic maximum. Using the known value of the game, the optimal control action is determined using the method of extremal displacement to the so-called accompanying point. The results obtained here open the way for investigating functional game problems of control in irregular cases.     

On linear differential games with integral constraints

The paper is devoted to quasilinear conflict-controlled processes of general form with a cylindrical terminal set. A specific feature is that, instead of a dynamical system, we start with representation of a solution in a form that allows one to include an additive term with the initial data and a control unit. This makes it possible to consider a broad spectrum of dynamic processes in a unified scheme. Our study is based on the method of resolving functions. We obtain sufficient conditions for the solvability of the pursuit problem at a certain guaranteed time in the class of strategies that use information on the behavior of the opponent in the past, as well as in the class of stroboscopic strategies. We also find conditions under which information on the prehistory of the evader does not matter. The guaranteed times of various schemes of the resolving function method are compared with the guaranteed time of Pontryagin’s first direct method. The qualitative results are illustrated by an example of a game problem with simple motions and incomplete sweeping for special control domains in the Pontryagin condition.     

The absolute maximum payoff in differential games and optimal control

This paper deals with a differential game or optimal control problem in which the payoff is the maximum (or minimum), during play, of some scalar functionK of the statex. This unconventional payoff has many practical applications. By defining certain auxiliary games for a significant class of problems, one can show how to solve the general case where more than one maximum ofk(t)=K[x(t)] occurs under optimal play. For a subclass of such problems, it is found thatclosed optimal solutions can exist on certain surfaces in the playing space. As the playing interval becomes indefinitely long, the open optimal trajectories converge to (or diverge from) such surfaces. In particular, for two-dimensional problems of this subclass, the closed optimal trajectories are periodic and called periodic barriers. They are analogous to limit cycles in uncontrolled nonlinear systems.The writer is indebted to Dr. R. Isaacs for many stimulating conversations in connection with this study.     

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.     

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.     

Partially observed semi-Markov zero-sum games with average payoff

We study a zero-sum partially observed semi-Markov game with average payoff on a countable state space. Under certain ergodicity conditions we show that a saddle point equilibrium exists. We achieve this by solving the corresponding average cost optimality equation using a span contraction method. The average value is shown to be the unique zero of a Lipschitz continuous function. A value iteration scheme is developed to compute the value.     

Optimality in matrix games with incompletely defined payoff

We study two-person, zero-sum matrix games whose payoffs are not defined for every pair of strategies. A necessary and sufficient condition for these games to possess a value is given, and we show that the value can be approximated by using universally playable strategies.This work was supported by the Centre d'Etudes Nucléaires, Saclay, France.     

Minimax algorithm for constructing an optimal control strategy in differential games with a Lipschitz payoff

For a zero-sum differential game, an algorithm is proposed for computing the value of the game and constructing optimal control strategies with the help of stepwise minimax. It is assumed that the dynamics can be nonlinear and the cost functional of the game is the sum of an integral term and a terminal payoff function that satisfies the Lipschitz condition but can be neither convex nor concave. The players’ controls are chosen from given sets that are generally time-dependent and unbounded. An error estimate for the algorithm is obtained depending on the number of partition points in the time interval and on the fineness of the spatial triangulation. Numerical results for an illustrative example are presented.     

Games with convex payoff function in the first variable

We show that any game over the unit square whose payoff functionM(x, y) is convex inx has a value. We also characterize the optimal strategies and offer constructive methods to find them.     

Positional strategies for mean payoff games

We study some games of perfect information in which two players move alternately along the edges of a finite directed graph with weights attached to its edges. One of them wants to maximize and the other to minimize some means of the encountered weights.     

Potential theory for mean payoff games

The paper presents an O(mn2ⁿ log Z) deterministic algorithm for solving the mean payoff game problem, m and n being the numbers of arcs and vertices, respectively, in the game graph, and Z being the maximum weight (the weights are assumed to be integers). The theoretical basis for the algorithm is the potential theory for mean payoff games. This theory allows one to restate the problem in terms of solving systems of algebraic equations with minima and maxima. Also, in order to solve the mean payoff game problem, the arc reweighting technique is used. To this end, simple modifications, which do not change the set of winning strategies, are applied to the game graph; in the end, a trivial instance of the problem is obtained. It is shown that any game graph can be simplified by n reweightings. Bibliography: 16 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 340, 2006, pp. 61–75.     

Linear differential pursuit games with integral constraints in the presence of delay

Problems involving linear differential pursuit games were studied by many authors; their work served as a basis for studying pursuit problems in linear differential games with integral constraints. In the present paper, we obtain sufficient conditions for the solvability of linear pursuit problems with integral constraints on the control of the players in the presence of delay.     

A polymatroid associated with convex games

A cooperative game with side payments is called convex if its characteristic function is supermodular. We define a polymatroid with the characteristic function of the convex game, and investigate some properties of a partition of the players equivalent to the principal partition of the polymatroid as well as a partial order among the elements of the partition. The partition and partial order reflects players' interdependences and one-way dependences respectively. The critical value in the polymatroid theory is related to the minimum amount of reasonable requirement between coalitions at the time of their amalgamation. Also shown is an application to the problem of oligopoly.     

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).     

Cores of convex games

The core of ann-person game is the set of feasible outcomes that cannot be improved upon by any coalition of players. A convex game is defined as one that is based on a convex set function. In this paper it is shown that the core of a convex game is not empty and that it has an especially regular structure. It is further shown that certain other cooperative solution concepts are related in a simple way to the core: The value of a convex game is the center of gravity of the extreme points of the core, and the von Neumann-Morgenstern stable set solution of a convex game is unique and coincides with the core.     

On the feasible payoff set of two-player repeated games with unequal discounting

We provide a novel characterization of the feasible payoff set of a general two-player repeated game with unequal discounting. In particular, we show that generically the Pareto frontier shifts outwards and the feasible payoff set expands in the sense of set inclusion, as the time horizon increases. This result reinforces and refines the insight in Lehrer and Pauzner (1999) by showing that a longer horizon enables the players to conduct intertemporal trade in a more flexible fashion.     

Wellposed convex integral functionals

Sufficient conditions are obtained for wellposedness of convex minimum problems of the calculus of variations for multiple integrals under strong or weak perturbations of the boundary data. Problems with a unique minimizer as well as problems with several solutions are treated. Wellposedness under weak convergence of the boundary data in W^{1 p}

ω is proved if p

>2 and a counterexample is exhibited if p

=2.