Overtaking optimality for controlled Markov-modulated diffusions

This article concerns controlled Markov-modulated diffusions (also known as piecewise diffusions or switching diffusions or diffusions with Markovian switchings). Our main objective is to give conditions for the existence and characterization of overtaking optimal policies. To this end, first, we use fact that the average reward Hamilton–Jacobi–Bellman equation gives that the family of the so-called canonical control policies is nonempty. Then, within this family, we search policies with some special feature, for instance, canonical policies that in addition maximize the bias, which turn out to be overtaking optimal.     

Sensitive equilibria for ergodic stochastic games with countable state spaces

We consider stochastic games with countable state spaces and unbounded immediate payoff functions. Our assumptions on the transition structure of the game are based on a recent work by Meyn and Tweedie [19] on computable bounds for geometric convergence rates of Markov chains. The main results in this paper concern the existence of sensitive optimal strategies in some classes of zero-sum stochastic games. By sensitive optimality we mean overtaking or 1-optimality. We also provide a new Nash equilibrium theorem for a class of ergodic nonzero-sum stochastic games with denumerable state spaces.     

Stochastic differential games: Occupation measure based approach

A new approach based on occupation measures is introduced for studying stochastic differential games. For two-person zero-sum games, the existence of values and optimal strategies for both players is established for various payoff criteria. ForN-person games, the existence of equilibria in Markov strategies is established for various cases.     

Stochastic Games with Average Payoff Criterion

We study two-person stochastic games on a Polish state and compact action spaces and with average payoff criterion under a certain ergodicity condition. For the zero-sum game we establish the existence of a value and stationary optimal strategies for both players. For the nonzero-sum case the existence of Nash equilibrium in stationary strategies is established under certain separability conditions. Accepted 9 January 1997     

Zero-sum stochastic games with average payoffs: New optimality conditions

In this paper we study zero-sum stochastic games. The optimality criterion is the long-run expected average criterion, and the payoff function may have neither upper nor lower bounds. We give a new set of conditions for the existence of a value and a pair of optimal stationary strategies. Our conditions are slightly weaker than those in the previous literature, and some new sufficient conditions for the existence of a pair of optimal stationary strategies are imposed on the primitive data of the model. Our results are illustrated with a queueing system, for which our conditions are satisfied but some of the conditions in some previous literatures fail to hold.     

A New Condition and Approach for Zero-Sum Stochastic Games with Average Payoffs

Abstract

This article deals with discrete-time two-person zero-sum stochastic games with Borel state and action spaces. The optimality criterion to be studied is the long-run expected average payoff criterion, and the (immediate) payoff function may have neither upper nor lower bounds. We first replace the optimality equation widely used in the previous literature with two so-called optimality inequalities, and give a new set of conditions for the existence of solutions to the optimality inequalities. Then, from the optimality inequalities we ensure the existence of a pair of average optimal stationary strategies. Our new condition is slightly weaker than those in the previous literature, and as a byproduct some interesting results such as the convergence of a value iteration scheme to the value of the discounted payoff game is obtained. Finally, we first apply the main results in this article to generalized inventory systems, and then further provide an example of controlled population processes for which all of our conditions are satisfied, while some of conditions in some of previous literature fail to hold.     

A Stochastic Differential Game in the Orthrant

We study a zero-sum stochastic differential game in the nonnegative orthrant. The state of the system is governed by controlled reflecting diffusions in the nonnegative orthrant. We consider discounted and average payoff evaluation criteria. We prove the existence of values and optimal strategies for both payoff criteria.     

Value and perfection in stochastic games

