Skip to main content

Non-Zero-Sum Stochastic Games

  • Living reference work entry
  • Latest version View entry history
  • First Online:
Handbook of Dynamic Game Theory

Abstract

This chapter describes a number of results obtained in the last 60 years on the theory of non-zero-sum discrete-time stochastic games. We provide an overview of almost all basic streams of research in this area such as the existence of stationary Nash and correlated equilibria in models on countable and general state spaces, the existence of subgame-perfect equilibria, algorithms, stopping games, and the existence of uniform equilibria. Our survey incorporates several examples of games studied in operations research and economics. In particular, separate sections are devoted to intergenerational games, dynamic Cournot competition and game models of resource extraction. The provided reference list includes not only seminal papers that commenced research in various directions but also exposes recent advances in this field.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Institutional subscriptions

Similar content being viewed by others

References

  • Abreu D, Pearce D, Stacchetti E (1986) Optimal cartel equilibria with imperfect monitoring. J Econ Theory 39:251–269

    Article  MathSciNet  MATH  Google Scholar 

  • Abreu D, Pearce D, Stacchetti E (1990) Toward a theory of discounted repeated games with imperfect monitoring. Econometrica 58:1041–1063

    Article  MathSciNet  MATH  Google Scholar 

  • Adlakha S, Johari R (2013) Mean field equilibrium in dynamic games with strategic complementarities. Oper Res 61:971–989

    Article  MathSciNet  MATH  Google Scholar 

  • Aliprantis C, Border K (2006) Infinite dimensional analysis: a Hitchhiker’s guide. Springer, New York

    MATH  Google Scholar 

  • Alj A, Haurie A (1983) Dynamic equilibria in multigenerational stochastic games. IEEE Trans Autom Control 28:193–203

    Article  MATH  Google Scholar 

  • Alós-Ferrer C, Ritzberger K (2015) Characterizing existence of equilibrium for large extensive form games: a necessity result. Econ Theory 63:407–430

    Article  MathSciNet  MATH  Google Scholar 

  • Alós-Ferrer C, Ritzberger K (2016) Equilibrium existence for large perfect information games. J Math Econ 62:5–18

    Article  MathSciNet  MATH  Google Scholar 

  • Altman E (1996) Non-zero-sum stochastic games in admission, service and routing control in queueing systems. Queueing Syst Theory Appl 23:259–279

    Article  MathSciNet  MATH  Google Scholar 

  • Altman E, Avrachenkov K, Bonneau N, Debbah M, El-Azouzi R, Sadoc Menasche D (2008) Constrained cost-coupled stochastic games with independent state processes. Oper Res Lett 36:160–164

    Article  MathSciNet  MATH  Google Scholar 

  • Altman E, Avrachenkov K, Marquez R, Miller G (2005) Zero-sum constrained stochastic games with independent state processes. Math Methods Oper Res 62:375–386

    Article  MathSciNet  MATH  Google Scholar 

  • Altman E, Hordijk A, Spieksma FM (1997) Contraction conditions for average and α-discount optimality in countable state Markov games with unbounded rewards. Math Oper Res 22:588–618

    Article  MathSciNet  MATH  Google Scholar 

  • Amir R (1996a) Continuous stochastic games of capital accumulation with convex transitions. Games Econ Behavior 15:132–148

    Article  MathSciNet  MATH  Google Scholar 

  • Amir R (1996b) Strategic intergenerational bequests with stochastic convex production. Econ Theory 8:367–376

    Article  MATH  Google Scholar 

  • Amir R (2003) Stochastic games in economics: the lattice-theoretic approach. In: Neyman A, Sorin S (eds) Stochastic games and applications. Kluwer, Dordrecht, pp 443–453

    Chapter  Google Scholar 

  • Artstein Z (1989) Parametrized integration of multifunctions with applications to control and optimization. SIAM J Control Optim 27:1369–1380

    Article  MathSciNet  MATH  Google Scholar 

  • Aumann RJ (1974) Subjectivity and correlation in randomized strategies. J Math Econ 1:67–96

    Article  MathSciNet  MATH  Google Scholar 

  • Aumann RJ (1987) Correlated equilibrium as an expression of Bayesian rationality. Econometrica 55:1–18

    Article  MathSciNet  MATH  Google Scholar 

  • Balbus Ł, Jaśkiewicz A, Nowak AS (2014) Robust Markov perfect equilibria in a dynamic choice model with quasi-hyperbolic discounting. In: Haunschmied J et al (eds) Dynamic games in economics, dynamic modeling and econometrics in economics and finance 16. Springer, Berlin/Heidelberg, pp 1–22

    Google Scholar 

  • Balbus Ł, Jaśkiewicz A, Nowak AS (2015a) Existence of stationary Markov perfect equilibria in stochastic altruistic growth economies. J Optim Theory Appl 165:295–315

    Article  MathSciNet  MATH  Google Scholar 

  • Balbus Ł, Jaśkiewicz A, Nowak AS (2015b) Stochastic bequest games. Games Econ Behavior 90:247–256

    Article  MathSciNet  MATH  Google Scholar 

  • Balbus Ł, Jaśkiewicz A, Nowak AS (2015c) Bequest games with unbounded utility functions. J Math Anal Appl 427:515–524

    Article  MathSciNet  MATH  Google Scholar 

  • Balbus Ł, Jaśkiewicz A, Nowak AS (2016) Non-paternalistic intergenerational altruism revisited. J Math Econ 63:27–33

    Article  MathSciNet  MATH  Google Scholar 

  • Balbus Ł, Nowak AS (2004) Construction of Nash equilibria in symmetric stochastic games of capital accumulation. Math Methods Oper Res 60:267–277

    Article  MathSciNet  MATH  Google Scholar 

  • Balbus Ł, Nowak AS (2008) Existence of perfect equilibria in a class of multigenerational stochastic games of capital accumulation. Automatica 44:1471–1479

    Article  MathSciNet  MATH  Google Scholar 

  • Balbus Ł, Reffett K, Woźny Ł (2012) Stationary Markovian equilibria in altruistic stochastic OLG models with limited commitment. J Math Econ 48:115–132

    Article  MATH  Google Scholar 

  • Balbus Ł, Reffett K, Woźny Ł (2013a) A constructive geometrical approach to the uniqueness of Markov stationary equilibrium in stochastic games of intergenerational altruism. J Econ Dyn Control 37:1019–1039

    Article  MathSciNet  Google Scholar 

  • Balbus Ł, Reffett K, Woźny Ł (2013b) Markov stationary equilibria in stochastic supermodular games with imperfect private and public information. Dyn Games Appl 3:187–206

    Article  MathSciNet  MATH  Google Scholar 

  • Balbus Ł, Reffett K, Woźny Ł (2014a) Constructive study of Markov equilibria in stochastic games with complementarities. J Econ Theory 150:815–840

    Article  MathSciNet  MATH  Google Scholar 

  • Balbus Ł, Jaśkiewicz A, Nowak AS, Woźny L (2017) A note on Markov perfect equilibria in a class of non-stationary bequest games. J Math Anal Appl 456:394–401

    Article  MathSciNet  MATH  Google Scholar 

  • Balbus Ł, Jaśkiewicz A, Nowak AS (2018, in press) Markov perfect equilibria in a dynamic decision model with quasi-hyperbolic discounting. Ann Oper Res

    Google Scholar 

  • Barelli P, Duggan J (2014) A note on semi-Markov perfect equilibria in discounted stochastic games. J Econ Theory 15:596–604

    Article  MathSciNet  MATH  Google Scholar 

  • Başar T, Olsder GJ (1995) Dynamic noncooperative game theory. Academic, New York

    MATH  Google Scholar 

  • Berg K (2016) Elementary subpaths in discounted stochastic games. Dyn Games Appl 6(3): 304–323

    Article  MathSciNet  MATH  Google Scholar 

  • Bernheim D, Ray D (1983) Altruistic growth economies I. Existence of bequest equilibria. Technical report no 419, Institute for Mathematical Studies in the Social Sciences, Stanford University

    Google Scholar 

  • Bernheim D, Ray D (1986) On the existence of Markov-consistent plans under production uncertainty. Rev Econ Stud 53:877–882

    Article  MathSciNet  MATH  Google Scholar 

  • Bernheim D, Ray D (1987) Economic growth with intergenerational altruism. Rev Econ Stud 54:227–242

    Article  MathSciNet  MATH  Google Scholar 

  • Bernheim D, Ray D (1989) Markov perfect equilibria in altruistic growth economies with production uncertainty. J Econ Theory 47:195–202

    Article  MathSciNet  MATH  Google Scholar 

  • Bhattacharya R, Majumdar M (2007) Random dynamical systems: theory and applications. Cambridge University Press, Cambridge

    Book  MATH  Google Scholar 

  • Billingsley P (1968) Convergence of probability measures. Wiley, New York

    MATH  Google Scholar 

  • Blackwell D (1965) Discounted dynamic programming. Ann Math Stat 36:226–235

    Article  MathSciNet  MATH  Google Scholar 

  • Blackwell D (1969) Infinite G δ -games with imperfect information. Zastosowania Matematyki (Appl Math) 10:99–101

    MathSciNet  MATH  Google Scholar 

  • Borkar VS, Ghosh MK (1993) Denumerable state stochastic games with limiting average payoff. J Optim Theory Appl 76:539–560

    Article  MathSciNet  MATH  Google Scholar 

  • Browder FE (1960) On continuity of fixed points under deformations of continuous mappings. Summa Brasiliensis Math 4:183–191

    MathSciNet  MATH  Google Scholar 

  • Carlson D, Haurie A (1996) A turnpike theory for infinite-horizon open-loop competitive processes. SIAM J Control Optim 34:1405–1419

    Article  MathSciNet  MATH  Google Scholar 

  • Castaing C, Valadier M (1977) Convex analysis and measurable multifunctions. Lecture notes in mathematics, vol 580. Springer, New York

    MATH  Google Scholar 

  • Chatterjee S, Eyigungor B (2016) Continuous Markov equilibria with quasi-geometric discounting. J Econ Theory 163:467–494

    Article  MathSciNet  MATH  Google Scholar 

  • Chiarella C, Kemp MC, Van Long N, Okuguchi K (1984) On the economics of international fisheries. Int Econ Rev 25:85–92

    Article  MathSciNet  MATH  Google Scholar 

  • Cingiz K, Flesch J, Herings JJP, Predtetchinski A (2016) Doing it now, later, or never. Games Econ Behavior 97:174–185

    Article  MathSciNet  MATH  Google Scholar 

  • Cole HL, Kocherlakota N (2001) Dynamic games with hidden actions and hidden states. J Econ Theory 98:114–126

    Article  MathSciNet  MATH  Google Scholar 

  • Cottle RW, Pang JS, Stone RE (1992) The linear complementarity problem. Academic, New York

    MATH  Google Scholar 

  • Curtat LO (1996) Markov equilibria of stochastic games with complementarities. Games Econ Behavior 17:177–199

    Article  MathSciNet  MATH  Google Scholar 

  • Doraszelski U, Escobar JF (2010) A theory of regular Markov perfect equilibria in dynamic stochastic games: genericity, stability, and purification. Theor Econ 5:369–402

    Article  MathSciNet  MATH  Google Scholar 

  • Doraszelski U, Pakes A (2007) A framework for applied dynamic analysis in IO. In: Amstrong M, Porter RH (eds) Handbook of industrial organization, vol 3. North Holland, Amsterdam/London, pp 1887–1966

    Google Scholar 

  • Doraszelski U, Satterthwaite M (2010) Computable Markov-perfect industry dynamics. Rand J Econ 41:215–243

    Article  Google Scholar 

  • Dubins LE, Savage LJ (2014) Inequalities for stochastic processes. Dover, New York

    MATH  Google Scholar 

  • Duffie D, Geanakoplos J, Mas-Colell A, McLennan A (1994) Stationary Markov equilibria. Econometrica 62:745–781

    Article  MathSciNet  MATH  Google Scholar 

  • Duggan J (2012) Noisy stochastic games. Econometrica 80:2017–2046

    Article  MathSciNet  MATH  Google Scholar 

  • Dutta PK (1995) A folk theorem for stochastic games. J Econ Theory 66:1–32

    Article  MathSciNet  MATH  Google Scholar 

  • Dutta PK, Sundaram RK (1992) Markovian equilibrium in class of stochastic games: existence theorems for discounted and undiscounted models. Econ Theory 2:197–214

    Article  MathSciNet  MATH  Google Scholar 

  • Dutta PK, Sundaram RK (1993) The tragedy of the commons? Econ Theory 3:413–426

    Article  MathSciNet  MATH  Google Scholar 

  • Dutta PK, Sundaram RK (1998) The equilibrium existence problem in general Markovian games. In: Majumdar M (ed) Organizations with incomplete information. Cambridge University Press, Cambridge, pp 159–207

    Chapter  Google Scholar 

  • Dynkin EB (1969) The game variant of a problem on optimal stopping. Sov Math Dokl 10:270–274

    MATH  Google Scholar 

  • Dynkin EB, Evstigneev IV (1977) Regular conditional expectations of correspondences. Theory Probab Appl 21:325–338

    Article  MATH  Google Scholar 

  • Eaves B (1972) Homotopies for computation of fixed points. Math Program 3:1–22

    Article  MathSciNet  MATH  Google Scholar 

  • Eaves B (1984) A course in triangulations for solving equations with deformations. Springer, Berlin

    Book  MATH  Google Scholar 

  • Elliott RJ, Kalton NJ, Markus L (1973) Saddle-points for linear differential games. SIAM J Control Optim 11:100–112

    Article  MathSciNet  MATH  Google Scholar 

  • Enns EG, Ferenstein EZ (1987) On a multi-person time-sequential game with priorities. Seq Anal 6:239–256

    Article  MATH  Google Scholar 

  • Ericson R, Pakes A (1995) Markov-perfect industry dynamics: a framework for empirical work. Rev Econ Stud 62:53–82

    Article  MATH  Google Scholar 

  • Escobar JF (2013) Equilibrium analysis of dynamic models of imperfect competition. Int J Ind Organ 31:92–101

    Article  Google Scholar 

  • Federgruen A (1978) On N-person stochastic games with denumerable state space. Adv Appl Probab 10:452–471

    MathSciNet  MATH  Google Scholar 

  • Ferenstein E (2007) Randomized stopping games and Markov market games. Math Methods Oper Res 66:531–544

    Article  MathSciNet  MATH  Google Scholar 

  • Filar JA, Schultz T, Thuijsman F, Vrieze OJ (1991) Nonlinear programming and stationary equilibria in stochastic games. Math Program 50:227–237

    Article  MathSciNet  MATH  Google Scholar 

  • Filar JA, Vrieze K (1997) Competitive Markov decision processes. Springer, New York

    MATH  Google Scholar 

  • Fink AM (1964) Equilibrium in a stochastic n-person game. J Sci Hiroshima Univ Ser A-I Math 28:89–93

    MathSciNet  MATH  Google Scholar 

  • Flesch J, Schoenmakers G, Vrieze K (2008) Stochastic games on a product state space. Math Oper Res 33:403–420

    Article  MathSciNet  MATH  Google Scholar 

  • Flesch J, Schoenmakers G, Vrieze K (2009) Stochastic games on a product state space: the periodic case. Int J Game Theory 38:263–289

    Article  MathSciNet  MATH  Google Scholar 

  • Flesch J, Thuijsman F, Vrieze OJ (1997) Cyclic Markov equilibrium in stochastic games. Int J Garne Theory 26:303–314

    Article  MATH  Google Scholar 

  • Flesch J, Thuijsman F, Vrieze OJ (2003) Stochastic games with non-observable actions. Math Methods Oper Res 58:459–475

    Article  MathSciNet  MATH  Google Scholar 

  • Flesch J, Kuipers J, Mashiah-Yaakovi A, Schoenmakers G, Solan E, Vrieze K (2010a) Perfect-information games with lower-semicontinuous payoffs. Math Oper Res 35:742–755

    Article  MathSciNet  MATH  Google Scholar 

  • Flesch J, Kuipers J, Schoenmakers G, Vrieze K (2010b) Subgame-perfection in positive recursive games with perfect information. Math Oper Res 35:193–207

    Article  MathSciNet  MATH  Google Scholar 

  • Flesch J, Kuipers J, Mashiah-Yaakovi A, Schoenmakers G, Shmaya E, Solan E, Vrieze K (2014) Non-existence of subgame-perfect 𝜖-equilibrium in perfect-information games with infinite horizon. Int J Game Theory 43:945–951

    Article  MathSciNet  MATH  Google Scholar 

  • Flesch J, Thuijsman F, Vrieze OJ (2007) Stochastic games with additive transitions. Eur J Oper Res 179:483–497

    Article  MathSciNet  MATH  Google Scholar 

  • Flesch J, Predtetchinski A (2015) On refinements of subgame perfect 𝜖 -equilibrium. Int J Game Theory 45:523–542

    Article  MathSciNet  MATH  Google Scholar 

  • Forges E (1986) An approach to communication equilibria. Econometrica 54:1375–1385

    Article  MathSciNet  MATH  Google Scholar 

  • Forges F (1992) Repeated games of incomplete information: non-zero-sum. In: Aumann RJ, Hart S (eds) Handbook of game theory, vol 1. North Holland, Amsterdam, pp 155–177

    Google Scholar 

  • Forges F (2009) Correlated equilibria and communication in games. In: Meyers RA (ed) Encyclopedia of complexity and systems science. Springer, New York, pp 1587–1596

    Chapter  Google Scholar 

  • Fudenberg D, Levine D (1983) Subgame-perfect equilibria of finite and infinite horizon games. J Econ Theory 31:251–268

    Article  MathSciNet  MATH  Google Scholar 

  • Fudenberg D, Tirole J (1991) Game theory. MIT Press, Cambridge

    MATH  Google Scholar 

  • Fudenberg D, Yamamoto Y (2011) The folk theorem for irreducible stochastic games with imperfect public monitoring. J Econ Theory 146:1664–1683

    Article  MathSciNet  MATH  Google Scholar 

  • Gale D (1967) On optimal development in a multisector economy. Rev Econ Stud 34:1–19

    Article  Google Scholar 

  • Glicksberg IL (1952) A further generalization of the Kakutani fixed point theorem with application to Nash equilibrium points. Proc Am Math Soc 3:170–174

    MathSciNet  MATH  Google Scholar 

  • Govindan S, Wilson R (2003) A global Newton method to compute Nash equilibria. J Econ Theory 110:65–86

    Article  MathSciNet  MATH  Google Scholar 

  • Govindan S, Wilson R (2009) Global Newton method for stochastic games. J Econ Theory 144:414–421

    Article  MathSciNet  MATH  Google Scholar 

  • Haller H, Lagunoff R (2000) Genericity and Markovian behavior in stochastic games. Econometrica 68:1231–1248

    Article  MathSciNet  MATH  Google Scholar 

  • Hamadène S, Hassani M (2014) The multi-player nonzero-sum Dynkin game in discrete time. Math Methods Oper Res 79:179–194

    Article  MathSciNet  MATH  Google Scholar 

  • Harris C (1985) Existence and characterization of perfect equilibrium in games of perfect information. Econometrica 53:613–628

    Article  MathSciNet  MATH  Google Scholar 

  • Harris C, Laibson D (2001) Dynamic choices of hyperbolic consumers. Econometrica 69:935–957

    Article  MathSciNet  MATH  Google Scholar 

  • Harris C, Reny PJ, Robson A (1995) The existence of subgame-perfect equilibrium in continuous games with almost perfect information: a case for public randomization. Econometrica 63:507–544

    Article  MathSciNet  MATH  Google Scholar 

  • Harsanyi JC (1973a) Oddness of the number of equilibrium points: a new proof. Int J Game Theory 2:235–250

    Article  MathSciNet  MATH  Google Scholar 

  • Harsanyi JC (1973b) Games with randomly disturbed payoffs: a new rationale for mixed-strategy equilibrium points. Int J Game Theory 2:1–23

    Article  MathSciNet  MATH  Google Scholar 

  • Haurie A, Krawczyk JB, Zaccour G (2012) Games and dynamic games. World Scientific, Singapore

    Book  MATH  Google Scholar 

  • He W, Sun Y (2017) Stationary Markov perfect equilibria in discounted stochastic games. J Econ Theory 169:35–61

    Article  MathSciNet  MATH  Google Scholar 

  • Heller Y (2012) Sequential correlated equilibria in stopping games. Oper Res 60:209–224

    Article  MathSciNet  MATH  Google Scholar 

  • Herings JJP, Peeters RJAP (2004) Stationary equilibria in stochastic games: structure, selection, and computation. J Econ Theory 118:32–60

    MathSciNet  MATH  Google Scholar 

  • Herings JJP, Peeters RJAP (2010) Homotopy methods to compute equilibria in game theory. Econ Theory 42:119–156

    Article  MathSciNet  MATH  Google Scholar 

  • Himmelberg CJ (1975) Measurable relations. Fundam Math 87:53–72

    Article  MathSciNet  MATH  Google Scholar 

  • Himmelberg CJ, Parthasarathy T, Raghavan TES, Van Vleck FS (1976) Existence of p-equilibrium and optimal stationary strategies in stochastic games. Proc Am Math Soc 60:245–251

    MathSciNet  MATH  Google Scholar 

  • Hopenhayn H, Prescott E (1992) Stochastic monotonicity and stationary distributions for dynamic economies. Econometrica 60:1387–1406

    Article  MathSciNet  MATH  Google Scholar 

  • Hörner J, Sugaya T, Takahashi S, Vieille N (2011) Recursive methods in discounted stochastic games: an algorithm for δ → 1 and a folk theorem. Econometrica 79:1277–1318

    Article  MathSciNet  MATH  Google Scholar 

  • Hörner J, Takahashi S, Vieille N (2014) On the limit perfect public equilibrium payoff set in repeated and stochastic game. Games Econ Behavior 85:70–83

    Article  MathSciNet  MATH  Google Scholar 

  • Horst U (2005) Stationary equilibria in discounted stochastic games with weakly interacting players. Games Econ Behavior 51:83–108

    Article  MathSciNet  MATH  Google Scholar 

  • Jaśkiewicz A, Nowak AS (2006) Approximation of noncooperative semi-Markov games. J Optim Theory Appl 131:115–134

    Article  MathSciNet  MATH  Google Scholar 

  • Jaśkiewicz A, Nowak AS (2014a) Stationary Markov perfect equilibria in risk sensitive stochastic overlapping generations models. J Econ Theory 151:411–447

    Article  MathSciNet  MATH  Google Scholar 

  • Jaśkiewicz A, Nowak AS (2014b) Robust Markov perfect equilibria. J Math Anal Appl 419:1322–1332

    Article  MathSciNet  MATH  Google Scholar 

  • Jaśkiewicz A, Nowak AS (2015a) On pure stationary almost Markov Nash equilibria in nonzero-sum ARAT stochastic games. Math Methods Oper Res 81:169–179

    Article  MathSciNet  MATH  Google Scholar 

  • Jaśkiewicz A, Nowak AS (2015b) Stochastic games of resource extraction. Automatica 54:310–316

    Article  MathSciNet  MATH  Google Scholar 

  • Jaśkiewicz A, Nowak AS (2016) Stationary almost Markov perfect equilibria in discounted stochastic games. Math Oper Res 41:430–441

    Article  MathSciNet  MATH  Google Scholar 

  • Jaśkiewicz A, Nowak AS (2018a) Zero-sum stochastic games. In: Basar T, Zaccour G (eds) Handbook of dynamic game theory, Birkhäuser, Basel

    Google Scholar 

  • Jaśkiewicz A, Nowak AS (2018b, in press) On symmetric stochastic games of resource extraction with weakly continuous transitions. TOP

    Google Scholar 

  • Kakutani S (1941) A generalization of Brouwer’s fixed point theorem. Duke Math J 8:457–459

    Article  MathSciNet  MATH  Google Scholar 

  • Kiefer YI (1971) Optimal stopped games. Theory Probab Appl 16:185–189

    Article  Google Scholar 

  • Kitti M (2016) Subgame-perfect equilibria in discounted stochastic games. J Math Anal Appl 435:253–266

    Article  MathSciNet  MATH  Google Scholar 

  • Klein E, Thompson AC (1984) Theory of correspondences. Wiley, New York

    MATH  Google Scholar 

  • Kohlberg E, Mertens JF (1986) On the strategic stability of equilibria. Econometrica 54:1003–1037

    Article  MathSciNet  MATH  Google Scholar 

  • Krasnosielska-Kobos A (2016) Construction of Nash equilibrium based on multiple stopping problem in multi-person game. Math Methods Oper Res (2016) 83:53–70

    Article  MathSciNet  MATH  Google Scholar 

  • Krasnosielska-Kobos A, Ferenstein E (2013) Construction of Nash equilibrium in a game version of Elfving’s multiple stopping problem. Dyn Games Appl 3:220–235

    Article  MathSciNet  MATH  Google Scholar 

  • Krishnamurthy N, Parthasarathy T, Babu S (2012) Existence of stationary equilibrium for mixtures of discounted stochastic games. Curr Sci 103:1003–1013

    Google Scholar 

  • Krishnamurthy N, Parthasarathy T, Ravindran G (2012) Solving subclasses of multi-player stochastic games via linear complementarity problem formulations – a survey and some new results. Optim Eng 13:435–457

    Article  MathSciNet  MATH  Google Scholar 

  • Kuipers J, Flesch J, Schoenmakers G, Vrieze K (2016) Subgame-perfection in recursive perfect information games, where each player controls one state. Int J Game Theory 45:205–237

    Article  MathSciNet  MATH  Google Scholar 

  • Kuratowski K, Ryll-Nardzewski C (1965) A general theorem on selectors. Bull Polish Acad Sci (Ser Math) 13:397–403

    MathSciNet  MATH  Google Scholar 

  • Küenle HU (1994) On Nash equilibrium solutions in nonzero-sum stochastic games with complete information. Int J Game Theory 23:303–324

    Article  MathSciNet  MATH  Google Scholar 

  • Küenle HU (1999) Equilibrium strategies in stochastic games with additive cost and transition structure and Borel state and action spaces. Int Game Theory Rev 1:131–147

    Article  MathSciNet  MATH  Google Scholar 

  • Leininger W (1986) The existence of perfect equilibria in model of growth with altruism between generations. Rev Econ Stud 53:349–368

    Article  MathSciNet  MATH  Google Scholar 

  • Lemke CE (1965) Bimatrix equilibrium points and mathematical programming. Manag Sci 11:681–689

    Article  MathSciNet  MATH  Google Scholar 

  • Lemke CE, Howson JT Jr (1964) Equilibrium points of bimatrix games. SIAM J Appl Math 12:413–423

    Article  MathSciNet  MATH  Google Scholar 

  • Levhari D, Mirman L (1980) The great fish war: an example using a dynamic Coumot-Nash solution. Bell J Econ 11:322–334

    Article  Google Scholar 

  • Levy YJ (2013) Discounted stochastic games with no stationary Nash equilibrium: two examples. Econometrica 81:1973–2007

    Article  MathSciNet  MATH  Google Scholar 

  • Levy YJ, McLennan A (2015) Corrigendum to: discounted stochastic games with no stationary Nash equilibrium: two examples. Econometrica 83:1237–1252

    Article  MathSciNet  Google Scholar 

  • Maitra A, Sudderth W (2003) Borel stay-in-a-set games. Int J Game Theory 32:97–108

    Article  MathSciNet  MATH  Google Scholar 

  • Maitra A, Sudderth WD (2007) Subgame-perfect equilibria for stochastic games. Math Oper Res 32:711–722

    Article  MathSciNet  MATH  Google Scholar 

  • Majumdar MK, Sundaram R (1991) Symmetric stochastic games of resource extraction. The existence of non-randomized stationary equilibrium. In: Raghavan et al (eds) Stochastic games and related topics. Kluwer, Dordrecht, pp 175–190

    Google Scholar 

  • Maliar, L, Maliar, S (2016) Ruling out multiplicity of smooth equilibria in dynamic games: a hyperbolic discounting example. Dyn Games Appl 6:243–261

    Article  MathSciNet  MATH  Google Scholar 

  • Mas-Colell A (1974) A note on a theorem of F. Browder. Math Program 6:229–233

    Article  MathSciNet  MATH  Google Scholar 

  • Mashiah-Yaakovi A (2009) Periodic stopping games. Int J Game Theory 38:169–181

    Article  MathSciNet  MATH  Google Scholar 

  • Mashiah-Yaakovi A (2014) Subgame-perfect equilibria in stopping games. Int J Game Theory 43:89–135

    Article  MathSciNet  MATH  Google Scholar 

  • Mashiah-Yaakovi A (2015) Correlated equilibria in stochastic games with Borel measurable payoffs. Dyn Games Appl 5:120–135

    Article  MathSciNet  MATH  Google Scholar 

  • Maskin E, Tirole J (2001) Markov perfect equilibrium: I. Observable actions. J Econ Theory 100:191–219

    Article  MathSciNet  MATH  Google Scholar 

  • Mertens JF (2002) Stochastic games. In: Aumann RJ, Hart S (eds) Handbook of game theory with economic applications, vol 3. North Holland, Amsterdam/London, pp 1809–1832

    Google Scholar 

  • Mertens JF (2003) A measurable measurable choice theorem. In: Neyman A, Sorin S (eds) Stochastic games and applications. Kluwer, Dordrecht, pp 107–130

    Chapter  Google Scholar 

  • Mertens JF, Neyman A (1981) Stochastic games. Int J Game Theory 10:53–56

    Article  MathSciNet  MATH  Google Scholar 

  • Mertens JF, Parthasarathy T (1991) Nonzero-sum stochastic games. In: Raghavan et al (eds) Stochastic games and related topics. Kluwer, Dordrecht, pp 145–148

    Google Scholar 

  • Mertens JF, Parthasarathy T (2003) Equilibria for discounted stochastic games. In: Neyman A, Sorin S (eds) Stochastic games and applications. Kluwer, Dordrecht, pp 131–172

    Chapter  Google Scholar 

  • Mertens JF, Sorin S, Zamir S (2015) Repeated games. Cambridge University Press, Cambridge

    Book  MATH  Google Scholar 

  • Milgrom P, Roberts J (1990) Rationalizability, learning and equilibrium in games with strategic complementarities. Econometrica 58:1255–1277

    Article  MathSciNet  MATH  Google Scholar 

  • Milgrom P, Shannon C (1994) Monotone comparative statics. Econometrica 62:157–180

    Article  MathSciNet  MATH  Google Scholar 

  • Mohan SR, Neogy SK, Parthasarathy T (1997) Linear complementarity and discounted polystochastic game when one player controls transitions. In: Ferris MC, Pang JS (eds) Proceedings of the international conference on complementarity problems. SIAM, Philadelphia, pp 284–294

    Google Scholar 

  • Mohan SR, Neogy SK, Parthasarathy T (2001) Pivoting algorithms for some classes of stochastic games: a survey. Int Game Theory Rev 3:253–281

    Article  MathSciNet  MATH  Google Scholar 

  • Monderer D, Shapley LS (1996) Potential games. Games Econ Behavior 14:124–143

    Article  MathSciNet  MATH  Google Scholar 

  • Montrucchio L (1987) Lipschitz continuous policy functions for strongly concave optimization problems. J Math Econ 16:259–273

    Article  MathSciNet  MATH  Google Scholar 

  • Morimoto H (1986) Nonzero-sum discrete parameter stochastic games with stopping times. Probab Theory Relat Fields 72:155–160

    Article  MathSciNet  MATH  Google Scholar 

  • Nash JF (1950) Equilibrium points in n -person games. Proc Nat Acad Sci USA 36:48–49

    Article  MathSciNet  MATH  Google Scholar 

  • Neveu J (1975) Discrete-parameter martingales. North-Holland, Amsterdam

    MATH  Google Scholar 

  • Neyman A (2017) Continuous-time stochastic games. Games Econ Behavior 104:92–130

    Article  MathSciNet  MATH  Google Scholar 

  • Neyman A, Sorin S (eds) (2003) Stochastic games and applications. Kluwer, Dordrecht

    MATH  Google Scholar 

  • Nowak AS (1985) Existence of equilibrium stationary strategies in discounted noncooperative stochastic games with uncountable state space. J Optim Theory Appl 45:591–602

    Article  MathSciNet  MATH  Google Scholar 

  • Nowak AS (1987) Nonrandomized strategy equilibria in noncooperative stochastic games with additive transition and reward structure. J Optim Theory Appl 52:429–441

    Article  MathSciNet  MATH  Google Scholar 

  • Nowak AS (2003a) N-person stochastic games: extensions of the finite state space case and correlation. In: Neyman A, Sorin S (eds) Stochastic games and applications. Kluwer, Dordrecht, pp 93–106

    Chapter  Google Scholar 

  • Nowak AS (2003b) On a new class of nonzero-sum discounted stochastic games having stationary Nash equilibrium point. Int J Game Theory 32:121–132

    Article  MathSciNet  MATH  Google Scholar 

  • Nowak AS (2006a) On perfect equilibria in stochastic models of growth with intergenerational altruism. Econ Theory 28:73–83

    Article  MathSciNet  MATH  Google Scholar 

  • Nowak AS (2006b) A multigenerational dynamic game of resource extraction. Math Social Sci 51:327–336

    Article  MathSciNet  MATH  Google Scholar 

  • Nowak AS (2006c) A note on equilibrium in the great fish war game. Econ Bull 17(2):1–10

    Google Scholar 

  • Nowak AS (2007) On stochastic games in economics. Math Methods Oper Res 66:513–530

    Article  MathSciNet  MATH  Google Scholar 

  • Nowak AS (2008) Equilibrium in a dynamic game of capital accumulation with the overtaking criterion. Econ Lett 99:233–237

    Article  MathSciNet  MATH  Google Scholar 

  • Nowak AS (2010) On a noncooperative stochastic game played by internally cooperating generations. J Optim Theory Appl 144:88–106

    Article  MathSciNet  MATH  Google Scholar 

  • Nowak AS, Altman E (2002) ε-Equilibria for stochastic games with uncountable state space and unbounded costs. SIAM J Control Optim 40:1821–1839

    Article  MathSciNet  MATH  Google Scholar 

  • Nowak AS, Jaśkiewicz A (2005) Nonzero-sum semi-Markov games with the expected average payoffs. Math Methods Oper Res 62:23–40

    Article  MathSciNet  MATH  Google Scholar 

  • Nowak AS, Raghavan TES (1992) Existence of stationary correlated equilibria with symmetric information for discounted stochastic games. Math Oper Res 17:519–526

    Article  MathSciNet  MATH  Google Scholar 

  • Nowak AS, Raghavan TES (1993) A finite step algorithm via a bimatrix game to a single controller non-zero sum stochastic game. Math Program Ser A 59:249–259

    Article  MathSciNet  MATH  Google Scholar 

  • Nowak AS, Szajowski K (1999) Nonzero-sum stochastic games. In: Ann Int Soc Dyn Games, vol 4. Birkhäuser, Boston, pp 297–343

    Google Scholar 

  • Nowak AS, Wiȩcek P (2007) On Nikaido-Isoda type theorems for discounted stochastic games. J Math Anal Appl 332:1109–1118

    Google Scholar 

  • Ohtsubo Y (1987) A nonzero-sum extension of Dynkin’s stopping problem. Math Oper Res 12:277–296

    Article  MathSciNet  MATH  Google Scholar 

  • Ohtsubo Y (1991) On a discrete-time nonzero-sum Dynkin problem with monotonicity. J Appl Probab 28:466–472

    Article  MathSciNet  MATH  Google Scholar 

  • Parthasarathy T (1973) Discounted, positive, and noncooperative stochastic games. Int J Game Theory 2:25–37

    Article  MathSciNet  MATH  Google Scholar 

  • Parthasarathy T, Sinha S (1989) Existence of stationary equilibrium strategies in nonzero-sum discounted stochastic games with uncountable state space and state-independent transitions. Int J Game Theory 18:189–194

    Article  MATH  Google Scholar 

  • Peleg B, Yaari M (1973) On the existence of consistent course of action when tastes are changing. Rev Econ Stud 40:391–401

    Article  MATH  Google Scholar 

  • Peski M, Wiseman T (2015) A folk theorem for stochastic games with infrequent state changes. Theoret Econ 10:131–173

    Article  MathSciNet  Google Scholar 

  • Phelps E, Pollak R (1968) On second best national savings and game equilibrium growth. Rev Econ Stud 35:195–199

    Article  Google Scholar 

  • Pollak R (1968) Consistent planning. Rev Econ Stud 35:201–208

    Article  Google Scholar 

  • Potters JAM, Raghavan TES, Tijs SH (2009) Pure equilibrium strategies for stochastic games via potential functions. In: Advances in dynamic games and their applications. Annals of the international society of dynamic games, vol 10. Birkhäuser, Boston, pp 433–444

    Google Scholar 

  • Purves RA, Sudderth WD (2011) Perfect information games with upper semicontinuous payoffs. Math Oper Res 36:468–473

    Article  MathSciNet  MATH  Google Scholar 

  • Puterman ML (1994) Markov decision processes: discrete stochastic dynamic programming. Wiley, Hoboken

    Book  MATH  Google Scholar 

  • Raghavan TES, Syed Z (2002) Computing stationary Nash equilibria of undiscounted single-controller stochastic games. Math Oper Res 27:384–400

    Article  MathSciNet  MATH  Google Scholar 

  • Raghavan TES, Tijs SH, Vrieze OJ (1985) On stochastic games with additive reward and transition structure. J Optim Theory Appl 47:451–464

    Article  MathSciNet  MATH  Google Scholar 

  • Ramsey FP (1928) A mathematical theory of savings. Econ J 38:543–559

    Article  Google Scholar 

  • Ray D (1987) Nonpaternalistic intergenerational altruism. J Econ Theory 40:112–132

    Article  MATH  Google Scholar 

  • Reny PJ, Robson A (2002) Existence of subgame-perfect equilibrium with public randomization: a short proof. Econ Bull 3(24):1–8

    Google Scholar 

  • Rieder U (1979) Equilibrium plans for non-zero sum Markov games. In: Moeschlin O, Pallaschke D (eds) Game theory and related topics. North-Holland, Amsterdam, pp 91–102

    Google Scholar 

  • Rogers PD (1969) Non-zero-sum stochastic games. Ph.D. dissertation, report 69–8, Univ of California

    Google Scholar 

  • Rosen JB (1965) Existence and uniqueness of equilibrium points for concave n-person games. Econometrica 33:520–534

    Article  MathSciNet  MATH  Google Scholar 

  • Rosenberg D, Solan E, Vieille N (2001) Stopping games with randomized strategies. Probab Theory Relat Fields 119:433–451

    Article  MathSciNet  MATH  Google Scholar 

  • Rubinstein A (1979) Equilibrium in supergames with the overtaking criterion. J Econ Theory 21:1–9

    Article  MathSciNet  MATH  Google Scholar 

  • Secchi P, Sudderth WD (2002a) Stay-in-a-set games. Int J Game Theory 30:479–490

    Article  MathSciNet  MATH  Google Scholar 

  • Secchi P, Sudderth WD (2002b) N-person stochastic games with upper semi-continuous payoffs. Int J Game Theory 30:491–502

    Article  MathSciNet  MATH  Google Scholar 

  • Secchi P, Sudderth.WD (2005) A simple two-person stochastic game with money. In: Annals of the international society of dynamic games, vol 7. Birkhäuser, Boston, pp 39–66

    Google Scholar 

  • Selten R (1975) Re-examination of the perfectness concept for equilibrium points in extensive games. Int J Game Theory 4:25–55

    Article  MATH  Google Scholar 

  • Shapley LS (1953) Stochastic games. Proc Nat Acad Sci USA 39:1095–1100

    Article  MathSciNet  MATH  Google Scholar 

  • Shubik M, Whitt W (1973) Fiat money in an economy with one non-durable good and no credit: a non-cooperative sequential game. In: Blaquière A (ed) Topics in differential games. North-Holland, Amsterdam, pp 401–448

    Google Scholar 

  • Shmaya E, Solan E (2004) Two player non-zero sum stopping games in discrete time. Ann Probab 32:2733–2764

    Article  MathSciNet  MATH  Google Scholar 

  • Shmaya E, Solan E, Vieille N (2003) An applications of Ramsey theorem to stopping games. Games Econ Behavior 42:300–306

    Article  MathSciNet  MATH  Google Scholar 

  • Simon RS (2007) The structure of non-zero-sum stochastic games. Adv Appl Math 38:1–26

    Article  MathSciNet  MATH  Google Scholar 

  • Simon R (2012) A topological approach to quitting games. Math Oper Res 37:180–195

    Article  MathSciNet  MATH  Google Scholar 

  • Simon RS (2016) The challenge of non-zero-sum stochastic games. Int J Game Theory 45:191–204

    Article  MathSciNet  MATH  Google Scholar 

  • Sleet C, Yeltekin S (2016) On the computation of value correspondences for dynamic games. Dyn Games Appl 6:174–186

    Article  MathSciNet  MATH  Google Scholar 

  • Smale S (1976) A convergent process of price adjustment and global Newton methods. J Math Econ 3:107–120

    Article  MathSciNet  MATH  Google Scholar 

  • Sobel MJ (1871) Non-cooperative stochastic games. Ann Math Stat 42:1930–1935

    Article  MATH  Google Scholar 

  • Solan E (1998) Discounted stochastic games. Math Oper Res 23:1010–1021

    Article  MathSciNet  MATH  Google Scholar 

  • Solan E (1999) Three-person absorbing games. Math Oper Res 24:669–698

    Article  MathSciNet  MATH  Google Scholar 

  • Solan E (2001) Characterization of correlated equilibria in stochastic games. Int J Game Theory 30:259–277

    Article  MathSciNet  MATH  Google Scholar 

  • Solan E (2017, in press) Acceptable strategy profiles in stochastic games. Games Econ Behavior

    Google Scholar 

  • Solan E, Vieille N (2001) Quitting games. Math Oper Res 26:265–285

    Article  MathSciNet  MATH  Google Scholar 

  • Solan E, Vieille N (2002) Correlated equilibrium in stochastic games. Games Econ Behavior 38:362–399

    Article  MathSciNet  MATH  Google Scholar 

  • Solan E, Vieille N (2003) Deterministic multi-player Dynkin games. J Math Econ 39:911–929

    Article  MathSciNet  MATH  Google Scholar 

  • Solan E, Vieille N (2010) Computing uniformly optimal strategies in two-player stochastic games. Econ Theory 42:237–253

    Article  MathSciNet  MATH  Google Scholar 

  • Solan E, Ziliotto B (2016) Stochastic games with signals. In: Annals of the international society of dynamic games, vol 14. Birkhäuser, Boston, pp 77–94

    Google Scholar 

  • Sorin S (1986) Asymptotic properties of a non-zero-sum stochastic games. Int J Game Theory 15:101–107

    Article  MATH  Google Scholar 

  • Spence M (1976) Product selection, fixed costs, and monopolistic competition. Rev Econ Stud 43:217–235

    Article  MATH  Google Scholar 

  • Stachurski J (2009) Economic dynamics: theory and computation. MIT Press, Cambridge, MA

    MATH  Google Scholar 

  • Stokey NL, Lucas RE, Prescott E (1989) Recursive methods in economic dynamics. Harvard University Press, Cambridge

    Google Scholar 

  • Strotz RH (1956) Myopia and inconsistency in dynamic utility maximization. Rev Econ Stud 23:165–180

    Article  Google Scholar 

  • Sundaram RK (1989a) Perfect equilibrium in a class of symmetric dynamic games. J Econ Theory 47:153–177

    Article  MATH  Google Scholar 

  • Sundaram RK (1989b) Perfect equilibrium in a class of symmetric dynamic games. Corrigendum. J Econ Theory 49:385–187

    Article  MATH  Google Scholar 

  • Szajowski K (1994) Markov stopping game with random priority. Z Oper Res 39:69–84

    MathSciNet  MATH  Google Scholar 

  • Szajowski K (1995) Optimal stopping of a discrete Markov process by two decision makers. SIAM J Control Optim 33:1392–1410

    Article  MathSciNet  MATH  Google Scholar 

  • Takahashi M (1964) Equilibrium points of stochastic non-cooperative n-person games. J Sci Hiroshima Univ Ser A-I Math 28:95–99

    MathSciNet  MATH  Google Scholar 

  • Thuijsman F, Raghavan TES (1997) Perfect information stochastic games and related classes. Int J Game Theory 26:403–408

    Article  MathSciNet  MATH  Google Scholar 

  • Topkis D (1978) Minimizing a submodular function on a lattice. Oper Res 26:305–321

    Article  MathSciNet  MATH  Google Scholar 

  • Topkis D (1998) Supermodularity and complementarity. Princeton University Press, Princeton

    Google Scholar 

  • Valadier M (1994) Young measures, weak and strong convergence and the Visintin-Balder theorem. Set-Valued Anal 2:357–367

    Article  MathSciNet  MATH  Google Scholar 

  • Van Long N (2011) Dynamic games in the economics of natural resources: a survey. Dyn Games Appl 1:115–148

    Article  MathSciNet  MATH  Google Scholar 

  • Vieille N (2000a) Two-player stochastic games I: a reduction. Isr J Math 119:55–92

    Article  MathSciNet  MATH  Google Scholar 

  • Vieille N (2000b) Two-player stochastic games II: the case of recursive games. Israel J Math 119:93–126

    Article  MathSciNet  MATH  Google Scholar 

  • Vieille N (2002) Stochastic games: Recent results. In: Aumann RJ, Hart S (eds) Handbook of game theory with economic applications, vol 3. North Holland, Amsterdam/London, pp 1833–1850

    Google Scholar 

  • Vives X (1990) Nash equilibrium with strategic complementarities. J Math Econ 19:305–321

    Article  MathSciNet  MATH  Google Scholar 

  • von Weizsäcker CC (1965) Existence of optimal programs of accumulation for an infinite horizon. Rev Econ Stud 32:85–104

    Article  Google Scholar 

  • Vrieze OJ, Thuijsman F (1989) On equilibria in repeated games with absorbing states. Int J Game Theory 18:293–310

    Article  MathSciNet  MATH  Google Scholar 

  • Whitt W (1980) Representation and approximation of noncooperative sequential games. SIAM J Control Optim 18:33–48

    Article  MathSciNet  MATH  Google Scholar 

  • Wiecek P (2009) Pure equilibria in a simple dynamic model of strategic market game. Math Methods Oper Res 69:59–79

    Article  MathSciNet  MATH  Google Scholar 

  • Wiecek P (2012) N-person dynamic strategic market games. Appl Math Optim 65:147–173

    Article  MathSciNet  MATH  Google Scholar 

  • Yasuda M (1985) On a randomised strategy in Neveu’s stopping problem. Stoch Process Appl 21:159–166

    Article  MATH  Google Scholar 

