Energy Structure of Optimal Positional Strategies
in Mean Payoff Games
Carlo Comin

arXiv:1508.02440v3 [cs.GT] 1 Dec 2016

(carlo.comin.86@gmail.com)

Abstract
This note studies structural aspects concerning Optimal Positional Strategies (OPSs) in Mean
Payoff Games (MPGs), it’s 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Γ ΣM
0 , 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Γ ΣM
0 ”. 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Γ ΣM
0 . 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 proposedenumeration 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.
Keywords: Mean Payoff Games, Optimal Strategy Synthesis, Pseudo-Polynomial Time,
Energy Games, Small Energy-Progress Measures.

1. Introduction
A Mean Payoff Game (MPG) is a two-player infinite game Γ = (V, E, w, hV0 ,V1 i), that is
played on a finite weighted directed graph, denoted GΓ , (V, E, w), where w : E → Z, the vertices
of which are partitioned into two classes, V0 and V1 , according to the player to which they belong.
At the beginning of the game a pebble is placed on some vertex vs ∈ V , then the two players,
named Player 0 and Player 1, move it along the arcs ad infinitum. Assuming the pebble is currently on some v ∈ V0 , then Player 0 chooses an arc (v, v′ ) ∈ E going out of v and moves the pebble
to the destination vertex v′ . Similarly, if the pebble is currently on some v ∈ V1 , it is Player 1’s turn
to choose an outgoing arc. The infinite sequence vs , v, v′ . . . of all the encountered vertices forms a
play. In order to play well, Player 0 wants to maximize the limit inferior of the long-run average
weight of the traversed arcs, i.e., to maximize lim infn→∞ n1 ∑n−1
i=0 w(vi , vi+1 ), whereas Player 1
wants to minimize the lim supn→∞ 1n ∑n−1
w(v
,
v
).
Ehrenfeucht
and Mycielski (1979) proved
i i+1
i=0
Γ
that each vertex v admits a value, denoted val (v), that each player can secure by means of a
memoryless (or positional) strategy, i.e., one depending only on the current vertex position and
not on the previous choices.
Preprint submitted to arXiv

Received: date / Accepted: date

