Stochastic games with two non-absorbing states

In the present paper we consider recursive games that satisfy an absorbing property defined by Vieille. We give two sufficient conditions for existence of an equilibrium payoff in such games, and prove that if the game has at most two non-absorbing states, then at least one of the conditions is satisfied. Using a reduction of Vieille, we conclude that every stochastic game which has at most two non-absorbing states admits an equilibrium payoff. This paper is part of the Ph.D. thesis of the author completed under the supervision of Prof. Abraham Neyman at the Hebrew University of Jerusalem. I would like to thank Prof. Neyman for many discussions and ideas and for the continuous help he offered. I also thank Nicolas Vieille for his comments on earlier versions of the paper.     

Repeated games with absorbing states and no signals

We recall the definition of stochastic games with signals. We show the existence of the MaxMin and MinMax if there is only one non absorbing state and if the players have no information about the other player's actions but only recall their own past moves.For having shared with me his experience in the domain, I would like to thank Sylvain Sorin.     

The MaxMin value of stochastic games with imperfect monitoring

We study finite zero-sum stochastic games in which players do not observe the actions of their opponent. Rather, at each stage, each player observes a stochastic signal that may depend on the current state and on the pair of actions chosen by the players. We assume that each player observes the state and his/her own action. We prove that the uniform max-min value always exists. Moreover, the uniform max-min value is independent of the information structure of player 2. Symmetric results hold for the uniform min-max value. We deeply thank E. Lehrer, J.-F. Mertens, A. Neyman and S. Sorin. The discussions we had, and the suggestions they provided, were extremely useful. We acknowledge the financial support of the Arc-en-Ciel/Keshet program for 2001/2002. The research of the second author was supported by the Israel Science Foundation (grant No. 69/01-1).     

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.     

Stochastic games with non-observable actions

We examine n-player stochastic games. These are dynamic games where a play evolves in stages along a finite set of states; at each stage players independently have to choose actions in the present state and these choices determine a stage payoff to each player as well as a transition to a new state where actions have to be chosen at the next stage. For each player the infinite sequence of his stage payoffs is evaluated by taking the limiting average. Normally stochastic games are examined under the condition of full monitoring, i.e. at any stage each player observes the present state and the actions chosen by all players. This paper is a first attempt towards understanding under what circumstances equilibria could exist in n-player stochastic games without full monitoring. We demonstrate the non-existence of -equilibria in n-player stochastic games, with respect to the average reward, when at each stage each player is able to observe the present state, his own action, his own payoff, and the payoffs of the other players, but is unable to observe the actions of them. For this purpose, we present and examine a counterexample with 3 players. If we further drop the assumption that the players can observe the payoffs of the others, then counterexamples already exist in games with only 2 players.     

Periodic stopping games

Stopping games (without simultaneous stopping) are sequential games in which at every stage one of the players is chosen, who decides whether to continue the interaction or stop it, whereby a terminal payoff vector is obtained. Periodic stopping games are stopping games in which both of the processes that define it, the payoff process as well as the process by which players are chosen, are periodic and do not depend on the past choices. We prove that every periodic stopping game without simultaneous stopping, has either periodic subgame perfect ϵ-equilibrium or a subgame perfect 0-equilibrium in pure strategies. This work is part of the master thesis of the author done under the supervision of Prof. Eilon Solan. I am thankful to Prof. Solan for his inspiring guidance. I also thank two anonymous referees of the International Journal of Game Theory for their comments.     

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.     

A Filippov-type lemma for functions involving delays and its application to time-delayed optimal control problems

A Filippov-type lemma for functions involving delays is derived. This lemma is used to prove the existence of an optimal control for a class of nonlinear control processes with delays appearing in both state and control variables.The author wishes to express his gratitude to Dr. E. Noussair and Dr. K. L. Teo for their guidance in the preparation of this paper. Also, the author wishes to thank Professor L. Cesari for his valuable suggestion.     

Perfect information stochastic games and related classes

Forn-person perfect information stochastic games and forn-person stochastic games with Additive Rewards and Additive Transitions (ARAT) we show the existence of pure limiting average equilibria. Using a similar approach we also derive the existence of limiting average ε-equilibria for two-person switching control stochastic games. The orderfield property holds for each of the classes mentioned, and algorithms to compute equilibria are pointed out.     

Ordered field property for stochastic games when the player who controls transitions changes from state to state

In this paper, we consider a zero-sum stochastic game with finitely many states restricted by the assumption that the probability transitions from a given state are functions of the actions of only one of the players. However, the player who thus controls the transitions in the given state will not be the same in every state. Further, we assume that all payoffs and all transition probabilities specifying the law of motion are rational numbers. We then show that the values of both a -discounted game, for rational , and of a Cesaro-average game are in the field of rational numbers. In addition, both games possess optimal stationary strategies which have only rational components. Our results and their proofs form an extension of the results and techniques which were recently developed by Parthasarathy and Raghavan (Ref. 1).The author wishes to thank Professor T. E. S. Raghavan for introducing him to this problem and for discussing stochastic games with him on many occasions. This research was supported in part by AFOSR Grant No. 78–3495B.     

