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.     

Single-type differential games with convex integral payoff

Single-type differential games are considered. The problem of taking a phase point to a disk of a fixed radius at a given time is studied. The payoff is the integral of a convex function depending on the norm of the first player’s control.     

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.     

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.     

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.     

Viscosity solutions with shocks

A solution of single nonlinear first order equations may develop jump discontinuities even if initial data is smooth. Typical examples include a crude model equation describing some bunching phenomena observed in epitaxial growth of crystals as well as conservation laws where jump discontinuities are called shocks. Conventional theory of viscosity solutions does not apply. We introduce a notion of proper (viscosity) solutions to track whole evolutions for such equations in multi‐dimensional spaces. We establish several versions of comparison principles. We also study the vanishing viscosity method to construct a unique global proper solution at least when the evolution is monotone in time or the initial data is monotone in some sense under additional technical assumptions. In fact, we prove that the graph of approximate solutions converges to that of a proper solution in the Hausdorff distance topology. Such a convergence is also established for conservation laws with monotone data. In particular, local uniform convergence outside shocks is proved. © 2001 John Wiley & Sons, Inc.     

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.     

Expected Shortfall and optimal hedging payoff

By using variational techniques, we provide an optimal payoff written on a given random variable for hedging – in the sense of minimizing the Expected Shortfall at a given threshold – a payoff written on another random variable. In numerous financially relevant examples, our result leads to optimal payoffs in closed form. From a theoretical viewpoint, our result is also useful for providing bounds to the classical Expected Shortfall minimization problem with given financial instruments.     

The expected payoff to Internet auctions

In an Internet auction, the expected payoff acts as a benchmark of the reasonableness of the price that is paid for the purchased item. Since the number of potential bidders is not observable, the expected payoff is difficult to estimate accurately. We approach this problem by considering the bids as a record and 2-record sequence of the potential bidder’s valuation and using the Extreme Value Theory models to model the tail distribution of the bidder’s valuation and study the expected payoff. Along the discussions for three different cases regarding the extreme value index γ, we show that the observed payoff does not act as an accurate estimation of the expected payoff in all the cases except a subclass of the case γ = 0. Within this subclass and under a second order condition, the observed payoff consistently converges to the expected payoff and the corresponding asymptotic normality holds.      

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.     

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

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.     

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.     

Nonzero-sum games for continuous-time Markov chains with unbounded transition and average payoff rates

This paper attempts to study two-person nonzero-sum games for denumerable continuous-time Markov chains determined by transition rates,with an expected average criterion.The transition rates are allowed to be unbounded,and the payoff functions may be unbounded from above and from below.We give suitable conditions under which the existence of a Nash equilibrium is ensured.More precisely,using the socalled "vanishing discount" approach,a Nash equilibrium for the average criterion is obtained as a limit point of a sequence of equilibrium strategies for the discounted criterion as the discount factors tend to zero.Our results are illustrated with a birth-and-death game.