On Nikaido-Isoda type theorems for discounted stochastic games

We present a class of countable state space stochastic games with discontinuous payoff functions satisfying some assumptions similar to the ones of Nikaido and Isoda for one-stage games. We prove that these games possess stationary equilibria. We show that after adding some concavity assumptions these equilibria are nonrandomized. Further, we present an example of input (or production) dynamic game satisfying the assumptions of our model. We give a closed-form solution for this game.     

Cooperative equilibria in discounted stochastic sequential games

This paper addresses the problem of computation of cooperative equilibria in discounted stochastic sequential games. The proposed approach contains as a special case the method of Green and Porter (developed originally for repeated oligopoly games), but it is more general than the latter in the sense that it generates nontrivial equilibrium solutions for a much larger class of dynamic games. This fact is demonstrated on two examples, one concerned with duopolistic economics and the other with fishery management.     

Linear complementarity and discounted switching controller stochastic games

The class of discounted switching controller stochastic games can be solved in one step by a linear complementarity program (LCP). Following the proof of this technical result is a discussion of a special formulation and initialization of a standard LCP pivoting algorithm which has, in numerical experiments, always terminated in a complementary solution. That the LCP algorithm as formulated always finds a complementary solution has not yet been proven, but these theoretical and experimental results have the potential to provide an alternative proof of the ordered field property for these games. Numerical experimentation with the reformulated LCP is reviewed.     

Fictitious play applied to sequences of games and discounted stochastic games

In this paper, we show that the iterative method of Brown and Robinson, for solving a matrix game, is also applicable to a converging sequence of matrices, where the players choose at staget a row and a column of thet-th matrix in the sequence. As an application of this result, we describe a new solution method for discounted stochastic games with finite state and action spaces.     

Algorithms for stochastic games — A survey

We consider finite state, finite action, stochastic games over an infinite time horizon. We survey algorithms for the computation of minimax optimal stationary strategies in the zerosum case, and of Nash equilibria in stationary strategies in the nonzerosum case. We also survey those theoretical results that pave the way towards future development of algorithms.

---

Zusammenfassung In dieser Arbeit werden unendlichstufige stochastische Spiele mit endlichen ZuStands- und Aktionenräumen untersucht. Es wird ein Überblick gegeben über Algorithmen zur Berechnung von optimalen stationären Minimax-Strategien in Nullsummen-Spielen und von stationären Nash-Gleichgewichtsstrategien in Nicht-Nullsummen-Spielen. Einige theoretische Ergebnisse werden vorgestellt, die für die weitere Entwicklung von Algorithmen nützlich sind.

---

---

This paper is based on the invited lectures given by the authors at the 12th Symposium for Operations Research in Passau, 1987. We are indebted to M. Abbad, Evangelista Fe, F. Thuijsman and O. J. Vrieze for valuable comments and discussion. Any remaining errors of either misinterpretation or of omission are the authors' alone.

---

Supported in part by the NSF under the grant # DMS-82601403.

---

Supported in part by the AFOSR and the NSF under the grant # ECS-8704954.     

On the functional equations in undiscounted and sensitive discounted stochastic games

This paper considers two-person zero-sum sequential games with finite state and action spaces. We consider the pair of functional equations (f.e.) that arises in the undiscounted infinite stage model, and show that a certain class of successive approximation schemes is guaranteed to converge to a solution pair whenever an equilibrium policy with respect to the average return per unit time criterion (AEP) exists. Existence of the latter thus implies the existence of a solution to this pair of f.e. whereas the converse implication is shown only to hold under special circumstances.In addition to this pair of f.e., a complete sequence of f.e. has to be considered when analyzing more sensitive optimality criteria that make further selections within the class of AEPs. A number of characterizations and interdependences between the existence of solutions to the f.e. and existence of stationary sensitive optimal equilibrium policies are obtained.

---

Zusammenfassung Die Arbeit behandelt sequentielle Zweipersonen-Nullsummenspiele mit endlichem Zustands- und endlichem Aktionenraum. Es wird das Paar von Funktionalgleichungen für das unendlich-stufige Modell ohne Diskontierung betrachtet und gezeigt, daß eine gewisse Klasse von sukzessiven Approximationen gegen ein Lösungspaar konvergiert, wenn eine Gleichgewichtspolitik für den Fall existiert, daß als Kriterium die durchschnittliche Auszahlung pro Zeiteinheit gewählt wird. Werden empfindlichere Optimalitätskriterien betrachtet, so muß zusätzlich zu dem obigen Funktionalgleichungspaar eine ganze Folge von Funktionalgleichungen untersucht werden. Weiter werden Resultate über die Existenz von Lösungen der Funktionalgleichungen und die damit zusammenhängende Existenz stationärer optimaler Gleichgewichtspolitiken hergeleitet.

     

Vertical linear complementarity and discounted zero-sum stochastic games with ARAT structure

In this paper we consider a two-person zero-sum discounted stochastic game with ARAT structure and formulate the problem of computing a pair of pure optimal stationary strategies and the corresponding value vector of such a game as a vertical linear complementarity problem. We show that Cottle-Dantzig’s algorithm (a generalization of Lemke’s algorithm) can solve this problem under a mild assumption. Received July 8, 1998 / Revised version received April 16, 1999? Published online September 15, 1999     

