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

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

Research output: Contribution to journalArticlepeer-review

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.
Original languageEnglish
Pages (from-to)1026-1041
Number of pages16
JournalDynamic Games and Applications
Volume9
Issue number4
DOIs
Publication statusPublished - 1 Dec 2019

Keywords

  • finite state
  • finite action
  • zero-sum
  • stochastic games
  • real algebraic numbers
  • univariate polynomials
  • vectors
  • rational
  • Ordered field property
  • Gröbner basis polynomial equations
  • Algebraic numbers
  • Algebraic variety
  • Stochastic games

Fingerprint

Dive into the research topics of 'Zero-Sum Stochastic Games over the Field of Real Algebraic Numbers'. Together they form a unique fingerprint.

Cite this