Skip to main content
SpringerLink
Log in

Zero-Sum Stochastic Games over the Field of Real Algebraic Numbers

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

Abstract

We consider a finite state, finite action, zero-sum stochastic games with data defining the game lying in the ordered field of real algebraic numbers. In both the discounted and the limiting average versions of these games, we prove that the value vector also lies in the same field of real algebraic numbers. Our method supplies finite construction of univariate polynomials whose roots contain these value vectors. In the case where the data of the game are rational, the method also provides a way of checking whether the entries of the value vectors are also rational.

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

Access this article

Log in via an institution

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.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Bewley T, Kohlberg E (1976) The asymptotic theory of stochastic games. Math Oper Res 1:197–208

    Article  MathSciNet  Google Scholar 

  2. Filar JA (1981) Ordered field property for stochastic games when the player who controls transitions changes from state to state. J Optim Theory Appl 34:503–515

    Article  MathSciNet  Google Scholar 

  3. Frederiksen S (2015) Semi-algebraic tools for stochastic games. Ph.D. thesis, Aarhus Universitet, Aarhus, Denmark

  4. Gillette D (1957) Stochastic games with zero stop probabilities. Contrib Theory Games 3:179–187

    MathSciNet  MATH  Google Scholar 

  5. Hansen K, Koucky M, Lauritzen N, Miltersen P, Tsigaridas E (2011) Exact algorithms for solving stochastic games: extended abstract. In: STOC 11 proceedings of the forty-third annual ACM symposium on theory of computing, pp 205–214

  6. Jaśkiewicz A, Nowak AS (2018) Nonzero-sum stochastic games. Springer, Berlin, pp 281–344

    Google Scholar 

  7. Jaśkiewicz A, Nowak AS (2018) Zero-sum stochastic games. Springer, Berlin, pp 215–280

    Google Scholar 

  8. Kaplansky I (1945) A contribution to von Neumann’s theory of games. Ann Math 46:474–479

    Article  MathSciNet  Google Scholar 

  9. Loustaunau P, Adams WW (1994) An introduction to Gröbner bases. American Mathematical Society, Providence

    MATH  Google Scholar 

  10. MacLane S, Birkhoff G (1967) Algebra. The Macmillan Company, New York

    MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  12. Mertens JF, Zamir S (1981) Incomplete information games with transcendental values. Math Oper Res 6:313–318

    Article  MathSciNet  Google Scholar 

  13. Milman E (2002) The semi-algebraic theory of stochastic games. Math Oper Res 27:401–418

    Article  MathSciNet  Google Scholar 

  14. Neyman A (2003) Real algebraic tools in stochastic games. Springer, Dordrecht, pp 57–75

    MATH  Google Scholar 

  15. Parthasarathy T, Raghavan TES (1981) An orderfield property for stochastic games when one player controls transition probabilities. J Optim Theory Appl 33:375–392

    Article  MathSciNet  Google Scholar 

  16. Parthasarathy T, Tijs SH, Vrieze OJ (1984) Stochastic games with state independent transitions and separable rewards. Springer, Berlin, pp 262–271

    MATH  Google Scholar 

  17. Raghavan TES, Filar JA (1991) Algorithms for stochastic games: a survey. Z Oper Res 35:437–472

    MathSciNet  MATH  Google Scholar 

  18. 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  Google Scholar 

  19. Rotman J (1998) Galois theory. Universitext. Springer, New York (Berlin. Print)

    Book  Google Scholar 

  20. Shapley LS (1953) Stochastic games. Proc Natl Acad Sci 39:1095–1100

    Article  MathSciNet  Google Scholar 

  21. Shapley LS, Snow RN (1952) Basic solutions of discrete games. Princeton University Press, Princeton, pp 27–36

    Google Scholar 

  22. Sobel MJ (1981) Myopic solutions of markov decision processes and stochastic games. Oper Res 29:995–1009

    Article  MathSciNet  Google Scholar 

  23. Szczechla WW, Connell SA, Filar JA, Vrieze OJ (1997) On the Puiseux series expansion of the limit discount equation of stochastic games. SIAM J Control Optim 35:860–875

    Article  MathSciNet  Google Scholar 

  24. Tarski A (1951) A decision method for elementary algebra and geometry. University of California Press, Berkeley

    MATH  Google Scholar 

  25. von Neumann J (1928) Zur theorie der gesellschaftsspiele. Math Ann 100:295–320

    Article  MathSciNet  Google Scholar 

  26. Weyl H (1952) Elementary proof of a minimax theorem due to Von Neumann. Princeton University Press, Princeton, pp 19–26

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Inria Sophia Antipolis, Biot, France

    K. Avrachenkov

  2. College of Science and Engineering, Flinders University of South Australia, Bedford Park, SA, 5042, Australia

    V. Ejov

  3. Faculty of Mechanics and Mathematics, MSU, GSP-1, 1 Leninskiye Gory, Moscow, Russia, 119991

    V. Ejov

  4. Centre for Applications in Natural Resource Mathematics, School of Mathematics and Physics, The University of Queensland, St Lucia, QLD, 4072, Australia

    J. A. Filar & A. Moghaddam

Authors
  1. K. Avrachenkov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. V. Ejov
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. J. A. Filar
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. A. Moghaddam
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to J. A. Filar.

Additional information

Publisher's Note

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

This research was supported by the Australian Research Council Discovery Grant DP150100618. The third author wishes to thank T.E.S. Raghavan for introducing him to this problem in the late 1970s. We are indebted to two anonymous referees, the associate editor and the editor-in-chief, for their helpful critique that helped us streamline the presentation.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Avrachenkov, K., Ejov, V., Filar, J.A. et al. Zero-Sum Stochastic Games over the Field of Real Algebraic Numbers. Dyn Games Appl 9, 1026–1041 (2019). https://doi.org/10.1007/s13235-018-00293-w

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13235-018-00293-w

Keywords

Mathematics Subject Classification

Search

Navigation