2015/08/10 by Comin, Carlo
#Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1508.02440
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, optΓΣM0, admits a unique complete decomposition in terms of so-called extremal-SEPMs in reweighted EGs; this points out what we called the "Energy-Lattice X^*Γ of optΓΣM0". Secondly, it is offered a pseudo-polynomial total-time recursive procedure for enumerating (w/o repetitions) all the elements of X^*Γ, and for computing the corresponding partitioning of optΓΣM0. It is observed that the corresponding recursion tree defines an additional lattice B^*Γ, whose elements are certain subgames Γ'⊆ Γ that we call basic subgames. The extremal-SEPMs of a given \MPG Γ coincide with the least-SEPMs of the basic subgames of Γ; so, X^*Γ is the energy-lattice comprising all and only the least-SEPMs of the basic subgames of Γ. The complexity of the proposed enumeration for both B^*Γ and X^*Γ is O(|V|3|E|W |B^*Γ|) total time and O(|V||E|)+Θ(|E| B^*Γ|) working space. Finally, it is constructed an \MPG Γ for which |B^*Γ| > |X^*Γ|, this proves that B^*Γ and X^*Γ are not isomorphic.