Paper detail

Energy Structure of Optimal Positional Strategies in Mean Payoff Games

This note studies structural aspects concerning Optimal Positional Strategies (OPSs) in Mean Payoff Games (MPGs), it is a contribution to understanding the relationship between OPSs in MPGs and Small Energy-Progress Measures (SEPMs) in reweighted Energy Games (EGs). Firstly, it is observed that the space of all OPSs, $\texttt{opt}_ΓΣ^M_0$, admits a unique complete decomposition in terms of so-called extremal-SEPM{s} in reweighted EG{s}; this points out what we called the "Energy-Lattice $\mathcal{X}^*_Γ$ of $\texttt{opt}_ΓΣ^M_0$". Secondly, it is offered a pseudo-polynomial total-time recursive procedure for enumerating (w/o repetitions) all the elements of $\mathcal{X}^*_Γ$, and for computing the corresponding partitioning of $\texttt{opt}_ΓΣ^M_0$. It is observed that the corresponding recursion tree defines an additional lattice $\mathcal{B}^*_Γ$, whose elements are certain subgames $Γ'\subseteq Γ$ that we call basic subgames. The extremal-SEPMs of a given \MPG $Γ$ coincide with the least-SEPMs of the basic subgames of $Γ$; so, $\mathcal{X}^*_Γ$ is the energy-lattice comprising all and only the least-SEPMs of the \emph{basic} subgames of $Γ$. The complexity of the proposed enumeration for both $\mathcal{B}^*_Γ$ and $\mathcal{X}^*_Γ$ is $O(|V|^3|E|W |\mathcal{B}^*_Γ|)$ total time and $O(|V||E|)+Θ\big(|E| \mathcal{B}^*_Γ|\big)$ working space. Finally, it is constructed an \MPG $Γ$ for which $|\mathcal{B}^*_Γ| > |\mathcal{X}^*_Γ|$, this proves that $\mathcal{B}^*_Γ$ and $\mathcal{X}^*_Γ$ are not isomorphic.