Faster O(|V|^2|E|W)-Time Energy Algorithms for Optimal Strategy Synthesis in Mean Payoff Games

Abstract

This study strengthens the links between Mean Payoff Games (\MPG{s}) and Energy Games (EG{s}). Firstly, we offer a faster $O(|V{|}^2|E|W)$ pseudo-polynomial time and $\Theta (|V|+|E|)$ space deterministic algorithm for solving the Value Problem and Optimal Strategy Synthesis in \MPG{s}. This improves the best previously known estimates on the pseudo-polynomial time complexity to: \[ O(|E|\log |V|) + Θ\Big(\sum_{v\in V}\texttt{deg}_Γ(v)\cdot\ell_Γ(v)\Big) = O(|V|^2|E|W), \] where ${\ell }_{\Gamma }(v)$ counts the number of times that a certain energy-lifting operator $\delta (\cdot ,v)$ is applied to any $v\in V$, along a certain sequence of Value-Iterations on reweighted \EG{s}; and ${\text{deg}}_{\Gamma }(v)$ is the degree of $v$. This improves significantly over a previously known pseudo-polynomial time estimate, i.e. $\Theta (|V{|}^2|E|W+{\sum }_{v\in V}{\text{deg}}_{\Gamma }(v)\cdot {\ell }_{\Gamma }(v))$ \citep{CR15, CR16}, as the pseudo-polynomiality is now confined to depend solely on ${\ell }_{\Gamma }$. Secondly, we further explore on the relationship between Optimal Positional Strategies (OPSs) in \MPG{s} and Small Energy-Progress Measures (SEPMs) in reweighted \EG{s}. It is observed that the space of all OPSs, ${\text{opt}}_{\Gamma }{\Sigma }_0^M$, admits a unique complete decomposition in terms of extremal-SEPM{s} in reweighted EG{s}. This points out what we called the "Energy-Lattice ${\mathcal{X}}_{\Gamma }^{\ast }$ associated to ${\text{opt}}_{\Gamma }{\Sigma }_0^M$". Finally, it is offered a pseudo-polynomial total-time recursive procedure for enumerating (w/o repetitions) all the elements of ${\mathcal{X}}_{\Gamma }^{\ast }$, and for computing the corresponding partitioning of ${\text{opt}}_{\Gamma }{\Sigma }_0^M$.