Skip to main content
Register
Springer Professional
SEARCH
MENU 1 2 3 4
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.
previous article Securing Infrastructure Facilities: When Does Proactive Defense Help?
next article Growth and Insecure Private Property of Capital

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.

inform now

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.

inform now

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.

inform now
Literature
1.
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 MathSciNetCrossRef
3.
Frederiksen S (2015) Semi-algebraic tools for stochastic games. Ph.D. thesis, Aarhus Universitet, Aarhus, Denmark
4.
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
7.
Jaśkiewicz A, Nowak AS (2018) Zero-sum stochastic games. Springer, Berlin, pp 215–280
8.
9.
Loustaunau P, Adams WW (1994) An introduction to Gröbner bases. American Mathematical Society, Providence MATH
10.
MacLane S, Birkhoff G (1967) Algebra. The Macmillan Company, New York MATH
11.
12.
13.
14.
Neyman A (2003) Real algebraic tools in stochastic games. Springer, Dordrecht, pp 57–75 MATH
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 MathSciNetCrossRef
16.
Parthasarathy T, Tijs SH, Vrieze OJ (1984) Stochastic games with state independent transitions and separable rewards. Springer, Berlin, pp 262–271 MATH
17.
18.
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.
Rotman J (1998) Galois theory. Universitext. Springer, New York (Berlin. Print) CrossRef
20.
21.
Shapley LS, Snow RN (1952) Basic solutions of discrete games. Princeton University Press, Princeton, pp 27–36
22.
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 MathSciNetCrossRef
24.
Tarski A (1951) A decision method for elementary algebra and geometry. University of California Press, Berkeley MATH
25.
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

OriginalPaper

Supervisory Control of Discrete-Event Systems Under Attacks

OriginalPaper

Generalized Cops and Robbers: A Multi-player Pursuit Game on Graphs

OriginalPaper

Optimal Evading Strategies and Task Allocation in Multi-player Pursuit–Evasion Problems

OriginalPaper

Evolutionary Stability of Polymorphic Profiles in Asymmetric Games

OriginalPaper

An Efficient Dynamic Allocation Mechanism for Security in Networks of Interdependent Strategic Agents

OriginalPaper

Risk-Sensitive Mean Field Games via the Stochastic Maximum Principle

Premium Partner

Neuer Inhalt
    Image Credits

    Version: 0.1964.0