Nothing Special   »   [go: up one dir, main page]

Skip to main content
Log in

Stationary Equilibria in Discounted Stochastic Games

  • Published:
Dynamic Games and Applications Aims and scope Submit manuscript

Abstract

We provide a new characterisation of the set of stationary equilibria for finite discounted N-player stochastic games, based on the definition of an auxiliary one-shot game with the same set of equilibria. This result is the extension, to the N-player case, of a similar characterisation for two-player zero-sum stochastic games (Attia and Oliu-Barton in Proc Natl Acad Sci USA 116:26435–26443, 2019) which led to a tractable formula for the limit value. Though the general case presents additional challenges, our characterisation may have further applications, notably in terms of the description and computation of stationary equilibria and of their limit as the discount rates vanish.

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

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Atkinson F (1972) Multiparameter Eigenvalue problems, vol I. Academic Press, New York

    Google Scholar 

  2. Attia L, Oliu-Barton M (2019) A formula for the value of a stochastic game. Proc Natl Acad Sci USA 116(52):26435–26443. https://doi.org/10.1073/pnas.190864311

    Article  MathSciNet  Google Scholar 

  3. Attia L, Oliu-Barton M (2021) Shapley-Snow kernels, multiparameter eigenvalue problems and stochastic games. Math Oper Res. https://doi.org/10.1287/moor.2020.1104

    Article  MathSciNet  Google Scholar 

  4. Breton M (1991) Algorithms for stochastic game. In: Shapley LS (ed) in Stochastic Games and Related Topics. Theory and Decision Library C: Game Theory, Mathematical Programming and Operations Research, vol 7. Kluwer Academic Publishers, Dordrecht, pp 45–57

  5. Breton M, Filar JA, Haurle A et al (1986) On the computation of equilibria in discounted stochastic dynamic games. Springer, Berlin

    Google Scholar 

  6. Dickhaut J, Kaplan T (1993) A program for finding Nash Equilibria. In: Economic and financial modeling with mathematica, Springer, New York, NY, pp 148–166. https://doi.org/10.1007/978-1-4757-2281-9_7

  7. Filar J, Vrieze K (2012) Competitive Markov decision processes. Springer Science & Business Media, Berlin

    Google Scholar 

  8. Filar JA, Schultz TA, Thuijsman F et al (1991) Nonlinear programming and stationary equilibria in stochastic games. Math Program 50:227–237. https://doi.org/10.1007/BF01594936

    Article  MathSciNet  Google Scholar 

  9. Fink AM (1964) Equilibrium in a stochastic \(n\)-person game. J Sci Hiroshima Univ Ser AI 28(1):89–93. https://doi.org/10.32917/hmj/1206139508

    Article  MathSciNet  Google Scholar 

  10. Herings P, Peeters R (2004) Stationary equilibria in stochastic games: structure, selection, and computation. J Econ Theory 118:32–60. https://doi.org/10.1016/j.jet.2003.10.001

    Article  MathSciNet  Google Scholar 

  11. Mohan S, Neogy S, Parthasarathy T (1997) Linear complementarity and discounted polystochastic game when one player controls transitions. In: Ferris MC , Pang JS (eds) Complementarity and variational problems. SIAM, Philadelphia, pp. 284–294

  12. Mohan S, Neogy S, Parthasarathy T (2001) Pivoting algorithms for some classes of stochastic games: a survey. Int Game Theory Rev 3:253–281. https://doi.org/10.1142/S0219198901000385

    Article  MathSciNet  Google Scholar 

  13. Nowak A, Raghavan T (1993) A finite step algorithm via a bimatrix game to a single controller non-zero sum stochastic game. Math Program 59(1):249–259. https://doi.org/10.1007/BF01581246

    Article  MathSciNet  Google Scholar 

  14. Oliu-Barton M (2020) New algorithms for solving zero-sum stochastic games. Math Oper Res. https://doi.org/10.1287/moor.2020.1055

    Article  MathSciNet  Google Scholar 

  15. Ostrowski A (1937) Sur la détermination des bornes inférieures pour une classe des determinants. Bull Sci Math 61:19–32. https://doi.org/10.1007/978-3-0348-9355-8_1

    Article  Google Scholar 

  16. Parthasarathy T, Raghavan T (1981) An orderfield property for stochastic games when one player controls transition probabilities. J Optim Theory Appl 33(3):375–392. https://doi.org/10.1007/BF00935250

    Article  MathSciNet  Google Scholar 

  17. Porter R, Nudelman E, Shoham Y (2008) Simple search methods for finding a nash equilibrium. Games Econ Behav 63(2):642–662

    Article  MathSciNet  Google Scholar 

  18. Raghavan T, Tijs S, Vrieze O (1985) On stochastic games with additive reward and transition structure. J Optim Theory Appl 47:451–464. https://doi.org/10.1007/BF00942191

    Article  MathSciNet  Google Scholar 

  19. Schultz TA (1986) Mathematical programming and stochastic games. PHD thesis, The John Hopkins University, Baltimore

  20. Shapley LS (1953) Stochastic games. Proc Natl Acad Sci USA 39:1095–1100. https://doi.org/10.1073/pnas.39.10.1095

    Article  MathSciNet  Google Scholar 

  21. Solan E, Vieille N (2015) Stochastic games. Proc Natl Acad Sci USA 112(45):13743–13746. https://doi.org/10.1073/pnas.1513508112

    Article  MathSciNet  Google Scholar 

  22. Sorin S (1986) Asymptotic properties of a non-zero sum stochastic game. Int J Game Theory 15(2):101–107. https://doi.org/10.1007/BF01770978

    Article  MathSciNet  Google Scholar 

  23. Takahashi M (1964) Equilibrium points of stochastic non-cooperative \(n\)-person games. J Sci Hiroshima Univ Ser A-I Math 28(1):95–99. https://doi.org/10.32917/hmj/1206139509

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The authors are indebted to Bruno Ziliotto, Bernhard Von Stengel, and to the anonymous referees for their insightful remarks on earlier versions of this draft.

Funding

This work is supported by a grant from the “Fondation CFM pour la Recherche.” The second author acknowledges the support of the French Agence Nationale de la Recherche (ANR) under reference ANR-21-CE40-0020 (CONVERGENCE project).

Author information

Authors and Affiliations

Authors

Contributions

The authors contributed equally to this work.

Corresponding author

Correspondence to Luc Attia.

Ethics declarations

Conflict of interest

The authors declare no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Attia, L., Oliu-Barton, M. Stationary Equilibria in Discounted Stochastic Games. Dyn Games Appl 14, 271–284 (2024). https://doi.org/10.1007/s13235-023-00495-x

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13235-023-00495-x

Keywords

Navigation