English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the computational complexity of solving mean payoff games. Thisclass of games can be seen as an extension of parity games, and they havesimilar complexity status: in both cases solving them is in $\textbf{NP} \cap\textbf{coNP}$ and not known to be in $\textbf{P}$. In a breakthrough resultCalude, Jain, Khoussainov, Li, and Stephan constructed in 2017 aquasipolynomial time algorithm for solving parity games, which was quicklyfollowed by two other algorithms with the same complexity. Our objective is toinvestigate how these techniques can be extended to the study of mean payoffgames.  The starting point is the notion of separating automata, which has been usedto present all three quasipolynomial time algorithms for parity games and givesthe best complexity to date. The notion naturally extends to mean payoff gamesand yields a class of algorithms for solving mean payoff games. Thecontribution of this paper is to prove tight bounds on the complexity ofalgorithms in this class. We construct two new algorithms for solving meanpayoff games. Our first algorithm depends on the largest weight $N$ (inabsolute value) appearing in the graph and runs in sublinear time in $N$,improving over the previously known linear dependence in $N$. Our secondalgorithm runs in polynomial time for a fixed number $k$ of weights.  We complement our upper bounds by providing in both cases almost matchinglower bounds, showing the limitations of the separating automata approach. Weshow that we cannot hope to improve on the dependence in $N$ nor break thelinear dependence in the exponent in the number $k$ of weights. In particular,this shows that separating automata do not yield a quasipolynomial algorithmfor solving mean payoff games.

The complexity of mean payoff games using universal graphs