Skip to main content
Log in

Two-player stochastic games I: A reduction

  • Published:
Israel Journal of Mathematics Aims and scope Submit manuscript

Abstract

This paper is the first step in the proof of existence of equilibrium payoffs for two-player stochastic games with finite state and action sets. It reduces the existence problem to the class of so-called positive absorbing recursive games. The existence problem for this class is solved in a subsequent paper.

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

Access this article

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

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. R. J. Aumann and M. B. Maschler with the collaboration of R. E. Stearns,Repeated Games with Incomplete Information, MIT Press, Cambridge, 1995.

    MATH  Google Scholar 

  2. T. Bewley and E. Kohlberg,The asymptotic solution of a recursion equation occurring in stochastic games, Mathematics of Operations Research1 (1976), 321–336.

    MATH  MathSciNet  Google Scholar 

  3. T. Bewley and E. Kohlberg,The asymptotic theory of stochastic games, Mathematics of Operations Research1 (1976), 197–208.

    Article  MATH  MathSciNet  Google Scholar 

  4. T. Bewley and E. Kohlberg,On stochastic games with stationary optimal strategies, Mathematics of Operations Research3 (1978), 104–125.

    MATH  MathSciNet  Google Scholar 

  5. D. Blackwell,Discounted dynamic programming, Annals of Mathematical Statistics336 (1965), 226–235.

    Article  MathSciNet  Google Scholar 

  6. D. Blackwell and T. S. Ferguson,The big match, Annals of Mathematical Statistics39 (1968), 159–163.

    Article  MathSciNet  MATH  Google Scholar 

  7. H. Everett,Recursive games, inContributions to the Theory of Games, Vol. III (M. Dresher, A. W. Tucker and P. Wolfe, eds.), Princeton University Press, Princeton, N.J., 1957, pp. 47–78.

    Google Scholar 

  8. A. M. Fink,Equilibrium in a stochastic n-person game, Journal of Science of Hiroshima University28 (1964), 89–93.

    MATH  MathSciNet  Google Scholar 

  9. D. Gillette,Stochastic games with zero-stop probabilities, inContributions to the Theory of Games, Vol. III (M. Dresher, A. W. Tucker and P. Wolfe, eds.), Princeton University Press, Princeton, N.J., 1957, pp. 179–187.

    Google Scholar 

  10. E. Kohlberg,Repeated games with absorbing states, The Annals of Statistics2 (1974), 724–738.

    Article  MATH  MathSciNet  Google Scholar 

  11. J. F. Mertens and A. Neyman,Stochastic games, International Journal of Game Theory10 (1981), 53–56.

    Article  MATH  MathSciNet  Google Scholar 

  12. J. F. Mertens and A. Neyman,Stochastic games have a value, Proceedings of the National Academy of Sciences of the United States of America79 (1982), 2145–2146.

    Article  MATH  MathSciNet  Google Scholar 

  13. J. F. Mertens and T. P. Parthasarathy,Non zero-sum stochastic games, inStochastic Games and Related Topics (T. E. S. Raghavan et al., eds.), Kluwer Academic Publishers, Dordrecht, 1991, pp. 145–148.

    Google Scholar 

  14. J. F. Mertens, S. Sorin and S. Zamir,Repeated games part b the central results, CORE Discussion Paper 9421, 1994.

  15. J. Milnor and L. S. Shapley,Ruin games, inContributions to the Theory of Games, Vol. III (M. Dresher, A. W. Tucker and P. Wolfe, eds.), Princeton University Press, Princeton, N.J., 1957, pp. 15–45.

    Google Scholar 

  16. T. E. S. Raghavan, S. H. Tijs and O. J. Vrieze,On stochastic games with additive reward and transition structure, Journal of Optimization Theory and Applications47 (1985), 451–464.

    Article  MATH  MathSciNet  Google Scholar 

  17. L. S. Shapley,Stochastic games, Proceedings of the National Academy of Sciences of the United States of America39 (1953), 1095–1100.

    Article  MATH  MathSciNet  Google Scholar 

  18. E. Solan,Three-player absorbing games, Mathematics of Operations Research24 (1999), 669–698.

    MATH  MathSciNet  Google Scholar 

  19. S. Sorin,Asymptotic properties of a non-zero sum stochastic game, International Journal of Game Theory11 (1986), 147–160.

    MATH  MathSciNet  Google Scholar 

  20. F. Thuijsman and T. E. S. Raghavan,Perfect information stochastic games and related classes, International Journal of Game Theory26 (1997), 403–408.

    MATH  MathSciNet  Google Scholar 

  21. N. Vieille,Contributions à la Théorie Des Jeux Répétés, PhD thesis, Université Paris 6—Pierre et Marie Curie, 1992.

    Google Scholar 

  22. N. Vieille,On equilibria in undiscounted stochastic games, Technical Report 9446, CEREMADE, 1994.

  23. N. Vieille,Two-player stochastic games II: The case of recursive games, Israel Journal of Mathematics, this volume, pp. 93–126.

  24. O. J. Vrieze and F. Thuijsman,On equilibria in stochastic games with absorbing states, International Journal of Game Theory18 (1989), 293–310.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Vieille, N. Two-player stochastic games I: A reduction. Isr. J. Math. 119, 55–91 (2000). https://doi.org/10.1007/BF02810663

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02810663

Keywords

Navigation