Solving an MPG consists in computing the values of all vertices (Value Problem) and, for
each player, a positional strategy that secures such values to that player (Optimal Strategy Synthesis). The corresponding decision problem lies in NP ∩ coNP (Zwick and Paterson, 1996) and
it was later shown to be in UP ∩ coUP (Jurdziński, 1998).
The problem of devising efficient algorithms for solving MPGs has been studied extensively
in the literature. The first milestone was settled in Gurvich et al. (1988), in which it was offered
an exponential time algorithm for solving a slightly wider class of MPGs called Cyclic Games.
Afterwards, Zwick and Paterson (1996) devised the first deterministic procedure for computing
values in MPGs, and optimal strategies securing them, within a pseudo-polynomial time and
polynomial space. In particular, it was established an O(|V |3 |E|W ) upper bound for the time
complexity of the Value Problem, as well as an upper bound of O(|V |4 |E|W log(|E|/|V |)) for
that of Optimal Strategy Synthesis (Zwick and Paterson, 1996).
Several research efforts have been spent in studying quantitative extensions of infinite games
for modeling quantitative aspects of reactive systems, e.g., the Energy Games (EGs) (Chakrabarti et al.,
2003; Bouyer et al., 2008; Brim et al., 2011). These studies unveiled interesting connections between EGs and MPGs; and by relying on these techniques, recently the worst-cast time complexity of the Value Problem and Optimal Strategy Synthesis was given an improved pseudopolynomial upper bound (Comin and Rizzi, 2015, 2016a); those works focused on offering a
simple proof of the improved upper bound. However, the running time of the proposed algorithm turned out to
|2 |E|W ), the actual time complexity being Θ |V |2 |E|W +
 be also Ω(|V
0
0
∑v∈V degΓ (v) · ℓΓ (v) , where ℓΓ (v) ≤ (|V | − 1)|V |W denotes the total number of times that a
certain energy-lifting operator δ (·, v) is applied to any v ∈ V . A way to overcome this issue
was found in Comin and Rizzi (2016b), where a novel algorithmic scheme, named Jumping, was
introduced; by tackling on some further regularities of the problem, the estimate on the pseudo
polynomial time complexity of MPGs was reduced to: O(|E| log |V |) + Θ ∑v∈V degΓ (v) · ℓ1Γ (v) ,
where, for every v ∈ V , ℓ1Γ (v) is the total number of applications of δ (·, v) that are made by the
algorithm; ℓ1Γ ≤ (|V | − 1)|V |W (worst-case, but experimentally ℓ1Γ ≪ ℓ0Γ ; see Comin and Rizzi
(2016b)), and the working space is Θ(|V | + |E|). With this, the pseudo-polynomiality was confined to depend solely on the total number ℓ1Γ of required energy-liftings.
Contribution. This work studies the relationship between Optimal Positional Strategies (OPSs)
in MPGs and Small Energy-Progress Measures (SEPMs) in reweighted EGs. Actually this paper
is an extended and revised version of Section 5 in Comin and Rizzi (2015). Here, we offer:
1. An Energy-Lattice Decomposition of the Space of Optimal Positional Strategies in MPGs.
Let’s denote by optΓ ΣM
0 the space of all the optimal positional strategies in a given MPG Γ. What
allows the algorithms given in Comin and Rizzi (2015, 2016a,b) to compute at least one σ0∗ ∈
optΓ ΣM
0 is a compatibility relation that links optimal arcs in MPGs to arcs that are compatible
w.r.t. least-SEPMs in reweighted EGs. The family EΓ of all SEPMs of a given EG Γ forms a
complete finite lattice, the Energy-Lattice of the EG Γ. Firstly, we observe that even though
compatibility w.r.t. least-SEPMs in reweighted EGs implies optimality of positional strategies
in MPGs (see Theorem 3), the converse doesn’t hold generally (see Proposition 5). Thus a
natural question was whether compatibility w.r.t. SEPMs was really appropriate to capture (e.g.,
to provide a recursive enumeration of) the whole optΓ ΣM
0 and not just a proper subset of it.
Partially motivated by this question we explored on the relationship between optΓ ΣM
0 and EΓ .
In Theorem 4, it is observed a unique complete decomposition of optΓ ΣM
0 which is expressed
in terms of so called extremal-SEPMs in reweighted EGs. This points out what we called the
2

“Energy-Lattice XΓ∗ associated to optΓ ΣM
0 ”, the family of all the extremal-SEPMs of a given
MPG Γ. So, compatibility w.r.t. SEPMs actually turns out to be appropriate for constructing
∗
the whole optΓ ΣM
0 ; but an entire lattice XΓ of extremal-SEPMs then arises (and not just the
least-SEPM, which turns out to account only for the join/top component of optΓ ΣM
0 ).
2. A Recursive Enumeration of Extremal-SEPMs and Optimal Positional Strategies in MPGs.
It is offered a pseudo-polynomial total time recursive procedure for enumerating (w/o repetitions)
all the elements of XΓ∗ , and for computing the associated partitioning of optΓ ΣM
0 . This shows
that the above mentioned compatibility relation is appropriate so to extend the algorithm given
∗
in Comin and Rizzi (2016b), recursively, in order to compute the whole optΓ ΣM
0 and XΓ . It is
∗
observed that the corresponding recursion tree actually defines an additional lattice BΓ , whose
elements are certain subgames Γ′ ⊆ Γ that we call basic subgames. The extremal-SEPMs of
a given Γ coincide with the least-SEPMs of the basic subgames of Γ; so, XΓ∗ is the energylattice comprising all and only the least-SEPMs of the basic subgames of Γ. The total time
complexity of the proposed enumeration
for both BΓ∗ and XΓ∗ is O(|V |3 |E|W |BΓ∗ |), it works in

∗
space O(|V ||E|) + Θ |E||BΓ | . An example of MPG Γ for which |BΓ∗ | > |XΓ∗ | ends this paper.
Organization. The following Section 2 introduces some notation and provides the required background on infinite 2-player pebble games and related algorithmic results. In Section 3, a suitable relation between values, optimal strategies, and certain reweighting operations is recalled
from Comin and Rizzi (2015, 2016a). Section 4 offers a unique and complete energy-lattice de∗
composition of optΓ ΣM
0 . Finally, Section 5 provides a recursive enumeration of XΓ and the
M
corresponding partitioning of optΓ Σ0 .
2. Notation and Preliminaries
We denote by N, Z, Q the set of natural, integer, and rational numbers. It will be sufficient to
consider integral intervals, e.g., [a, b] , {z ∈ Z | a ≤ z ≤ b} and [a, b) , {z ∈ Z | a ≤ z < b} for
any a, b ∈ Z. Our graphs are directed and weighted on the arcs; thus, if G = (V, E, w) is a graph,
then every arc e ∈ E is a triplet e = (u, v, we ), where we = w(u, v) ∈ Z. Let W , maxe∈E |we | be
the maximum absolute weight. Given a vertex u ∈ V , the set of its successors is NΓout (u) , {v ∈
V | (u, v) ∈ E}, and the set of its predecessors is NΓin (u) , {v ∈ V | (v, u) ∈ E}. Let degΓ (v) ,
|NΓin (v)| + |NΓout (v)|. A path is a sequence v0 v1 . . . vn . . . such that ∀i∈[n] (vi , vi+1 ) ∈ E. Let V ∗
be the set of all (possibly empty) finite paths. A simple path is a finite path v0 v1 . . . vn having
no repetitions, i.e., for any i, j ∈ [0, n] it holds vi 6= v j if i 6= j. A cycle is a path v0 v1 . . . vn−1 vn
such that v0 . . . vn−1 is simple and vn = v0 . The average weight of a cycle v0 . . . vn is w(C)/|C| =
1 n−1
n ∑i=0 w(vi , vi+1 ). A cycle C = v0 v1 . . . vn is reachable from v in G if there is some path p in G
such that p ∩C 6= 0.
/
An arena is a tuple Γ = (V, E, w, hV0 ,V1 i) where GΓ , (V, E, w) is a finite weighted directed
graph and (V0 ,V1 ) is a partition of V into the set V0 of vertices owned by Player 0, and V1 owned
by Player 1. It is assumed that GΓ has no sink, i.e., ∀v∈V NΓout (v) 6= 0;
/ we remark that GΓ is
not required to be a bipartite graph on colour classes V0 and V1 . A subarena Γ′ (or subgame)
of Γ is any arena Γ′ = (V ′ , E ′ , w′ , hV0′ ,V1′ i) such that: V ′ ⊆ V , ∀i∈{0,1}Vi′ = V ′ ∩ Vi , E ′ ⊆ E, and
′
∀e∈E w′e = we . Given S ⊆ V , the subarena of Γ induced by S is denoted Γ|S , its vertex set is S
and its edge set is E ′ = {(u, v) ∈ E | u, v ∈ S}. A game on Γ is played for infinitely many rounds
by two players moving a pebble along the arcs of GΓ . At the beginning of the game the pebble
3

is found on some vertex vs ∈ V , which is called the starting position of the game. At each turn,
assuming the pebble is currently on a vertex v ∈ Vi (for i = 0, 1), Player i chooses an arc (v, v′ ) ∈ E
and then the next turn starts with the pebble on v′ . Below, Fig. 1 depicts an example arena Γex .
+3
A

−5

B

0
D

0

+3
C

0

E

−5

0

−5
F

G

+3

Figure
1:
An
arena
Γex = hV, E, w, (V0 ,V1 )i.
Here,
V =
{A, B,C, D, E, F, G}
and
E
=
{(A, B, +3), (B,C, +3), (C, D, −5),
(D, A, −5), (E, A, 0), (E,C, 0), (E, F, 0), (E, G, 0), (F, G, −5), (G, F, +3)}.
Also, V0 =
{B, D, E, G} is colored in red, while V1 = {A,C, F} is filled in blue.
A play is any infinite path v0 v1 . . . vn . . . ∈ V ω in Γ. For any i ∈ {0, 1}, a strategy of Player i
is any function σi : V ∗ × Vi → V such that for every finite path p′ v in GΓ , where p′ ∈ V ∗ and
v ∈ Vi , it holds that (v, σi (p′ , v)) ∈ E. A strategy σi of Player i is positional (or memoryless) if
σi (p, vn ) = σi (p′ , v′m ) for every finite paths pvn = v0 . . . vn−1 vn and p′ v′m = v′0 . . . v′m−1 v′m in GΓ
such that vn = v′m ∈ Vi . The set of all the positional strategies of Player i is denoted by ΣM
i . A
play v0 v1 . . . vn . . . is consistent with a strategy σ ∈ Σi if v j+1 = σ (v0 v1 . . . v j ) whenever v j ∈ Vi .
Given a starting position vs ∈ V , the outcome of two strategies σ0 ∈ Σ0 and σ1 ∈ Σ1 , denoted
outcomeΓ (vs , σ0 , σ1 ), is the unique play that starts at vs and is consistent with both σ0 and σ1 .
Given a memoryless strategy σi ∈ ΣM
i of Player i in Γ, then G(σi , Γ) = (V, Eσi , w) is the graph
obtained from GΓ by removing all the arcs (v, v′ ) ∈ E such that v ∈ Vi and v′ 6= σi (v); we say that
G(σi , Γ) is obtained from GΓ by projection w.r.t. σi .
For any weight function w′ : E → Z, the reweighting of Γ = (V, E, w, hV0 ,V1 i) w.r.t. w′ is the
′
arena Γw = (V, E, w′ , hV0 ,V1 i). Also, for w : E → Z and any ν ∈ Z, we denote by w+ ν the weight
function w′ defined as ∀e∈E w′e , we + ν . Indeed, we shall consider reweighted games of the form
Γw−q , for some q ∈ Q. Notice that the corresponding weight function w′ : E → Q : e 7→ we − q is
rational, while we required the weights of the arcs to be always integers. To overcome this issue,
it is sufficient to re-define Γw−q by scaling all weights by a factor equal to the denominator of
q ∈ Q; i.e., when q ∈ Q, say q = N/D for gcd(N, D) = 1 we define Γw−q , ΓD·w−N . This rescaling operation doesn’t change the winning regions of the corresponding games, let’s denote this
equivalence as Γw−q ∼
= ΓD·w−N , and it has the significant advantage of allowing for a discussion
(and an algorithmics) which is strictly based on integer weights.
2.1. Mean Payoff Games
A Mean Payoff Game (MPG) (Brim et al., 2011; Zwick and Paterson, 1996; Ehrenfeucht and Mycielski,
1979) is a game played on some arena Γ for infinitely many rounds by two opponents, Player 0
gains a payoff defined as the long-run average weight of the play, whereas Player 1 loses that
value. Formally, the Player 0’s payoff of a play v0 v1 . . . vn . . . in Γ is defined as follows:
MP0 (v0 v1 . . . vn . . .) , lim inf
n→∞

4

1 n−1
∑ w(vi , vi+1 ).
n i=0

The value secured by a strategy σ0 ∈ Σ0 in a vertex v is defined as:

valσ0 (v) , inf MP0 outcomeΓ (v, σ0 , σ1 ) ,
σ1 ∈Σ1

Notice that payoffs and secured values can be defined symmetrically for the Player 1 (i.e., by
interchanging the symbol 0 with 1 and inf with sup).
Ehrenfeucht and Mycielski Ehrenfeucht and Mycielski (1979) proved that each vertex v ∈ V
admits a unique value, denoted valΓ (v), which each player can secure by means of a memoryless
(or positional) strategy. Moreover, uniform positional optimal strategies do exist for both players,
in the sense that for each player there exist at least one positional strategy which can be used to
secure all the optimal values, independently with respect to the starting position vs . Thus, for
v∈V
every MPG Γ, there exists a strategy σ0 ∈ ΣM
valσ0 (v) ≥ valΓ (v), and there
0 such that ∀
σ
Γ
M
v∈V
1
exists a strategy σ1 ∈ Σ1 such that ∀ val (v) ≤ val (v). The (optimal) value of a vertex
v ∈ V in the MPG Γ is given by:
valΓ (v) = sup valσ0 (v) = inf valσ1 (v).
σ0 ∈Σ0

σ1 ∈Σ1

Thus,
a strategy σ0 ∈ Σ0 is optimal if valσ0 (v) = valΓ (v) for all v ∈ V . We denote optΓ ΣM
0 ,

v∈V valΓ (v) = valΓ (v) . A strategy σ ∈ Σ is said to be winning for Player 0
(Γ)
|
∀
σ0 ∈ ΣM
0
0
σ0
0
if ∀v∈V valσ0 (v) ≥ 0, and σ1 ∈ Σ1 is winning for Player 1 if valσ1 (v) < 0. Correspondingly, a
vertex v ∈ V is a winning starting position for Player 0 if valΓ (v) ≥ 0, otherwise it is winning
for Player 1. The set of all winning starting positions of Player i is denoted by Wi for i ∈ {0, 1}.
A refined formulation of the determinacy theorem is offered in Björklund et al. (2004).
Theorem 1 (Björklund et al. (2004)). Let Γ be an MPG and let {Ci }m
i=1 be a partition (called ergodic) of its vertices into m ≥ 1 classes each one having the same optimal value νi ∈ Q. Formally,
F
i∈[m] ∀v∈Ci valΓi (v) = ν , where Γ , Γ .
V= m
i
i
|Ci
i=1 Ci and ∀
Then, Player 0 has no vertices with outgoing arcs leading from Ci to C j whenever νi < ν j ,
and Player 1 has no vertices with outgoing arcs leading from Ci to C j whenever νi > ν j ;
M
moreover, there exist σ0 ∈ ΣM
0 and σ1 ∈ Σ1 such that:
– If the game starts from any vertex in Ci , then σ0 secures a gain at least νi to Player 0 and
σ1 secures a loss at most νi to Player 1;
– Any play that starts from Ci always stays in Ci , if it is consistent with both strategies σ0 , σ1 ,
i.e., if Player 0 plays according to σ0 , and Player 1 according to σ1 .
A finite variant of MPGs is well-known in the literature (Ehrenfeucht and Mycielski, 1979;
Zwick and Paterson, 1996; Brim et al., 2011), where the game stops as soon as a cyclic sequence of vertices is traversed. It turns out that this is equivalent to the infinite game formulation (Ehrenfeucht and Mycielski, 1979), in the sense that the values of an MPG are in a strong
relationship with the average weights of its cycles, as in the next lemma.
Proposition 1 (Brim, et al. Brim et al. (2011)). Let Γ be an MPG. For all ν ∈ Q, for all σ0 ∈ ΣM
0 ,
and for all v ∈ V , the value valσ0 (v) is greater than ν iff all cycles C reachable from v in the
projection graph GΓσ0 have an average weight w(C)/|C| greater than ν .
The proof of Proposition 1 follows from the memoryless determinacy of MPGs. We remark
that a proposition which is symmetric to Proposition 1 holds for Player 1 as well: for all ν ∈ Q,
σ1
for all positional strategies σ1 ∈ ΣM
1 of Player 1, and for all vertices v ∈ V , the value val (v) is
5

less than ν iff if all cycles reachable from v in the projection graph GσΓ1 have an average weight
less than ν . Also, it is well-known (Brim et al., 2011; Ehrenfeucht and Mycielski, 1979) that
each value valΓ (v) is contained within the following set of rational numbers:
n
o
SΓ = N/D | D ∈ [1, |V |], N ∈ [−D ·W, D ·W] .
Notice, |SΓ | ≤ |V |2W .
The present work focuses on the algorithmics of the following classical problem:
– Optimal Strategy Synthesis. Compute an optimal positional strategy for Player 0 in Γ.
Also, in Section 5 we shall consider the problem of computing the whole optΓ ΣM
0 :
– Optimal Strategy Enumeration. Provide a listing1 of all the optimal positional strategies of
Player 0 in the MPG Γ.
2.2. Energy Games and Small Energy-Progress Measures
An Energy Game (EG) is a game that is played on an arena Γ for infinitely many rounds by
two opponents, where the goal of Player 0 is to construct an infinite play v0 v1 . . . vn . . . such that
j
for some initial credit c ∈ N the following holds: c + ∑i=0
w(vi , vi+1 ) ≥ 0 , for all j ≥ 0. Given
an initial credit c ∈ N, a play v0 v1 . . . vn . . . is winning for Player 0 if it satisfies (1), otherwise
it is winning for Player 1. A vertex v ∈ V is a winning starting position for Player 0 if there
exists an initial credit c ∈ N and a strategy σ0 ∈ Σ0 such that, for every strategy σ1 ∈ Σ1 , the play
outcomeΓ (v, σ0 , σ1 ) is winning for Player 0. As in the case of MPGs, the EGs are memoryless
determined Brim et al. (2011), i.e., for every v ∈ V , either v is winning for Player 0 or v is winning
for Player 1, and (uniform) memoryless strategies are sufficient to win the game. In fact, as shown
in the next lemma, the decision problems of MPGs and EGs are intimately related.
Proposition 2 (Brim et al. (2011)). Let Γ be an arena. For all threshold ν ∈ Q, for all vertices
v ∈ V , Player 0 has a strategy in the MPG Γ that secures value at least ν from v if and only if,
for some initial credit c ∈ N, Player 0 has a winning strategy from v in the reweighted EG Γw−ν .
In this work we are especially interested in the Minimum Credit Problem (MCP) for EGs: for
each winning starting position v, compute the minimum initial credit c∗ = c∗ (v) such that there
exists a winning strategy σ0 ∈ ΣM
0 for Player 0 starting from v. A fast pseudo-polynomial time
deterministic procedure for solving MCPs comes from Brim et al. (2011).
Theorem 2 (Brim et al. (2011)). There exists a deterministic algorithm for solving the MCP
within O(|V | |E|W ) pseudo-polynomial time, on any input EG (V, E, w, hV0 ,V1 i).
The algorithm mentioned in Theorem 2 is the Value-Iteration algorithm (Brim et al., 2011).
Its rationale relies on the notion of Small Energy-Progress Measures (SEPMs).
2.3. Energy-Lattices of Small Energy-Progress Measures
Small-Energy Progress Measures are bounded, non-negative and integer-valued functions
that impose local conditions to ensure global properties on the arena, in particular, witnessing
that Player 0 has a way to enforce conservativity (i.e., non-negativity of cycles) in the resulting
1 The listing has to be exhaustive (i.e., each element is listed eventually) and without repetitions (i.e., no element is
listed twice).

6

game’s graph. Recovering standard notation, see e.g. Brim et al. (2011), let us denote CΓ = {n ∈
N | n ≤ (|V | − 1)W } ∪ {⊤} and let  be the total order on CΓ defined as: x  y iff either y = ⊤
or x, y ∈ N and x ≤ y. In order to cast the minus operation to range over CΓ , let us consider an
operator ⊖ : CΓ × Z → CΓ defined as follows:

max(0, a − b), if a 6= ⊤ and a − b ≤ (|V | − 1)W;
a⊖b ,
a ⊖ b = ⊤,
otherwise.
Given an EG Γ on vertex set V = V0 ∪ V1 , a function f : V → CΓ is a Small Energy-Progress
Measure (SEPM) for Γ if and only if the following two conditions are met:
1. if v ∈ V0 , then f (v)  f (v′ ) ⊖ w(v, v′ ) for some (v, v′ ) ∈ E;
2. if v ∈ V1 , then f (v)  f (v′ ) ⊖ w(v, v′ ) for all (v, v′ ) ∈ E.
The values of a SEPM, i.e., the elements of the image f (V ), are called the energy levels of f .
It is worth to denote by V f = {v ∈ V | f (v) 6= ⊤} the set of vertices having finite energy. Given a
SEPM f : V → CΓ and a vertex v ∈ V0 , an arc (v, v′ ) ∈ E is said to be compatible with f whenever
f (v)  f (v′ ) ⊖ w(v, v′ ); otherwise (v, v′ ) is said to be incompatible with f . Moreover, a positional
v∈V0 if σ (v) = v′ then (v, v′ ) ∈ E is
strategy σ0 ∈ ΣM
0
0 is said to be compatible with f whenever: ∀
compatible with f ; otherwise, σ0 is incompatible with f .
It is well-known that the family of all the SEPMs of a given Γ forms a complete (finite)
lattice, which we denote by EΓ call it the Energy-Lattice of Γ. Therefore, we shall consider:
EΓ , { f : V → CΓ | f is SEPM of Γ}, ⊑),
where for any two SEPMs f , g define f ⊑ g iff ∀v ∈ V f (v)  g(v). Notice that, whenever f and
g are SEPMs, then so is the minimum function defined as: ∀v∈V h(v) , min{ f (v), g(v)}. This fact
allows one to consider the least SEPM, namely, the unique SEPM f ∗ : V → CΓ such that, for any
other SEPM g : V → CΓ , the following holds: ∀v∈V f ∗ (v)  g(v). Thus, EΓ is a complete lattice.
So, EΓ enjoys of Knaster–Tarski Theorem, which states that the set of fixed-points of a monotone
function on a complete lattice is again a complete lattice.
Also concerning SEPMs, we shall rely on the following lemmata. The first one relates
SEPMs to the winning region W0 of Player 0 in EGs.
Proposition 3 (Brim et al. (2011)). Let Γ be an EG. Then the following hold.
1. If f is any SEPM of the EG Γ and v ∈ V f , then v is a winning starting position for Player 0
in the EG Γ. Stated otherwise, V f ⊆ W0 ;
2. If f ∗ is the least SEPM of the EG Γ, and v is a winning starting position for Player 0 in
the EG Γ, then v ∈ V f ∗ . Thus, V f ∗ = W0 .
The following bound holds on the energy-levels of any SEPM (by definition of CΓ ).
Proposition 4. Let Γ be an EG. Let f be any SEPM of Γ.
Then, for every v ∈ V either f (v) = ⊤ or 0 ≤ f (v) ≤ (|V | − 1)W .
3. Optimal Strategies from Reweightings
It is now recalled a sufficient condition, for a positional strategy to be optimal, which is
expressed in terms of reweighted EGs and their SEPMs.
7

