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 ℝ, 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 α of degree m≥ 1 over ℚ is the undiscounted value of a rational m× m absorbing game. We prove this conjecture, and in fact within a special subclass of absorbing games: for every such α, 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 α>0 it can moreover be taken positive recursive, with positive absorbing payoffs. As a corollary, the set of undiscounted values of rational m× m absorbing games is exactly the set of real algebraic numbers of degree at most m.
Related
- Infinite-Horizon Stochastic Recursive Differential Games with Jumps: Nonautonomous Coefficients and Nonzero Terminal Values
- A Twelve-Row Seed and a One-Row Extension for Five-Column Recursive-Line Zarankiewicz Numbers
- Recursive-Line Zarankiewicz Numbers with Four Columns
- Overtake and the recursive-line equality for second-order Zarankiewicz numbers
- Multiplicative Dependence of Shifted Quadratic and Cubic Algebraic Numbers
BibTeX
@misc{asadi2026values,
title = {{Values of Absorbing Recursive Games Express All Real Algebraic Numbers}},
author = {Ali Asadi and Krishnendu Chatterjee},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11583},
eprint = {2609.11583},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11583},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Values of Absorbing Recursive Games Express All Real Algebraic Numbers
AU - Ali Asadi
AU - Krishnendu Chatterjee
PY - 2026
DA - 2026/09/11
PB - arXiv
DO - 10.48550/arxiv.2609.11583
UR - https://arxiv.org/abs/2609.11583
AB - Many classes of two-player zero-sum stochastic games have the orderfield property: if all payoffs and transition probabilities lie in a subfield of ℝ, 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 α of degree m≥ 1 over ℚ is the undiscounted value of a rational m× m absorbing game. We prove this conjecture, and in fact within a special subclass of absorbing games: for every such α, 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 α>0 it can moreover be taken positive recursive, with positive absorbing payoffs. As a corollary, the set of undiscounted values of rational m× m absorbing games is exactly the set of real algebraic numbers of degree at most m.
ER -