PaperfootJoin free
arXiv

Algorithm solves simple stochastic games in quasipolynomial time

The mathematical method calculates approximate fixed points for nonexpanding mappings and shows that simple stochastic games can be solved in quasipolynomial time.

Paper by Ashkan Soleymani, Gabriele Farina
A light blue maze surrounds tightly nested squares and a black dot, with a black path, scattered dark blue-green fragments, and loose gray squares.
Preprint: method

Edited by Boris Djordjevic · Paperfoot

Paper

In a preprint, researchers introduced an algorithm to calculate an approximate fixed point of any nonexpanding mapping across multiple dimensions under the infinity norm. A nonexpanding function never moves points farther apart, and the infinity norm measures distance by the single largest difference among coordinates. The algorithm finds an approximate fixed point—a location barely shifted by the function—in time scaling as log(1/eps)^(O(log^2 d)), where d is the dimension count and eps is the approximation error. At its core, the technique uses a boosting argument to geometrically shrink a search region. Among other consequences, the authors showed that simple stochastic games, a standard model of games involving chance, can be solved in quasipolynomial time.

Why it matters

The result establishes that simple stochastic games can be solved in quasipolynomial time through a formal proof. It also provides a new geometric boosting framework for calculating fixed points in nonexpanding systems.

Caveats

The paper is a theoretical preprint that establishes mathematical bounds without implementing the algorithm or measuring its runtime on hardware. In addition, quasipolynomial time is not polynomial time, which remains the benchmark for truly efficient algorithms.

In this paper

computing an eps-approximate fixed point of l_(infinity) nonexpansions

Methods
Solve (this paper)Label (this paper)ThinLabel (this paper)Amplify (this paper)AdaBoost

What it shows

An algorithm computes an eps-approximate fixed point of any d-dimensional l_(infinity)-nonexpansion in time log(1/eps)^(O(log^2 d)).

We give an algorithm for computing an eps-approximate fixed point of any d-dimensional nonexpansion with respect to the l_(∞) norm in time log(1/eps)^(O(log^2 d)).

Abstract

Simple stochastic games can be solved in quasipolynomial time as a consequence of the algorithm.

Among other consequences, our algorithm implies that simple stochastic games can be solved in quasipolynomial time.

Abstract

For any possibly degenerate box and positive eta, ThinLabel returns either an eta-approximate fixed point or a (gamma*eta/8)-accurate labeling.

For any possibly degenerate box [L,U] and \eta>0, \mathsf{ThinLabel}(L,U;\eta) (Algorithm 2) returns either an \eta -approximate fixed point in [0,1]^{d} or a \frac{\gamma\eta}{8} -accurate labeling of [L,U].

Lemma 2.

Quoted word for word from the full text on arXiv.

The paper

A Quasipolynomial Algorithm for ℓ_(∞) Contractions

Ashkan Soleymani, Gabriele Farina

arXiv, Oct 21, 2026, Open access, Preprint, not peer-reviewed

doi.org/10.48550/arxiv.2610.30122

arXiv:2610.30122v1 in cs.GT, also cs.CC, cs.LG, math.OC

AbstractPDFHTML

Cite as BibTeX
@misc{soleymani2026quasipolynomial,
  title = {A Quasipolynomial Algorithm for $\ell_\infty$ Contractions},
  author = {Soleymani, Ashkan and Farina, Gabriele},
  year = {2026},
  eprint = {2610.30122},
  archivePrefix = {arXiv},
  primaryClass = {cs.GT},
  doi = {10.48550/arxiv.2610.30122},
  url = {https://arxiv.org/abs/2610.30122}
}

Related