This study strengthens the links between Mean Payoff Games (MPGs) and Energy Games (EGs). Firstly, we offer a faster pseudo-polynomial time and 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:
where counts the number of times that a certain energy-lifting operator is applied to any , along a certain sequence of Value-Iterations on reweighted EGs; and is the degree of . This improves significantly over a previously known pseudo-polynomial time estimate, i.e. , as the pseudo-polynomiality is now confined to depend solely on . 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, , admits a unique complete decomposition in terms of extremal-SEPMs in reweighted EGs. This points out what we called the “Energy-Lattice associated to “. Finally, it is offered a pseudo-polynomial total-time recursive procedure for enumerating (w/o repetitions) all the elements of , and for computing the corresponding partitioning of .