Theorem 3 (Comin and Rizzi (2016a)). Let Γ = (V, E, w, hV0 ,V1 i) be an MPG. For each u ∈ V ,
Γ
consider the reweighted EG Γu ∼
= Γw−val (u) . Let fu : V → CΓu be any SEPM of Γu such that
u ∈ V fu (i.e., fu (u) 6= ⊤). Moreover, we assume: fu1 = fu2 whenever valΓ (u1 ) = valΓ (u2 ).
When u ∈ V0 , let v fu ∈ NΓout (u) be any vertex such that (u, v fu ) ∈ E is compatible with fu in
u∈V0 σ ∗ (u) , v .
EG Γu , and consider the positional strategy σ0∗ ∈ ΣM
fu
0 defined as follows: ∀
0
∗
Then, σ0 is an optimal positional strategy for Player 0 in the MPG Γ.
Proof. See the proof of [Theorem 4 in Comin and Rizzi (2016a)].

✷

Remark 1. Notice that Theorem 3 holds, particularly, when fu is the least SEPM fu∗ of the
reweighted EG Γu . This is because u ∈ V fu∗ always holds for the least SEPM fu∗ of the EG Γu :
indeed, by Proposition 2 and by definition of Γu , then u is a winning starting position for Player 0
in the EG Γu (for some initial credit); thus, by Proposition 3, it follows that u ∈ V fu∗ .
4. An Energy-Lattice Decomposition of optΓ ΣM
0
Recall the example arena Γex shown in Fig. 1. It is easy to see that ∀v∈V valΓex (v) = −1.
Indeed, Γex contains only two cycles, i.e., CL = [A, B,C, D] and CR = [F, G], also notice that
w+1 can be computed
w(CL )/CL = w(CR )/CR = −1. The least-SEPM f ∗ of the reweighted EG Γex
by running a Value Iteration (Brim et al., 2011). Taking into account the reweighting w ❀ w + 1,
as in Fig. 2: f ∗ (A) = f ∗ (E) = f ∗ (G) = 0, f ∗ (B) = f ∗ (D) = f ∗ (F) = 4, and f ∗ (C) = 8.
4

