Values of Absorbing Recursive Games Express All Real Algebraic Numbers

Abstract

Many classes of two-player zero-sum stochastic games have the orderfield property: if all payoffs and transition probabilities lie in a subfield of $\mathbb{R}$, so does the undiscounted value. Absorbing games fail this property, and Oliu-Barton and Vigeral [Absorbing games with irrational values, Oper. Res. Lett. 51 (2023) 555--559] conjectured the precise extent of the failure: every real algebraic number $\alpha$ of degree $m\ge 1$ over $\mathbb{Q}$ is the undiscounted value of a rational $m\times m$ absorbing game. We prove this conjecture, and in fact within a special subclass of absorbing games: for every such $\alpha$, the game realizing it is strictly absorbing and recursive, i.e., every action pair is absorbing with positive probability and all non-absorbing stage payoffs are zero; when $\alpha >0$ it can moreover be taken positive recursive, with positive absorbing payoffs. As a corollary, the set of undiscounted values of rational $m\times m$ absorbing games is exactly the set of real algebraic numbers of degree at most $m$.