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.     

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.     

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.     

Polytope Games

Starting from the definition of a bimatrix game, we restrict the pair of strategy sets jointly, not independently. Thus, we have a set , which is the set of all feasible strategy pairs. We pose the question of whether a Nash equilibrium exists, in that no player can obtain a higher payoff by deviating. We answer this question affirmatively for a very general case, imposing a minimum of conditions on the restricted sets and the payoff. Next, we concentrate on a special class of restricted games, the polytope bimatrix game, where the restrictions are linear and the payoff functions are bilinear. Further, we show how the polytope bimatrix game is a generalization of the bimatrix game. We give an algorithm for solving such a polytope bimatrix game; finally, we discuss refinements to the equilibrium point concept where we generalize results from the theory of bimatrix games.     

Almost Stationary ∈-Equilibria in Zero-Sum Stochastic Games

We show the existence of almost stationary -equilibria, for all > 0, in zero-sum stochastic games with finite state and action spaces. These are -equilibria with the property that, if neither player deviates, then stationary strategies are played forever with probability almost 1. The proof is based on the construction of specific stationary strategy pairs, with corresponding rewards equal to the value, which can be supplemented with history-dependent -optimal strategies, with small > 0, in order to obtain almost stationary -equilibria.     

Total Reward Stochastic Games and Sensitive Average Reward Strategies

In this paper, total reward stochastic games are surveyed. Total reward games are motivated as a refinement of average reward games. The total reward is defined as the limiting average of the partial sums of the stream of payoffs. It is shown that total reward games with finite state space are strategically equivalent to a class of average reward games with an infinite countable state space. The role of stationary strategies in total reward games is investigated in detail. Further, it is outlined that, for total reward games with average reward value 0 and where additionally both players possess average reward optimal stationary strategies, it holds that the total reward value exists.     

Nonlinear programming and stationary equilibria in stochastic games

Stationary equilibria in discounted and limiting average finite state/action space stochastic games are shown to be equivalent to global optima of certain nonlinear programs. For zero sum limiting average games, this formulation reduces to a linear objective, nonlinear constraints program, which finds the best stationary strategies, even when-optimal stationary strategies do not exist, for arbitrarily small. The work of the first author was supported in part by the Air Force Office of Scientific Research, and by the National Science Foundation under Grant No ECS-8704954.The work of the third author was supported by The Netherlands Organization for Scientific Research NWO, project 10-64-10.     

Repeated Games with Bonuses

This paper deals with 2-player zero-sum repeated games in which player 1 receives a bonus at stage t if he repeats the action he played at stage t−1. We investigate the optimality of simple strategies for player 1. A simple strategy for player 1 consists of playing the same mixed action at every stage, irrespective of past play. Furthermore, for games in which player 1 has a simple optimal strategy, we characterize the set of stationary optimal strategies for player 2.