+4
0

A

−4

B

8

+1
D

+1

+4
C

+1

−4

0
E

+1

4

−4

F

G

0

+4

4

w+1 (energy-levels are depicted in circled boldface). All and
Figure 2: The least-SEPM f ∗ of Γex
only those arcs of Player 0 that are compatible with f ∗ are (B,C), (D, A), (E, A), (E, G), (G, F )
(thick red arcs).

So, Γex (Fig. 2) implies the following.
Proposition 5. The converse statement of Theorem 3 doesn’t hold; there exist infinitely many
MPGs Γ having at least one σ0 ∈ optΓ ΣM
0 which is not compatible with the least-SEPM of Γ.
w+1 . The only vertex
Proof. Consider the Γex of Fig. 2, and the least-SEPM f ∗ of the EG Γex
at which Player 0 really has a choice is E. Every arc going out of E is optimal in the MPG
Γex : whatever arc (E, X) ∈ E (for any X ∈ {A,C, F, G}) Player 0 chooses at E, the resulting
w+1 . Observe, (E,C) and
payoff equals valΓex (E) = −1. Let f ∗ be the least-SEPM of f ∗ in Γex
∗
w+1
(E, F) are not compatible with f in Γex , only (E, A) and (E, G) are. For instance, the positional strategy σ0 ∈ ΣM
0 defined as σ0 (E) , F, σ0 (B) , C, σ0 (D) , A, σ0 (G) , F ensures a
w+1 (because
payoff ∀v∈V valΓex (v) = −1, but it is not compatible with the least-SEPM f ∗ of Γex
∗
∗
f (E) = 0 < 3 = f (F) ⊖ w(E, F)). It is easy to turn the Γex of Fig. 2 into a family on infinitely
8