On discounted stochastic games with incomplete information on payoffs and a security application

This paper presents a robust optimization model for n$n$-person finite state/action stochastic games with incomplete information on payoffs. For polytopic uncertainty sets, we propose an explicit mathematical programming formulation for an equilibrium calculation. It turns out that a global optimal of this mathematical program yields an equilibrium point and epsilon-equilibria can be calculated based on this result. We briefly describe an incomplete information version of a security application that can benefit from robust game theory.     

Existence of equilibrium stationary strategies in discounted noncooperative stochastic games with uncountable state space

This paper considers discounted noncooperative stochastic games with uncountable state space and compact metric action spaces. We assume that the transition law is absolutely continuous with respect to some probability measure defined on the state space. We prove, under certain additional continuity and integrability conditions, that such games have -equilibrium stationary strategies for each >0. To prove this fact, we provide a method for approximating the original game by a sequence of finite or countable state games. The main result of this paper answers partially a question raised by Parthasarathy in Ref. 1.     

On a new class of nonzero-sum discounted stochastic games having stationary Nash equilibrium points

A new class of nonzero-sum Borel state space discounted stochastic games having stationary Nash equilibria is presented. Some applications to economic theory are also included. Received: January 2002/Revised: July 2002     

Algorithms for lattice games

This paper provides effective methods for the polyhedral formulation of impartial finite combinatorial games as lattice games (Guo et al. Oberwolfach Rep 22: 23–26, 2009; Guo and Miller, Adv Appl Math 46:363–378, 2010). Given a rational strategy for a lattice game, a polynomial time algorithm is presented to decide (i) whether a given position is a winning position, and to find a move to a winning position, if not; and (ii) to decide whether two given positions are congruent, in the sense of misère quotient theory (Plambeck, Integers, 5:36, 2005; Plambeck and Siegel, J Combin Theory Ser A, 115: 593–622, 2008). The methods are based on the theory of short rational generating functions (Barvinok and Woods, J Am Math Soc, 16: 957–979, 2003).     

Algorithms for uniform optimal strategies in two-player zero-sum stochastic games with perfect information

We deal with zero-sum two-player stochastic games with perfect information. We propose two algorithms to find the uniform optimal strategies and one method to compute the optimality range of discount factors. We prove the convergence in finite time for one algorithm. The uniform optimal strategies are also optimal for the long run average criterion and, in transient games, for the undiscounted criterion as well.     

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.     

Regularity for nonlinear stochastic games

We establish regularity for functions satisfying a dynamic programming equation, which may arise for example from stochastic games or discretization schemes. Our results can also be utilized in obtaining regularity and existence results for the corresponding partial differential equations.     

On continuous-time discounted stochastic dynamic programming

In this paper a continuous-time discounted dynamic programming problem in a Markov decision model is investigated. In many cases it is difficult to search directly for an optimal solution for such a programming problem. We introduce a Lagrangian-type programming problem associated with the original programming problem and show that, under some assumptions, a weak optimal solution exists for the Lagrangian problem. Moreover, we consider the original programming problem in the perturbed programming one and develop the Lagrangian duality.     

Adaptive policies for time-varying stochastic systems under discounted criterion

We consider a class of time-varying stochastic control systems, with Borel state and action spaces, and possibly unbounded costs. The processes evolve according to a discrete-time equation x _{n + 1}=G _n (x _n , a _n , ξ_n), n=0, 1, … , where the ξ_n are i.i.d. ℜ^k-valued random vectors whose common density is unknown, and the G _n are given functions converging, in a restricted way, to some function G _∞ as n→∞. Assuming observability of ξ_n, we construct an adaptive policy which is asymptotically discounted cost optimal for the limiting control system x _n+1=G _∞ (x _n , a _n , ξ_n).     

Existence of stationary equilibrium strategies in non-zero sum discounted stochastic games with uncountable state space and state-independent transitions

Non-zero sum discounted stochastic games with uncountable state space and state in-dependent transitions have stationary equilibrium strategies.     

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.     

Perturbation theory for games in normal form and stochastic games

In this paper, the effect on values and optimal strategies of perturbations of game parameters (payoff function, transition probability function, and discount factor) is studied for the class of zero-sum games in normal form and for the class of stationary, discounted, two-person, zero-sum stochastic games.A main result is that, under certain conditions, the value depends on these parameters in a pointwise Lipschitz continuous way and that the sets of -optimal strategies for both players are upper semicontinuous multifunctions of the game parameters.Extensions to general-sum games and nonstationary stochastic games are also indicated.     

The use of public randomization in discounted repeated games

This paper presents an example where the set of subgame-perfect equilibrium payoffs of the infinitely repeated game without public randomization is not convex, no matter how large the discount factor is. Also, the set of pure-strategy equilibrium payoffs is not monotonic with respect to the discount factor in this example. These results are in sharp contrast to the fact that the equilibrium payoff set is convex and monotonic if public randomization is available.