Top

Dynamic Games and Applications

Published in:

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

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

über 102.000 Bücher
über 537 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

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

inform now

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

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–515MathSciNetCrossRef

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

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

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

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

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

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

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

10.

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

11.

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

12.

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

13.

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

14.

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

15.

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

16.

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

17.

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

18.

Raghavan TES, Tijs SH, Vrieze OJ (1985) On stochastic games with additive reward and transition structure. J Optim Theory Appl 47:451–464MathSciNetCrossRef

19.

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

20.

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

21.

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

22.

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

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–875MathSciNetCrossRef

24.

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

25.

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

26.

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

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

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 4/2019

Securing Infrastructure Facilities: When Does Proactive Defense Help?

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

Iterative Computation of Security Strategies of Matrix Games with Growing Action Set

Dynamic Games in Cyber-Physical Security: An Overview

Climb on the Bandwagon: Consensus and Periodicity in a Lifetime Utility Model with Strategic Interactions

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

Premium Partner