Zero-sum risk-sensitive stochastic games for continuous time Markov chains

We study infinite horizon discounted-cost and ergodic-cost risk-sensitive zero-sum stochastic games for controlled continuous time Markov chains on a countable state space. For the discounted-cost game, we prove the existence of value and saddle-point equilibrium in the class of Markov strategies under nominal conditions. For the ergodic-cost game, we prove the existence of values and saddle point equilibrium by studying the corresponding Hamilton-Jacobi-Isaacs equation under a certain Lyapunov condition.     

Zero-sum games for continuous-time Markov jump processes with risk-sensitive finite-horizon cost criterion

In this paper we study the zero-sum games for continuous-time Markov jump processes under the risk-sensitive finite-horizon cost criterion. The state space is a Borel space and the transition rates are allowed to be unbounded. Under the suitable conditions, we use a new value iteration approach to establish the existence of a solution to the risk-sensitive finite-horizon optimality equations of the players, obtain the existence of the value of the game and show the existence of saddle-point equilibria.     

Existence of optimal strategies in Markov games with incomplete information

The existence of a value and optimal strategies is proved for the class of two-person repeated games where the state follows a Markov chain independently of players’ actions and at the beginning of each stage only Player 1 is informed about the state. The results apply to the case of standard signaling where players’ stage actions are observable, as well as to the model with general signals provided that Player 1 has a nonrevealing repeated game strategy. The proofs reduce the analysis of these repeated games to that of classical repeated games with incomplete information on one side. This research was supported in part by Israeli Science Foundation grants 382/98, 263/03, and 1123/06, and by the Zvi Hermann Shapira Research Fund.     

Finitely additive and epsilon Nash equilibria

We prove the existence of a mixed strategy Nash equilibrium in normal form games when the space of mixed strategies consists of finitely additive probability measures. It is then proved that from this result an existence result for epsilon equilibria with countably additive mixed strategies can be obtained. These results are applied to the classic Cournot game.     

Complementarity and Diagonal Dominance in Discounted Stochastic Games

We consider discounted stochastic games characterized by monotonicity, supermodularity and diagonal dominance assumptions on the reward functions and the transition law. A thorough novel discussion of the scope and limitations of this class of games is provided. Existence of a Markov-stationary equilibrium for the infinite-horizon game, proved by Curtat (1996), is summarized. Uniqueness of Markov equilibrium and dominance solvability of the finite-horizon game are established. In both cases, the equilibrium strategies and the corresponding value functions are nondecreasing Liptschitz-continuous functions of the state vector. Some specific economic applications are discussed.     

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.     

COMPUTING THE EQUILIBRIA OF DYNAMIC COMMON PROPERTY GAMES

In this paper we discuss techniques for rapidly computing the equilibria of a class of dynamic linear-quadratic games involving the extraction of a common property resource. Though this class of games has been much studied, the search for equilibria of these games has only been attempted in special cases, and analysis of the game has tended to focus on its steady-state properties. We construct a pseudo-planning problem, the optimal of which correspond to the Markov perfect equilibria of the class of games we explore. We show how the optima (equilibria) of this pseudo-planning problem (game) can be rapidly computed via a Riccati-like equation. Finally, we illustrate the use of these techniques with several examples involving the extraction of a common property resource.     

A Shared-Constraint Approach to Multi-Leader Multi-Follower Games

Multi-leader multi-follower games are a class of hierarchical games in which a collection of leaders compete in a Nash game constrained by the equilibrium conditions of another Nash game amongst the followers. The resulting equilibrium problem with equilibrium constraints is complicated by nonconvex agent problems and therefore providing tractable conditions for existence of global or even local equilibria has proved challenging. Consequently, much of the extant research on this topic is either model specific or relies on weaker notions of equilibria. We consider a modified formulation in which every leader is cognizant of the equilibrium constraints of all leaders. Equilibria of this modified game contain the equilibria, if any, of the original game. The new formulation has a constraint structure called shared constraints, and our main result shows that if the leader objectives admit a potential function, the global minimizers of the potential function over this shared constraint are equilibria of the modified formulation. We provide another existence result using fixed point theory that does not require potentiality. Additionally, local minima, B-stationary, and strong-stationary points of this minimization problem are shown to be local Nash equilibria, Nash B-stationary, and Nash strong-stationary points of the corresponding multi-leader multi-follower game. We demonstrate the relationship between variational equilibria associated with this modified shared-constraint game and equilibria of the original game from the standpoint of the multiplier sets and show how equilibria of the original formulation may be recovered. We note through several examples that such potential multi-leader multi-follower games capture a breadth of application problems of interest and demonstrate our findings on a multi-leader multi-follower Cournot game.     

