Quasipolynomial algorithms for mean-payoff and simple stochastic games

Prelegent(ci)

Paweł Parys

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

28 października 2026 14:15

Pokój

p. 5440

Tytuł w języku polskim

Quasipolynomial algorithms for mean-payoff and simple stochastic games

Seminarium

Seminarium „Teoria automatów”

---

We consider infinite-duration games played on finite graphs. In
mean-payoff games, edges are labeled with weights, and Eve's objective is
to maximize the long-run average of the weights along the play. In simple
stochastic games, the objective is reachability; in addition to vertices
controlled by Eve and Adam, there are stochastic vertices, where the
successor is chosen at random.

It is known that parity games can be reduced in polynomial time to
mean-payoff games, which in turn can be reduced in polynomial time to
simple stochastic games; no polynomial-time reductions in the opposite
directions are known. Since 2017, parity games have been known to admit
quasipolynomial-time algorithms, but extending this result to the more
general classes of mean-payoff and simple stochastic games remained a
major open problem.

This month, two independent quasipolynomial approaches to these problems
were announced. OpenAI obtained quasipolynomial algorithms for mean-payoff
games and turn-based stochastic mean-payoff games, the latter implying a
quasipolynomial algorithm for simple stochastic games. Independently,
Soleymani and Farina (MIT) obtained a quasipolynomial algorithm for simple
stochastic games via a more general algorithm for fixed points of
l_\infty-contractions. I will present the main ideas behind these two
approaches.
 

---