A stochastic game isvalued if for every playerk there is a functionr ^k:S→R from the state spaceS to the real numbers such that for every ε>0 there is an ε equilibrium such that with probability at least 1−ε no states is reached where the future expected payoff for any playerk differs fromr ^k(s) by more than ε. We call a stochastic gamenormal if the state space is at most countable, there are finitely many players, at every state every player has only finitely many actions, and the payoffs are uniformly bounded and Borel measurable as functions on the histories of play. We demonstrate an example of a recursive two-person non-zero-sum normal stochastic game with only three non-absorbing states and limit average payoffs that is not valued (but does have ε equilibria for every positive ε). In this respect two-person non-zero-sum stochastic games are very different from their zero-sum varieties. N. Vieille proved that all such non-zero-sum games with finitely many states have an ε equilibrium for every positive ε, and our example shows that any proof of this result must be qualitatively different from the existence proofs for zero-sum games. To show that our example is not valued we need that the existence of ε equilibria for all positive ε implies a “perfection” property. Should there exist a normal stochastic game without an ε equilibrium for some ε>0, this perfection property may be useful for demonstrating this fact. Furthermore, our example sews some doubt concerning the existence of ε equilibria for two-person non-zero-sum recursive normal stochastic games with countably many states. This research was supported financially by the German Science Foundation (Deutsche Forschungsgemeinschaft) and the Center for High Performance Computing (Technical University, Dresden). The author thanks Ulrich Krengel and Heinrich Hering for their support of his habilitation at the University of Goettingen, of which this paper is a part.     

Pure strategy equilibria in symmetric two-player zero-sum games

We observe that a symmetric two-player zero-sum game has a pure strategy equilibrium if and only if it is not a generalized rock-paper-scissors matrix. Moreover, we show that every finite symmetric quasiconcave two-player zero-sum game has a pure equilibrium. Further sufficient conditions for existence are provided. Our findings extend to general two-player zero-sum games using the symmetrization of zero-sum games due to von Neumann. We point out that the class of symmetric two-player zero-sum games coincides with the class of relative payoff games associated with symmetric two-player games. This allows us to derive results on the existence of finite population evolutionary stable strategies.     

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.     

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.     

A nonzero-sum stochastic differential game in the orthant

We study a nonzero-sum stochastic differential game where the state is a controlled reflecting diffusion in the nonnegative orthant. Under certain conditions, we establish the existence of Nash equilibria in stationary strategies for both discounted and average payoff criteria.     

Zero-sum continuous games with no compact support

In this work, we study the mixed extension of the zero-sum two person games, with sets of pure strategies, semi-open on the right side real intervals, and continuous payoff function. It is proved that these games may not have a value and next we offer some conditions for the existence of a value in these games.     

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

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

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.     

Remarks on sensitive equilibria in stochastic games with additive reward and transition structure

A class of stochastic games with additive reward and transition structure is studied. For zero-sum games under some ergodicity assumptions 1-equilibria are shown to exist. They correspond to so-called sensitive optimal policies in dynamic programming. For a class of nonzero-sum stochastic games with nonatomic transitions nonrandomized Nash equilibrium points with respect to the average payoff criterion are also obtained. Included examples show that the results of this paper can not be extented to more general payoff or transition structure.     

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.     

Zero-Sum Stochastic Games with Partial Information and Average Payoff

We consider a discrete time partially observable zero-sum stochastic game with average payoff criterion. We study the game using an equivalent completely observable game. We show that the game has a value and also we present a pair of optimal strategies for both the players.     

On the existence of almost-pure-strategy Nash equilibrium in <Emphasis Type="Italic">n</Emphasis>-person finite games

This paper gives wide characterization of n-person non-coalitional games with finite players’ strategy spaces and payoff functions having some concavity or convexity properties. The characterization is done in terms of the existence of two-point-strategy Nash equilibria, that is equilibria consisting only of mixed strategies with supports being one or two-point sets of players’ pure strategy spaces. The structure of such simple equilibria is discussed in different cases. The results obtained in the paper can be seen as a discrete counterpart of Glicksberg’s theorem and other known results about the existence of pure (or “almost pure”) Nash equilibria in continuous concave (convex) games with compact convex spaces of players’ pure strategies.