A pseudo-quasi-polynomial algorithm for mean-payoff parity games

DOI10.1145/3209108.3209162MaRDI QIDQ5145306zbMATHOpenAlexFDO

Authors Laure Daviaud, Martin Jurdziński, Ranko Lazić

Publication date 20 January 2021

Published in Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.04756

Mathematics Subject Classification ID

Analysis of algorithms (68W40) 2-person games (91A05) Games involving graphs (91A43)

Abstract: In a mean-payoff parity game, one of the two players aims both to achieve a qualitative parity objective and to minimize a quantitative long-term average of payoffs (aka. mean payoff). The game is zero-sum and hence the aim of the other player is to either foil the parity objective or to maximize the mean payoff. Our main technical result is a pseudo-quasi-polynomial algorithm for solving mean-payoff parity games. All algorithms for the problem that have been developed for over a decade have a pseudo-polynomial and an exponential factors in their running times; in the running time of our algorithm the latter is replaced with a quasi-polynomial one. By the results of Chatterjee and Doyen (2012) and of Schewe, Weinert, and Zimmermann (2018), our main technical result implies that there are pseudo-quasi-polynomial algorithms for solving parity energy games and for solving parity games with weights. Our main conceptual contributions are the definitions of strategy decompositions for both players, and a notion of progress measures for mean-payoff parity games that generalizes both parity and energy progress measures. The former provides normal forms for and succinct representations of winning strategies, and the latter enables the application to mean-payoff parity games of the order-theoretic machinery that underpins a recent quasi-polynomial algorithm for solving parity games.

Recommendations

• Solving mean-payoff games via quasi dominions
• Faster algorithms for mean-payoff games
• Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
• Faster algorithms for mean-payoff parity games
• Energy parity games

Cited in

(19)

• Simple stochastic games with almost-sure energy-parity objectives are in NP and conp
• Parity games with weights
• Quasipolynomial computation of nested fixpoints
• scientific article; zbMATH DE number 7445162 (Why is no real title available?)
• Universal algorithms for parity games and nested fixpoints
• Solving mean-payoff games via quasi dominions
• New algorithms for combinations of objectives using separating automata
• Faster algorithms for mean-payoff games
• Energy mean-payoff games
• scientific article; zbMATH DE number 7649926 (Why is no real title available?)
• Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games
• Solving mean-payoff games via quasi dominions
• The Theory of Universal Graphs for Infinite Duration Games
• Improving parity games in practice
• scientific article; zbMATH DE number 7649916 (Why is no real title available?)
• Pseudopolynomial iterative algorithm to solve total-payoff games and min-cost reachability games
• Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
• scientific article; zbMATH DE number 7533361 (Why is no real title available?)
• Faster algorithms for mean-payoff parity games

This page was built for publication: A pseudo-quasi-polynomial algorithm for mean-payoff parity games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145306)