# Comparison of Poisson structures on moduli spaces

Indranil Biswas  School of Mathematics, Tata Institute of Fundamental
Research, Homi Bhabha Road, Mumbai 400005, India<EMAIL_ADDRESS>,
Francesco Bottacin  Dipartimento di Matematica, Università degli Studi di
Padova, Via Trieste 63, 35121 Padova, Italy<EMAIL_ADDRESS>and  Tomás
L. Gómez  Instituto de Ciencias Matemáticas (CSIC-UAM-UC3M-UCM), Nicolás
Cabrera 15, Campus Cantoblanco UAM, 28049 Madrid, Spain<EMAIL_ADDRESS>
###### Abstract.

Let $X$ be a complex irreducible smooth projective curve, and let
${\mathbb{L}}$ be an algebraic line bundle on $X$ with a nonzero section
$\sigma_{0}$. Let ${\mathcal{M}}$ denote the moduli space of stable Hitchin
pairs $(E,\,\theta)$, where $E$ is an algebraic vector bundle on $X$ of fixed
rank $r$ and degree $\delta$, and
$\theta\,\in\,H^{0}(X,\,{\mathcal{E}nd}(E)\otimes K_{X}\otimes{\mathbb{L}})$.
Associating to every stable Hitchin pair its spectral data, an isomorphism of
${\mathcal{M}}$ with a moduli space ${\mathcal{P}}$ of stable sheaves of pure
dimension one on the total space of $K_{X}\otimes{\mathbb{L}}$ is obtained.
Both the moduli spaces ${\mathcal{P}}$ and ${\mathcal{M}}$ are equipped with
algebraic Poisson structures, which are constructed using $\sigma_{0}$. Here
we prove that the above isomorphism between ${\mathcal{P}}$ and
${\mathcal{M}}$ preserves the Poisson structures.

###### Key words and phrases:

Spectral data, Hitchin pair, Poisson structure, hypercohomology

###### 2010 Mathematics Subject Classification:

53D17, 53D30, 14H60, 14J60

##  1\. Introduction

Let $X$ be a complex irreducible smooth projective curve of genus $g$. Take an
algebraic line bundle $N$ on $X$ such that $N\otimes K^{-1}_{X}$ admits a
nonzero section, where $K_{X}$ is the canonical bundle of $X$; fix a section
$\sigma_{0}\,\in\,H^{0}(X,\,N\otimes K^{-1}_{X})\setminus\\{0\\}$. Fix
integers $r$ and $\delta$. Let ${\mathcal{M}}$ denote the moduli space of
stable pairs of the form $(E,\,\theta)$, where $E$ is an algebraic vector
bundle on $X$ of rank $r$ and degree $\delta$, and
$\theta\,\in\,H^{0}(X,\,{\mathcal{E}nd}(E)\otimes N)$. These are called
Hitchin pairs; when $N\,=\,K_{X}$, they are called Higgs bundles. The moduli
space ${\mathcal{M}}$ is nonempty if one of the following four assumptions
hold (cf. [Ma, Remark 3.4]):

  1. (1)

the genus $g$ of $X$ is at least $2$;

  2. (2)

$g\,=\,1$, $N\,=\,K_{X}$ and $\gcd(r,\,\delta)\,=\,1$;

  3. (3)

$g\,=\,1$ and $\deg(N\otimes K_{X}^{-1})\,>\,0$; and

  4. (4)

$g=0$ and $\deg(N\otimes K_{X}^{-1})\,\geq\,3$.

We assume that one of these four conditions hold. This moduli space
${\mathcal{M}}$ has a natural algebraic Poisson structure [Bo1], [Ma], which
is constructed using $\sigma_{0}$.

In the special case where $N\,=\,K_{X}$ and $\sigma_{0}$ is the constant
function $1$, this ${\mathcal{M}}$ is a moduli space of Higgs bundles. In that
case, the Poisson structure is nondegenerate, meaning it is a symplectic
structure; this symplectic structure was constructed earlier in [Hi1], [Hi2].
Furthermore, there is a natural algebraic $1$–form on ${\mathcal{M}}$ such
that the symplectic form is the exterior derivative of it.

Let $S$ denote the smooth complex quasi-projective surface defined by the
total space of the line bundle $N$. Given any Hitchin pair
$(E,\,\theta)\,\in\,{\mathcal{M}}$, there is a subscheme
$Y_{(E,\theta)}\,\subset\,S$ of dimension one associated to it. Furthermore,
associated to the pair $(E,\,\theta)$ there is a coherent sheaf
${{\mathcal{L}}}_{(E,\theta)}$ on $Y_{(E,\theta)}$ which is pure of dimension
one. This pair $(Y_{(E,\theta)},\,{{\mathcal{L}}}_{(E,\theta)})$ is known as
the spectral datum associated to $(E,\,\theta)$. This construction produces an
algebraic map

$\Phi\,:\,{\mathcal{M}}\,\longrightarrow\,{\mathcal{P}}\,,$ (1.1)

where ${\mathcal{P}}$ is a moduli space of stable sheaves of pure dimension
one on $S$. This construction is reversible, and $\Phi$ is in fact an
isomorphism (see [Hi1], [Hi2], [Si], [BNR]).

The earlier mentioned section $\sigma_{0}$ of $N\otimes K^{-1}_{X}$ produces a
Poisson structure on the surface $S$. An algebraic Poisson structure on
${\mathcal{P}}$ is constructed using this Poisson structure on $S$ [Bo2],
[Ty].

It may be mentioned that when $N\,=\,K_{X}$ and $\sigma_{0}$ is the constant
function $1$, the Poisson structure on $S$ is the canonical symplectic form on
the cotangent bundle $K_{X}$ of $X$. In that case the Poisson structure on
${\mathcal{P}}$ coincides with the symplectic structure on ${\mathcal{P}}$
constructed by Mukai in [Mu]. Also, in this case there is a natural algebraic
$1$–form on ${\mathcal{P}}$ such that the symplectic form is the exterior
derivative of it.

In this continuation of the papers [Bo1, Bo2] of the second author, our aim is
to prove the following (see Theorem 4.6):

######  Theorem 1.1.

The isomorphism $\Phi$ in (1.1) takes the Poisson structure on ${\mathcal{M}}$
to the Poisson structure on ${\mathcal{P}}$.

When $N\,=\,K_{X}$, related results can be found in [HK], [HH], [BM]; there
the symplectic form on a moduli space of Higgs bundles is compared with the
symplectic form on the Hilbert scheme of zero dimensional subschemes of fixed
length of the total space of $K_{X}$ (Mukai had shown that this Hilbert scheme
has a symplectic structure).

##  2\. Hitchin pairs and spectral data

Let $X$ be an irreducible smooth complex projective curve of genus $g$, and
let $N$ be a fixed algebraic line bundle on $X$. A Hitchin pair $(E,\,\theta)$
is an algebraic vector bundle $E$ on $X$ together with a morphism
$\theta\,:\,E\,\longrightarrow\,E\otimes N$ of ${\mathcal{O}}_{X}$-modules
[Hi1, Ni].

A Hitchin pair $(E,\,\theta)$ is _stable_ (respectively, _semistable_) if

$\frac{\deg F}{\operatorname{rk}F}\,<\,\frac{\deg E}{\operatorname{rk}E}\ \ \
\text{(respectively,}\ \frac{\deg F}{\operatorname{rk}F}\,\leq\,\frac{\deg
E}{\operatorname{rk}E}\text{)}$

for all subbundles $0\,\not=\,F\,\subsetneq\,E$ for which
$\theta(F)\,\subset\,F\otimes N$.

Let $\overline{\mathcal{M}}$ denote the moduli space of all S-equivalence
classes of semistable Hitchin pairs (constructed in [Ni]; see [Ni, Definition
4.2] for definition of S-equivalence) of fixed rank $r$ and degree $\delta$.
Let

${\mathcal{M}}\,\subset\,\overline{\mathcal{M}}$

be the open subset of stable Hitchin pairs. We remark that the S-equivalence
class of a stable Hitchin pair is the same thing as its isomorphism class, so
this moduli space parametrizes isomorphism classes of objects.

######  Lemma 2.1.

The moduli space ${\mathcal{M}}$ of stable Hitchin pairs $(E,\theta:E\to
E\otimes N)$, with $\deg(E)=\delta$, $\operatorname{rk}(E)=r$, and
$N=K_{X}(D)$ for an effective divisor $D\geq 0$, is smooth.

###### Proof.

This is well-known, but since we did not find a reference, we include a sketch
of the proof. Fix a line bundle $\Delta\in\operatorname{Pic}^{\delta}(X)$ on
$X$ of degree $\delta$, and let ${\mathcal{M}}_{\Delta}$ be the moduli space
of stable Hitchin pairs with fixed determinant $\det(E)\cong\Delta$ and ${\rm
tr}(\theta)=0$. Consider the determinant morphism

$\det:{\mathcal{M}}\longrightarrow\operatorname{Pic}^{\delta}(X)\times
H^{0}(N)$ (2.1)

sending $(E,\theta)$ to $(\det(E),{\rm tr}(\theta))$. This morphism is
surjective, and the target is smooth, so to prove smoothness of
${\mathcal{M}}$ it is enough to show that the morphism is flat and the fibers
are smooth. Note that the fiber over a point $(L,\alpha)$ is isomorphic to the
moduli space ${\mathcal{M}}_{\Delta}$. Indeed, let $\eta\in J(X)$ such that
$\eta^{r}=L\otimes\Delta^{-1}$, and send $(E,\theta)\in{\mathcal{M}}_{\Delta}$
to $(E\otimes\eta,\theta+\frac{1}{r}\alpha)$. We can choose a root $\eta$ in
an étale neighbourhood of $\Delta$, so the determinant morphism is étale
locally trivial, and in particular it is flat. Therefore, it only remains to
prove that ${\mathcal{M}}_{\Delta}$ is smooth.

The deformation theory of the moduli space ${\mathcal{M}}$ of Hitchin pairs of
fixed degree is governed by the complex (in degrees 0 and 1)

$C^{\bullet}_{{\mathcal{E}nd}}:{\mathcal{E}nd}(E)\stackrel{{\scriptstyle[\cdot,\theta]}}{{\longrightarrow}}{\mathcal{E}nd}(E)\otimes
N$

This is proved in [BR]. In particular, the infinitesimal deformations are
given by $\mathbb{H}^{1}(C^{\bullet}_{{\mathcal{E}nd}})$, and
$\mathbb{H}^{2}(C^{\bullet}_{{\mathcal{E}nd}})$ is the obstruction space.
Furthermore, the exact sequence of complexes

$0\longrightarrow{\mathcal{E}nd}(E)\otimes N[-1]\longrightarrow
C^{\bullet}_{{\mathcal{E}nd}}\longrightarrow{\mathcal{E}nd}(E)\longrightarrow
0$

($[-1]$ means that the sheaf is placed in degree 1) gives an exact sequence

$0\longrightarrow\mathbb{H}^{0}(C^{\bullet}_{{\mathcal{E}nd}})\longrightarrow
H^{0}({\mathcal{E}nd}(E))\stackrel{{\scriptstyle[\cdot,\theta]}}{{\longrightarrow}}H^{0}({\mathcal{E}nd}(E)\otimes
N)$ (2.2)

and then $\mathbb{H}^{0}(C^{\bullet}_{{\mathcal{E}nd}})$ represents the
endomorphisms of $(E,\theta)$ in the category of Hitchin pairs, i.e.,
endomorphisms of $E$ which commute with $\theta$.

On the other hand, the deformation theory of the moduli space
${\mathcal{M}}_{\Delta}$ of stable Hitchin pairs of fixed determinant is given
by the complex

$C^{\bullet}_{ad}:ad(E)\stackrel{{\scriptstyle[\cdot,\theta]}}{{\longrightarrow}}ad(E)\otimes
N$

This can be checked by a straightforward modification of the proofs in [BR],
requiring at each step that the deformation of $E$ does not change its
determinant, and that the deformation of $\theta$ preserves the vanishing of
its trace.

It is well-known that if $E$ is a stable vector bundle, then its only
endomorphisms are given by scalar multiplication (cf. [HL, Proposition 1.2.7
and Corollary 1.2.8]). A straightforward modification of the usual argument
for vector bundles shows that this is also true in the category of Hitchin
pairs, i.e., if $(E,\theta)$ is stable as a Hitchin pair, and $\varphi:E\to E$
is a homomorphism which commutes with $\theta$, then $\varphi$ is the
multiplication by a scalar. Therefore, using (2.2) we have

$\mathbb{H}^{0}(C^{\bullet}_{{\mathcal{E}nd}})=\mathbb{C}\cdot\operatorname{id}_{E}$

Using the exact sequence

$0\longrightarrow\mathbb{H}^{0}(C^{\bullet}_{ad})\longrightarrow
H^{0}(ad(E))\stackrel{{\scriptstyle[\cdot,\theta]}}{{\longrightarrow}}H^{0}(ad(E)\otimes
N)$

we obtain

$\mathbb{H}^{0}(C^{\bullet}_{ad})=0$ (2.3)

because this cohomology is given by the endomorphisms of $E$ which are
traceless and commute with $\theta$.

We claim that $\mathbb{H}^{2}(C^{\bullet}_{ad})$ vanishes. Indeed, this group
is dual to

$\mathbb{H}^{0}(ad(E)\otimes N^{-1}\otimes K_{X}\longrightarrow ad(E)\otimes
K_{X})$ (2.4)

If $N\cong K_{X}$, then this is just $\mathbb{H}^{0}(C^{\bullet}_{ad})$, which
we have just seen that it is zero (2.3). On the other hand, if $N\cong
K_{X}(D)$ with $D>0$ an effective, nonzero divisor, then note that the complex
which appears in (2.4) is just $C^{\bullet}_{ad}\otimes{\mathcal{O}}_{X}(-D)$.
We have an exact sequence of complexes

$0\longrightarrow C^{\bullet}_{ad}\otimes{\mathcal{O}}_{X}(-D)\longrightarrow
C^{\bullet}_{ad}\longrightarrow
C^{\bullet}_{ad}\otimes{\mathcal{O}}_{D}\longrightarrow 0$

The associated long exact cohomology sequence starts as

$0\longrightarrow\mathbb{H}^{0}(C^{\bullet}_{ad}\otimes{\mathcal{O}}_{X}(-D))\longrightarrow\mathbb{H}^{0}(C^{\bullet}_{ad})\longrightarrow\mathbb{H}^{0}(C^{\bullet}_{ad}|_{D})$

The vanishing of $\mathbb{H}^{0}(C^{\bullet}_{ad})$ (2.3) implies the
vanishing of $\mathbb{H}^{0}(C^{\bullet}_{ad}\otimes{\mathcal{O}}_{X}(-D))$.
So we have proved that the obstruction space
$\mathbb{H}^{2}(C^{\bullet}_{ad})$ vanishes.

Summing up, there are no infinitesimal isomorphisms, and the obstruction space
vanishes, so ${\mathcal{M}}_{\Delta}$ is smooth, and then the smoothness of
$\operatorname{Pic}^{\delta}(X)$ implies the smoothness of ${\mathcal{M}}$. ∎