Risk-sensitive stochastic differential games with reflecting diffusions

We study risk-sensitive differential games for controlled reflecting diffusion processes in a bounded domain. We consider both nonzero-sum and zero-sum cases. We treat two cost evaluation criteria; namely, discounted cost and ergodic cost. Under certain assumptions we establish the existence of Nash/saddle-point equilibria for relevant cases.     

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.     

Pure subgame-perfect equilibria in free transition games

We consider a class of stochastic games, where each state is identified with a player. At any moment during play, one of the players is called active. The active player can terminate the game, or he can announce any player, who then becomes the active player. There is a non-negative payoff for each player upon termination of the game, which depends only on the player who decided to terminate. We give a combinatorial proof of the existence of subgame-perfect equilibria in pure strategies for the games in our class.     

Non-additive anonymous games

This paper introduces a class of non-additive anonymous games where agents are assumed to be uncertain (in the sense of Knight) about opponents’ strategies and about the initial distribution over players’ characteristics in the game. We model uncertainty by non-additive measures or capacities and prove the Cournot–Nash equilibrium existence theorem for this class of games. Equilibrium distribution can be symmetrized under milder conditions than in the case of additive games. In particular, it is not required for the space characteristics to be atomless under capacities. The set-valued map of the Cournot–Nash equilibria is upper-semicontinuous as a function of initial beliefs of the players for non-additive anonymous games.     

Cyclic Markov equilibria in stochastic games

We examine a three-person stochastic game where the only existing equilibria consist of cyclic Markov strategies. Unlike in two-person games of a similar type, stationary ε-equilibria (ε > 0) do not exist for this game. Besides we characterize the set of feasible equilibrium rewards.     

Conditional Markov equilibria in discounted dynamic games

This paper introduces conditional Markov strategies in discrete-time discounted dynamic games with perfect monitoring. These are strategies in which players follow Markov policies after all histories. Policies induced by conditional Markov equilibria can be supported with the threat of reverting to the policy that yields the smallest expected equilibrium payoff for the deviator. This leads to a set-valued fixed-point characterization of equilibrium payoff functions. The result can be used for the computation of equilibria and for showing the existence in behavior strategies.     

Optimal strategic reasoning with McNaughton functions

The aim of the paper is to explore strategic reasoning in strategic games of two players with an uncountably infinite space of strategies the payoff of which is given by McNaughton functions—functions on the unit interval which are piecewise linear with integer coefficients. McNaughton functions are of a special interest for approximate reasoning as they correspond to formulas of infinitely valued Lukasiewicz logic. The paper is focused on existence and structure of Nash equilibria and algorithms for their computation. Although the existence of mixed strategy equilibria follows from a general theorem (Glicksberg, 1952) [5], nothing is known about their structure neither the theorem provides any method for computing them. The central problem of the article is to characterize the class of strategic games with McNaughton payoffs which have a finitely supported Nash equilibrium. We give a sufficient condition for finite equilibria and we propose an algorithm for recovering the corresponding equilibrium strategies. Our result easily generalizes to n-player strategic games which don't need to be strictly competitive with a payoff functions represented by piecewise linear functions with real coefficients. Our conjecture is that every game with McNaughton payoff allows for finitely supported equilibrium strategies, however we leave proving/disproving of this conjecture for future investigations.     

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.     

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.     

The modified stochastic game

We present a new tool for the study of multiplayer stochastic games, namely the modified game, which is a normal-form game that depends on the discount factor, the initial state, and for every player a partition of the set of states and a vector that assigns a real number to each element of the partition. We study properties of the modified game, like its equilibria, min–max value, and max–min value. We then show how this tool can be used to prove the existence of a uniform equilibrium in a certain class of multiplayer stochastic games.     

Approximate equilibria for Bayesian games

In this paper the problem of the existence of approximate equilibria in mixed strategies is central. Sufficient conditions are given under which approximate equilibria exist for non-finite Bayesian games. Further one possible approach is suggested to the problem of the existence of approximate equilibria for the class of multicriteria Bayesian games.     

On saddle-point optimality in differential games

A family of two-person, zero-sum differential games in which the admissible strategies are Borel measurable is defined, and two types of saddle-point conditions are introduced as optimality criteria. In one, saddle-point candidates are compared at each point of the state space with all playable pairs at that point; and, in the other, they are compared only with strategy pairs playable on the entire state space. As a theorem, these two types of optimality are shown to be equivalent for the defined family of games. Also, it is shown that a certain closure property is sufficient for this equivalence. A game having admissible strategies everywhere constant, in which the two types of saddle-point candidates are not equivalent, is discussed.This paper is based on research supported by ONR.