Family 104Theoretical computer scienceLeanNot yet digested
Quasipolynomial algorithms for mean-payoff, stochastic and parity games
Gives deterministic algorithms using bit operations, for complete binary input length L, for ordinary mean-payoff games and two separate extensions. They compute exact values and optimal positional strategies in ordinary games, the nonnegative expectation-of-liminf value set in turn-based stochastic games, and the winning set for nonnegative liminf mean payoff conjoined with parity. Signed rewards, rational chance probabilities, and parity priorities are unrestricted and binary-encoded.
Manuscripts in this family · 4
Turn-Based Stochastic Mean-Payoff Games in Deterministic Quasipolynomial Time
Oct 5, 2026·stochastic-mean-payoff-games.pdf
We give a uniform deterministic quasipolynomial-time algorithm for finite turn-based stochastic mean-payoff games with signed integer rewards and rational chance-transition probabilities encoded in binary. It computes exactly the vertices of nonnegative value, including value zero, for the expectation of the pathwise liminf mean payoff. The algorithm uses exact rational arithmetic and bit operations, where L is the complete binary input length.
Mean-payoff parity games in quasipolynomial time
Oct 5, 2026·mean-payoff-parity.pdf
We give a uniform deterministic quasipolynomial-time algorithm for mean-payoff parity games. It computes all vertices from which a player can enforce both nonnegative liminf mean payoff and the parity condition, with arbitrary signed binary rewards and unrestricted binary priorities. The running time is bit operations, where L is the complete input length.
Deterministic quasipolynomial-time mean-payoff games
Sep 25, 2026·paper.pdf
We give a deterministic algorithm that computes the complete zero-threshold winning set of a finite mean-payoff game with arbitrary signed integer edge weights encoded in binary. For total explicit input length L, it uses bit operations. A reduction also computes the exact rational value at every vertex and globally optimal positional strategies for both players within the same quasipolynomial bound.
Randomized quasipolynomial-time mean-payoff games
Sep 25, 2026·paper.pdfLean
We give a randomized algorithm that computes the complete zero-threshold winning set of a finite mean-payoff game with arbitrary signed integer edge weights encoded in binary. For total explicit input length L, it uses bit operations on every random tape and is correct with probability at least 7/8. A polynomial-time check certifies the winning regions and positional strategies for both players or reports failure. Independent repetition therefore gives an always-correct algorithm with the same expected quasipolynomial bit bound.