In the sequel we assume that one of the following four assumptions hold:

  1. (1)

$g\,\geq\,2$;

  2. (2)

$g\,=\,1$, $N\,=\,K_{X}$ and $\gcd(r,\,\delta)\,=\,1$;

  3. (3)

$g\,=\,1$ and $\deg(N\otimes K_{X}^{-1})\,>\,0$;

  4. (4)

$g\,=\,0$ and $\deg(N\otimes K_{X}^{-1})\,\geq\,3$.

This assumption implies the existence of stable Hitchin pairs [Ma, Remark
3.4], and hence ${\mathcal{M}}$ is nonempty.

We will now recall the _spectral construction_ , which is a bijective
correspondence between Hitchin pairs $(E,\,\theta)$ and certain sheaves
${\mathcal{L}}$ on the total space

$p\,:\,S\,:=\,\mathbb{V}(N)\,\longrightarrow\,X$ (2.5)

of the line bundle $N$. This construction is in [Hi2, § 5] for smooth spectral
curves, [BNR, p. 173–174, Proposition 3.6] for integral spectral curves, and
[Si, p. 18, Lemma 6.8] in general (see also [BNR, p. 173–174, Remark 3.7] and
[Sc]).

Consider the projection $p$ in (2.5). Let $x$ denote the tautological section
of $p^{*}N$ on $S\,=\,\mathbb{V}(N)$. For a Hitchin pair
$(E,\,E\stackrel{{\scriptstyle\theta}}{{\longrightarrow}}E\otimes N)$, we
define the associated sheaf ${\mathcal{L}}$ using the following short exact
sequence of coherent sheaves on $S$

$0\,\longrightarrow\,p^{*}(E\otimes N^{\vee})\,\stackrel{{\scriptstyle
h}}{{\longrightarrow}}\,p^{*}E\,\longrightarrow\,{\mathcal{L}}\,\longrightarrow\,0\,,$
(2.6)

where $p$ is the projection in (2.5) and $h\,:=\,p^{*}\theta-x$, with $x$
being the tensor product with the above mentioned tautological section $x$;
the homomorphism $E\otimes N^{\vee}\,\longrightarrow\,E$ given by $\theta$ is
denoted here by $\theta$ also. Throughout, the dual will be denoted by the
superscript “$\vee$”. The homomorphism $h$ in (2.6) is injective (it is an
isomorphism over the generic point of $S$), so (2.6) is indeed a short exact
sequence of coherent sheaves. The spectral curve

$Y\,\subset\,S$

for $(E,\,\theta)$ is the subscheme defined by the characteristic polynomial

$\det(p^{*}\theta-x)\,=\,0\,.$

Equivalently, the spectral curve $Y$ is the subscheme defined by the $0$–th
Fitting ideal sheaf

${\rm Fitt}_{0}({\mathcal{L}})\,\subset\,{\mathcal{O}}_{S}\,.$

To see this equivalence, note that (2.6) gives a presentation of
${\mathcal{L}}$, and, by definition, the $0$–th Fitting ideal is the ideal
generated by the codimension zero minors of the morphism $h$ in (2.6). Since
the ranks of the source and target of $h$ are equal, we only have one minor
which is the determinant $\det(h)\,=\,\det(p^{*}\theta-x)$, in other words the
characteristic polynomial of $\theta$. We have the following diagram

$\textstyle{{Y}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{i}$$\scriptstyle{\pi}$$\textstyle{{S}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{p}$$\textstyle{{X}}$
(2.7)

The spectral curve $Y$ is given as the zero of $\det(h)$, which is a section
of $p^{*}N^{r}$, and it is proper over $X$, of degree $r$. Note that
${\mathcal{L}}$ is pure of dimension 1 because $p_{*}{\mathcal{L}}=E$ is
torsion free. The Euler characteristic of ${\mathcal{L}}$ is
$\chi({\mathcal{L}})=\chi(E)=\deg(E)+r(1-g)$. We collect all these properties
in the following definition.

######  Definition 2.2.

A spectral sheaf ${\mathcal{L}}$ on $S$, with invariants $r$ and $\delta$, is
a coherent sheaf such that

  1. (1)

${\mathcal{L}}$ is pure of dimension 1

  2. (2)

The subscheme $Y\subset S$ defined by its 0-th Fitting ideal is in the divisor
class given by $p^{*}N^{r}$

  3. (3)

The projection $Y\longrightarrow X$ is proper, finite of degree $r$.

  4. (4)

$\chi({\mathcal{L}})=\delta+r(1-g)$

If the spectral curve $Y\subset S$ associated to a spectral sheaf
${\mathcal{L}}$ is smooth, then there is a line bundle $L$ on $Y$ such that
${\mathcal{L}}\,=\,i_{*}L$, where $i$ is the map in (2.7) ([BNR, p. 173–174,
Remarks 3.7 and 3.8]).

Conversely, let ${\mathcal{L}}$ be a spectral sheaf on $S$. The push-forward

$E\,=\,p_{*}{\mathcal{L}}$ (2.8)

is then a torsion free coherent sheaf, of rank $r$ and degree $\delta$. Define
the Hitchin pair $(E,\,\theta)$ by setting $\theta\,=\,p_{*}x$, where $p$ is
the projection in (2.7). More explicitly, consider the multiplication by the
tautological section $x$ of $p^{*}N$

${\mathcal{L}}\,\stackrel{{\scriptstyle
x}}{{\longrightarrow}}\,{\mathcal{L}}\otimes p^{*}N$

and then $\theta\,=\,p_{*}x$ is defined as the push-forward of this
homomorphism, using the projection formula

$\theta\,:\,E\,=\,p_{*}{\mathcal{L}}\,\longrightarrow\,p_{*}({\mathcal{L}}\otimes
p^{*}N)\,=\,(p_{*}{\mathcal{L}})\otimes N\,=\,E\otimes N$

(see (2.8)). The above reversible construction gives a correspondence between
the Hitchin pairs $(E,\,\theta)$ and the spectral sheaves ${\mathcal{L}}$ on
$S$

Note that the push-forward $p_{*}{\mathcal{L}}$ is coherent if and only if the
projection $Y\longrightarrow X$ is proper, and this holds if and only if the
closure of $Y$ in $\overline{S}\,=\,\mathbb{P}(N\oplus{\mathcal{O}}_{X})$ lies
in $S$ ([Si, p. 18, Lemma 6.8]).

We shall now recall the definition of stability given by Simpson ([Si]) for a
spectral sheaf ${\mathcal{L}}$. Let

$P({\mathcal{L}},m)\,=\,\chi({\mathcal{L}}\otimes p^{*}{\mathcal{O}}_{X}(m))$

be its Hilbert polynomial. Its degree $d$ is equal to the dimension of the
support of ${\mathcal{L}}$, and the leading coefficient is $am^{d}/d!$, where
$a\,=\,a({\mathcal{L}})$ is an integer which we call the rank of
${\mathcal{L}}$. We say that ${\mathcal{L}}$ is _stable_ (respectively,
_semistable_) if for all proper subsheaves
$0\,\not=\,{\mathcal{L}}^{\prime}\,\subset\,{\mathcal{L}}$,

$a({\mathcal{L}})P({\mathcal{L}}^{\prime},m)\,<\,a({\mathcal{L}}^{\prime})P({\mathcal{L}},m)\
\ \ \text{ (respectively, }\,\
a({\mathcal{L}})P({\mathcal{L}}^{\prime},m)\,\leq\,a({\mathcal{L}}^{\prime})P({\mathcal{L}},m)\text{)}$

It is easy to see that if ${\mathcal{L}}$ is semistable, then it has pure
dimension, i.e., the dimension of the support of every nonzero subsheaf is the
same as the dimension of the support of ${\mathcal{L}}$. Note that, in the
spectral construction, the condition that ${\mathcal{L}}^{\prime}$ is a
subsheaf of ${\mathcal{L}}$ translates into the condition that the subbundle

$E^{\prime}\,:=\,p_{*}{\mathcal{L}}^{\prime}\,\subset\,E\,:=\,p_{*}{\mathcal{L}}$

satisfies the condition $\theta(E^{\prime})\,\subset\,E^{\prime}\otimes N$. It
follows that a Hitchin pair is stable (respectively, semistable) if and only
if the corresponding spectral sheaf on $S$ is stable (respectively,
semistable) [Si, p. 19, Corollary 6.9].

The spectral construction can be carried out for families, so we get an
isomorphism between the moduli functors. Since the stability conditions
coincide, we get an isomorphism between the moduli space of stable Hitchin
pairs ${\mathcal{M}}$ or rank $r$ and degree $\delta$ and the moduli space
${\mathcal{P}}$ of stable spectral sheaves with invariants $r$ and $\delta$

$\Phi\,:\,{\mathcal{M}}\,\longrightarrow\,{\mathcal{P}}\,.$ (2.9)

In particular, both moduli spaces, ${\mathcal{M}}$ and ${\mathcal{P}}$, are
smooth (Lemma 2.1).

We are interested in calculating the differential of the isomorphism $\Phi$ in
(2.9). More generally, we will give an isomorphism between the infinitesimal
deformation space of a Hitchin pair $(E,\,\theta)$ and the infinitesimal
deformation space of the corresponding sheaf ${\mathcal{L}}$ on $S$.

##  3\. Poisson structure on the moduli spaces

The infinitesimal deformation space of a spectral sheaf (Definition 2.2)
${\mathcal{L}}$ is given by

$\operatorname{Ext}^{1}({\mathcal{L}},\,{\mathcal{L}})$ (3.1)

[Bo2, p. 425, (3.1)]. To calculate the dual of this vector space we will use
Serre duality. Recall that ${\mathcal{L}}$ is a coherent sheaf on the surface
$S\,=\,\mathbb{V}(N)$ in (2.5) which is not projective. However, it has a
projective compactification

$j\,:\,S\,\longrightarrow\,\overline{S}\,=\,\mathbb{P}(N\oplus{\mathcal{O}}_{X})\,;$

furthermore, the direct image $j_{*}{\mathcal{L}}$ is a coherent sheaf on
$\overline{S}$, because the closure, in $\overline{S}$, of the support of
${\mathcal{L}}$ does not meet the boundary $\overline{S}\setminus S$ (this
argument is in [Si, p. 18, Lemma 6.8]). We have

$\operatorname{Ext}^{1}({\mathcal{L}},\,{\mathcal{L}})^{\vee}\,=\,\operatorname{Ext}^{1}_{{\mathcal{O}}_{\overline{S}}}(j_{*}{\mathcal{L}},\,j_{*}{\mathcal{L}})^{\vee}\,\cong\,\operatorname{Ext}^{1}_{{\mathcal{O}}_{\overline{S}}}(j_{*}{\mathcal{L}},\,j_{*}{\mathcal{L}}\otimes
K_{\overline{S}})\,=\,\operatorname{Ext}^{1}({\mathcal{L}},\,{\mathcal{L}}\otimes
K_{S})\,,$ (3.2)

where the second isomorphism is Serre duality on the projective surface
$\overline{S}$.

Let ${\mathcal{P}}$ be the moduli space of stable spectral sheaves on $S$ (cf.
(2.9)). The tangent space $T_{[{\mathcal{L}}]}{\mathcal{P}}$ at the point
corresponding to ${\mathcal{L}}$ is canonically identified with
$\operatorname{Ext}^{1}({\mathcal{L}},\,{\mathcal{L}})$, and the cotangent
space $T^{\vee}_{[{\mathcal{L}}]}{\mathcal{P}}$ is canonically identified with
$\operatorname{Ext}^{1}({\mathcal{L}},\,{\mathcal{L}}\otimes K_{S})$ (see
(3.2)).

Henceforth assume that the line bundle $N\otimes K^{-1}_{X}$ on $X$ admits a
nonzero section. We fix a nonzero section

$\sigma_{0}\,\in\,H^{0}(X,\,N\otimes K^{-1}_{X})\setminus\\{0\\}\,.$ (3.3)

Since the anticanonical line bundle $K_{S}^{\vee}$ of the surface $S$ in (2.5)
is identified with $p^{*}(N\otimes K^{-1}_{X})$, where $p$ is the projection
in (2.5), we have

$s\,:=\,p^{*}\sigma_{0}\,\in\,H^{0}(S,\,K_{S}^{\vee})\,,$ (3.4)

where $\sigma_{0}$ is the section in (3.3). This $s$ produces an algebraic
Poisson structure on ${\mathcal{P}}$

$B\,:\,T^{\vee}{\mathcal{P}}\,\longrightarrow\,T{\mathcal{P}}$ (3.5)

[Bo2], [Ty]. We will recall below the fiberwise construction of $B$.

Tensoring with the section $s$ produces a homomorphism ${\mathcal{L}}\otimes
K_{S}\,\longrightarrow\,{\mathcal{L}}$. Consequently, we obtain a homomorphism

$T^{\vee}_{[{\mathcal{L}}]}{\mathcal{P}}\,\cong\,\operatorname{Ext}^{1}({\mathcal{L}},\,{\mathcal{L}}\otimes
K_{S})\,\longrightarrow\,\operatorname{Ext}^{1}({\mathcal{L}},\,{\mathcal{L}})\,\cong\,T_{[{\mathcal{L}}]}{\mathcal{P}}\,.$
(3.6)

The isomorphism
$\operatorname{Ext}^{1}({\mathcal{L}},\,{\mathcal{L}})\,\cong\,T_{[{\mathcal{L}}]}{\mathcal{P}}$
is a consequence of the fact that the infinitesimal deformations of
${\mathcal{L}}$ are parametrized by
$\operatorname{Ext}^{1}({\mathcal{L}},\,{\mathcal{L}})$, while the isomorphism
$T^{\vee}_{[{\mathcal{L}}]}{\mathcal{P}}\,\cong\,\operatorname{Ext}^{1}({\mathcal{L}},\,{\mathcal{L}}\otimes
K_{S})$ follows from (3.2). Let $B([{\mathcal{L}}])$ be the restriction to the
fiber over the point $[{\mathcal{L}}]$ of the bundle map $B$ in (3.5). This
homomorphism $B([{\mathcal{L}}])$ coincides with the one in (3.6) (see [Bo2,
p. 428, Formula (4.4)]).

On the other hand, the infinitesimal deformation space of a Hitchin pair
$(E,\,\theta)$ is given by the first hypercohomology of a complex

$\mathbb{H}^{1}(E^{\vee}\otimes
E\,\stackrel{{\scriptstyle[\cdot,\,\theta]}}{{\longrightarrow}}\,E^{\vee}\otimes
E\otimes N)$ (3.7)

(see [Bo1, p. 399, Proposition 3.1.2], [Ma, p. 271, Proposition 7.1], [BR, p.
220, Theorem 2.3]). The dual vector space

$\mathbb{H}^{1}(E^{\vee}\otimes
E\,\stackrel{{\scriptstyle[\cdot,\,\theta]}}{{\longrightarrow}}\,E^{\vee}\otimes
E\otimes N)^{\vee}$

is calculated using Serre duality for hypercohomologies. Denote by
$A^{\bullet}$ the complex

$A^{\bullet}\,:\,\quad E^{\vee}\otimes
E\,\stackrel{{\scriptstyle[\cdot,\,\theta]}}{{\longrightarrow}}\,E^{\vee}\otimes
E\otimes N$

concentrated in degrees $0$ and $1$. Serre duality gives an isomorphism

$\mathbb{H}^{1}(A^{\bullet})^{\vee}\stackrel{{\scriptstyle\cong}}{{\longrightarrow}}\mathbb{H}^{-1}(A^{\bullet}{}^{\vee}[1]\otimes
K_{X})=\mathbb{H}^{1}(A^{\bullet}{}^{\vee}[-1]\otimes K_{X})$

[Hu, p. 67, Theorem 3.12]. The dual complex

$A^{\bullet}{}^{\vee}\,:\quad E\otimes E^{\vee}\otimes
N^{\vee}\,\stackrel{{\scriptstyle[\cdot,\,\theta]^{t}}}{{\longrightarrow}}\,E\otimes
E^{\vee}$

is concentrated in degrees $-1$ and $0$. We identify $E\otimes E^{\vee}$ and
$E^{\vee}\otimes E$ by switching the factors; then the morphism
$[\cdot,\,\theta]^{t}$ becomes $[\theta,\,\cdot]$, so

$A^{\bullet}{}^{\vee}\,:\quad E^{\vee}\otimes E\otimes
N^{\vee}\,\stackrel{{\scriptstyle[\theta,\,\cdot]}}{{\longrightarrow}}\,E^{\vee}\otimes
E\,.$ (3.8)

Finally we shift the complex in (3.8) by $[-1]$. Recall that, when we shift a
complex by one unit, we multiply by $-1$ all the differentials [Hu, p. 28,
Definition 2.4], so we get the complex, concentrated in degrees $0$ and $1$

$A^{\bullet}{}^{\vee}[-1]\otimes K_{X}\,:\quad E^{\vee}\otimes E\otimes
N^{\vee}\otimes
K_{X}\,\stackrel{{\scriptstyle[\cdot,\,\theta]}}{{\longrightarrow}}\,E^{\vee}\otimes
E\otimes K_{X}\,.$ (3.9)

######  Remark 3.1.

In [Bo1, p. 402, Proposition 3.1.10] the morphism is actually
$[\theta,\,\cdot]$ instead of the homomorphism $[\cdot,\,\theta]$ in (3.7). Of
course there is an isomorphism between the two complexes (multiplication by
$-1$ in one term and $+1$ in the other).

As in (2.9), let ${\mathcal{M}}$ be a moduli space of stable Hitchin pairs
such that the rank and degree of the vector bundle underlying a Hitchin pair
are $r$ and $\delta$ respectively. Using the section $\sigma_{0}$ in (3.3) an
algebraic Poisson structure

$B^{H}\,:\,T^{\vee}{\mathcal{M}}\,\longrightarrow\,T{\mathcal{M}}$ (3.10)

on ${\mathcal{M}}$ is constructed [Bo1, § 4.3], [Ma, p. 278, Corollary 7.15].
We recall below a fiberwise construction of the homomorphism $B^{H}$ in
(3.10).

Tensoring with the section $\sigma_{0}$ in (3.3) induces homomorphisms
$N^{\vee}\otimes K_{X}\,\longrightarrow\,{{\mathcal{O}}}_{X}$ and
$K_{X}\,\longrightarrow\,N$. Using these we obtain a homomorphism of complexes

$\begin{matrix}{E^{\vee}\otimes E\otimes N^{\vee}\otimes
K_{X}}&\stackrel{{\scriptstyle[\cdot,\,\theta]}}{{\longrightarrow}}&{E^{\vee}\otimes
E\otimes K_{X}}\\\
\sigma_{0}\Big{\downarrow}\,\,\,\,\,\,\,&&\,\,\,\,\,\,\,\Big{\downarrow}\sigma_{0}\\\
{E^{\vee}\otimes
E}&\stackrel{{\scriptstyle[\cdot,\,\theta]}}{{\longrightarrow}}&{E^{\vee}\otimes
E\otimes N}.\end{matrix}$ (3.11)

The morphism of complexes in (3.11) gives a morphism of cohomologies

$\displaystyle\mathbb{H}^{1}(E^{\vee}\otimes E\otimes N^{\vee}\otimes K_{X}$
$\displaystyle\,\stackrel{{\scriptstyle[\cdot,\,\theta]}}{{\longrightarrow}}\,E^{\vee}\otimes
E\otimes K_{X})$ $\displaystyle\longrightarrow\,\mathbb{H}^{1}(E^{\vee}\otimes
E$
$\displaystyle\stackrel{{\scriptstyle[\cdot,\,\theta]}}{{\longrightarrow}}E^{\vee}\otimes
E\otimes N)\,.$ (3.12)

We have $T_{[(E,\theta)]}{\mathcal{M}}\,=\,\mathbb{H}^{1}(E^{\vee}\otimes
E\stackrel{{\scriptstyle[\cdot,\,\theta]}}{{\longrightarrow}}E^{\vee}\otimes
E\otimes N)$, because the infinitesimal deformations of $(E,\,\theta)$ are
parametrized by $\mathbb{H}^{1}(E^{\vee}\otimes
E\stackrel{{\scriptstyle[\cdot,\,\theta]}}{{\longrightarrow}}E^{\vee}\otimes
E\otimes N)$ (see (3.7)); this and (3.9) together imply that

$T^{\vee}_{[(E,\theta)]}{\mathcal{M}}\,=\,\mathbb{H}^{1}(E^{\vee}\otimes
E\otimes N^{\vee}\otimes
K_{X}\,\stackrel{{\scriptstyle[\cdot,\,\theta]}}{{\longrightarrow}}\,E^{\vee}\otimes
E\otimes K_{X})\,.$ (3.13)

Using (3.13) and (3.7), the homomorphism in (3.12) becomes a homomorphism

$T^{\vee}_{[(E,\theta)]}{\mathcal{M}}\,\longrightarrow\,T_{[(E,\theta)]}{\mathcal{M}}\,.$

This homomorphism coincides with $B^{H}([(E,\theta)])$ in (3.10) [Bo1, § 4.3],
[Ma, p. 278, Corollary 7.15].

######  Remark 3.2.

If we compare (3.11) with the commutative diagram in [Bo1, Remark 1.3.3], we
see that the sign is changed in the vertical left arrow and in one of the
horizontal arrows (there is $[\theta,\,\cdot]$ in [Bo1, Remark 1.3.3] as
opposed to $[\cdot,\,\theta]$ here).

##  4\. Comparison of Poisson structures

We shall compare the Poisson structures $B$ and $B^{H}$, constructed in (2.9)
and (3.10) respectively, using the isomorphism $\Phi$ in (2.9).

We first recall that the global Ext can be calculated using locally free
resolutions and hypercohomology.

######  Lemma 4.1 ([Gr, Corollary 2 to Theorem 4.2.1]).

Let $V$ and $W$ be coherent sheaves on a scheme $T$. Let

$\cdots\,\longrightarrow\,L^{-3}\,\longrightarrow\,L^{-2}\,\longrightarrow\,L^{-1}\,\longrightarrow\,L^{0}\,\longrightarrow\,V\,\longrightarrow\,0$

be a resolution of $V$ by finitely generated locally free sheaves. Then there
is an isomorphism

$\operatorname{Ext}^{i}(V,\,W)\,\cong\,\mathbb{H}^{i}({\mathcal{H}om}(L^{\bullet},\,W))$

which is functorial on $W$.

######  Proposition 4.2.

Let $W$ be a coherent sheaf on the surface $S$ in (2.5). Let
$x\,:\,W\,\longrightarrow\,W\otimes p^{*}N$ be multiplication by the
tautological section of $p^{*}N$ on $S$, where $p$ is the projection in (2.5).
Then for any $(E,\,\theta)\,\in\,{\mathcal{M}}$ (see (2.9)) there is an
isomorphism

$\varphi_{W}\,\,\,:\,\,\,\operatorname{Ext}^{1}({\mathcal{L}},\,W)\,\stackrel{{\scriptstyle\cong}}{{\longrightarrow}}\,\mathbb{H}^{1}(E^{\vee}\otimes
p_{*}W\,\stackrel{{\scriptstyle f_{W}}}{{\longrightarrow}}\,E^{\vee}\otimes
N\otimes p_{*}W)\,,$

where ${\mathcal{L}}\,=\,\Phi((E,\,\theta))$ (see (2.9)),
$f_{W}\,=\,\theta^{\vee}\otimes 1-1\otimes p_{*}x$, and $f_{W}$ is seen as a
complex concentrated in degrees $0$ and $1$. This isomorphism is functorial on
$W$, meaning a homomorphism $V\,\longrightarrow\,W$ of coherent sheaves on $S$
induces a commutative diagram

$\textstyle{{\operatorname{Ext}^{1}({\mathcal{L}},\,V)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\mathbb{H}^{1}(E^{\vee}\otimes
p_{*}V\stackrel{{\scriptstyle f_{V}}}{{\longrightarrow}}E^{\vee}\otimes
N\otimes
p_{*}V)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\operatorname{Ext}^{1}({\mathcal{L}},\,W)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\mathbb{H}^{1}(E^{\vee}\otimes
p_{*}W\stackrel{{\scriptstyle f_{W}}}{{\longrightarrow}}E^{\vee}\otimes
N\otimes p_{*}W)}}$

###### Proof.

The short exact sequence in (2.6) gives a locally free resolution
$L^{\bullet}$ of ${\mathcal{L}}$ (concentrated on degrees $-1$ and $0$)

$L^{\bullet}\,:\quad p^{*}(E\otimes N^{\vee})\,\stackrel{{\scriptstyle
h}}{{\longrightarrow}}\,p^{*}E\,.$

For any sheaf $W$ on $S$, Lemma 4.1 gives an isomorphism functorial for $W$

$\operatorname{Ext}^{1}({\mathcal{L}},\,W)\,=\,\mathbb{H}^{1}({\mathcal{H}om}(L^{\bullet},\,W))\,.$
(4.1)

Consider the diagram

---
$\textstyle{{S}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{p}$$\textstyle{{X}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\gamma}$$\textstyle{{\operatorname{Spec}\mathbb{C}}}$

where $f$ and $\gamma$ are the structure morphisms. Note that the
hypercohomology of any complex $D^{\bullet}$ on $S$ can be calculated as the
cohomology of the complex $Rf_{*}D^{\bullet}$ (where $Rf_{*}$ is the derived
functor between the derived categories). We have

$Rf_{*}\,=\,R(\gamma_{*}\circ
p_{*})\,\stackrel{{\scriptstyle\cong}}{{\longrightarrow}}\,R\gamma_{*}\circ
Rp_{*}\,.$

The morphism $p$ is affine, hence $p_{*}$ is exact and then
$Rp_{*}\,=\,p_{*}$. If we apply this observation to the complex
${\mathcal{H}om}(L^{\bullet},W)$, we get

$\mathbb{H}^{1}({\mathcal{H}om}(L^{\bullet},\,W))\,\stackrel{{\scriptstyle\cong}}{{\longrightarrow}}\,\mathbb{H}^{1}(p_{*}{\mathcal{H}om}(L^{\bullet},\,W))\,.$
(4.2)

In view of (4.1) and (4.2), to finish the proof, it only remains to show that
the complex $p_{*}{\mathcal{H}om}(L^{\bullet},W)$ is equal to the complex
$f_{W}$ in the statement of the proposition.

Applying ${\mathcal{H}om}(\cdot,\,W)$ to the complex $L^{\bullet}$ we obtain a
complex concentrated in degrees $0$ and $1$

${\mathcal{H}om}(L^{\bullet},\,W)\,:\quad p^{*}E^{\vee}\otimes
W\,\stackrel{{\scriptstyle
h^{\prime}}}{{\longrightarrow}}\,p^{*}E^{\vee}\otimes p^{*}N\otimes W\,,$
(4.3)

where $h^{\prime}\,:=\,p^{*}\theta^{\vee}\otimes 1-1\otimes x$. By the
projection formula, $p_{*}{\mathcal{H}om}(L^{\bullet},W)$ is

$E^{\vee}\otimes p_{*}W\,=\,p_{*}(p^{*}E^{\vee}\otimes
W)\,\stackrel{{\scriptstyle
p_{*}h^{\prime}}}{{\longrightarrow}}\,p_{*}(p^{*}E^{\vee}\otimes p^{*}N\otimes
W)\,=\,E^{\vee}\otimes N\otimes p_{*}W\,,$

where $p_{*}h^{\prime}\,=\,\theta^{\vee}\otimes 1-1\otimes p_{*}x$, and the
proposition follows. ∎

######  Remark 4.3.

In the proof of Proposition 4.2, the main step is the isomorphism in (4.2),
because it facilitates the passage of objects defined on $S$ to objects
defined on $X$. Note that this isomorphism is induced by the push-forward
$p_{*}$ using $p$.

Let

$d\Phi\,:\,T{\mathcal{M}}\,\longrightarrow\,\Phi^{*}T{\mathcal{P}}$ (4.4)

be the differential of the isomorphism $\Phi$ in (2.9).

######  Lemma 4.4.

Let

$\varphi\,\,\,:\,\,\,\operatorname{Ext}^{1}({\mathcal{L}},\,{\mathcal{L}})\,\stackrel{{\scriptstyle\cong}}{{\longrightarrow}}\,\mathbb{H}^{1}(E^{\vee}\otimes
E\,\stackrel{{\scriptstyle
f_{{\mathcal{L}}}}}{{\longrightarrow}}\,E^{\vee}\otimes N\otimes E)$

be the homomorphism given by Proposition 4.2 for $W\,=\,{\mathcal{L}}$ (see
(2.8)). Then the following diagram is commutative

$\begin{matrix}\operatorname{Ext}^{1}({\mathcal{L}},\,{\mathcal{L}})&\stackrel{{\scriptstyle\varphi}}{{\longrightarrow}}&{\mathbb{H}^{1}(E^{\vee}\otimes
E\stackrel{{\scriptstyle[\cdot,\,\theta]}}{{\longrightarrow}}E^{\vee}\otimes
E\otimes N)}\\\ \,\,\,\,\Big{\uparrow}\alpha&&\,\,\,\,\Big{\downarrow}\beta\\\
T_{[{\mathcal{L}}]}{\mathcal{P}}&\xleftarrow{d\Phi(\Phi^{-1}([{\mathcal{L}}]))}&T_{[(E,\theta)]}{\mathcal{M}}\end{matrix}$

where $\alpha$ and $\beta$ are the infinitesimal deformation maps in (3.1) and
(3.7) respectively, and $d\Phi(\Phi^{-1}([{\mathcal{L}}]))$ is the
homomorphism in (4.4) at $\Phi^{-1}([{\mathcal{L}}])\,\in\,{\mathcal{M}}$.

###### Proof.

Consider an infinitesimal deformation ${\mathcal{L}}_{\epsilon}$ of
${\mathcal{L}}$, i.e., a sheaf on
$S\times\operatorname{Spec}(\mathbb{C}[\epsilon]/(\epsilon^{2}))$ flat over
$\operatorname{Spec}(\mathbb{C}[\epsilon]/(\epsilon^{2}))$, that fits in a
short exact sequence

$0\,\longrightarrow\,{\mathcal{L}}\,\stackrel{{\scriptstyle\epsilon}}{{\longrightarrow}}\,{\mathcal{L}}_{\epsilon}\,\stackrel{{\scriptstyle{\rm
mod}\,\epsilon}}{{\longrightarrow}}\,{\mathcal{L}}\,\longrightarrow\,0\,.$
(4.5)

By applying the functor $\operatorname{Hom}({\mathcal{L}},\,\cdot)$ to this
short exact sequence we obtain a long exact sequence

$\cdots\,\longrightarrow\,\operatorname{Hom}({\mathcal{L}},\,{\mathcal{L}}_{\epsilon})\,\longrightarrow\,\operatorname{Hom}({\mathcal{L}},\,{\mathcal{L}})\,\stackrel{{\scriptstyle\delta}}{{\longrightarrow}}\,\operatorname{Ext}^{1}({\mathcal{L}},\,{\mathcal{L}})\,\longrightarrow\,\cdots\,;$

the element of $\operatorname{Ext}^{1}({\mathcal{L}},\,{\mathcal{L}})$ that
corresponds to the infinitesimal deformation ${\mathcal{L}}_{\epsilon}$ is
$\delta(\operatorname{id})$, the image of the identity
$\operatorname{id}\,\in\,\operatorname{Hom}({\mathcal{L}},\,{\mathcal{L}})$ by
the connecting homomorphism $\delta$.

If we set $W\,=\,{\mathcal{L}}$ in Proposition 4.2, we have $p_{*}W\,=\,E$ and
$p_{*}x\,=\,\theta$; then $f_{W}\,=\,[\cdot,\,\theta]$, and Proposition 4.2
produces the isomorphism $\varphi$.

The element

$\beta\circ\varphi\circ\alpha({\mathcal{L}}_{\epsilon})\,\in\,T_{[(E,\theta)]}{\mathcal{M}}\,,$
(4.6)

where ${\mathcal{L}}_{\epsilon}\,\in\,T_{[{\mathcal{L}}]}{\mathcal{P}}$ is the
element in (4.5), has the following description.

Consider the short exact sequence (4.5). Applying $p_{*}$ to it, we obtain an
exact sequence of complexes

$0\,\longrightarrow\,K^{\bullet}\,\stackrel{{\scriptstyle\epsilon}}{{\longrightarrow}}\,K^{\bullet}_{\epsilon}\,\stackrel{{\scriptstyle{\rm
mod}\,\epsilon}}{{\longrightarrow}}\,K^{\bullet}\,\longrightarrow\,0\,,$ (4.7)

where $K^{\bullet}$ denotes the complex
$0\,\longrightarrow\,E\,\stackrel{{\scriptstyle\theta}}{{\longrightarrow}}\,E\otimes
N\,\longrightarrow\,0$. Since $K^{\bullet}_{\epsilon}$ in (4.7) is a family of
Hitchin pairs on $X$ parametrized by
$\operatorname{Spec}(\mathbb{C}[\epsilon]/(\epsilon^{2}))$, it corresponds to
an element of $T_{[(E,\theta)]}{\mathcal{M}}$. This element of
$T_{[(E,\theta)]}{\mathcal{M}}$ coincides with the one in (4.6). Now from the
construction of the map $\Phi$ it follows that

$d\Phi(\Phi^{-1}([{\mathcal{L}}]))(\beta\circ\varphi\circ\alpha({\mathcal{L}}_{\epsilon}))\,\in\,T_{[{\mathcal{L}}]}{\mathcal{P}}$

coincides with
${\mathcal{L}}_{\epsilon}\,\in\,T_{[{\mathcal{L}}]}{\mathcal{P}}$. ∎

We remark that the key to the commutativity of the diagram in the statement of
Lemma 4.4 is that both $\varphi$ and $\Phi^{-1}$ are induced by the push-
forward $p_{*}$.

######  Lemma 4.5.

Consider

$\varphi_{1}\,:=\,(\varphi_{{\mathcal{L}}\otimes
K_{S}})^{-1}\,:\,{\mathbb{H}^{1}(E^{\vee}\otimes E\otimes K_{X}\otimes
N^{\vee}\stackrel{{\scriptstyle[\cdot,\,\theta]}}{{\longrightarrow}}E^{\vee}\otimes
E\otimes
K_{X})}\,\longrightarrow\,\operatorname{Ext}^{1}({\mathcal{L}},\,{\mathcal{L}}\otimes
K_{S}),$

where $\varphi_{{\mathcal{L}}\otimes K_{S}}$ is the isomorphism in Proposition
4.2 for $W\,=\,{\mathcal{L}}\otimes K_{S}$. Let
$(d\Phi)^{\vee}([{\mathcal{L}}])$ be dual of the differential of the
isomorphism $\Phi$ at $[{\mathcal{L}}]$. Then the following diagram is
commutative

$\begin{matrix}\operatorname{Ext}^{1}({\mathcal{L}},\,{\mathcal{L}}\otimes
K_{S})&\stackrel{{\scriptstyle\varphi_{1}}}{{\longleftarrow}}&{\mathbb{H}^{1}(E^{\vee}\otimes
E\otimes K_{X}\otimes
N^{\vee}\stackrel{{\scriptstyle[\cdot,\,\theta]}}{{\longrightarrow}}E^{\vee}\otimes
E\otimes K_{X})}\\\
\,\,\,\,\Big{\downarrow}\alpha^{\vee}&&\,\,\,\,\Big{\uparrow}\beta^{\vee}\\\
{T^{\vee}_{[{\mathcal{L}}]}{\mathcal{P}}}&\xrightarrow{(d\Phi)^{\vee}([{\mathcal{L}}])}&T^{\vee}_{[(E,\theta)]}{\mathcal{M}}\end{matrix}$

where $\alpha^{\vee}$ and $\beta^{\vee}$ are the natural isomorphisms obtained
from (3.2) and (3.9) respectively, and $(d\Phi)^{\vee}$ is the dual of the
homomorphism in (4.4).

###### Proof.

Consider the homomorphism $\varphi$ in Lemma 4.4. For any

$\omega\,\in\,{\mathbb{H}^{1}(E^{\vee}\otimes E\otimes K_{X}\otimes
N^{\vee}\stackrel{{\scriptstyle[\cdot,\,\theta]}}{{\longrightarrow}}E^{\vee}\otimes
E\otimes K_{X})}$

and $v\,\in\,\operatorname{Ext}^{1}({\mathcal{L}},\,{\mathcal{L}})$, we have

$\varphi_{1}(\omega)(v)\,=\,\omega(\varphi(v))\,\in\,{\mathbb{C}}\,;$ (4.8)

recall that

$\mathbb{H}^{1}(E^{\vee}\otimes E\otimes K_{X}\otimes
N^{\vee}\stackrel{{\scriptstyle[\cdot,\,\theta]}}{{\longrightarrow}}E^{\vee}\otimes
E\otimes K_{X})\,=\,\mathbb{H}^{1}(E^{\vee}\otimes
E\,\stackrel{{\scriptstyle[\cdot,\,\theta]}}{{\longrightarrow}}\,E^{\vee}\otimes
E\otimes N)^{\vee}$

(see (3.13) and (3.7)), and

$\operatorname{Ext}^{1}({\mathcal{L}},\,{\mathcal{L}}\otimes
K_{S})\,=\,\operatorname{Ext}^{1}({\mathcal{L}},\,{\mathcal{L}})^{\vee}$

(see (3.2)). From (4.8) it follows immediately that $\varphi_{1}$ coincides
with the dual homomorphism $\varphi^{\vee}$.

Therefore, every homomorphism in the diagram in this lemma is the dual of the
corresponding homomorphism in the diagram in Lemma 4.4. Hence the lemma
follows from Lemma 4.4. ∎

The homomorphism $B$ in (3.5) gives an algebraic section

$B\,\in\,H^{0}({\mathcal{P}},\,\bigwedge\nolimits^{2}T{\mathcal{P}})\,,$ (4.9)

and the homomorphism $B^{H}$ in (3.10) gives an algebraic section

$B^{H}\,\in\,H^{0}({\mathcal{M}},\,\bigwedge\nolimits^{2}T{\mathcal{M}})\,.$

Consider the homomorphism $d\Phi$ in (4.4). We note that

$\Phi_{*}B^{H}\,:=\,(\bigwedge\nolimits^{2}d\Phi)(B^{H})\,\in\,H^{0}({\mathcal{P}},\,\bigwedge\nolimits^{2}T{\mathcal{P}})$
(4.10)

is a Poisson structure on ${\mathcal{P}}$.

######  Theorem 4.6.

The isomorphism $\Phi$ in (2.9) satisfies the condition

$\Phi_{*}B^{H}\,=\,B\,,$

where $\Phi_{*}B^{H}$ and $B$ are the sections in (4.10) and (4.9)
respectively.

###### Proof.

The section $\sigma_{0}\,\in\,H^{0}(X,\,N\otimes K^{\vee}_{X})$ gives a
section $s$ of $K_{S}^{\vee}\,=\,p^{*}(N\otimes K^{\vee}_{X})$, and hence it
produces a homomorphism ${\mathcal{L}}\otimes
K_{S}\,\longrightarrow\,{\mathcal{L}}$. We apply Proposition 4.2 to this
homomorphism and get the following commutative diagram:

$\textstyle{{\operatorname{Ext}^{1}({\mathcal{L}},{\mathcal{L}}\otimes
K_{S})}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\cong}$$\scriptstyle{\varphi^{\prime}}$$\textstyle{{\mathbb{H}^{1}(E^{\vee}\otimes
E\otimes K_{X}\otimes
N^{\vee}\stackrel{{\scriptstyle[\cdot,\,\theta]}}{{\longrightarrow}}E^{\vee}\otimes
E\otimes
K_{X})}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\operatorname{Ext}^{1}({\mathcal{L}},\,{\mathcal{L}})}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\cong}$$\scriptstyle{\varphi}$$\textstyle{{\mathbb{H}^{1}(E^{\vee}\otimes
E\,\stackrel{{\scriptstyle[\cdot,\,\theta]}}{{\longrightarrow}}\,E^{\vee}\otimes
E\otimes N)}}$ (4.11)

where the left vertical homomorphism is the one in (3.6) and the right
vertical homomorphism is the one in (3.12).

Lemma 4.5 shows that the top horizontal homomorphism $\varphi^{\prime}$ in
(4.11) coincides with $(d\Phi)^{\vee}([{\mathcal{L}}])$. We note that
$\varphi^{\prime}\,=\,(\varphi_{1})^{-1}$, where $\varphi_{1}$ is the
homomorphism in Lemma 4.5. On the other hand, Lemma 4.4 shows that the bottom
horizontal homomorphism in (4.11) coincides with
$d\Phi^{-1}([{\mathcal{L}}])$. The left vertical homomorphism in (4.11) gives
$B([{\mathcal{L}}])$, the Poisson structure on ${\mathcal{P}}$, while the
right vertical homomorphism in (4.11) gives
$B^{H}([(E,\theta)])\,=\,B^{H}(\Phi^{-1}([{\mathcal{L}}]))$, the Poisson
structure on ${\mathcal{M}}$. Consequently, the theorem follows from the
commutativity of the diagram in (4.11). ∎

## Acknowledgements

We thank Oscar García-Prada for helpful discussions on the smoothness and
deformation theory of the moduli space of Hitchin pairs. We thank that referee
for comments which improved the exposition. The first author is supported by a
J. C. Bose fellowship. The third author is supported by Ministerio de Ciencia
e Innovación of Spain (grants PID2019-108936GB-C21 and ICMAT Severo Ochoa
project CEX2019-000904-S) and CSIC (2019AEP151 and Ayuda extraordinaria a
Centros de Excelencia Severo Ochoa 20205CEX001).

## References

  * [BNR] A. Beauville, M.S. Narasimhan and S. Ramanan, Spectral curves and the generalised theta divisor, J. Reine Angew. Math. 398 (1989), 169–179.
  * [BM] I. Biswas and A. Mukherjee, Symplectic structures of moduli space of Higgs bundles over a curve and Hilbert scheme of points on the canonical bundle, Comm. Math. Phys. 221 (2001), 293–304.
  * [BR] I. Biswas and S. Ramanan, An infinitesimal study of the moduli of Hitchin pairs, Jour. Lond. Math. Soc. 49 (1994), 219–231.
  * [Bo1] F. Bottacin, Symplectic geometry on moduli spaces of stable pairs, Ann. Sci. École Norm. Sup. 28 (1995), 391–433.
  * [Bo2] F. Bottacin, Poisson structures on moduli spaces of sheaves over Poisson surfaces, Invent. Math. 121 (1995), 421–436.
  * [Gr] A. Grothendieck, Sur quelques points d’algèbre homologique, Tohoku Math. Jour. 9 (1957), 119–221.
  * [HH] J. Harnad and J. Hurtubise, Multi-Hamiltonian structures for $r$-matrix systems, Jour. Math. Phys. 49 (2008), no. 6, 062903.
  * [Hi1] N. Hitchin, The self-duality equations on a Riemann surface, Proc. London Math. Soc. 55 (1987), 59–126.
  * [Hi2] N. Hitchin, Stable bundles and integrable systems, Duke Math. Jour. 54 (1987), 91–114.
  * [HK] J. C. Hurtubise and M. Kjiri, Separating coordinates for the generalized Hitchin systems and the classical r-matrices, Comm. Math. Phys. 210 (2000), 521–540.
  * [HL] D. Huybrechts and M. Lehn, The geometry of moduli spaces of sheaves. Aspects of Mathematics, E31, Firedr. Vieweg & Sohn, Braunschweig, 1997.
  * [Hu] D. Huybrechts, Fourier-Mukai transforms in algebraic geometry, Oxford Mathematical Monographs, Oxford University Press, 2006.
  * [Ma] E. Markman, Spectral curves and integrable systems, Compositio Math. 93 (1994), 255–290.
  * [Mu] S. Mukai, Symplectic structure of the moduli space of sheaves on an abelian or K3 surface, Invent. Math. 77 (1984), 101–116.
  * [Ni] N. Nitsure, Moduli space of semistable pairs on a curve, Proc. London Math. Soc. 62 (1991), 275–300.
  * [Sc] D. Schaub, Courbes spectrales et compactifications de jacobiennes, Math. Zeit. 227 (1998), 295–312.
  * [Si] C. Simpson, Moduli of representations of the fundamental group of a smooth projective variety. II, Inst. Hautes Études Sci. Publ. Math. 80 (1994), 5–79.
  * [Ty] A. N. Tyurin, Symplectic structures on the varieties of moduli of vector bundles on algebraic surfaces with $p_{g}>0$, Math. USSR Izvestiya 33 (1989), 139–177.


Université Paris Saclay, UVSQ<EMAIL_ADDRESS>Xavier
Badin de Montjoye [500]Theory of computation Algorithmic game theory

###### Acknowledgements.

We would like to thanks David Auger, Pierre Coucheney and Yann Strozecki for
sharing their insights on SSGs. John Q. Open and Joan R. Access 2 42nd
Conference on Very Important Topics (CVIT 2016) CVIT 2016 CVIT 2016 December
24–27, 2016 Little Whinging, United Kingdom 42 23

# A Recursive Algorithm for Solving Simple Stochastic Games

Xavier Badin de Montjoye

###### Abstract

We present two recursive strategy improvement algorithms for solving simple
stochastic games. First we present an algorithm for solving SSGs of degree
$\displaystyle d$ that uses at most $\displaystyle
O\left(\left\lfloor(d+1)^{2}/2\right\rfloor^{n/2}\right)$ iterations, with
$\displaystyle n$ the number of MAX vertices. Then, we focus on binary SSG and
propose an algorithm that has complexity $\displaystyle
O\left(\varphi^{n}Poly(N)\right)$ where $\displaystyle\varphi=(1+\sqrt{5})/2$
is the golden ratio. To the best of our knowledge, this is the first
deterministic strategy improvement algorithm that visits $\displaystyle
2^{cn}$ strategies with $\displaystyle c<1$.

###### keywords:

Simple Stochastic Games, Strategy Improvement, Parametrized Complexity,
Recursif algorithm

##  1 Introduction

Simple stochastic games (SSG) are a restriction introduced by Condon [6, 7] of
the notion of stochastic games defined by Shapley [12]. An SSG is a turn-based
zero-sum game with perfect information played by two players named max and
min. A token is placed on a directed graph and moves alongside the graph arcs.
The set of vertices is partitioned in max, min, Random and Sink vertices. If
the token is in a max or min vertices, the corresponding player chooses its
next position in the outneighbourhood of the currently occupied vertex. In the
case of random vertices, the token is moved randomly. Finally, when a sink
vertex $\displaystyle s$ is reached, the game ends and player min must pay
some penalty value $\displaystyle\mbox{Val}(s)$ to player max. The goal of min
is to minimise the expected penalty, and the goal of max is to maximise it.
One reason to study SSGs and their related complexity is that the stochastic
versions of classical games such as parity games, mean and discounted payoff
are all equivalent to SSG [1].

Simple stochastic games admit a pair of optimal strategies [7] whose expected
value satisfies a Nash equilibrium. Our goal is to compute such a pair of
optimal strategy. This problem is known to be in PPAD [10] a subset of the
class FNP, but is not known to be in FP. SSG have several applications, such
as modelling autonomous urban driving [5] or in the domain of model checking
of modal $\displaystyle\mu$-calculus [13].

We note $\displaystyle n$ the number of max vertices, $\displaystyle N$ the
number of total vertices and $\displaystyle r$ the number of random vertices.
Every known algorithm in the literature for solving SSGs has exponential time
complexity bounds. There exist several FPT algorithms that can be used for
specific families of SSGs. For instance, for SSGs with random vertices of
degree $\displaystyle 2$ and uniform probability distribution, Ibsen-Jensen
and Milterson gives a value iteration algorithm in [9] with complexity
$\displaystyle O\left(r2^{r}(r\log(r)+N)\right)$.

One of the main families of algorithms for solving SSGs are strategy
improvement algorithms. In the case of SSG with max vertices of outdegree
exactly $\displaystyle 2$, Tripathi, Valkanova and Kumar present in [14] an
algorithm with $\displaystyle O\left(2^{n}/n\right)$ iterations, which is the
only current bounds that deterministically improve the trivial $\displaystyle
2^{n}$ iterations of checking every possible strategies of player max. Ludwig
offers a randomised algorithm in [11], which does $\displaystyle\displaystyle
2^{O\left(\sqrt{n}\right)}$ iterations on average. In this paper, we provide a
deterministic algorithm for the same family of SSGs that has complexity
$\displaystyle O\left(2^{cn}Poly(N)\right)$ for some $\displaystyle c<1$.
Moreover, we will provide the first deterministic algorithm of this family
with parametrised complexity in the degree $\displaystyle d$ of max vertices
and number of max vertices, improving the trivial bound of $\displaystyle
O\left(d^{n}Poly(N)\right)$ to $\displaystyle
O\left(((d+1)/\sqrt{2})^{n}Poly(N)\right)$.

In the general case, Gimbert and Horn give in [8] a strategy improvement
algorithm whose complexity is a function of the random vertices with an
algorithm of complexity $\displaystyle\displaystyle O\left(r!Poly(N)\right)$.
Moreover, in [3], Auger Coucheney and Strozecki present a stochastic algorithm
that runs in $\displaystyle 2^{O(r)}$.

Auger, Badin de Montjoye and Strozecki present in [2] a general formulation
for strategy improvement algorithms that offers a general bound on the
complexity of all such algorithms depending on the format of the probability
value of the random nodes. It states that if there is some $\displaystyle q$
such that all probabilities are of the format $\displaystyle p/q$ and if each
iteration of the algorithm is done in polynomial time, then any strategy
improvement algorithm runs in $\displaystyle O\left(nq^{r}Poly(N)\right)$.

### Contributions

In this paper, we focus on SSGs whose max vertices have outdegree
$\displaystyle d$ with no constraints on the probability distribution of
random vertices. We introduce two new recursive algorithms to solve SSGs. The
first one, in Section 4, fixes the strategies on two vertices and recursively
solves the rest of the SSG. This algorithm has bound $\displaystyle
O\left(\left(\left\lfloor\frac{(d+1)^{2}}{2}\right\rfloor-1\right)^{n/2}Poly(|G|)\right)$.
The second algorithm presented in Section 5 works only for SSG of degree
$\displaystyle 2$. However, it achieves a better bound that the $\displaystyle
O\left(\sqrt{3}^{n}Poly(N)\right)$ of the first algorithm by reaching
$\displaystyle O\left(\varphi^{n}Poly(N)\right)$ with
$\displaystyle\varphi=(1+\sqrt{5})/2$ the golden ratio, which is, to the best
of our knowledge, the best complexity for deterministic algorithm on this
family of SSGs. Moreover, our algorithm does not require SSGs to be stopping,
a common technical hypothesis, which may require a squarring of the number of
vertices to be met.

##  2 An Overview of Simple Stochastic Games

Simple Stochastic Games where introduce by Anne Condon in [6]. We give a
definition close to the one given in [14, 2].

######  Definition 2.1.

A Simple Stochastic Game (SSG) is a directed graph $\displaystyle G=(V,E)$
with a partition of the vertex set $\displaystyle V$ in $\displaystyle
V_{\text{\sc max}}$, $\displaystyle V_{\text{\sc min}}$, $\displaystyle V_{R}$
and $\displaystyle V_{S}$ respectively called, max, min, random and sink
vertices such that:

  * •

every vertex of $\displaystyle V_{\text{\sc max}}$ and $\displaystyle
V_{\text{\sc min}}$ has outdegree at least two.

  * •

every vertex $\displaystyle x$ of $\displaystyle V_{R}$ has outdegree at least
one, and an associated rational probability distribution $\displaystyle
p_{x}(\cdot)$ on the outneighbourhood of $\displaystyle x$.

  * •

every vertex $\displaystyle x\in V_{S}$, there is an associated rational value
$\displaystyle\mbox{Val}(x)$ in the closed interval $\displaystyle[0,1]$.

######  Definition 2.2.

A binary SSG is an SSG where every vertex of $\displaystyle V_{\text{\sc
max}}$ has outdegree $\displaystyle 2$. An SSG is of degree $\displaystyle d$
if its max vertices are of degree at most $\displaystyle d$.

In this article we denote $\displaystyle|V_{\text{\sc max}}|$ by
$\displaystyle n$. We will write $\displaystyle|G|$ the size of the
representations of the game $\displaystyle G$ in bits. We present an instance
of an SSG in Figure 1.

$\displaystyle x_{1}$$\displaystyle 1$$\displaystyle n_{1}$$\displaystyle
r_{1}$$\displaystyle n_{2}$$\displaystyle x_{2}$$\displaystyle
n_{3}$$\displaystyle r_{2}$$\displaystyle x_{3}$$\displaystyle
x_{4}$$\displaystyle r_{3}$$\displaystyle 0$ Figure 1: Instance of an SSG
where square, circle and diamond vertices are respectively max, min and random
vertices and grey vertices are sinl vertices. The probability distributions of
the random vertices is the uniform distribution over their children.

The game is played by two players named max and min. The game starts by
placing a token on some initial vertex $\displaystyle x_{0}$. Then, the token
is moved according to the following rule. If the token is in a max or a min
vertex $\displaystyle x$, then the corresponding player moves the token
according to an outgoing arc from $\displaystyle x$. If the token is in a
random vertex $\displaystyle x$, then the token is moved according to the
probability distribution $\displaystyle p_{x}$. When the token reaches a sink
$\displaystyle s$, then player min has to pay player max the value
$\displaystyle\mbox{Val}(x)$. Informally, the goal of the game for max is to
maximise the value of the final sink and, conversely, the goal of the game for
min is to minimise it.

This game is turn-based, with perfect information. The strategies consider by
both players should thus be deterministic and only relies on the current
position of the token. This is a well-known result on simple stochastic games
and a proof of this can be found in [6, 14]. We thus only consider positional
strategies.

######  Definition 2.3.

A positional max strategy is a function $\displaystyle\sigma$ from
$\displaystyle V_{\text{\sc max}}$ to $\displaystyle V$ such that for all
$\displaystyle x$ in $\displaystyle V_{\text{\sc max}}$,
$\displaystyle(x,\sigma(x))$ is an arc of $\displaystyle G$.

A positional min strategy is a function $\displaystyle\tau$ from
$\displaystyle V_{\text{\sc min}}$ to $\displaystyle V$ such that for all
$\displaystyle x$ in $\displaystyle V_{\text{\sc min}}$,
$\displaystyle(x,\tau(x))$ is an arc of $\displaystyle G$.

In this paper when we talk about a pair of strategies
$\displaystyle(\sigma,\tau)$, $\displaystyle\sigma$ is a positional max
strategy and $\displaystyle\tau$ is a positional min strategy. We can now
define the value vector of a pair of strategy.

######  Definition 2.4.

For $\displaystyle(\sigma,\tau)$ a pair of strategies, and $\displaystyle
x_{0}$ a vertex of $\displaystyle V$, the value $\displaystyle
v_{\sigma,\tau}(x_{0})$ is the expected gain for max if both players play
according to $\displaystyle\sigma$ and $\displaystyle\tau$. In other words:

$\displaystyle v_{\sigma,\tau}(x_{0})=\sum\limits_{s\in
V_{S}}\mathds{P}_{\sigma,\tau}(x_{0}\longrightarrow s)\mbox{Val}(s)$

where $\displaystyle\mathds{P}_{\sigma,\tau}(x_{0}\longrightarrow s)$ is the
probability that the game ends in $\displaystyle s$ while starting in
$\displaystyle x_{0}$ and such that when the token is in a max vertex (resp.
min vertex) $\displaystyle x$ it moves to $\displaystyle\sigma(x)$ (resp.
$\displaystyle\tau(x)$).

The value vector $\displaystyle v_{\sigma,\tau}$ is the vector
$\displaystyle\left(v_{\sigma,\tau}(x)\right)_{x\in V}$. We compare value
vectors according to the pointwise order. For two value vector $\displaystyle
v$ and $\displaystyle v^{\prime}$, $\displaystyle v>v^{\prime}$ if, for all
$\displaystyle x$, $\displaystyle v(x)\geq v^{\prime}(x)$ and there is some
$\displaystyle y\in V$ such that $\displaystyle v(y)>v^{\prime}(y)$. As usual,
$\displaystyle v\geq v^{\prime}$ if $\displaystyle v>v^{\prime}$ or if
$\displaystyle v=v^{\prime}$.

Computing the value vector of a pair of strategies is equivalent to solving a
Markov chain which can be done in time polynomial in $\displaystyle|G|$.

For a max strategy $\displaystyle\sigma$ we say that a min strategy
$\displaystyle\tau$ is a best response for $\displaystyle\sigma$ if and only
if, for every min strategy $\displaystyle\tau^{\prime}$, we have
$\displaystyle v_{\sigma,\tau}\leq v_{\sigma,\tau^{\prime}}$. It is also well
known that best response exists.

######  Proposition 2.5 ([6]).

For every positional max strategy $\displaystyle\sigma$, there exists a
positional min strategy $\displaystyle\tau$ that is a best response for
$\displaystyle\sigma$. Moreover, a best response can be computed in polynomial
time by linear programming.

In the same way, we can define the best response for a min strategy.

######  Definition 2.6.

For every max strategy $\displaystyle\sigma$, we write $\displaystyle
v_{\sigma}=v_{\sigma,\tau(\sigma)}$ where $\displaystyle\tau(\sigma)$ is a
best response to $\displaystyle\sigma$.

We say that $\displaystyle\sigma$ is better than
$\displaystyle\sigma^{\prime}$ or has greater value, or we note
$\displaystyle\sigma>\sigma^{\prime}$ if $\displaystyle
v_{\sigma}>v_{\sigma^{\prime}}$.

It is well known in the literature ([6, 14]) that there is a pair of
positional strategies $\displaystyle(\sigma^{*},\tau^{*})$ that are called
optimal strategies such that they are best response of each other. The value
vector equilibrium $\displaystyle v_{\sigma^{*},\tau^{*}}$ is unique. Our goal
is to compute this value vector. A known characteristic of a pair of optimal
strategy is that its associated value vector satisfies local optimality.

######  Proposition 2.7 ([6]).

Let $\displaystyle G=(V,E)$ be an SSG. For $\displaystyle\sigma$ a max
strategy, $\displaystyle(\sigma,\tau(\sigma))$ is a pair of optimal strategy
if and only if $\displaystyle v_{\sigma}$ satisfies the following local
optimality condition:

  * •

for $\displaystyle x\in V_{\text{\sc max}}$, $\displaystyle
v_{\sigma}(x)=\max\\{v_{\sigma,\tau}(y)\;|\;(x,y)\in E\\}$

  * •

for $\displaystyle x\in V_{\text{\sc min}}$, $\displaystyle
v_{\sigma}(x)=\min\\{v_{\sigma,\tau}(y)\;|\;(x,y)\in E\\}$

It is important to notice that the converse of the proposition is true only
because we consider the best response to a max strategy. If we consider a min
strategy and its best response, then it does not hold anymore because of
possible loops.

##  3 Switch set and super-switch

###  3.1 Switch set

In this section we present an important concept for strategy improvement
algorithm: the switch set. We present several properties of the switch set for
SSG that we use to prove the complexity of our algorithms.

######  Definition 3.1.

Let $\displaystyle G=(V,E)$ be an SSG and $\displaystyle\sigma$ a max
strategy. The switch set of $\displaystyle\sigma$, written $\displaystyle
S_{\sigma}$, is the set of vertices $\displaystyle x$ such that there is
$\displaystyle y$ with $\displaystyle(x,y)\in E$ and $\displaystyle
v_{\sigma}(x)<v_{\sigma}(y)$

######  Definition 3.2.

Let $\displaystyle\sigma$ be a max strategy. For all $\displaystyle x\in
S_{\sigma}$, the improvement set, written $\displaystyle IS_{\sigma}(x)$ is
the set of neighbours $\displaystyle y$ of $\displaystyle x$ such that
$\displaystyle v_{\sigma}(y)>v_{\sigma}(x)$ and the best improvement option is
defined as $\displaystyle
bio_{\sigma}(x)=\operatorname*{arg\,max}\limits_{y\in
IS_{\sigma(x)}}\\{v_{\sigma}(y)\\}$.

In other words, the switch set of a max strategy is the set of max vertices
that do not satisfy the local optimality condition presented Proposition 2.7.
This notion directly gives the concept of $\displaystyle\sigma$-switch.

######  Definition 3.3.

Let $\displaystyle\sigma$ be a max strategy with a non-empty switch set
$\displaystyle S_{\sigma}$. A max strategy $\displaystyle\sigma^{\prime}$ is
said to be a $\displaystyle\sigma$-switch if
$\displaystyle\sigma^{\prime}\neq\sigma$, for all $\displaystyle x\in
V_{\text{\sc max}}\smallsetminus S_{\sigma}$,
$\displaystyle\sigma(x)=\sigma^{\prime}(x)$ and for all $\displaystyle x\in
S_{\sigma}$ such that $\displaystyle\sigma^{\prime}(x)\neq\sigma(x)$,
$\displaystyle\sigma^{\prime}(x)\in IS_{\sigma}(x)$.

A $\displaystyle\sigma$-switch is a strategy, where the strategy on vertices
that satisfy local optimality for $\displaystyle\sigma$ has been kept and it
had been changed on some vertices that did not satisfy local optimality.
Informally, as the name implies, it is a strategy where we "switch" the
strategy on some vertices that can achieve immediate better value by selecting
another child. A representation of a switch is given in Figure 3.

######  Definition 3.4.

For $\displaystyle\sigma$ a max strategy, the total switch
$\displaystyle\bar{\sigma}$ is the $\displaystyle\sigma$-switch where for all
$\displaystyle x\in S_{\sigma}$,
$\displaystyle\bar{\sigma}(x)=bio_{\sigma}(x)$.

######  Proposition 3.5 ([6, 14]).

For $\displaystyle\sigma$ a max strategy and $\displaystyle\sigma^{\prime}$ a
$\displaystyle\sigma$-switch, $\displaystyle v_{\sigma^{\prime}}>v_{\sigma}$.

The demonstration of this proposition uses the condition that the SSG is
stopping, which means that the SSG ends in a sink with probability
$\displaystyle 1$ and this for any pair of strategy. However, it had been
shown that this condition is unnecessary [4, 2].

######  Corollary 3.6.

A positional max strategy $\displaystyle\sigma$ is optimal if and only if
$\displaystyle S_{\sigma}$ is empty.

This property directly gives a family of algorithms called Hoffmann-Karp
algorithms. Starting from some max strategy $\displaystyle\sigma$, compute
$\displaystyle v_{\sigma}$ then, if $\displaystyle S_{\sigma}$ is not empty,
choose a $\displaystyle\sigma$-switch and iterate. Since the number of
strategies is bounded by $\displaystyle d^{n}$ where $\displaystyle d$ is the
degree of $\displaystyle G$, this algorithm terminates and provides an optimal
max strategy. Tripathi, Valkanova and Kumar shows in [14] that for binary SSG,
if at each iteration, we consider the $\displaystyle\sigma$-switch
$\displaystyle\bar{\sigma}$, then the algorithm needs $\displaystyle
O\left(2^{n}/n\right)$ iterations. We will show in Theorem 3.16 an extended
version of their main result that we use to find a bound of the Algorithm 1
presented in Section 4.

For $\displaystyle T$ a set of max vertices, and $\displaystyle\sigma$ a max
strategy, we define the subgame $\displaystyle G_{|T[\sigma]}$ as the game
$\displaystyle G$ where some max vertices have been replaced with random
vertices that go to some vertex with probability one according to the max
strategy $\displaystyle\sigma$. In other words, $\displaystyle G_{|T[\sigma]}$
is the game $\displaystyle G$ where max has to play as in
$\displaystyle\sigma$ in $\displaystyle T$.

######  Definition 3.7.

Let $\displaystyle G=(V,E)$ an SSG. For $\displaystyle\sigma$ a strategy and
$\displaystyle T$ a subset of $\displaystyle V_{\text{\sc max}}$ we write
$\displaystyle G_{|T[\sigma]}=(V,E^{\prime})$ the SSG that is a copy of
$\displaystyle G$ where $\displaystyle
E^{\prime}=E\smallsetminus\\{(x,y)\;|\;x\in T,\;y\neq\sigma(x)\\}$ and all
vertices $\displaystyle x$ of $\displaystyle T$ are random vertices, with
associated probability distribution $\displaystyle p_{x}(\sigma(x))=1$.

We provide an example of this transformation in Figure 2.

$\displaystyle x_{1}$$\displaystyle 1$$\displaystyle n_{1}$$\displaystyle
r_{1}$$\displaystyle n_{2}$$\displaystyle x_{2}$$\displaystyle
n_{3}$$\displaystyle r_{2}$$\displaystyle x_{3}$$\displaystyle
x_{4}$$\displaystyle r_{3}$$\displaystyle
0$$\displaystyle\longrightarrow$$\displaystyle r^{\prime}_{1}$$\displaystyle
1$$\displaystyle n_{1}$$\displaystyle r_{1}$$\displaystyle
n_{2}$$\displaystyle x_{2}$$\displaystyle n_{3}$$\displaystyle
r_{2}$$\displaystyle r^{\prime}_{3}$$\displaystyle
r^{\prime}_{4}$$\displaystyle r_{3}$$\displaystyle 0$ Figure 2: Transformation
of the game $\displaystyle G$ in the game $\displaystyle G_{T[\sigma]}$ where
$\displaystyle T=\\{x_{1};x_{3},x_{4}\\}$ and $\displaystyle\sigma(x_{1})=1$,
$\displaystyle\sigma(x_{3})=x_{2}$ and $\displaystyle\sigma(x_{4})=r2$. The
probability distribution on the random vertices is the uniform distribution.

There is a bijection between the strategy of $\displaystyle G_{|T[\sigma]}$
and the strategy of $\displaystyle G$ that plays has in $\displaystyle\sigma$
in T. In the rest of the paper, we identify those two sets of strategy.
Moreover, for a strategy $\displaystyle\sigma^{\prime}$ that plays as in
$\displaystyle\sigma$ in $\displaystyle T$ and any min strategy
$\displaystyle\tau$, there is equality between the value vectors
$\displaystyle v_{\sigma^{\prime},\tau}$ in $\displaystyle G$ and
$\displaystyle G_{|T[\sigma]}$.

######  Lemma 3.8 ([14]).

For any max strategy $\displaystyle\sigma$, $\displaystyle\sigma$ is optimal
in $\displaystyle G_{|S_{\sigma}[\sigma]}$.

######  Proof 3.9.

The switch set of $\displaystyle\sigma$ in $\displaystyle G_{|T[\sigma]}$ is
empty, hence, by Corollary 3.6, $\displaystyle\sigma$ is optimal in
$\displaystyle G_{|T[\sigma]}$.

The following proposition also appears in [14] and it allows us to study
strategies by just looking at their switch set.

######  Proposition 3.10.

Let $\displaystyle G$ be a binary SSG. For $\displaystyle\sigma$ and
$\displaystyle\sigma^{\prime}$ two max strategies such that $\displaystyle
S_{\sigma}\subsetneq S_{\sigma^{\prime}}$, then $\displaystyle
v_{\sigma}>v_{\sigma^{\prime}}$.

######  Proof 3.11.

Let $\displaystyle\sigma$ and $\displaystyle\sigma^{\prime}$ be two max
strategies such that $\displaystyle S_{\sigma}\subsetneq S_{\sigma^{\prime}}$.
If $\displaystyle\sigma^{\prime}$ is a strategy of $\displaystyle
G_{|S_{\sigma}[\sigma]}$, then $\displaystyle\sigma^{\prime}$ is not optimal
in $\displaystyle G_{|S_{\sigma}[\sigma]}$ by Corollary 3.6 and by Lemma 3.8,
$\displaystyle v_{\sigma}>v_{\sigma^{\prime}}$. Otherwise, we consider
$\displaystyle\sigma^{\prime\prime}$ that plays as in
$\displaystyle\sigma^{\prime}$ in $\displaystyle V_{\text{\sc
max}}\smallsetminus S_{\sigma}$ and as in $\displaystyle\sigma$ in
$\displaystyle S_{\sigma}$. $\displaystyle\sigma^{\prime\prime}$ is a
$\displaystyle\sigma^{\prime}$-switch, and a strategy of $\displaystyle
G_{|S_{\sigma}[\sigma]}$, thus: $\displaystyle
v_{\sigma^{\prime}}<v_{\sigma^{\prime\prime}}\leq v_{\sigma}$

In the same way, we can also consider the case where both switch sets are
equal.

######  Lemma 3.12.

Let $\displaystyle G$ be a binary SSG. For $\displaystyle\sigma$ and
$\displaystyle\sigma^{\prime}$ two max strategies such that $\displaystyle
S_{\sigma}=S_{\sigma^{\prime}}$, then $\displaystyle
v_{\sigma}=v_{\sigma^{\prime}}$ and for every $\displaystyle x$ in
$\displaystyle S_{\sigma}$, $\displaystyle\sigma(x)=\sigma^{\prime}(x)$

######  Proof 3.13.

Let $\displaystyle\sigma$ and $\displaystyle\sigma^{\prime}$ be two strategies
that satisfies our condition, and for the sake of contradiction, let us assume
that there is $\displaystyle x$ in $\displaystyle S_{\sigma}$ such that
$\displaystyle\sigma(x)\neq\sigma^{\prime}(x)$. Then, the strategy
$\displaystyle\sigma^{\prime\prime}$ that plays as $\displaystyle\sigma$ in
$\displaystyle S_{\sigma}$ and as $\displaystyle\sigma^{\prime}$ in the other
vertices is a $\displaystyle\sigma^{\prime}$-switch. Thus $\displaystyle
v_{\sigma^{\prime\prime}}>v_{\sigma^{\prime}}$. Since
$\displaystyle\sigma^{\prime\prime}$ plays as $\displaystyle\sigma$ on
$\displaystyle S_{\sigma}$, by Lemma 3.8, $\displaystyle v_{\sigma}\geq
v_{\sigma^{\prime\prime}}$. Thus $\displaystyle
v_{\sigma}>v_{\sigma^{\prime}}$. We similarly can prove that $\displaystyle
v_{\sigma^{\prime}}>v_{\sigma}$, which yields a contradiction. Hence,
$\displaystyle\sigma$ and $\displaystyle\sigma^{\prime}$ plays similarly on
$\displaystyle S_{\sigma}$. The strategy $\displaystyle\sigma$ and
$\displaystyle\sigma^{\prime}$ are optimal strategy of $\displaystyle
G_{|S_{\sigma}[\sigma]}$ and thus have the same value.

###  3.2 Super-Switch

In this section, we will extend the classic notion of switch in order to add a
perfect resolution on some of its vertices.

A super-switch is obtained by switching some vertices of
$\displaystyle\sigma$, fixing the strategy on a set of max vertices that
include the switched vertices and then considering the optimal strategy of the
subgame.

Let $\displaystyle\sigma$ be a max strategy with a non-empty switch set
$\displaystyle S_{\sigma}$ and $\displaystyle T\subset V_{\text{\sc max}}$
with $\displaystyle T\cap S_{\sigma}\neq\emptyset$. A
$\displaystyle(\sigma,T)$-super-switch is a strategy
$\displaystyle\tilde{\sigma}$ obtained from an intermediate
$\displaystyle\sigma$-switch $\displaystyle\sigma^{\prime}$ such that
$\displaystyle\forall x\notin T,\;\sigma(x)=\sigma^{\prime}(x)$ by computing
an optimal strategy of $\displaystyle G_{|T[\sigma^{\prime}]}$.

We gives a representation of a super-switch in Figure 3

$\displaystyle 0$$\displaystyle r_{1}$$\displaystyle 2/7$$\displaystyle
x_{1}$$\displaystyle 4/7$$\displaystyle x_{2}$$\displaystyle
2/7$$\displaystyle r_{2}$$\displaystyle 1/7$$\displaystyle
x_{3}$$\displaystyle 0$$\displaystyle r_{3}$$\displaystyle 4/7$$\displaystyle
x_{4}$$\displaystyle 0$$\displaystyle x_{5}$$\displaystyle 1/7$$\displaystyle
1$$\displaystyle\sigma$:$\displaystyle\sigma^{\prime}$:$\displaystyle\sigma^{\prime\prime}$:$\displaystyle\longrightarrow$$\displaystyle
0$$\displaystyle r_{1}$$\displaystyle 2/7$$\displaystyle x_{1}$$\displaystyle
1/7$$\displaystyle x_{2}$$\displaystyle 2/7$$\displaystyle
r_{2}$$\displaystyle 1/7$$\displaystyle x_{3}$$\displaystyle
4/7$$\displaystyle r_{3}$$\displaystyle 4/7$$\displaystyle
x_{4}$$\displaystyle 1$$\displaystyle x_{5}$$\displaystyle 1/7$$\displaystyle
1$$\displaystyle\longrightarrow$$\displaystyle 0$$\displaystyle
r_{1}$$\displaystyle 2/7$$\displaystyle x_{1}$$\displaystyle
1/7$$\displaystyle x_{2}$$\displaystyle 4/7$$\displaystyle
r_{2}$$\displaystyle 1/7$$\displaystyle x_{3}$$\displaystyle
4/7$$\displaystyle r_{3}$$\displaystyle 4/7$$\displaystyle
x_{4}$$\displaystyle 1$$\displaystyle x_{5}$$\displaystyle 1/7$$\displaystyle
1$ Figure 3: The strategy of max are represented by plain arcs and the
probability distribution on the random vertices is the uniform distribution.
The switch set of $\displaystyle\sigma$, $\displaystyle S_{\sigma}$ is
$\displaystyle\\{x_{3},x_{4},x_{5}\\}$. The strategy
$\displaystyle\sigma^{\prime}$ is a $\displaystyle\sigma$-switch and
$\displaystyle\sigma^{\prime\prime}$ is a
$\displaystyle(\sigma,S_{\sigma})$-super-switch.

######  Lemma 3.14.

For $\displaystyle\sigma$ a non-optimal max strategy, $\displaystyle T$ a set
of max vertices and $\displaystyle\sigma^{\prime}$ a
$\displaystyle(\sigma,T)$-super-switch, $\displaystyle
v_{\sigma^{\prime}}>v_{\sigma}$.

######  Proof 3.15.

We consider the strategy $\displaystyle\sigma^{\prime\prime}$ that plays as
$\displaystyle\sigma^{\prime}$ on T and as $\displaystyle\sigma$ on
$\displaystyle V_{\text{\sc max}}\smallsetminus T$. The strategy
$\displaystyle\sigma^{\prime\prime}$ is a $\displaystyle\sigma$-switch and by
Proposition 3.5 $\displaystyle v_{\sigma^{\prime\prime}}>v_{\sigma}$.
Moreover, $\displaystyle\sigma^{\prime}$ is the optimal strategy of
$\displaystyle G_{|T[\sigma^{\prime\prime}]}$ and
$\displaystyle\sigma^{\prime\prime}$ is also a strategy of $\displaystyle
G_{|T[\sigma^{\prime\prime}]}$. Hence, $\displaystyle v_{\sigma^{\prime}}\geq
v_{\sigma^{\prime\prime}}$ and $\displaystyle v_{\sigma^{\prime}}>v_{\sigma}$.

In [14], Tripathi, Valkanova and Kumar, show that for a strategy
$\displaystyle\sigma$, there is at least $\displaystyle|S|-1$
$\displaystyle\sigma$-switch $\displaystyle\sigma^{\prime}$ different from
$\displaystyle\bar{\sigma}$ such that $\displaystyle v_{\sigma^{\prime}}\leq
v_{\bar{\sigma}}$. In Theorem 3.16 we adapt their proof to show that this
result can be extended to super-switch.

For $\displaystyle\sigma$ a max strategy, $\displaystyle T$ a set of max
vertices and $\displaystyle\sigma^{\prime}$ a $\displaystyle(\sigma,T)$-super-
switch, we note $\displaystyle D_{\sigma,\sigma^{\prime}}$ the set
$\displaystyle\\{x\;|\;\sigma(x)\neq\sigma^{\prime}(x),x\in T\\}$ the set of
vertices that has been switched in the intermediate
$\displaystyle\sigma$-switch.

######  Theorem 3.16.

For $\displaystyle\sigma$ a non-optimal max strategy, $\displaystyle T$ a set
of max vertices intersecting $\displaystyle S_{\sigma}$ and
$\displaystyle\sigma^{\prime}$ a $\displaystyle(\sigma,T)$-super-switch, there
is at least $\displaystyle|D_{\sigma,\sigma^{\prime}}|-1$
$\displaystyle(\sigma,T)$-super-switches
$\displaystyle\sigma^{\prime\prime}\neq\sigma^{\prime}$ such that
$\displaystyle v_{\sigma}<v_{\sigma^{\prime\prime}}\leq v_{\sigma^{\prime}}$.

######  Proof 3.17.

First, we show that Theorem 3.16 is true in the case $\displaystyle
D_{\sigma,\sigma^{\prime}}=2$. Let $\displaystyle
D_{\sigma,\sigma^{\prime}}=\\{x;y\\}$. We consider the game $\displaystyle
G^{\prime}$ which is the game $\displaystyle
G_{|T\smallsetminus\\{x;y\\}[\sigma]}$ where all edges
$\displaystyle(x,x^{\prime})$ and $\displaystyle(y,y^{\prime})$ with
$\displaystyle x^{\prime}\notin\\{\sigma(x);\sigma^{\prime}(x)\\}$ and
$\displaystyle y^{\prime}\notin\\{\sigma(y),\sigma^{\prime}(y)\\}$ has been
removed. Both $\displaystyle\sigma$ and $\displaystyle\sigma^{\prime}$ are
strategies in the game $\displaystyle G^{\prime}$. We write $\displaystyle
S_{\tilde{\sigma}}$ the switch set of a strategy $\displaystyle\tilde{\sigma}$
in the game $\displaystyle G$ and $\displaystyle S^{\prime}_{\tilde{\sigma}}$
the switch set of a strategy $\displaystyle\tilde{\sigma}$ in the game
$\displaystyle G^{\prime}$. Hence, $\displaystyle
S^{\prime}_{\sigma}=\\{x;y\\}$. Let call $\displaystyle\sigma_{x}$ and
$\displaystyle\sigma_{y}$ the $\displaystyle(\sigma,T)$-super-switch where
respectively only $\displaystyle x$ and only $\displaystyle y$ has been
switched in $\displaystyle T$.

By Lemma 3.10, $\displaystyle S^{\prime}_{\sigma^{\prime}}$ is strictly
included in $\displaystyle\\{x;y\\}$ and thus is at most a singleton. If
$\displaystyle S^{\prime}_{\sigma^{\prime}}$ is empty then, $\displaystyle
v_{\sigma}<v_{\sigma_{x}},v_{\sigma_{y}}\leq v_{\sigma^{\prime}}$. We suppose
that $\displaystyle S^{\prime}_{\sigma^{\prime}}=\\{x\\}$. Then, we notice
that $\displaystyle\sigma_{x}$ and $\displaystyle\sigma^{\prime}$ are both
strategies of $\displaystyle G^{\prime}_{|\\{x\\}[\sigma^{\prime}]}$ and
$\displaystyle\sigma^{\prime}$ is optimal in $\displaystyle
G^{\prime}_{|\\{x\\}[\sigma^{\prime}]}$. Thus, $\displaystyle
v_{\sigma}<v_{\sigma_{x}}\leq v_{\sigma^{\prime}}$ and $\displaystyle
v_{\sigma_{y}}>v_{\sigma^{\prime}}$. This implies that if $\displaystyle
v_{\sigma_{x}}\ngtr v_{\sigma_{y}}$, $\displaystyle v_{\sigma^{\prime}}\geq
v_{\sigma_{x}}$ and if we also have $\displaystyle v_{\sigma_{x}}\neq
v_{\sigma_{y}}$ then $\displaystyle y\in S^{\prime}_{\sigma_{x}}$

Now we look at the general case. Let $\displaystyle
D_{\sigma,\sigma^{\prime}}=\\{x_{,}\ldots,x_{t}\\}$. For $\displaystyle
E\subset\\{1,\ldots,t\\}$, we write $\displaystyle v_{E}$ the value of the
$\displaystyle(\sigma,T)$-super-switch $\displaystyle\sigma_{\\{E\\}}$ where
only the vertices $\displaystyle x_{i}$ for $\displaystyle i\in E$ has been
switched. We assume that for all $\displaystyle i<j\leq t$, $\displaystyle
v_{\\{i\\}}\ngtr v_{\\{j\\}}$. If for all $\displaystyle j>1$, $\displaystyle
v_{\\{1\\}}\neq v_{\\{j\\}}$ then $\displaystyle v_{\\{1;j\\}}\geq
v_{\\{1\\}}$ and $\displaystyle j\in S_{\\{}\sigma_{\\{1\\}}\\}$.

Otherwise, we suppose that there is $\displaystyle k>1$ such that for all
$\displaystyle 2\leq j\leq k$, $\displaystyle v_{\\{1\\}}=v_{\\{j\\}}$ and for
all $\displaystyle j>k$, $\displaystyle v_{\\{1\\}}\neq v_{\\{j\\}}$. We
consider the game $\displaystyle G^{\prime}$ which is the game $\displaystyle
G_{|T\smallsetminus\\{x_{1};\ldots;x_{k}\\}[\sigma]}$ and where for
$\displaystyle i\leq k$, all edges from $\displaystyle x_{i}$ not towards
$\displaystyle\sigma(x_{i})$ or $\displaystyle\sigma^{\prime}(x_{i})$ are
removed. We note $\displaystyle S^{\prime}$ the switch sets in $\displaystyle
G^{\prime}$ and $\displaystyle\sigma^{\prime}=\sigma_{\\{1;\ldots;k\\}}$. By
Lemma 3.10, $\displaystyle S^{\prime}_{\sigma^{\prime}}$ is strictly included
in $\displaystyle\\{1;\ldots;k\\}$. We suppose that $\displaystyle
S^{\prime}_{\sigma^{\prime}}=\\{1;\ldots;k^{\prime}\\}$ for some
$\displaystyle k^{\prime}<k$. By induction hypothesis, we know that
$\displaystyle v_{\\{1\\}}\leq v_{\\{1;\ldots;k^{\prime}\\}}$ and
$\displaystyle\sigma^{\prime}$ and
$\displaystyle\sigma_{\\{1;\ldots;k^{\prime}\\}}$ are both optimal strategies
of $\displaystyle G^{\prime}_{|\\{1;\ldots;k^{\prime}\\}[\sigma^{\prime}]}$
and thus have same value. Thus, $\displaystyle v_{E}\leq v_{\sigma^{\prime}}$
for all $\displaystyle E\subseteq\\{1;\ldots;k\\}$ and for all $\displaystyle
j>k$, $\displaystyle x_{j}\in S_{\sigma^{\prime}}$. We conclude by induction
on the $\displaystyle\\{x_{j};\ldots;x_{t}\\}$.

Thus, we have that $\displaystyle
v_{\sigma^{\prime}}=v_{\\{1,2,\ldots,t\\}}\geq
v_{\\{1,2,\ldots,t-1\\}}\geq\ldots\geq v_{\\{1\\}}$ and we have proven that
there is at least $\displaystyle|D_{\sigma,\sigma^{\prime}}|-1$
$\displaystyle(\sigma,T)$-super-switchs
$\displaystyle\sigma^{\prime\prime}\neq\sigma^{\prime}$ such that
$\displaystyle v_{\sigma}<v_{\sigma^{\prime\prime}}\leq v_{\sigma^{\prime}}$.

We notice that a $\displaystyle\sigma$-switch is a
$\displaystyle(\sigma,V_{\text{\sc max}})$-super-switch. Hence, Theorem 3.16
also proves the main theorem of [14].

##  4 A recursive algorithm with a pair of fixed vertices

In all this section, we only consider SSGs of degree $\displaystyle d$.

Algorithm 1 works by fixing the strategy of the game on two vertices, then
recursively solving the rest of the game. If this does not yield an optimal
strategy, then it switches the strategy on the fixed vertices and iterate. The
switch sets of the considered strategies after the recursive call (line
$\displaystyle 9$) are included in of $\displaystyle\\{x,y\\}$.

Data: $\displaystyle G$ an SSG

Result: $\displaystyle\sigma$ an optimal max strategy and $\displaystyle v$
the optimal value vector.

1 begin

2 if  _$\displaystyle|V_{\text{\sc max}}|\leq 1$_ then

3 Compute the optimal strategy $\displaystyle\sigma$ by testing all
possibilities

4 return _$\displaystyle(\sigma,v_{\sigma})$_

5 $\displaystyle\sigma\longleftarrow$ a max strategy

6 $\displaystyle x,\;y\longleftarrow$ two vertices of $\displaystyle
V_{\text{\sc max}}$

7 $\displaystyle(\sigma,v)\longleftarrow$ RecursivePair($\displaystyle
G_{|\\{x,y\\}[\sigma]}$)

8 while  _$\displaystyle\sigma$ is not optimal_ do

9 $\displaystyle\sigma\longleftarrow\bar{\sigma}$

10 $\displaystyle(\sigma,v)\longleftarrow$ RecursivePair($\displaystyle
G_{|\\{x,y\\}[\sigma]}$)

11

12 return _$\displaystyle(\sigma,v)$_

13

Algorithm 1 RecursivePair

Let us first recall that computing $\displaystyle v_{\sigma}$ can be done in
polynomial time in $\displaystyle|G|$ by solving a linear programming problem.

We write $\displaystyle N$ the number of iterations of the loop. Let
$\displaystyle\sigma_{i}$ be the value of $\displaystyle\sigma$ at the start
of the $\displaystyle i$-th iteration of the loop line 8 and
$\displaystyle\sigma_{N+1}$ the value of $\displaystyle\sigma$ after the last
iteration of the loop. Algorithm 1 makes $\displaystyle N+1$ recursive calls
to an instance with $\displaystyle n-2$ max vertices. We notice that for all
$\displaystyle i$, $\displaystyle S_{\sigma_{i}}\subseteq\\{x;y\\}$.

######  Lemma 4.1.

For all $\displaystyle i<N+1$, $\displaystyle|S_{\sigma_{i}}|\neq 0$.
Moreover, tere is at most $\displaystyle 2(d-1)$ indices $\displaystyle k$
such that $\displaystyle|S_{\sigma_{k}}|=1$.

######  Proof 4.2.

If $\displaystyle S_{\sigma_{i}}=\emptyset$, then the algorithm stops and
$\displaystyle i=N+1$. Thus, for all $\displaystyle k<N+1$, $\displaystyle
S_{\sigma_{k}}\neq\emptyset$.

For all neighbours $\displaystyle x^{\prime}$ of $\displaystyle x$ there is at
most one $\displaystyle k$ such that $\displaystyle\sigma_{k}(x)=x^{\prime}$
and $\displaystyle S_{\sigma_{k}}=\\{x\\}$ since such strategies are all
optimal in $\displaystyle G_{|\\{x\\}[\sigma_{k}]}$ and thus have the same
value. Moreover, if there is an optimal strategy $\displaystyle\sigma^{*}$
such that $\displaystyle\sigma^{*}(x)=x^{\prime}$, then all optimal strategies
of $\displaystyle G_{|\\{x\\}[\sigma^{*}]}$ are optimal on $\displaystyle G$
and there is no strategy $\displaystyle\sigma$ such that
$\displaystyle\sigma(x)=x^{\prime}$ and $\displaystyle S_{\sigma}=\\{x\\}$.
Hence, there is at most $\displaystyle 2(d-1)$ visited strategies with switch
set of size $\displaystyle 1$.

######  Proposition 4.3.

Algorithm 1 runs in $\displaystyle
O\left(\left(\left\lfloor\frac{(d+1)^{2}}{2}\right\rfloor-1\right)^{n/2}Poly(|G|)\right)$.

######  Proof 4.4.

If we write, $\displaystyle n_{0}$, $\displaystyle n_{1}$ and $\displaystyle
n_{2}$ the number of indices $\displaystyle i$ such that
$\displaystyle\sigma_{i}$ has a switch set of respectively size $\displaystyle
0$, $\displaystyle 1$ and $\displaystyle 2$, then $\displaystyle
N+1=n_{0}+n_{1}+n_{2}$. By Theorem 3.16, if $\displaystyle
S_{\sigma_{i}}=\\{x;y\\}$, then there is a super-switch
$\displaystyle\sigma^{\prime}$ such that $\displaystyle
v_{\sigma_{i}}<v_{\sigma^{\prime}}\leq v_{\sigma_{i+1}}$. Thus, $\displaystyle
n_{0}+n_{1}+2n_{2}\leq d^{2}$. We also know by Lemma 4.1 that $\displaystyle
n_{0}+n_{1}\leq 2d-1$. Then:

$\displaystyle 2(N+1)=(n_{0}+n_{1})+(n_{0}+n_{1}+2n_{2})\leq d^{2}+2d-1$

Which gives:

$\displaystyle N+1\leq\frac{(d+1)^{2}}{2}-1$

Since $\displaystyle N+1$ is an integer, we have $\displaystyle
N+1\leq\left\lfloor\frac{(d+1)^{2}}{2}-1\right\rfloor$. Hence, Algorithm 1
makes at most $\displaystyle\left\lfloor\frac{(d+1)^{2}}{2}-1\right\rfloor$
recursive calls to an instance with $\displaystyle n-2$ max vertices and
Algorithm 1 runs in $\displaystyle
O\left(\left(\left\lfloor\frac{(d+1)^{2}}{2}\right\rfloor-1\right)^{n/2}Poly(|G|)\right)$.

In the case of binary SSG, Algorithm 1 is similar to Ludwig’s Algorithm [11]
which fixes the strategy on the vertices one at a time. The choice of which
vertex to fix is random and provides an algorithm that runs in expected time
$\displaystyle 2^{O\left(\sqrt{n}\right)}Poly\left(|V|\right)$. However,
despite the proximity of the two algorithms, we were yet not able to find a
similar analysis as the one in [11] to the stochastic version of Algorithm 1.

On binary SSG, Algorithm 1 gives a complexity bound in $\displaystyle
O\left(\sqrt{3}^{n}Poly(|G|)\right)$ which is better that the currently known
one for binary SSG in [14]. However, it is still possible to improve this
complexity, as we show in the next section.

##  5 A Recursive Algorithm for Binary SSGs

In all this section, we will only consider binary SSG.

The concept of Algorithm 1 is to fix a subset of vertices and recursively
solve the rest of the game. Then, we switch the current strategy and fix a
smaller subset of vertices and reiterate. We show that we never make a call to
an instance with $\displaystyle n-1$ max vertices. This is done by carefully
selecting the set of fixed vertices.

Data: $\displaystyle G$ an SSG

Result: $\displaystyle\sigma$ an optimal max strategy and $\displaystyle v$
the optimal value vector.

1 begin

2 $\displaystyle\sigma\longleftarrow$ a max strategy

3 $\displaystyle S\longleftarrow S_{\sigma}$

4 $\displaystyle\sigma\longleftarrow\bar{\sigma}$

5 $\displaystyle v\longleftarrow v_{\sigma}$

6 $\displaystyle T\longleftarrow S\cup S_{\sigma}$

7 $\displaystyle S\longleftarrow S_{\sigma}$

8 while  _$\displaystyle S\neq\emptyset$_ do

9 $\displaystyle\sigma\longleftarrow\bar{\sigma}$

10 $\displaystyle(\sigma,v)\longleftarrow$ DecreasingFixedSet($\displaystyle
G_{|T[\sigma]}$)

11 $\displaystyle T\longleftarrow S\cup S_{\sigma}$

12 $\displaystyle S\longleftarrow S_{\sigma}$

13

14 return _$\displaystyle(\sigma,v)$_

15

Algorithm 2 DecreasingFixedSet

As stated before, the goal of Algorithm 2 is to avoid the call to a game with
$\displaystyle n-1$ max vertices. In order to achieve this, the set of
vertices that is fixed in the recursive call is the union of the previous and
current switch set. Computing $\displaystyle S_{\sigma}$ at line 11 can be
done in linear time with the value vector $\displaystyle v$ computed at line
10.

######  Lemma 5.1.

Algorithm 2 terminates and computes an optimal max strategy and its value
vector.

######  Proof 5.2.

The value vectors of the visited strategies are increasing by Proposition 3.5
and there are a finite number of max strategies, hence Algorithm 2 terminates.
The algorithm ends when the switch set of a max strategy is empty, hence when
the algorithm terminates it computes an optimal max strategy. Alternatively,
Algorithm 2 is a strategy improvement algorithm, thus by [2], it terminates
and computes an optimal strategy.

Let us call $\displaystyle T_{0}=V_{\text{\sc max}}$ and $\displaystyle S_{0}$
and $\displaystyle\sigma_{0}$ the value of the variables $\displaystyle S$ and
$\displaystyle\sigma$ after line 3. In addition, we call
$\displaystyle\sigma_{i}$, $\displaystyle T_{i}$ and $\displaystyle S_{i}$ the
value of the variables $\displaystyle\sigma$, $\displaystyle T$ and
$\displaystyle S$ at the beginning of the $\displaystyle i$-th iteration of
the while loop. Let $\displaystyle N$ be the number of iterations. We call
$\displaystyle T_{N+1}$, $\displaystyle S_{N+1}$ and
$\displaystyle\sigma_{N+1}$ the value of those variables at the end of the
last iteration. By line 11 of Algorithm 2 for every $\displaystyle i$,
$\displaystyle S_{i}\subset T_{i}$. We create a partition of $\displaystyle
T_{i}$ by considering $\displaystyle S_{i}$ and $\displaystyle
S_{i-1}\smallsetminus S_{i}$.

If for all $\displaystyle i\geq 1$, $\displaystyle S_{i-1}\smallsetminus
S_{i}$ is not empty, then $\displaystyle|T_{i}|>|S_{i}|$ and $\displaystyle
S_{i}$ not empty implies that $\displaystyle|T_{i}|\geq 2$. Then, all
recursive calls to Algorithm 2 are made to a subgame with at most
$\displaystyle n-2$ max vertices.

######  Proposition 5.3.

For every $\displaystyle 1\leq i\leq N$, $\displaystyle S_{i-1}\smallsetminus
S_{i}$ is not empty.

######  Proof 5.4.

For every $\displaystyle 1\leq i\leq N$, by definition $\displaystyle
T_{i}=S_{i-1}\cup S_{i}$. The strategy $\displaystyle\sigma_{i}$ is a
$\displaystyle(\sigma_{i-1},T_{i-1})$-super-switch, thus $\displaystyle
v_{\sigma_{i}}>v_{\sigma_{i-1}}$ and $\displaystyle S_{i-1}$ is not a subset
or equal to $\displaystyle S_{i}$ according to the contraposition of
Proposition 3.10.

Now, we need to prove that each iteration of the loop strictly decreases the
size of $\displaystyle T$.

######  Proposition 5.5.

For $\displaystyle 1\leq i<N$, $\displaystyle T_{i+1}\subsetneq T_{i}$.

######  Proof 5.6.

Let $\displaystyle 1\leq i<N$. First of all, we notice that $\displaystyle
S_{i}\subseteq T_{i-1}$ since $\displaystyle\sigma_{i}$ is optimal in
$\displaystyle G_{T_{i-1}[\sigma_{i}]}$, and $\displaystyle T_{i}=S_{i-1}\cup
S_{i}$. Thus, we have $\displaystyle T_{i}\subseteq T_{i-1}$.

We recall that strategy $\displaystyle\sigma_{i-1}$ is optimal in the game
$\displaystyle G_{S_{i-1}[\sigma_{i-1}]}$. We notice that for every
$\displaystyle x\in S_{i-1}\cap S_{i}$,
$\displaystyle\sigma_{i+1}(x)=\sigma_{i-1}(x)$: the strategy of every vertex
in $\displaystyle S_{i-1}\cap S_{i}$ has been changed twice, thus going back
to its original value since we consider binary SSG. We recall that
$\displaystyle S_{i-1}\smallsetminus S_{i}$ is not empty by Proposition 5.3
and assume for the sake of contradiction that $\displaystyle
S_{i-1}\smallsetminus S_{i}\subset S_{i+1}$. Then we define the strategy
$\displaystyle\sigma^{\prime}$ as follows:

$\displaystyle\forall x\in S_{i-1}\smallsetminus
S_{i},\;\sigma^{\prime}(x)\neq\sigma_{i+1}(x)$ $\displaystyle\forall x\notin
S_{i-1}\smallsetminus S_{i},\;\sigma^{\prime}(x)=\sigma_{i+1}(x)$

Since $\displaystyle S_{i}\smallsetminus S_{i-1}$ is a subset of
$\displaystyle S_{i+1}$, $\displaystyle\sigma^{\prime}$ is a
$\displaystyle\sigma_{i+1}$-switch and by Proposition 3.5
$\displaystyle\sigma^{\prime}>\sigma_{i+1}>\sigma_{i}$. However, for all
$\displaystyle x\in S_{i-1}$,
$\displaystyle\sigma^{\prime}(x)=\sigma_{i-1}(x)$ and
$\displaystyle\sigma^{\prime}$ is a strategy of $\displaystyle
G_{S_{i-1}[\sigma_{i-1}]}$ which contradicts the optimality of
$\displaystyle\sigma_{i-1}$ on this game. This shows that there exists
$\displaystyle x$ in $\displaystyle S_{i-1}\smallsetminus S_{i}$ but not in
$\displaystyle S_{i+1}$. In other words, there is $\displaystyle x$ in
$\displaystyle S_{i-1}$ and thus in $\displaystyle T_{i}$ but not in
$\displaystyle S_{i}\cup S_{i+1}$ and thus not in $\displaystyle T_{i+1}$.
Therefore, we have proven that $\displaystyle T_{i+1}\subsetneq T_{i}$. In
order to better visualise this proof a representation of the successive
switches is provided Figure 4.

$\displaystyle x$$\displaystyle x$$\displaystyle x$$\displaystyle
x$$\displaystyle x$$\displaystyle x$$\displaystyle\sigma_{i-1}$$\displaystyle
S_{i-1}$$\displaystyle T_{i}$$\displaystyle x$$\displaystyle x$$\displaystyle
x$$\displaystyle x$$\displaystyle x$$\displaystyle
x$$\displaystyle\sigma_{i}$$\displaystyle S_{i}$$\displaystyle
T_{i}$$\displaystyle x$$\displaystyle x$$\displaystyle x$$\displaystyle
x$$\displaystyle x$$\displaystyle
x$$\displaystyle\sigma_{i+1}$$\displaystyle\notin S_{i+1}$$\displaystyle
T_{i}$ Figure 4: Strategy on the vertices of $\displaystyle T_{i}$ under
strategies $\displaystyle\sigma_{i-1}$, $\displaystyle\sigma_{i}$ and
$\displaystyle\sigma_{i+1}$

We can now give a bound on the complexity of Algorithm 2.

######  Theorem 5.7.

Algorithm 2 has time complexity $\displaystyle
O\left(\varphi^{n}Poly(|G|)\right)$, where
$\displaystyle\varphi=\frac{1+\sqrt{5}}{2}$ is the golden ratio.

######  Proof 5.8.

We denote by $\displaystyle C(0,k)$, the complexity of solving an SSG with
$\displaystyle 0$ max vertices and $\displaystyle k$ total vertices. This is
the resolution of a one-player game and can be done in polynomial time in the
size of the game by solving a linear programming problem. We define
$\displaystyle C(n,k)$ as:

$\displaystyle C(n,k)=C(n-2,k)+C(n-3,k)+\ldots+C(1,k)+3C(0,k)$

We show by induction that the complexity of solving an SSG using Algorithm 2
with $\displaystyle n$ max vertices and $\displaystyle k$ total vertices is
bounded by $\displaystyle C(n,k)$. According to Proposition 5.5, each call to
DecreasingFixedSet is done on an SSG with a decreasing number of max vertices.
Proposition 5.3 also stipulates that if $\displaystyle S_{i}$ is not empty,
then $\displaystyle S_{i-1}\smallsetminus S_{i}$ is also not empty and
$\displaystyle|T_{i}|$ is greater than one. Thus, each recursive call is made
on an instance with at most $\displaystyle n-2$ max vertices. Finally,
$\displaystyle v_{\sigma}$ is computed twice before the loop, costing
$\displaystyle C(0,k)$ operations. Therefore Algorithm 2 has time complexity
$\displaystyle O\left(C(n,k)\right)$. We notice that $\displaystyle
C(n,k)-C(n-1,k)=C(n-2,k)$. Thus, we have:

$\displaystyle C(n,k)=O\left(\varphi^{n}Poly(|G|)\right)$

Thus, we have shown that Algorithm 2 has time complexity $\displaystyle
O\left(\varphi^{n}Poly(|G|)\right)$.

The polynomial factor in all our Algorithms corresponds to the complexity of
computing $\displaystyle v_{\sigma}$ from $\displaystyle\sigma$. We recall
that this is the complexity of solving a linear programming problem with
$\displaystyle|V|$ variables. It is the same polynomial factor as the one in
Tripathi, Valkanova and Kumar’s algorithm [14] which runs in $\displaystyle
O\left(2/n\cdot Poly(|G|)\right)$.

However, the analysis of Algorithm 2 does not hold in the case of SSG with
higher degree. Algorithm 1 can still be improved for some degree by changing
the size of the fixed set according to $\displaystyle d$. For instance, if we
fix set of size $\displaystyle 3$ the complexity of solving SSG of degree
$\displaystyle 3$ is $\displaystyle O\left(17^{n/3}\right)$ iterations instead
of $\displaystyle O\left(7^{n/2}\right)$. For information, $\displaystyle
17^{1/3}\simeq 2.57$ and $\displaystyle 7^{1/2}\simeq 2.65$. However,
increasing the size of the fixed set not always hold better complexity. For
binary SSG, the number of iterations with set of size $\displaystyle 2$ is
$\displaystyle O\left(3^{n/2}\right)$ and $\displaystyle
O\left(6^{n/3}\right)$ for set of size $\displaystyle 3$ and we know that
$\displaystyle 6^{1/3}\simeq 1.82$ and $\displaystyle 3^{1/2}\simeq 1.73$.

## References

  * [1] Daniel Andersson and Peter Bro Miltersen.  The complexity of solving stochastic games on graphs.  In International Symposium on Algorithms and Computation, pages 112–121, 2009.
  * [2] David Auger, Xavier Badin de Montjoye, and Yann Strozecki.  A Generic Strategy Improvement Method for Simple Stochastic Games.  In Filippo Bonchi and Simon J. Puglisi, editors, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), volume 202 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:22, 2021.
  * [3] David Auger, Pierre Coucheney, and Yann Strozecki.  Solving Simple Stochastic Games with Few Random Nodes Faster Using Bland’s Rule.  In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), pages 9:1–9:16, 2019.
  * [4] Krishnendu Chatterjee, Luca de Alfaro, and Thomas A. Henzinger.  Strategy improvement for concurrent reachability and turn-based stochastic safety games.  Journal of Computer and System Sciences, 79(5):640 – 657, 2013\.
  * [5] Taolue Chen, Marta Kwiatkowska, Aistis Simaitis, and Clemens Wiltsche.  Synthesis for multi-objective stochastic games: An application to autonomous urban driving.  In Quantitative Evaluation of Systems, pages 322–337, 2013.
  * [6] Anne Condon.  On algorithms for simple stochastic games.  pages 51–72, 1990.
  * [7] Anne Condon.  The complexity of stochastic games.  Information and Computation, 96(2):203–224, 1992.
  * [8] Hugo Gimbert and Florian Horn.  Simple stochastic games with few random vertices are easy to solve.  In Foundations of Software Science and Computational Structures, pages 5–19. Springer, 2008.
  * [9] Rasmus Ibsen-Jensen and Peter Bro Miltersen.  Solving simple stochastic games with few coin toss positions.  In European Symposium on Algorithms, pages 636–647. Springer, 2012\.
  * [10] Brendan Juba.  On the hardness of simple stochastic games.  Master’s thesis, CMU, 2005.
  * [11] Walter Ludwig.  A subexponential randomized algorithm for the simple stochastic game problem.  Information and computation, 117(1):151–155, 1995.
  * [12] L. S. Shapley.  Stochastic games.  Proceedings of the National Academy of Sciences, 39(10):1095–1100, 1953.
  * [13] C Stirling.  Bisimulation, modal logic and model checking games.  Logic Journal of the IGPL, 7(1):103–124, 1999.
  * [14] Rahul Tripathi, Elena Valkanova, and VS Anil Kumar.  On strategy improvement algorithms for simple stochastic games.  Journal of Discrete Algorithms, 9(3):263–278, 2011.