The sequence method for finding solutions to infinite games: A first demonstrating example

A noncooperative infinite game can be approached by a sequence of discrete games. For each game in the sequence, a Nash solution can be found as well as their limit. This idea and procedure was used before as a theoretical device to prove existence of solutions to games with continuous payoffs and recently even for a class of games with discontinuous ones (Dasgupta and Maskin, 1981). No one, however, used the method for the actual solution of a game. Here, an example demonstrates the method's usefulness in finding a solution to a two-person game on the unit square with discontinuous payoff functions.The author wishes to thank D. McFadden for very useful discussions. Financial support was provided in part by NSF Grant No. SOC-72-05551A02 to the University of California, Berkeley, California.     

Equilibrium selection in multi-leader-follower games with vertical information

We consider two-stage multi-leader-follower games, called multi-leader-follower games with vertical information, where leaders in the first stage and followers in the second stage choose simultaneously an action, but those chosen by any leader are observed by only one “exclusive” follower. This partial unobservability leads to extensive form games that have no proper subgames but may have an infinity of Nash equilibria. So it is not possible to refine using the concept of subgame perfect Nash equilibrium and, moreover, the concept of weak perfect Bayesian equilibrium could be not useful since it does not prescribe limitations on the beliefs out of the equilibrium path. This has motivated the introduction of a selection concept for Nash equilibria based on a specific class of beliefs, called passive beliefs, that each follower has about the actions chosen by the leaders rivals of his own leader. In this paper, we illustrate the effectiveness of this concept and we investigate the existence of such a selection for significant classes of problems satisfying generalized concavity properties and conditions of minimal character on possibly discontinuous data.     

On a Noncooperative Stochastic Game Played by Internally Cooperating Generations

We study a model of intergenerational stochastic game with general state space in which each generation consists of n players. The main objective is to prove the existence of a perfect stationary equilibrium in an infinite-horizon intergenerational game in which cooperation is assumed inside every generation. A suitable change in the terminology used in this paper provides a new equilibrium theorem for stochastic games with so-called “hyperbolic players”. A discussion of perfect equilibria in games of noncooperative generations is also given. Some applications to economic theory are included.     

On equilibria in repeated games with absorbing states

We prove the existence of ε-(Nash) equilibria in two-person non-zerosum limiting average repeated games with absorbing states. These are stochastic games in which all states but one are absorbing. A state is absorbing if the probability of ever leaving that state is zero for all available pairs of actions.     

Perfect equilibria in stochastic games

We examine stochastic games with finite state and action spaces. For the -discounted case, as well as for the irreducible limiting average case, we show the existence of trembling-hand perfect equilibria and give characterizations of those equilibria. In the final section, we give an example which illustrates that the existence of stationary limiting average equilibria in a nonirreducible stochastic game does not imply the existence of a perfect limiting average equilibrium.Support was provided by the Netherlands Organization for Scientific Research NWO via the Netherlands Foundation for Mathematics SMC, Project 10-64-10.     

Densities of One-Dimensional Backward SDEs

This work is devoted to the study of the existence and smoothness of the marginal densities of the solution of one-dimensional backward stochastic differential equations. Under monotonicity conditions of a function of the coefficients, we obtain that the smoothness properties of the forward process influencing the backward equation, transfer to the densities of the solution. Once established these conditions, we apply the result to study the tail behavior of the solution process. Mathematics Subject Classification (2000) 60H10.Fabio Antonelli: The first author was partially supported by the MIUR COFIN grant 2000.Arturo Kohatsu-Higa: The second author was partially supported by grants BFM2003-03324 and BFM 2003-04294. The authors wish to thank the referee for his/her comments.     

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.     

Differential games without pure strategy saddle-point solutions

In some two-player, zero-sum differential games, pure strategy saddle-point solutions do not exist. For such games, the concept of a minmax strategy is examined, and sufficient conditions for a control to be a minmax control are presented. Both the open-loop and the closed-loop cases are considered.The research was partially supported by ONR under Contract No. N00014-69-A-0200-12. An earlier version of this paper was presented at the Eleventh Annual Allerton Conference on Circuit and System Theory, Monticello, Illinois, 1973.The author wishes to acknowledge his many valuable discussions of this problem with Professor G. Leitmann and also to thank one of the reviewers for his suggestions for simplifying the proof of Theorem 2.1.     

Existence of value in differential games with fixed time duration

A differential game of prescribed duration with general-type phase constraints is investigated. The existence of a value in the Varaiya-Lin sense and an optimal strategy for one of the players is obtained under assumptions ensuring that the sets of all admissible trajectories for the two players are compact in the Banach space of all continuous functions. These results are next widened on more general games, examined earlier by Varaiya.The author wishes to express his thanks to an anonymous reviewer for his many valuable comments.     

On stochastic games

In this paper, we consider the stochastic games of Shapley, when the state and action spaces are all infinite. We prove that, under certain conditions, the stochastic game has a value and that both players have optimal strategies.Part of this research was supported by NSF grant. The authors are indebted to L. S. Shapley for the useful discussions on this and related topics. The authors thank the referee for pointing out an ambiguity in the formulation of Lemma 2.4 in an earlier draft of this article.