Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

Published in: Dynamic Games and Applications 4/2019

25-01-2019

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

Authors: K. Avrachenkov, V. Ejov, J. A. Filar, A. Moghaddam

Published in: Dynamic Games and Applications | Issue 4/2019

Login to get access
share
SHARE

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.

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 15 Tage kostenlos.

Literature
2.
go back to reference 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 MathSciNetCrossRef 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 MathSciNetCrossRef
3.
go back to reference Frederiksen S (2015) Semi-algebraic tools for stochastic games. Ph.D. thesis, Aarhus Universitet, Aarhus, Denmark Frederiksen S (2015) Semi-algebraic tools for stochastic games. Ph.D. thesis, Aarhus Universitet, Aarhus, Denmark
4.
5.
go back to reference 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 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.
go back to reference Jaśkiewicz A, Nowak AS (2018) Nonzero-sum stochastic games. Springer, Berlin, pp 281–344 Jaśkiewicz A, Nowak AS (2018) Nonzero-sum stochastic games. Springer, Berlin, pp 281–344
7.
go back to reference Jaśkiewicz A, Nowak AS (2018) Zero-sum stochastic games. Springer, Berlin, pp 215–280 Jaśkiewicz A, Nowak AS (2018) Zero-sum stochastic games. Springer, Berlin, pp 215–280
9.
go back to reference Loustaunau P, Adams WW (1994) An introduction to Gröbner bases. American Mathematical Society, Providence MATH Loustaunau P, Adams WW (1994) An introduction to Gröbner bases. American Mathematical Society, Providence MATH
10.
go back to reference MacLane S, Birkhoff G (1967) Algebra. The Macmillan Company, New York MATH MacLane S, Birkhoff G (1967) Algebra. The Macmillan Company, New York MATH
12.
14.
go back to reference Neyman A (2003) Real algebraic tools in stochastic games. Springer, Dordrecht, pp 57–75 MATH Neyman A (2003) Real algebraic tools in stochastic games. Springer, Dordrecht, pp 57–75 MATH
15.
go back to reference Parthasarathy T, Raghavan TES (1981) An orderfield property for stochastic games when one player controls transition probabilities. J Optim Theory Appl 33:375–392 MathSciNetCrossRef Parthasarathy T, Raghavan TES (1981) An orderfield property for stochastic games when one player controls transition probabilities. J Optim Theory Appl 33:375–392 MathSciNetCrossRef
16.
go back to reference Parthasarathy T, Tijs SH, Vrieze OJ (1984) Stochastic games with state independent transitions and separable rewards. Springer, Berlin, pp 262–271 MATH Parthasarathy T, Tijs SH, Vrieze OJ (1984) Stochastic games with state independent transitions and separable rewards. Springer, Berlin, pp 262–271 MATH
17.
18.
go back to reference Raghavan TES, Tijs SH, Vrieze OJ (1985) On stochastic games with additive reward and transition structure. J Optim Theory Appl 47:451–464 MathSciNetCrossRef Raghavan TES, Tijs SH, Vrieze OJ (1985) On stochastic games with additive reward and transition structure. J Optim Theory Appl 47:451–464 MathSciNetCrossRef
19.
go back to reference Rotman J (1998) Galois theory. Universitext. Springer, New York (Berlin. Print) CrossRef Rotman J (1998) Galois theory. Universitext. Springer, New York (Berlin. Print) CrossRef
21.
go back to reference Shapley LS, Snow RN (1952) Basic solutions of discrete games. Princeton University Press, Princeton, pp 27–36 Shapley LS, Snow RN (1952) Basic solutions of discrete games. Princeton University Press, Princeton, pp 27–36
22.
23.
go back to reference 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 MathSciNetCrossRef 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 MathSciNetCrossRef
24.
go back to reference Tarski A (1951) A decision method for elementary algebra and geometry. University of California Press, Berkeley MATH Tarski A (1951) A decision method for elementary algebra and geometry. University of California Press, Berkeley MATH
26.
go back to reference Weyl H (1952) Elementary proof of a minimax theorem due to Von Neumann. Princeton University Press, Princeton, pp 19–26 Weyl H (1952) Elementary proof of a minimax theorem due to Von Neumann. Princeton University Press, Princeton, pp 19–26
Metadata
Title
Zero-Sum Stochastic Games over the Field of Real Algebraic Numbers
Authors
K. Avrachenkov
V. Ejov
J. A. Filar
A. Moghaddam
Publication date
25-01-2019
Publisher
Springer US
Published in
Dynamic Games and Applications / Issue 4/2019
Print ISSN: 2153-0785
Electronic ISSN: 2153-0793
DOI
https://doi.org/10.1007/s13235-018-00293-w

Other articles of this Issue 4/2019

Dynamic Games and Applications 4/2019 Go to the issue

Premium Partner