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

This study strengthens the links between Mean Payoff Games (MPGs) and Energy Games (EGs). 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 MPGs. This improves the best previously known estimates on the pseudo-polynomial time complexity to:
O(|E|\log |V|) + \Theta\Big(\sum_{v\in V}\texttt{deg}_{\Gamma}(v)\cdot\ell_{\Gamma}(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 EGs; and \texttt{deg}_{\Gamma}(v) is the degree of v. This improves significantly over a previously known pseudo-polynomial time estimate, i.e. \Theta\big(|V|^2|E|W + \sum_{v\in V}\texttt{deg}_{\Gamma}(v)\cdot\ell_{\Gamma}(v)\big), 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 MPGs and Small Energy-Progress Measures (SEPMs) in reweighted EGs. It is observed that the space of all OPSs, \texttt{opt}_{\Gamma}\Sigma^M_0, admits a unique complete decomposition in terms of extremal-SEPMs in reweighted EGs. This points out what we called the “Energy-Lattice \mathcal{X}^*_{\Gamma} associated to \texttt{opt}_{\Gamma}\Sigma^M_0“. Finally, it is offered a pseudo-polynomial total-time recursive procedure for enumerating (w/o repetitions) all the elements of \mathcal{X}^*_{\Gamma}, and for computing the corresponding partitioning of \texttt{opt}_{\Gamma}\Sigma^M_0.

Download: manuscript.