article

The Asymptotic Theory of Stochastic Games

Authors:

Elon KohlbergAuthors Info & Claims

Mathematics of Operations Research, Volume 1, Issue 3

Pages 197 - 208

https://doi.org/10.1287/moor.1.3.197

Published: 01 August 1976 Publication History

Abstract

We study two person, zero sum stochastic games. We prove that lim_n→∞{V_n/n} = lim_r→0rVr, where V_n is the value of the n-stage game and Vr is the value of the infinite-stage game with payoffs discounted at interest rate r > 0. We also show that Vr may be expanded as a Laurent series in a fractional power of r. This expansion is valid for small positive r. A similar expansion exists for optimal strategies. Our main proof is an application of Tarski's principle for real closed fields.

References

[1]

Ahlfors. Lars (1966). Complex Analysis. Second edition McGraw-Hill, New York.

[2]

Bewley, Truman and Kohlherg, Elon. The Asymptotic Solution of a Recursion Equation Arising in Stochastic Games. To appear in this Journal.

[3]

Bewley, Truman, Stochastic Games with Stationary Optimal Strategies.

[4]

Blackwell, D. (1962). Discrete Dynamic Programming. Ann. Math. Stat. 33 719-726.

[5]

Cartan, Henri (1963). Elementary Theory of Analytic Functions of One or Several Complex Variables. Addison-Wesley, Reading, Massachusetts.

[6]

Gillette, D. (1957). Stochastic Games with Zero Stop Probabilities. Contributions to the Theory of Games. III. Annals of Mathematics Studies, No. 39. Princeton University Press, Princeton. 179-187.

[7]

Hoffman, A. J. and Karp, R. M. (1966). On Nonterminating Stochastic Games. Management Sci. 12 359-370.

Digital Library

[8]

Jacobson, Nathan (1964). Lectures in Abstract Algebra. III. D. van Nostrand, Princeton.

[9]

Karlin, S. (1959). Mathematical Methods and Theory in Games, Programming, and Economics. 1. Addison-Wesley, Reading, Massachusetts.

[10]

Seidenberg, A. (1954). A New Decision Method for Elementary Algebra. Ann. of Math. 60 365-374.

[11]

Shapley, L. (1953). Stochastic Games. Proc. Nat. Acad. Sci. U.S.A. 39 1095-1100.

[12]

Siegel, C. (1969). Topics in Complex Function Theory. I. Wiley, New York.

[13]

Stern. Martin A. (1975). On Stochastic Games with Limiting Average Payoff. Doctoral Dissertation in Mathematics, University of Illinois.

[14]

Tarski. Alfred (1951). A Decision Method for Elementary Algebra and Geometry. Second edition, revised. University of California Press. Berkeley and Los Angeles.

[15]

Weyl, H. (1950). Elementary Proof of a Minimax Theorem Due to von Neumann. Contributions to the Theory of Games. I. Annals of Mathematics Studies, No. 24. Princeton University Press. Princeton. 19-25.

Cited By

Attia LOliu-Barton MSaona R(2025)Marginal Values of a Stochastic GameMathematics of Operations Research10.1287/moor.2023.029750:1(482-505)Online publication date: 1-Feb-2025
https://dl.acm.org/doi/10.1287/moor.2023.0297
Ragel T(2024)Weak Approachability of Convex Sets in Absorbing GamesMathematics of Operations Research10.1287/moor.2021.016049:3(1372-1402)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1287/moor.2021.0160
Dohmen TTrivedi AAgmon NAn BRicci AYeoh W(2023)Reinforcement Learning with Depreciating AssetsProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3599024(2628-2630)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3599024
Show More Cited By

The Asymptotic Theory of Stochastic Games
1. Mathematics of computing
  1. Mathematical analysis

Recommendations

The Asymptotic Solution of a Recursion Equation Occurring in Stochastic Games

We show that there exists a Laurent series in a fractional power of n which approximates V_n up to log n, where V_n is the value of an n-stage two person zero sum stochastic game. We prove this result by showing that the Laurent series is an approximate ...
The complexity of stochastic Müller games

The theory of graph games with @w-regular winning conditions is the foundation for modeling and synthesizing reactive processes. In the case of stochastic reactive processes, the corresponding stochastic graph games have three players, two of them (...
On Stochastic Games with Stationary Optimal Strategies

We study two-person zero-sum stochastic games in which the state and action spaces are finite. We give both necessary and sufficient conditions for the players to have stationary optimal strategies in the infinite-stage game.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematics of Operations Research

Mathematics of Operations Research Volume 1, Issue 3

August 1976

111 pages

ISSN:0364-765X

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 August 1976

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

50
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Attia LOliu-Barton MSaona R(2025)Marginal Values of a Stochastic GameMathematics of Operations Research10.1287/moor.2023.029750:1(482-505)Online publication date: 1-Feb-2025
https://dl.acm.org/doi/10.1287/moor.2023.0297
Ragel T(2024)Weak Approachability of Convex Sets in Absorbing GamesMathematics of Operations Research10.1287/moor.2021.016049:3(1372-1402)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1287/moor.2021.0160
Dohmen TTrivedi AAgmon NAn BRicci AYeoh W(2023)Reinforcement Learning with Depreciating AssetsProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3599024(2628-2630)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3599024
Garnier GZiliotto B(2023)Percolation GamesMathematics of Operations Research10.1287/moor.2022.133448:4(2156-2166)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1287/moor.2022.1334
Savas YAhmadi MTanaka TTopcu U(2022)Entropy-Regularized Stochastic Games2019 IEEE 58th Conference on Decision and Control (CDC)10.1109/CDC40024.2019.9029555(5955-5962)Online publication date: 28-Dec-2022
https://dl.acm.org/doi/10.1109/CDC40024.2019.9029555
Laraki R(2022)Explicit formulas for repeated games with absorbing statesInternational Journal of Game Theory10.1007/s00182-009-0193-239:1-2(53-69)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1007/s00182-009-0193-2
Attia LOliu-Barton M(2021)Shapley–Snow Kernels, Multiparameter Eigenvalue Problems, and Stochastic GamesMathematics of Operations Research10.1287/moor.2020.110446:3(1181-1202)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1287/moor.2020.1104
Oliu-Barton M(2021)New Algorithms for Solving Zero-Sum Stochastic GamesMathematics of Operations Research10.1287/moor.2020.105546:1(255-267)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1287/moor.2020.1055
Laraki RRenault J(2020)Acyclic Gambling GamesMathematics of Operations Research10.1287/moor.2019.103045:4(1237-1257)Online publication date: 1-Nov-2020
https://dl.acm.org/doi/10.1287/moor.2019.1030
Renault JZiliotto B(2020)Limit Equilibrium Payoffs in Stochastic GamesMathematics of Operations Research10.1287/moor.2019.101545:3(889-895)Online publication date: 1-Aug-2020
https://dl.acm.org/doi/10.1287/moor.2019.1015
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents