|\leavevmode\nobreak\ x_{j}\geq\lambda(v)\mathrm{\leavevmode\nobreak\
with\leavevmode\nobreak\ }v\in V_{j}\right\\}.$

The set $X$, intersection of a polyhedron and a polytope, is a polytope:
therefore, there exists a vertex $\bar{x}$ of that polytope which minimizes
$x_{i}$ for $\bar{x}\in X$. That vertex is the intersection between a face of
the greater polytope $P=\underset{c\in C}{\mathrm{Conv}}\leavevmode\nobreak\
\mu(c^{\omega})$, and some of the hyperplanes $H_{v}$ (possibly zero), defined
as the hyperplanes of equation $x_{j}=\lambda(v)$ for $j\in\Pi$ controlling
$v$, such that $\lambda(v)=\underset{w\in M\cap V_{j}}{\max}\lambda(w)$.

######  Example 9.

With three cycles and two players against player $i$, each controlling one
vertex $v$ such that $\lambda(v)=0$, the vertex $\bar{x}$ is the red point in
Figure 7 and Figure 8.

$j_{1}$$i$$j_{2}$$\bullet$ Figure 7: The intersection between a
$0$-dimensional face and zero hyperplane $j_{1}$$i$$j_{2}$$\bullet$ Figure 8:
The intersection between a $2$-dimensional face and two hyperplanes

The set of vertices of the polyhedron $X$ is included in the finite set:

$Y=\left\\{\bar{y}_{WD}\in\mathbb{R}^{\Pi\cup\\{\star\\}}\leavevmode\nobreak\
\left|\leavevmode\nobreak\ \begin{matrix}W\subseteq M,\leavevmode\nobreak\
D\subseteq C,\\\ \underset{c\in D}{\mathrm{Conv}}\leavevmode\nobreak\
\mu(c^{\omega})\cap\underset{w\in W}{\bigcap}H_{w}=\\{\bar{y}_{WD}\\}\\\
\mathrm{and\leavevmode\nobreak\ }\forall j,\leavevmode\nobreak\ \forall v\in
M\cap V_{j},\\\ y_{WDj}\geq\lambda(v)\end{matrix}\right.\right\\},$

where the tuple $\bar{y}_{WD}$ is the intersection of the face of $P$
delimited by the values of the cycles of $D$, and the hyperplanes $H_{v}$ for
$v\in W$, as states the condition $\underset{c\in
D}{\mathrm{Conv}}\leavevmode\nobreak\ \mu(c^{\omega})\cap\underset{w\in
W}{\bigcap}H_{w}=\\{\bar{y}_{WD}\\}$.

The condition $\forall j,\forall v\in M\cap V_{j},y_{WDj}\geq\lambda(v)$
states that the vertex $\bar{y}_{WD}$ is, moreover, the outcome of a
$\lambda$-consistent play of $G$, which guarantees that this set $Y$ is itself
included in $X$.

We have, therefore:

$\mathrm{opt}(K)=\min\\!^{\star}\underset{c\in
C}{\mathrm{Conv}}\leavevmode\nobreak\ \mu(c^{\omega})=\min_{\bar{y}\in
Y}y_{i}.$

Let now $\bar{y}\in Y$, and let $W$ and $D$ be such that
$\bar{y}=\bar{y}_{WD}$.

Let us choose $D$ and $W$ minimal, so that each player $j\in\Pi$ controls at
most one state $w\in W$, and so that there exists only one decomposition:

$\bar{y}=\underset{c\in D}{\sum}\alpha_{c}\mu(c^{\omega})$

with $0<\alpha_{c}<1$ for each $c$, and $\sum_{c}\alpha_{c}=1$. Furthermore,
$\bar{y}$ is the only such solution of the system of equations:

$\forall j\in\Pi,\forall w\in W\cap V_{j},y_{j}=\lambda(w).$

Therefore, the vector $\bar{\alpha}=(\alpha_{c})_{c\in D}$ is the only
solution of the system:

$\left\\{\begin{matrix}\underset{c\in D}{\sum}\alpha_{c}=1\\\ \forall
j\in\Pi,\forall w\in W\cap V_{j},\underset{c\in
D}{\sum}\alpha_{c}\mu_{j}(c^{\omega})=\lambda(w)\\\ \forall c\in
D,\alpha_{c}>0.\end{matrix}\right.$

Then, if $\oplus$ is a symbol and $A_{WD}$ is the matrix:

$A_{WD}=\left(\left\\{\begin{matrix}1&\mathrm{if\leavevmode\nobreak\
}w=\oplus\\\ \mu_{j}(c^{\omega})&\mathrm{else,\leavevmode\nobreak\
with\leavevmode\nobreak\ }w\in
V_{j}\end{matrix}\right.\right)_{\tiny{\begin{matrix}w\in
W\cup\\{\oplus\\},\\\ c\in D\end{matrix}}}$

then $A_{WD}$ is invertible and:

$\bar{\alpha}=A_{WD}^{-1}\left(\left\\{\begin{matrix}1&\mathrm{if\leavevmode\nobreak\
}w=\oplus\\\ \lambda(w)&\mathrm{otherwise}\end{matrix}\right.\right)_{w\in
W\cup\\{\oplus\\}},$

with $\alpha_{c}>0$ for all $c\in D$.

Let us write:

$\bar{\beta}_{\lambda
W}=\left(\left\\{\begin{matrix}1&\mathrm{if\leavevmode\nobreak\ }j=\oplus\\\
\lambda(w)&\mathrm{otherwise}\end{matrix}\right.\right)_{w\in
W\cup\\{\oplus\\}}.$

We have, thus, $\bar{\alpha}=A_{WD}^{-1}\bar{\beta}_{\lambda W}$.

Let us write, for each player $j$,
$\bar{\gamma}_{D}^{j}=(\mu_{j}(c^{\omega}))_{c\in D}$. Then, we can write:

$\begin{matrix}y_{i}&=&\sum_{c}\alpha_{c}\mu_{i}(c^{\omega})\\\
&=&\\!{}^{\mathrm{t}}\bar{\gamma}_{D}^{i}\leavevmode\nobreak\ \bar{\alpha}\\\
&=&\\!{}^{\mathrm{t}}\bar{\gamma}_{D}^{i}\leavevmode\nobreak\
A_{WD}^{-1}\leavevmode\nobreak\ \bar{\beta}_{\lambda W}.\end{matrix}$

Finally, if we write:

$B_{W}=\left(\left\\{\begin{matrix}1&\mathrm{if\leavevmode\nobreak\ }w=v\\\
0&\mathrm{otherwise}\end{matrix}\right.\right)_{w\in W\cup\\{\oplus\\},v\in
V}$

and:

$\delta\mspace{-9.0mu}\bar{\phantom{v}}_{W}=\left(\left\\{\begin{matrix}1&\mathrm{if\leavevmode\nobreak\
}w=\oplus\\\ 0&\mathrm{otherwise}\end{matrix}\right.\right)_{w\in
W\cup\\{\oplus\\}}$

we have $\bar{\beta}_{\lambda
W}=B_{W}\lambda\mspace{-10.0mu}\bar{\phantom{v}}+\delta\mspace{-9.0mu}\bar{\phantom{v}}_{W}$,
and therefore:

$y_{i}=\\!^{\mathrm{t}}\bar{\gamma}_{D}^{i}\leavevmode\nobreak\
A_{WD}^{-1}\leavevmode\nobreak\ (B_{W}\leavevmode\nobreak\
\lambda\mspace{-10.0mu}\bar{\phantom{v}}+\delta\mspace{-9.0mu}\bar{\phantom{v}}_{W}).$

Conversely, the tuple $\bar{y}$ defined by, for each $j\in\Pi$,

$y_{j}=\\!^{\mathrm{t}}\bar{\gamma}_{D}^{j}\leavevmode\nobreak\
A_{WD}^{-1}\leavevmode\nobreak\ (B_{W}\leavevmode\nobreak\
\lambda\mspace{-10.0mu}\bar{\phantom{v}}+\delta\mspace{-9.0mu}\bar{\phantom{v}}_{W})$

for given $W\subseteq M$ and $D\subseteq C$, is an element of the set $Y$ if
and only if:

  * •

the intersection $\underset{c\in D}{\mathrm{Conv}}\leavevmode\nobreak\
\mu(c^{\omega})\cap\underset{w\in W}{\bigcap}H_{w}$ is a singleton, i.e. the
matrix $A_{WD}$ is invertible (otherwise the matrix $A_{WD}^{-1}$ is not
defined);

  * •

$\bar{y}\in\underset{c\in D}{\mathrm{Conv}}\leavevmode\nobreak\
\mu(c^{\omega})$, i.e. the tuple $\bar{\alpha}=A_{WD}^{-1}\leavevmode\nobreak\
(B_{W}\leavevmode\nobreak\
\lambda\mspace{-10.0mu}\bar{\phantom{v}}+\delta\mspace{-9.0mu}\bar{\phantom{v}}_{W})$
has only non-negative coordinates (actually positive if $D$ is minimal);

  * •

for each player $j$, for each vertex $v\in M\cap V_{j}$, we have
$y_{j}\geq\lambda(v)$, i.e.
$\\!{}^{\mathrm{t}}\gamma_{D}^{j}A_{WD}^{-1}(B_{W}\lambda\mspace{-10.0mu}\bar{\phantom{v}}+\delta\mspace{-9.0mu}\bar{\phantom{v}}_{W})\geq\lambda(v)$.

We finally find the formula:

$\mathrm{nego}(\lambda)(v_{0})=\max_{\tiny{\tau_{\mathbb{C}}\in\mathrm{ML}\left(\mathrm{Conc}_{\lambda_{0}i}(G)\right)}}\leavevmode\nobreak\
\min_{\tiny{\begin{matrix}K\in\mathrm{SConn}\left(\mathrm{Conc}_{\lambda_{0}i}(G)[\tau_{\mathbb{C}}]\right)\\\
\mathrm{accessible\leavevmode\nobreak\ from\leavevmode\nobreak\
}(v_{0},\\{v_{0}\\})\end{matrix}}}\left\\{\begin{matrix}\mathrm{if\leavevmode\nobreak\
}K\mathrm{\leavevmode\nobreak\ contains\leavevmode\nobreak\
dev.}:&\underset{c\in\mathrm{SC}(K)}{\min}\leavevmode\nobreak\
\hat{\mu}_{\star}(c^{\omega})\\\ \mathrm{otherwise}:&\min
S_{K},\end{matrix}\right.$

where $S_{K}$ is the set of real numbers of the form:

$\\!{}^{\mathrm{t}}\bar{\gamma}_{D}^{i}A^{-1}_{WD}(B_{W}\lambda\mspace{-10.0mu}\bar{\phantom{v}}+\delta\mspace{-9.0mu}\bar{\phantom{v}}_{W})$

with:

  * •

$W\subseteq M$, common memory of the states of $K$;

  * •

$D\subseteq C$, set of the cycles of the form $\dot{c}$, where $c$ is a simple
cycle of $K$;

  * •

the matrix $A_{WD}$ is invertible;

  * •

the vector
$A_{WD}^{-1}(B_{W}\lambda\mspace{-10.0mu}\bar{\phantom{v}}+\delta\mspace{-9.0mu}\bar{\phantom{v}}_{W})$
has only positive coordinates;

  * •

and for each $j\in\Pi$, for each $v\in M_{K}\cap V_{j}$, we have
$\\!{}^{\mathrm{t}}\bar{\gamma}_{D}^{j}A^{-1}_{WD}(B_{W}\lambda\mspace{-10.0mu}\bar{\phantom{v}}+\delta\mspace{-9.0mu}\bar{\phantom{v}}_{W})\geq\lambda(v)$.

This is, indeed, the expression of a piecewise linear function.

Computing a complete and effective expression of that function can be done by
constructing all the concrete games
$\mathrm{Conc}_{\lambda_{0}i}(G)_{\upharpoonright(v_{0},\\{v_{0}\\})}$ for
$i\in\Pi$ and $v_{0}\in V_{i}$ (there are as many of them as there are
vertices in $G$, and their size is exponential in the size of $G$, hence so is
the time that one needs for their construction), and then applying the formula
above for each memoryless strategy of Challenger (their number is exponential
in the size of the concrete game, i.e. double exponential in the size of $G$)
and each strongly connected component of the induced graph (their number is
bounded by the size of the concrete game). For each $K$, the computation of
$\mathrm{opt}(K)$ with the formula given above requires only elementary
operations on matrices and vectors, that can all be done in polynomial time:
therefore, the effective construction of $\mathrm{nego}$ as a piecewise linear
function requires a time double exponential in the size of $G$. ∎

##  Appendix L Proof of Theorem 5

Theorem 5. _The SPE constrained existence problem is NP-hard._

###### Proof.

We proceed by reduction from the NP-complete problem SAT. This proof is
liberally inspired from the proof of the NP-hardness of the NE constrained
existence problem in co-Büchi games by Michael Ummels, in [21].

Let $\varphi=\bigwedge_{i=1}^{n}\bigvee_{j=1}^{m}L_{ij}$ be a formula from
propositional logic, written in conjunctive normal form, over the finite
variable set $X$. We construct a mean-payoff game
$G^{\varphi}_{\upharpoonright v_{0}}$ that admits an SPE where the player
$\mathbb{P}$ gets the payoff $1$, if and only if $\varphi$ is satisfiable.

First, we define the set of players $\Pi=\\{\mathbb{P}\\}\cup X$: every
variable of $\varphi$ is a player and there is an additional special player
$\mathbb{P}$, called _Prover_ , who wants to prove that $\varphi$ is
satisfiable.

Then, let us define the state space: for each clause $C_{i}$, with
$i\in\mathbb{Z}/n\mathbb{Z}$, of $\varphi$, we define a state $C_{i}$ that is
controlled by Prover, and for each litteral $L_{ij}$ of $C_{i}$ we define a
state $(C_{i},L_{ij})$, that is controlled by the player $x$ such that
$L_{ij}=x$ or $\neg x$. We add a transition from $C_{i}$ to $(C_{i},L_{ij})$,
and another one from $(C_{i},L_{ij})$ to $C_{i+1}$. Moreover, we add a sink
state $\bot$, with a transition from it to itself, and transitions from all
the states of the form $(C,\neg x)$ to it.

We define the weight function $\pi$ on this game as follows:

  * •

$\pi_{\mathbb{P}}(\bot\bot)=0$, and $\pi_{\mathbb{P}}(uv)=1$ for any other
transition $vw$;

  * •

for each player $x$, we have $\pi_{x}(uv)=0$ for every transition leading to a
state of the form $v=(C,x)$, and $\pi_{x}(uv)=1$ for any other transition.

Note that Prover can only get the payoffs $0$ (in a play that reaches $\bot$)
or $1$ (in any other play). Another player $x$ gets the payoff $1$ in a play
that never visits (or finitely often, or infinitely often but with negligible
frequence) a vertex of the form $(C,x)$. Otherwise, he may get any payoff
between $0.5$ and $1$, depending on the frequence with which such a state is
visited.

Finally, we initialize that game in $v_{0}=C_{1}$.

######  Example 10.

The game $G^{\varphi}$, when $\varphi$ is the tautology $(x_{1}\vee\neg
x_{1})\wedge\dots\wedge(x_{6}\vee\neg x_{6})$, is represented by Figure 9.
When the weights of an edge are not written, they are equal to $1$ for all
players.

$C_{1}$$x_{1}$$\neg x_{1}$$C_{2}$$x_{2}$$\neg x_{2}$$C_{3}$$x_{3}$$\neg
x_{3}$$C_{4}$$x_{4}$$\neg x_{4}$$C_{5}$$x_{5}$$\neg x_{5}$$C_{6}$$x_{6}$$\neg
x_{6}$$\bot$$\stackrel{{\scriptstyle x_{1}}}{{0}}\stackrel{{\scriptstyle
x_{2}}}{{1}}\stackrel{{\scriptstyle x_{3}}}{{1}}\stackrel{{\scriptstyle
x_{4}}}{{1}}\stackrel{{\scriptstyle x_{5}}}{{1}}\stackrel{{\scriptstyle
x_{6}}}{{1}}\stackrel{{\scriptstyle\mathbb{P}}}{{1}}$$\stackrel{{\scriptstyle
x_{1}}}{{1}}\stackrel{{\scriptstyle x_{2}}}{{0}}\stackrel{{\scriptstyle
x_{3}}}{{1}}\stackrel{{\scriptstyle x_{4}}}{{1}}\stackrel{{\scriptstyle
x_{5}}}{{1}}\stackrel{{\scriptstyle
x_{6}}}{{1}}\stackrel{{\scriptstyle\mathbb{P}}}{{1}}$$\stackrel{{\scriptstyle
x_{1}}}{{1}}\stackrel{{\scriptstyle x_{2}}}{{1}}\stackrel{{\scriptstyle
x_{3}}}{{0}}\stackrel{{\scriptstyle x_{4}}}{{1}}\stackrel{{\scriptstyle
x_{5}}}{{1}}\stackrel{{\scriptstyle
x_{6}}}{{1}}\stackrel{{\scriptstyle\mathbb{P}}}{{1}}$$\stackrel{{\scriptstyle
x_{1}}}{{1}}\stackrel{{\scriptstyle x_{2}}}{{1}}\stackrel{{\scriptstyle
x_{3}}}{{1}}\stackrel{{\scriptstyle x_{4}}}{{0}}\stackrel{{\scriptstyle
x_{5}}}{{1}}\stackrel{{\scriptstyle
x_{6}}}{{1}}\stackrel{{\scriptstyle\mathbb{P}}}{{1}}$$\stackrel{{\scriptstyle
x_{1}}}{{1}}\stackrel{{\scriptstyle x_{2}}}{{1}}\stackrel{{\scriptstyle
x_{3}}}{{1}}\stackrel{{\scriptstyle x_{4}}}{{1}}\stackrel{{\scriptstyle
x_{5}}}{{0}}\stackrel{{\scriptstyle
x_{6}}}{{1}}\stackrel{{\scriptstyle\mathbb{P}}}{{1}}$$\stackrel{{\scriptstyle
x_{1}}}{{1}}\stackrel{{\scriptstyle x_{2}}}{{1}}\stackrel{{\scriptstyle
x_{3}}}{{1}}\stackrel{{\scriptstyle x_{4}}}{{1}}\stackrel{{\scriptstyle
x_{5}}}{{1}}\stackrel{{\scriptstyle
x_{6}}}{{0}}\stackrel{{\scriptstyle\mathbb{P}}}{{1}}$$\stackrel{{\scriptstyle
x_{1}}}{{1}}\stackrel{{\scriptstyle x_{2}}}{{1}}\stackrel{{\scriptstyle
x_{3}}}{{1}}\stackrel{{\scriptstyle x_{4}}}{{1}}\stackrel{{\scriptstyle
x_{5}}}{{1}}\stackrel{{\scriptstyle
x_{6}}}{{1}}\stackrel{{\scriptstyle\mathbb{P}}}{{0}}$ Figure 9: The game
$G^{\varphi}$

Now, let us prove that there is an SPE in $G^{\varphi}_{\upharpoonright
v_{0}}$ in which Prover gets the payoff $1$, if and only if the formula
$\varphi$ is satisfiable.

  * •

If such an SPE exists: let us write it $\bar{\sigma}$, and let
$\rho=\langle\bar{\sigma}\rangle_{C_{1}}$. Since $\mu_{\mathbb{P}}(\rho)=1$,
the sink state $\bot$ is never visited. Let us define a valuation $\nu$ on $X$
as follows: for each variable $x$, we have $\nu(x)=1$ if and only if
$\mu_{x}(\rho)<1$.

Now, let $C$ be a clause of $\varphi$: since $C$, as a state, is necessarily
visited infinitely often and with a fixed frequence in the play $\rho$
(because no player ever go to the sink state $\bot$), one of its successors,
say $(C,L)$, is visited with a non-negligible frequence (more formally, the
time between two occurrences of $(C,L)$ is bounded). If $L$ is a positive
litteral, say $x$, then by definition of $\nu$, we have $\nu(x)=1$ and the
clause $C$ is satisfied.

If $L$ has the form $\neg x$, then each time the state $(C,\neg x)$ is
traversed, player $x$ has the possibility to deviate and to go to the sink
state $\bot$, where he is sure to get the payoff $1$. Since $\bar{\sigma}$ is
an SPE, it means that he already gets the payoff $1$ in the play $\rho$. By
definition of $\nu$, we then have $\nu(x)=0$, hence the litteral $\neg x$ is
satisfied, hence so is the clause $C$.

The valuation $\nu$ satisfies all the clauses of $\varphi$, and therefore
satisfies the formula $\varphi$ itself.

  * •

If $\varphi$ is satisfied by some valuation $\nu$: let us define a strategy
profile $\bar{\sigma}$ by:

    * –

for each history $hC$ where $C$ is a clause of $\varphi$,
$\sigma_{\mathbb{P}}(hC)=(C,L)$ where $L$ is a litteral of $C$ that is
satisfied in the valuation $\nu$;

    * –

and for each history $h(C,\neg x)$ where $C$ is a clause of $\varphi$ and $x$
is a variable, $\sigma_{x}(h(C,\neg x))=\bot$ if and only if $\nu(x)=1$.

Any other state has only one successor, hence we now have completely defined a
strategy profile. Now, let us prove it is an SPE, in which Prover gets the
payoff $1$.

Let $hC$ be a history, where $C$ is a clause of $\varphi$. We want to prove
that $\bar{\sigma}_{\upharpoonright hC}$ is a Nash equilibrium, in which
Prover gets the payoff $1$. Let $\rho=\langle\bar{\sigma}_{\upharpoonright
hC}\rangle_{C}$. If $\mu_{\mathbb{P}}(\rho)<1$, i.e. if $\rho$ is of the form
$hD(D,\neg x)\bot^{\omega}$, then by definition of $\bar{\sigma}$ we have
$\nu(x)=0$. But then, we cannot have $\sigma_{\mathbb{P}}(D)=(D,\neg x)$:
contradiction. The play $\rho$ never reaches the state $\bot$, and Prover gets
the payoff $1$, and as a consequence she does not have any profitable
deviation.

Now, if another player $x$ has a profitable deviation, it means that he does
not get the payoff $1$ in $\rho$, and therefore that some state of the form
$(D,x)$ is visited infinitely often. But then, if Prover choose to go to the
state $(D,x)$, it means that the litteral $x$ is satisfied in $\nu$, i.e. that
$\nu(x)=1$. In that case, if some clause $D^{\prime}$ contains the litteral
$\neg x$, it is not a litteral satisfied by $\nu$, and therefore the strategy
$\sigma_{\mathbb{P}}$, as we defined it, never chooses the transition to the
state $(D^{\prime},\neg x)$, where player $x$ could have the possibility to
deviate from his strategy. Contradiction.

Finally, after a history of the form $h(C,L)$, either:

    * –

$L=\neg x$ with $\nu(x)=1$, and in that case, we have
$\langle\bar{\sigma}_{\upharpoonright
h(C,L)}\rangle_{(C,L)}=(C,L)\bot^{\omega}$, player $x$ gets the payoff $1$,
and no player has a profitable deviation;

    * –

or $L$ is a positive litteral, and then there exists only one transition from
the state $(C,L)$ to another clause $D$, and we go back to the previous case;

    * –

or $L=\neg x$ with $\nu(x)=0$, and in that case, we have $\sigma_{x}(C,L)=D$
where $D$ is the following clause, and by the first case the strategy profile
$\bar{\sigma}_{\upharpoonright h(C,\neg x)D}$ is a Nash equilibrium. Moreover,
since the litteral $\neg x$ is not satisfied in $\nu$, the play
$\langle\bar{\sigma}_{\upharpoonright h(C,\neg x)D}\rangle_{D}$ does never
traverse again any state of the form $(D^{\prime},\neg x)$, hence player $x$
wins, and therefore has no profitable deviation: the strategy profile
$\bar{\sigma}_{\upharpoonright h(C,\neg x)}$ is a Nash equilibrium.

The constrained SPE existence problem is NP-hard in mean-payoff games. ∎

##  Appendix M Construction of the automaton solving the SPE constrained
existence problem

In the proof of Theorem 6, we invoked a multi-mean-payoff automaton
$\mathcal{A}_{\lambda}$, defined from a requirement $\lambda$ and two
thresholds $\bar{x},\bar{y}\in\mathbb{Q}^{\Pi}$, that recognizes the language
of the plays $\rho\in V^{\omega}$ that are $\lambda$-consistent, and that
satisfy $\bar{x}\leq\mu(\rho)\leq\bar{y}$. We give here the details of its
construction.

  * •

The state space of $\mathcal{A}_{\lambda}$ is:

$Q=V\times 2^{V},$

where a state $(v,M)$ must be interpreted as follows: we are currently in the
vertex $v$, and we already traversed the states of the set $M$. The initial
state is $(v_{0},\\{v_{0}\\})$.

  * •

The automaton $\mathcal{A}_{\lambda}$ is $2\mathrm{card}\Pi$-dimensional, and
its dimension set is $\Pi\times\\{\lambda,0\\}$.

  * •

The transitions of $\mathcal{A}_{\lambda}$ are all the transitions of the
form:

$(v,M)(w,M\cup\\{w\\})$

where $vw\in E$. Each such transition is labelled by the vertex $v$ as a
letter of the alphabet $V$, and is weighted by:

    * –

$\pi_{i}(vw)-\underset{u\in M}{\max}\leavevmode\nobreak\ \lambda(u)$ on each
dimension $(i,\lambda)$;

    * –

$\pi_{i}(vw)$ on each dimension $(i,0)$.

  * •

A run $\rho$ of $\mathcal{A}_{\lambda}$ is accepting if its mean-payoff is
nonnegative along each dimension $(i,\lambda)$, and its mean-payoff along each
dimension $(i,0)$ belongs to the interval $[x_{i},y_{i}]$.

##  Appendix N Some examples of negotiation sequences

We gather in this section some examples that could be interesting for the
reader who would want to get a full overall view on the behaviour of the
negotiation function on the mean-payoff games. For all of them, we computed
the negotiation sequence, as defined in Appendix I. For some of them, we just
gave the negotiation sequence; for the most important ones, we gave a complete
explanation of how we computed it, using the abstract negotiation game, as
defined in Appendix D.

######  Example 11.

Let us take again the game of Example 2: let us give (in red) the values of
$\lambda_{1}=\mathrm{nego}(\lambda_{0})$, which correspond to the antagonistic
values.

$a$$c$$b$$d$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{1}}$$(\lambda_{1})$$1$$2$$1$$2$

At the second step, let us execute the abstract game on the state $a$, with
the requirement $\lambda_{1}$: whatever Prover proposes at first, Challenger
has the possibility to deviate and to reach the state $b$. Then, Prover has to
propose a $\lambda_{1}$-consistent play from the state $b$, i.e. a play in
which player $\Circle$ gets at least the payoff $2$: such a play necessarily
ends in the state $d$, and gives player $\Box$ the payoff $2$.

The other states keep the same values.

$a$$c$$b$$d$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{1}}$$(\lambda_{2})$$2$$2$$1$$2$

But then, at the third step, from the state $b$: whatever Prover proposes at
first, Challenger can deviate to reach the state $a$. Then, Prover has to
propose a $\lambda_{2}$-consistent play from $a$, i.e. a play in which player
$\Circle$ gets at least the payoff $2$: such a play necessarily end in the
state $d$, i.e. after possibly some prefix, Prover proposes the play
$abd^{\omega}$. But then, Challenger can always deviate to go back to the
state $a$; and the play which is thus created is $(ab)^{\omega}$ which gives
player $\Box$ the payoff $3$.

$a$$c$$b$$d$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{1}}$$(\lambda_{3})$$2$$3$$1$$2$

Finally, from the states $a$ and $b$, there exists no $\lambda_{3}$-consistent
play, and therefore no $\lambda$-rational strategy profile.

$a$$c$$b$$d$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{1}}$$(\lambda_{4})$$+\infty$$+\infty$$1$$2$

and for all $n\geq 4$, $\lambda_{n}=\lambda_{4}$.

######  Example 12.

In this example, we show a game that can be turned into a family of games,
where the negotiation function needs as many steps as there are states to
reach its limit: when the requirement changes in some state, it opens new
possibilities from the neighbour states, and so on.

$a$$b$$c$$d$$e$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{1}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{2}}$$(\lambda_{1})$$1$$0$$0$$0$$2$

$a$$b$$c$$d$$e$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{1}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{2}}$$(\lambda_{2})$$1$$1$$0$$2$$2$

$a$$b$$c$$d$$e$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{1}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{2}}$$(\lambda_{3})$$1$$1$$2$$2$$2$

$a$$b$$c$$d$$e$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{1}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{2}}$$(\lambda_{4})$$1$$2$$2$$2$$2$

$a$$b$$c$$d$$e$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{1}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{2}}$$(\lambda_{5})$$2$$2$$2$$2$$2$

and the requirement $\lambda_{5}$ is a fixed point of the negocation function.

######  Example 13.

In all the previous examples, all the games whose underlying graphs were
strongly connected contained SPEs. Here is an example of game with a strongly
connected underlying graph that does not contain SPEs.

$b$$c$$a$$d$$e$$f$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{1}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{4}}$$(\lambda_{1})$$1$$1$$3$$2$$2$$4$

$b$$c$$a$$d$$e$$f$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{1}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{4}}$$(\lambda_{2})$$2$$1$$3$$2$$2$$4$

$b$$c$$a$$d$$e$$f$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{1}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{4}}$$(\lambda_{3})$$2$$1$$3$$3$$2$$4$

$b$$c$$a$$d$$e$$f$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{1}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{4}}$$(\lambda_{4})$$+\infty$$+\infty$$+\infty$$+\infty$$+\infty$$+\infty$

######  Example 14.

This example shows how a new requirement can emerge from the combination of
several cycles.

Let $G$ be the following game:

$a$$b$$c$$d$$e$$f$$g$$(\lambda_{1})$$1$$1$$0$$0$$0$$0$$3$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$

At the first step, the requirement $\lambda_{1}$ captures the antagonistic
values.

Then, from the state $c$, if player $\Box$ forces the access to the state $b$,
then player $\Circle$ must get at least $1$: the worst play that can be
proposed to player $\Box$ is then $(babc)^{\omega}$, which gives player $\Box$
the payoff $\frac{3}{2}$.

From the state $f$, if player $\Box$ forces the access to the state $g$, then
the worst play that can be proposed to them is $g^{\omega}$.

$a$$b$$c$$d$$e$$f$$g$$(\lambda_{2})$$1$$1$$\frac{3}{2}$$0$$0$$2$$3$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$

Then, from the state $d$, if player $\Circle$ forces the access to the state
$c$, then player $\Box$ must get at least $\frac{3}{2}$: the worst play that
can be proposed to player $\Circle$ is then $(cccd)^{\omega}$, which gives
player $\Circle$ the payoff $\frac{1}{2}$.

At the same time, from the state $e$, player $\Circle$ can now force the acces
to the state $f$: then, the worst play that can be proposed to them is
$fg^{\omega}$.

$a$$b$$c$$d$$e$$f$$g$$(\lambda_{3})$$1$$1$$\frac{3}{2}$$\frac{1}{2}$$3$$2$$3$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$

But then, from the state $c$, player $\Box$ can now force the access to the
state $e$: then, the worst play that can be proposed to them is
$efg^{\omega}$.

$a$$b$$c$$d$$e$$f$$g$$(\lambda_{4})$$1$$1$$2$$\frac{1}{2}$$3$$2$$3$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$

And finally, from that point, if from the state $d$ player $\Circle$ forces
the access to the state $c$, then player $\Box$ must have at least the payof
$2$; and therefore, the worst play that can be proposed to player $\Circle$ is
now $(ccd)^{\omega}$, which gives her the payoff $\frac{2}{3}$.

$a$$b$$c$$d$$e$$f$$g$$(\lambda_{5})$$1$$1$$2$$\frac{2}{3}$$3$$2$$3$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$

The requirement $\lambda_{5}$ is a fixed point of the negotiation function.