Download references

Acknowledgements

We thank Tamer Başar and Georges Zaccour for inviting us to write this chapter and their help. We also thank Elżbieta Ferenstein, János Flesch, Eilon Solan, Yeneng Sun, Krzysztof Szajowski and two reviewers for their comments on an earlier version of this survey.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Anna Jaśkiewicz .

Editor information

Editors and Affiliations

Section Editor information

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer International Publishing AG

About this entry

Check for updates. Verify currency and authenticity via CrossMark

Cite this entry

Jaśkiewicz, A., Nowak, A.S. (2018). Non-Zero-Sum Stochastic Games. In: Basar, T., Zaccour, G. (eds) Handbook of Dynamic Game Theory. Springer, Cham. https://doi.org/10.1007/978-3-319-27335-8_33-3

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-27335-8_33-3

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-27335-8

  • Online ISBN: 978-3-319-27335-8

  • eBook Packages: Springer Reference Religion and PhilosophyReference Module Humanities and Social SciencesReference Module Humanities

Publish with us

Policies and ethics

Chapter history

  1. Latest

    Non-Zero-Sum Stochastic Games
    Published:
    14 December 2017

    DOI: https://doi.org/10.1007/978-3-319-27335-8_33-3

  2. Non-Zero-Sum Stochastic Games
    Published:
    28 June 2017

    DOI: https://doi.org/10.1007/978-3-319-27335-8_33-2

  3. Original

    Non-Zero-Sum Stochastic Games
    Published:
    10 November 2016

    DOI: https://doi.org/10.1007/978-3-319-27335-8_33-1