English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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

Energy Structure of Optimal Positional Strategies in Mean Payoff Games