many similar examples.

✷

We now aim at strengthening the relationship between optΓ ΣM
0 and the Energy-Lattice EΓ .
For this, we assume wlog ∃ν ∈Q ∀v∈V valΓ (v) = ν ; this follows from Theorem 1, which allows
one to partition Γ into several domains Γi , Γ|C each one satisfying: ∃νi ∈Q ∀v∈Ci valΓi (v) = νi .
i
M
By Theorem 1 we can study optΓi ΣM
0 , independently w.r.t. optΓ j Σ0 for j 6= i.
We say that an MPG Γ is ν -valued if and only if ∃ν ∈Q ∀v∈V valΓ (v) = ν .
′ ′
Γ
Given an MPG Γ and σ0 ∈ ΣM
0 (Γ), recall, G(Γ, σ0 ) , (V, E , w ) is obtained from G by
deleting all and only those arcs that are not part of σ0 , i.e.,


E ′ , (u, v) ∈ E | u ∈ V0 and v = σ0 (u) ∪ (u, v) ∈ E | u ∈ V1 ,

where each e ∈ E ′ is weighted as in Γ, i.e., w′ : E ′ → Z : e 7→ we .
When G = (V, E, w) is a weighted directed graph, a feasible-potential (FP) for G is any map
out
π : V → CG s.t. ∀u∈V ∀v∈N (u) π (u)  π (v) ⊖ w(u, v). The least-FP π ∗ = πG∗ is the (unique) FP
s.t., for any other FP π , it holds ∀v∈V π ∗ (v)  π (v). Given G, the Bellman-Ford algorithm can
∗
be used to produce πG∗ in O(|V ||E|) time. Let πG(Γ,
σ0 ) be the least-FP of G(Γ, σ0 ). Notice, for
M
∗
every σ0 ∈ Σ0 , the least-FP πG(Γ,σ0 ) is actually a SEPM for the EG Γ; still it can differ from the
least-SEPM of Γ, due to σ0 . We consider the following family of strategies.
Definition 1 (∆M
0 ( f , Γ)-Strategies). Let Γ = hV, E, w, (V0 ,V1 )i and let f : V → CΓ be a SEPM
M
for the EG Γ. Let ∆M
0 ( f , Γ) ⊆ Σ0 (Γ) be the family of all and only those positional strategies of
∗
Player 0 in Γ s.t. πG(Γ,σ0 ) coincides with f pointwisely, i.e.,
o
n
M
v∈V ∗
πG(Γ,σ0 ) (v) = f (v) .
∆M
0 ( f , Γ) , σ0 ∈ Σ0 (Γ) | ∀
M
We now aim at exploring further on the relationship between EΓ and optΓ ΣM
0 , via ∆0 ( f , Γ).

Definition 2 (The Energy-Lattice of optΓ ΣM
0 ). Let Γ be a ν -valued MPG. Let X ⊆ EΓw−ν be a
sublattice of SEPMs of the reweighted EG Γw−ν .
f ∈X M
We say that X is an “Energy-Lattice of optΓ ΣM
∆0 ( f , Γw−ν ) 6= 0/ and the follow0 ” iff ∀
ing disjoint-set decomposition holds:
optΓ ΣM
0 =

G

