Nonlinear programming and stationary strategies in stochastic games

We show that an undiscounted stochastic game possesses optimal stationary strategies if and only if a global minimum with objective value zero can be found to an appropriate nonlinear program with linear constraints. This nonlinear program arises as a method for solving a certain bilinear system, satisfaction of which is also equivalent to finding a stationary optimal solution for the game. The objective function of the program is a nonnegatively valued quadric polynomial.This research was supported in part by the National Science Foundation under the grant #ECS-8503440. We wish to thank the referee for many helpful comments and in streamlining the presentation.     

Zero-sum stochastic games with stopping and control

We study a zero-sum stochastic game where each player uses both control and stopping times. Under certain conditions we establish the existence of a saddle point equilibrium, and show that the value function of the game is the unique solution of certain dynamic programming inequalities with bilateral constraints.     

Asymptotic behavior for second order stochastic evolution equations with memory

In this paper, a general second order integro-differential evolution equation with memory driven by multiplicative noise is considered. We prove the existence of global mild solution and asymptotic stability of the zero solution using Lyapunov function techniques. Moreover, we discuss three examples to show that the asymptotic stability results can be applied to various partial differential equations.     

Asymptotic behavior of linear fractional stochastic differential equations with time-varying delays

In this paper we give a sufficient condition for the exponential asymptotic behavior of solutions of a general class of linear fractional stochastic differential equations with time-varying delays. Our obtained results allow us to employ the theories developed for the deterministic systems and to illustrate this, some examples are provided.     

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.     

Fictitious play in stochastic games

In this paper we examine an extension of the fictitious play process for bimatrix games to stochastic games. We show that the fictitious play process does not necessarily converge, not even in the 2 × 2 × 2 case with a unique equilibrium in stationary strategies. Here 2 × 2 × 2 stands for 2 players, 2 states, 2 actions for each player in each state.     

Bilinear programming and structured stochastic games

One-step algorithms are presented for two classes of structured stochastic games, namely, those with additive rewards and transitions and those which have switching controllers. Solutions to such classes of games under the average reward criterion can be derived from optimal solutions to appropriate bilinear programs. The validity of using bilinear programming as a solution method follows from two preliminary theorems, the first of which is a complete classification of undiscounted stochastic games with optimal stationary strategies. The second of these preliminary theorems relaxes the conditions of the classification theorem for certain classes of stochastic games and provides the basis for the bilinear programming results. Analogous results hold for the discounted stochastic games with the above special structures.This research was supported in part by the Air Force Office of Scientific Research and by the National Science Foundation under Grant No. ECS-850-3440.     

On stationary equilibria of a single-controller stochastic game

We consider a two-person, general-sum, rational-data, undiscounted stochastic game in which one player (player II) controls the transition probabilities. We show that the set of stationary equilibrium points is the union of a finite number of sets such that, every element of each of these sets can be constructed from a finite number of extreme equilibrium strategies for player I and from a finite number of pseudo-extreme equilibrium strategies for player II. These extreme and pseudo-extreme strategies can themselves be constructed by finite (but inefficient) algorithms. Analogous results can also be established in the more straightforward case of discounted single-controller games.     

On a problem of stochastic differential games

The process of bargaining between management and union during a strike is modelled by a nonlinear stochastic differential game. It is assumed that the two sides bargain in the mood of a cooperative game. A pair of Pareto-optimal strategies is obtained.     

Optimal non-proportional reinsurance control and stochastic differential games

We study stochastic differential games between two insurance companies who employ reinsurance to reduce risk exposure. We consider competition between two companies and construct a single payoff function of two companies’ surplus processes. One company chooses a dynamic reinsurance strategy in order to maximize the payoff function while its opponent is simultaneously choosing a dynamic reinsurance strategy so as to minimize the same quantity. We describe the Nash equilibrium of the game and prove a verification theorem for a general payoff function. For the payoff function being the probability that the difference between two surplus reaches an upper bound before it reaches a lower bound, the game is solved explicitly.     

On shortest path games

A class of cooperative TU-games arising from shortest path problems is introduced and analyzed. Some conditions under which a shortest path game is balanced are obtained. Also an axiomatic characterization of the Shapley value for this class of games is provided.     

Asymptotic behavior of a stochastic virus dynamics model with intracellular delay and humoral immunity

In this paper, we formulate a stochastic virus dynamics model with intracellular delay and humoral immunity. By constructing some suitable Lyapunov functions, we show that the solution of stochastic model is going around each of the steady states of the corresponding deterministic model under some conditions. Then, numerical simulations are given to support the theoretical results. Finally, we propose several more effective way to control the spread of the virus by analyzing the sensitivity of the threshold of spread.     

A note on two-person zero-sum communicating stochastic games

For undiscounted two-person zero-sum communicating stochastic games with finite state and action spaces, a solution procedure is proposed that exploits the communication property, i.e., working with irreducible games over restricted strategy spaces. The proposed procedure gives the value of the communicating game with an arbitrarily small error when the value is independent of the initial state.     

Stackelberg strategies in linear-quadratic stochastic differential games

This paper obtains the Stackelberg solution to a class of two-player stochastic differential games described by linear state dynamics and quadratic objective functionals. The information structure of the problem is such that the players make independent noisy measurements of the initial state and are permitted to utilize only this information in constructing their controls. Furthermore, by the very nature of the Stackelberg solution concept, one of the players is assumed to know, in advance, the strategy of the other player (the leader). For this class of problems, we first establish existence and uniqueness of the Stackelberg solution and then relate the derivation of the leader's Stackelberg solution to the optimal solution of a nonstandard stochastic control problem. This stochastic control problem is solved in a more general context, and its solution is utilized in constructing the Stackelberg strategy of the leader. For the special case Gaussian statistics, it is shown that this optimal strategy is affine in observation of the leader. The paper also discusses numerical aspects of the Stackelberg solution under general statistics and develops algorithms which converge to the unique Stackelberg solution.This work was performed while the second author was on sabbatical leave at the Department of Applied Mathematics, Twente University of Technology, Enschede, Holland.     

Characterization of correlated equilibria in stochastic games

A general communication device is a device that at every stage of the game receives a private message from each player, and in return sends a private signal to each player; the signals the device sends depend on past play, past signals it sent, and past messages it received.  An autonomous correlation device is a general communication device where signals depend only on past signals the device sent, but not on past play or past messages it received.  We show that the set of all equilibrium payoffs in extended games that include a general communication device coincides with the set of all equilibrium payoffs in extended games that include an autonomous correlation device. A stronger result is obtained when the punishment level is independent of the history. Final version July 2001     

A class of stochastic games with ordered field property

It is shown that discounted general-sum stochastic games with two players, two states, and one player controlling the rewards have the ordered field property. For the zero-sum case, this result implies that, when starting with rational data, also the value is rational and that the extreme optimal stationary strategies are composed of rational components.     

Asymptotic behaviour of the stochastic Lotka-Volterra model

This paper examines the asymptotic behaviour of the stochastic extension of a fundamentally important population process, namely the Lotka-Volterra model. The stochastic version of this process appears to have far more intriguing properties than its deterministic counterpart. Indeed, the fact that a potential deterministic population explosion can be prevented by the presence of even a tiny amount of environmental noise shows the high level of difference which exists between these two representations.     

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

Stationary distribution of stochastic SIS epidemic model with vaccination under regime switching

This paper addresses a stochastic SIS epidemic model with vaccination under regime switching. The stochastic model in this paper includes white and color noises. By constructing stochastic Lyapunov functions with regime switching, we establish sufficient conditions for the existence of a unique ergodic stationary distribution.