w−ν
∆M
).
0 ( f,Γ

f ∈X
w−ν , σ ∗ ) is conservative
Lemma 1. Let Γ be a ν -valued MPG, and let σ0∗ ∈ optΓ ΣM
0
0 . Then, G(Γ
(i.e., it contains no negative cycle).

Proof. Let C , (v1 . . . , vk , v1 ) by any cycle in G(Γw−ν , σ0∗ ). Since we have σ0∗ ∈ optΓ ΣM
0 and
∀v∈V valΓ (v) = ν , thus w(C)/k = 1k ∑ki=1 w(vi , vi+1 ) ≥ ν (for vk+1 , v1 ) by Proposition 1, so that,

assuming w′ , w − ν , then: w′ (C)/k = 1k ∑ki=1 w(vi , vi+1 ) − ν = w(C)/k − ν ≥ ν − ν = 0. ✷
Some aspects of the following Proposition 6 rely heavily on Theorem 3: the compatibility
relation comes again into play. Moreover, we observe that Proposition 6 is equivalent to the
9

following fact, which provides a sufficient condition for a positional strategy to be optimal. ConM
sider a ν -valued MPG Γ, for some ν ∈ Q, and let σ0∗ ∈ optΓ ΣM
0 . Let σ̂0 ∈ Σ0 (Γ) be any (not
necessarily optimal) positional strategy for Player 0 in the MPG Γ. Suppose the following holds:
∗
∗
∀v∈V πG(Γ
w−ν ,σ̂ ) (v) = πG(Γw−ν ,σ ∗ ) (v).
0
0

Then, by Proposition 6, σˆ0 is an optimal positional strategy for Player 0 in the MPG Γ.
We are thus relying on the same compatibility relation between ΣM
0 and SEPMs in reweighted
EGs which was at the base of Theorem 3, aiming at extending Theorem 3 so to describe the whole
optΓ ΣM
0 (and not just the join/top component of it).
Proposition 6. Let the MPG Γ be ν -valued, for some ν ∈ Q.
There is at least one Energy-Lattice of optΓ ΣM
0 :
M
∗
XΓ∗ , {πG(Γ
w−ν ,σ ) | σ0 ∈ optΓ Σ0 }.
0
w−ν
) ⊆ optΓ ΣM
Proof. The only non-trivial point to check being: f ∈XΓ∗ ∆M
0 .
0 ( f,Γ
∗
M
w−
ν
For this, we shall rely on Theorem 3. Let fˆ ∈ XΓ and σ̂0 ∈ ∆0 ( fˆ, Γ
) be fixed (arbitrarily).
∗
∗ ∈ opt ΣM . Therefore, the following holds:
for
some
σ
Since fˆ ∈ XΓ∗ , then fˆ = πG(Γ
∗
w−ν ,σ )
Γ 0
0

F

0

∗
∗
ˆ
πG(Γ
w−ν ,σ̂ ) = f = πG(Γw−ν ,σ ∗ ) .
0
0

∗
Clearly, σ̂0 is compatible with fˆ in the EG Γw−ν , because fˆ = πG(Γ
w−ν ,σ̂ ) . By Lemma 1, since
0
∗
w−ν
∗
σ0 is optimal, then G(Γ
, σ0 ) is conservative. Therefore:

V fˆ = Vπ ∗

G(Γw−ν ,σ0∗ )

= V.

Notice, σ̂0 satisfies exactly the hypotheses required by Theorem 3. Therefore, σ̂0 ∈ optΓ ΣM
0 .
F
M ( f , Γw−ν ), and concludes the proof.
∗
This proves (*).This also shows optΓ ΣM
=
∆
✷
f ∈X
0
0
Γ

Proposition 7. Let the MPG Γ be ν -valued, for some ν ∈ Q. Let XΓ∗ 1 and XΓ∗ 2 be two Energy∗
∗
Lattices for optΓ ΣM
0 . Then, XΓ 1 = XΓ 2 .
Proof. By symmetry, it is sufficient to prove that XΓ∗ 1 ⊆ XΓ∗ 2 . Let f1 ∈ XΓ∗ 1 be fixed (arbitrarM
M
∗
∗
ily). Then, f1 = πG(Γ
w−ν ,σ̂ ) for some σ̂0 ∈ optΓ Σ0 . Since σ̂0 ∈ optΓ Σ0 and since XΓ 2 is an
0
∗
w−ν
Energy-Lattices, there exists f2 ∈ XΓ∗ 2 s.t. σ̂0 ∈ ∆M
), which implies πG(Γ
w−ν ,σ̂ ) = f 2 .
0 ( f2 , Γ
0
∗
∗
✷
Thus, f1 = πG(Γw−ν ,σ̂ ) = f2 . This implies f1 ∈ XΓ 2 .
0

The next theorem summarizes the main point of this section.
M
∗
Theorem 4. Let Γ be a ν -valued MPG, for some ν ∈ Q. Then, XΓ∗ , {πG(Γ
w−ν ,σ ) | σ0 ∈ optΓ Σ0 }
0
is the unique Energy-Lattice of optΓ ΣM
0 .

Proof. By Proposition 6 and Proposition 7.

✷
10

Example 1. Consider the MPG Γex , as defined in Fig. 1. Then, XΓ∗ex = { f ∗ , f1 , f2 }, where f ∗
w+1 , and where the following holds: f (A) = f (A) =
is the least-SEPM of the reweighted EG Γex
1
2
∗
∗
f (A) = 0; f1 (B) = f2 (B) = f (B) = 4; f1 (C) = f2 (C) = f ∗ (C) = 8; f1 (D) = f2 (D) = f ∗ (D) =
4; f1 (F) = f2 (F) = f ∗ (F) = 4; f1 (G) = f2 (G) = f ∗ (G) = 0; finally, f ∗ (E) = 0, f1 (E) = 3,
f2 (E) = 7. An illustration of f1 is offered in Fig. 3a (energy-levels are depicted in circled boldface). whereas f2 is depicted in Fig. 3b. Notice that f ∗ (v) ≤ f1 (v) ≤ f2 (v) for every v ∈ V , and
this ordering relation is illustrated in Fig. 3.

4

+4
0

A

−4

B

+4
8

+1
D

C

4

+1
+1

3

+1

E

−4

−4

+4

4
F

G

0

0

+4

−4

4

(a) The extremal-SEPM f1 of

A

B

8

+1
D

+1

+4
C

+1

7
E

+1

−4

−4
4
F

G

0

+4

4

Γw+1
ex

(b) The extremal-SEPM f2 of Γw+1
ex .

Definition 3. Each element f ∈ XΓ∗ is called extremal-SEPM.
The next lemma is the converse of Lemma 1.
Lemma 2. Let the MPG Γ be ν -valued, for some ν ∈ Q. Consider any σ0 ∈ ΣM
0 (Γ), and assume
.
that G(Γw−ν , σ0 ) is conservative. Then, σ0 ∈ optΓ ΣM
0
Proof. Let C = (v1 , . . . , vℓ v1 ) any cycle
the following holds (if vℓ+1 = v1 ):
 in G(Γ, σ0 ). Then,


w(C)
1 ℓ
1 ℓ
1 ℓ
ℓ = ℓ ∑i=1 w(vi , vi+1 ) = ν + ℓ ∑i=1 w(vi , vi+1 ) − ν ≥ ν , where ℓ ∑i=1 w(vi , vi+1 ) − ν ≥ 0

holds because G(Γw−ν , σ0 ) is conservative. By Proposition 1, since w(C)/ℓ ≥ ν for every cycle
✷
C in GσΓ0 , then σ0 ∈ optΓ ΣM
0 .
The following proposition asserts some properties of the extremal-SEPMs.

Proposition 8. Let the MPG Γ be ν -valued, for some ν ∈ Q. Let XΓ∗ be the Energy-Lattice of
w−ν . Then, the following
optΓ ΣM
0 . Moreover, let f : V → CΓ be a SEPM for the reweighted EG Γ
three properties are equivalent:
1. f ∈ XΓ∗ ;
∗
2. There exists σ0 ∈ optΓ ΣM
0 s.t. πG(Γw−ν ,σ ) (v) = f (v) for every v ∈ V .
0

w−ν ) 6= 0;
3. V f = W0 (Γw−ν ) = V and ∆M
/
0 ( f,Γ

M
∗
Proof of (1 ⇐⇒ 2). Indeed, XΓ∗ = {πG(Γ
w−ν ,σ ) | σ0 ∈ optΓ Σ0 }.
0

✷

∗
Proof of (1 ⇒ 3). Assume f ∈ XΓ∗ . Since (1 ⇐⇒ 2), there exist σ0 ∈ optΓ ΣM
0 s.t. πG(Γw−ν ,σ0 ) =
ν
M
w−
ν
w−
ν
M
w−
f . Thus, σ0 ∈ ∆0 ( f , Γ
), so that ∆0 ( f , Γ
) 6= 0.
/ We claim V f = W0 (Γ
) = V . Since
∀(v ∈ V ) valΓ (v) = ν , then W0 (Γw−ν ) = V by Proposition 2. Next, G(Γw−ν , σ0 ) is conservative
11

w−ν ) = {σ }
∆M
0 ( f1 , Γ
0
(4)

4

B

+4
A

0

−4

8

+1

+4
+1
C

+1
7
E

+1

4

−4

F

(4)

G

σ0 (D) = A

f2

0

(4)

σ0 (E) = C

+4

−4

D

(4)
σ0 (B) = C

(4)

σ0 (G) = F

4

w−ν ) = {σ }
∆M
0 ( f1 , Γ
0
(3)

4

+4
0

A

−4

B
8

+1
D

+4
+1
C

+1
3
E

+1

(3)

4

σ0 (B) = C

−4

F

G

(3)
σ0 (D) = A

f1

0

(3)

σ0 (E) = F

+4

−4

(3)

σ0 (G) = F

4

∗ w−ν ) = {σ , σ }
∆M
0 ( f ,Γ
0
0
(1)

4

+4
0

A

−4

B
8

+1
D

+4
+1
C
−4

+1
0
E

+1

4

F

(1)

σ0 (B) = C

σ0 (D) = A

(1)

σ0 (D) = A

(1)
σ0 (E) = A

(2)
σ0 (E) = G

σ0 (B) = C

−4
G

f∗

0

+4

(1)

σ0 (G) = F

4

(2)

(2)

(2)

(2)

σ0 (G) = F

Figure 3: The decomposition of optΓ ΣM
0 (right), for the MPG Γex , which corresponds to the
Energy-Lattice XΓ∗ex = { f ∗ , f1 , f2 } (center) (as in Example 1). Here, f ∗ ≤ f1 ≤ f2 . This brings
a lattice DΓ∗ex of 3 basic subgames of Γex (left).
∗
by Lemma 1. Since G(Γw−ν , σ0 ) is conservative and f = πG(Γ
w−ν ,σ ) , then V f = V . Therefore,
0
✷
V f = W0 (Γw−ν ) = V .
w−ν ); so, f = π ∗
w−ν ) 6= 0,
Proof of (1 ⇐ 3). Since ∆M
/ pick some σ0 ∈ ∆M
0 ( f,Γ
0 ( f,Γ
G(Γw−ν ,σ0 ) .
w−ν
∗
w−ν
, σ0 ) is conservative. Since G(Γ
, σ0 ) is conSince V f = V and f = πG(Γw−ν ,σ ) , then G(Γ
0
∗
M
M
servative, then σ0 ∈ optΓ Σ0 by Lemma 2. Since f = πG∗ and σ0 ∈ optΓ Σ0 , then f ∈ XΓ∗
because 2 ⇒ 1.
✷

5. A Recursive Enumeration of XΓ∗ and optΓ ΣM
0



An enumeration algorithm for a set S provides an exhaustive listing of all the elements of S
(without repetitions). As mentioned in Section 4, by Theorem 1, no loss of generality occurs if
we assume Γ to be ν -valued for some ν ∈ Q. One run of the algorithm given in Comin and Rizzi
(2016b) allows one to partition an MPG Γ, into several domains Γi each one being νi -valued
for νi ∈ SΓ ; in O(|V |2 |E|W ) time and linear space. Still, by Proposition 5, Theorem 3 is not
M ∗ w−ν ) where f ∗ is
sufficient for enumerating the whole optΓ (ΣM
ν
0 ); it is enough only for ∆0 ( f ν , Γ
12

the least-SEPM of Γw−ν , which is just the join/top component of optΓ (ΣM
0 ). However, thanks to
∗
Theorem 4, we now have a refined description of optΓ ΣM
in
terms
X
.
0
Γ
We offer a recursive enumeration of all the extremal-SEPMs, i.e., XΓ∗ , and for computing
the corresponding partitioning of optΓ ΣM
0 . In order to avoid duplicate elements in the enumeration, the algorithm needs to store a lattice BΓ∗ of subgames of Γ, which is related to XΓ∗ . We
assume to have a data-structure TΓ supporting the following operations, given a subarena Γ′ of
Γ: insert(Γ′ , TΓ ) stores Γ′ into TΓ ; contains(Γ′ , TΓ ) returns T if and only if Γ′ is in TΓ , and F
otherwise. A simple implementation of TΓ goes by indexing NΓout
′ (v) for each v ∈ V (e.g., with a
trie data-structure). This can run in O(|E| log |V |) time, consuming O(|E|) space per stored item.
Similarly, one can index SEPMs in O(|V | log(|V |W )) time and O(|V |) space per stored item.
The listing procedure is named enum(), it takes a ν -valued MPG Γ and goes as follows.
1. Compute the least-SEPM f ∗ of Γ, and print Γ to output. Theorem 3 can be employed at
∗ w−ν ): indeed, these are all and only those positional
this stage for enumerating ∆M
0 ( f ,Γ
strategies lying in the Cartesian product of all the arcs (u, v) ∈ E that are compatible with
f ∗ in Γw−ν (because f ∗ is the least-SEPM of Γ).
2. Let St ← 0/ be an empty stack of vertices.
3. For each û ∈ V0 , do the following:
• Compute Eû ← {(û, v) ∈ E | f ∗ (û) ≺ f ∗ (v) ⊖ (w(û, v) − ν )};
• If Eû 6= 0,
/ then:
– Let E ′ ← Eû ∪ {(u, v) ∈ E | u 6= û} and Γ′ ← (V, E ′ , w, hV0 ,V1 i).
– If contains(Γ′ , TΓ ) = F, do the following:
∗ Compute the least-SEPM f ′ ∗ of Γ′ w−ν ;
∗ If V f ′ ∗ = V :
– Push û on top of St and insert(Γ′ , TΓ ).
– If contains( f ′ ∗ , TΓ ) = F, then insert( f ′ ∗ , TΓ ) and print f ′ ∗ .
4. While St 6= 0:
/
• pop û from St; Let Eû ← {(û, v) ∈ E | f ∗ (û) ≺ f ∗ (v) ⊖ (w(û, v) − ν )}, and E ′ ←
Eû ∪ {(u, v) ∈ E | u 6= û}, and Γ′ ← (V, E ′ , w, hV0 ,V1 i);
• Make a recursive call to enum() on input Γ′ .
Down the recursion tree, when computing least-SEPMs, the children Value-Iterations can amortize by starting from the energy-levels of the parent. The lattice of subgames BΓ∗ comprises
all and only those subgames Γ′ ⊆ Γ that are eventually inserted into TΓ at Step (3) of enum();
these are called the basic subgames of Γ. The correctness of enum() follows by Theorem 4 and
Theorem 3. In summary, we obtain the following result.
Theorem 5. There exists a recursive algorithm for enumerating (w/o repetitions) all elements
3
of BΓ∗ with time-delay2 O(|V
Γ; moreover, the algorithm works with
 | |E|W ), on any input MPG
∗
O(|V ||E|) + Θ |E||BΓ |) space. So, it enumerates XΓ∗ (w/o repetitions) in O |V |3 |E|W |BΓ∗ |
total time, and O(|V ||E|) + Θ |E||BΓ∗ | space.
2

A listing algorithm has O( f (n)) time-delay when the time spent between any two consecutives is O( f (n)).

13

To conclude we observe that BΓ∗ and XΓ∗ are not isomorphic as lattices, not even as sets
(the cardinality of BΓ∗ can be greater that that of XΓ∗ ). Indeed, there is a surjective antitone
mapping ϕΓ from BΓ∗ onto XΓ∗ , (i.e., ϕΓ sends Γ′ ∈ BΓ∗ to its least-SEPM fΓ∗′ ∈ XΓ∗ ); still, we
can construct instances of MPGs such that |BΓ∗ | > |XΓ∗ |, i.e., ϕΓ is not into and BΓ∗ , XΓ∗ are not
isomorphic. That would be a case of degeneracy, and an example MPG Γd is given in Fig. 4.
0

0

u2

v2

0
−2
u3

1

0

0

0

u1

v1

0

−10
0

−2

0

−1

v3

−1
t

1

0

0

0

u4

v4

0

0

0

u5

0
v5

0

0

Figure 4: An MPG Γd for which |BΓ∗ | > |XΓ∗ |.

0

0

u2

0
−2
2

u3

0
v2

0

0

u1

0
v1

0

0

−1
−10

−2
2

2

0

u5

0

0
v1

0

0

−1

−2
v3

−1
t

0

u4

0

0

v4

0

0

u5

0

2

0

10

0

v5

0

0
u1

−10
0
v4

0

u3

0

u4

0

−2

v3

−1
t

v2

0

10

0

0

u2

0
v5

0

0

Figure 5: Two basic subgames Γ1d 6= Γ2d of Γd , having the same least-SEPM f1∗ = f2∗ .
In the MPG Γd , Player 0 has to decide how to move only at u3 , v3 and t; the remaining moves are forced. The least-SEPM f ∗ of Γd is: f ∗ (u3 ) = 1, f ∗ (v3 ) = 1, f ∗ (t) = 0, and
∀x∈VΓ \{u3 ,v3 ,t} f ∗ (x) = 0; leading to the following memory-less strategy: σ0∗ (u3 ) = t, σ0∗ (v3 ) = t,
d
σ0∗ (t) = v4 . Then, consider the lattice of subgames BΓ∗ d ; particularly, consider the following two
basic subgames Γ1d , Γ2d : let Γ′d be the arena obtained by removing the arc (t, v4 ) from Γd ; let Γ1d be
the arena obtained by removing the arc (u3 ,t) from Γ′d ; let Γ2d be the arena obtained by removing
the arc (v3 ,t) from Γ′d . See Fig. 5 for an illustration. Next, let f1∗ , f2∗ be the least-SEPMs of Γ1d
and Γ2d , respectively; then, f1∗ (u3 ) = f2∗ (u3 ) = 2, f1∗ (v3 ) = f2∗ (v3 ) = 2, f1∗ (t) = f2∗ (t) = 10, and
∀x∈VΓ \{u3 ,v3 ,t} f1∗ (x) = f2∗ (x) = 0. Thus, Γ1d 6= Γ2d , but f1∗ = f2∗ ; this proves that Γd is degenerate
d
and that BΓ∗ , XΓ∗ are not isomorphic.

14

6. Conclusion
We observed a unique complete decomposition of optΓ ΣM
0 in terms of extremal-SEPMs in
reweighted EGs, also offering a pseudo-polynomial total-time recursive algorithm for enumerating (w/o repetitions) all the elements of XΓ∗ , i.e., all extremal-SEPMs, and for computing the
components of the corresponding partitioning BΓ∗ of optΓ ΣM
0 .
It would be interesting to study further properties enjoyed by BΓ∗ and XΓ∗ ; and we ask for
more efficient algorithms for enumerating XΓ∗ , e.g., pseudo-polynomial time-delay and polynomial space enumerations.
Acknowledgments. This work was supported by Department of Computer Science, University
of Verona, Verona, Italy, under PhD grant “Computational Mathematics and Biology”, on a cotutelle agreement with LIGM, Université Paris-Est in Marne-la-Vallée, Paris, France.
References
A. Ehrenfeucht, J. Mycielski, Positional strategies for mean payoff games, International Journal of Game Theory 8 (2)
(1979) 109–113.
U. Zwick, M. Paterson, The Complexity of Mean Payoff Games on Graphs, Theoretical Computer Science 158 (1996)
343–359.
M. Jurdziński, Deciding the winner in parity games is in UP ∩ co-UP, Information Processing Letters 68 (3) (1998) 119
– 124.
V. Gurvich, A. Karzanov, L. Khachiyan, Cyclic games and an algorithm to find minimax cycle means in directed graphs,
USSR Computational Mathematics and Mathematical Physics 28 (5) (1988) 85 – 91.
A. Chakrabarti, L. de Alfaro, T. Henzinger, M. Stoelinga, Resource Interfaces, in: R. Alur, I. Lee (Eds.), Embedded
Software, vol. 2855 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 117–133, 2003.
P. Bouyer, U. Fahrenberg, K. Larsen, N. Markey, J. Srba, Infinite Runs in Weighted Timed Automata with Energy
Constraints, in: F. Cassez, C. Jard (Eds.), Formal Modeling and Analysis of Timed Systems, vol. 5215 of Lecture
Notes in Computer Science, Springer Berlin Heidelberg, 33–47, 2008.
L. Brim, J. Chaloupka, L. Doyen, R. Gentilini, J. Raskin, Faster Algorithms for Mean-Payoff Games, Formal Methods
in System Design 38 (2) (2011) 97–118.
C. Comin, R. Rizzi, Energy Structure and Improved Complexity Upper Bound for Optimal Positional Strategies in Mean
Payoff Games, in: 3rd International Workshop on Strategic Reasoning, vol. 20, 2015.
C. Comin, R. Rizzi, Improved Pseudo-polynomial Bound for the Value Problem and Optimal Strategy Synthesis in Mean
Payoff Games, Algorithmica (February, 2016a) 1–27.
C. Comin, R. Rizzi, Faster O(|V |2 |E|W )-Time Energy Algorithm for Optimal Strategy Synthesis in Mean Payoff Games,
CoRR abs/1609.01517.
H. Björklund, S. Sandberg, S. Vorobyov, Memoryless determinacy of parity and mean payoff games: a simple proof,
Theoretical Computer Science 310 (1–3) (2004) 365 – 378.
R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley
Longman Publishing Co., Inc., Boston, MA, USA, 2nd edn., 1994.

15

