An Objective Improvement Approach to Solving Discounted Payoff Games]An Objective Improvement Approach  to Solving Discounted Payoff Games*
*This work is based on [10], which appeared in GandALF'23.

D. Dell'Erba]Daniele Dell'Erba0000-0003-1196-6110[a]
A. Dumas]Arthur Dumas[b]
S. Schewe]Sven Schewe0000-0002-9093-9518[a]
University of Liverpool, United Kingdom
<EMAIL_ADDRESS><EMAIL_ADDRESS>
ENS Rennes, France

While discounted payoff games and classic games that reduce to them, like parity and mean-payoff games, are symmetric, their solutions are not.
We have taken a fresh view on the properties that optimal solutions need to have, and devised a novel way to converge to them, which is entirely symmetric.
We achieve this by building a constraint system that uses every edge to define an inequation, and update the objective function by taking a single outgoing edge for each vertex into account.
These edges loosely represent strategies of both players, where the objective function intuitively asks to make the inequation to these edges sharp, leading to an `error' or 0.
For co-optimal strategies, and only for them, this can be achieved, and while we have not found them, we step-wise improve the error by improving the solution for a given objective function or by improving the objective function for a given solution.
This also challenges the gospel that methods for solving payoff games are either based on strategy improvement or on value iteration.

§ INTRODUCTION

We study turn-based zero sum games played between two players on directed graphs.
The two players take turns to move a token along the
vertices of finite labelled graph with the goal to optimise their adversarial

Various classes of graph games are characterised by the objective of the
players, for instance in parity games the objective is to optimise the parity
of the dominating colour occurring infinitely often, while in discounted and
mean-payoff games the objective of the players is to minimise resp. maximise the discounted and limit-average sum of
the colours.

Solving graph games is the central and most expensive step
in many model
checking [22, 13, 37, 9, 1, 32],
checking [37, 22, 35],
and synthesis [29, 33]
Progress in algorithms for solving graph games will therefore allow for the
development of more efficient model checkers and contribute to bringing synthesis
techniques to practice.

There is a hierarchy among the graph games mentioned earlier, with simple and well known reductions from parity games to mean payoff games, from mean-payoff games to discounted payoff games, and from discounted payoff games to simple stochastic games like the ones from [39], while no reductions are known in the other direction. Therefore, one can solve instances of all these games by using an algorithm for stochastic games.
All of these games are in  and  [19], while no tractable algorithm is known.

Most research has focused on parity games: as the most special class of games, algorithms have the option to use the special structure of their problems, and they are most directly linked to the synthesis and verification problems mentioned earlier.
Parity games have thus enjoyed a special status among graph games and the quest for efficient
algorithms [14, 12, 27, 39, 2, 38, 28, 4, 3]
for solving them has been an active field of research during the last
decades, which has received further boost with the arrival of quasi-polynomial techniques [7, 18, 17, 24, 25, 11].

Interestingly, the one class of efficient techniques for solving parity games that does not (yet) have a quasi-polynomial approach is strategy improvement
algorithms [26, 30, 36, 6, 31, 15, 34],
a class of algorithms closely related to the Simplex for linear programming, known to perform well in practice.
Most of these algorithms reduce to mean [6, 31, 34, 5]
or discounted [26, 30, 16, 23] payoff games.

With the exception of the case in which the fixed-point of discounted payoff games is explicitly computed [39], all these algorithms share a disappointing feature: they are inherently non-symmetric approaches for solving an inherently symmetric problem.
However, some of these approaches have a degree of symmetry. Recursive approaches treat even and odd colours symmetrically, one at a time, but they treat the two players very differently for a given colour.
Symmetric strategy improvement [34] runs a strategy improvement algorithms for both players in parallel, using the intermediate results of each of them to inform the updates of the other, but at heart, these are still two intertwined strategy improvement algorithms that, individually, are not symmetric.
This is in due to the fact that applying strategy improvement itself symmetrically can lead to cycles [8].

The key contribution of this paper is to devise a new class of algorithms to solve discounted payoff games, which is entirely symmetric.
Like strategy improvement algorithms, it seeks to find co-optimal strategies, and improves strategies while they are not optimal.
In order to do so, however, it does not distinguish between the strategies of the two players.
This seems surprising, as maximising and minimising appear to pull in opposing directions.

Similar to strategy improvement approaches, the new objective improvement approach turns the edges of a game into constraints (here called inequations), and minimises an objective function.
However, while strategy improvement algorithms take only the edges in the strategy of one player (and all edges of the other player) into account and then finds the optimal response by solving the resulting one player game, objective improvement always takes all edges into account.
The strategies under consideration then form a subset of the inequations, and the goal would be to make them sharp (i.e. as equations), which only works when both strategies are optimal.
When they are not, then there is some offset for each of the inequations, and the objective is to reduce this offset in every improvement step.

This treats the strategies of both players completely symmetrically.

§.§ Organisation of the Paper.

The rest of the paper is organised as follows.
After the preliminaries (Section <ref>),
we start by outlining our method and use a simple game to explain it (Section <ref>).
We then formally introduce our objective improvement algorithm in Section <ref>, keeping the question of how to choose a better strategies abstract.
Section <ref> discusses how to find better strategies, and Section <ref> provides an experimental evaluation of the algorithm.
We finally wrap up with a discussion of our results in Section <ref>.

§ PRELIMINARIES

A discounted payoff game (DPG) is a tuple $\mathcal{G} = (V_{\min}, V_{\max}, E, w, \lambda)$, where $V= V_{\min} \cup V_{\max}$ are the vertices of the game, partitioned into two disjoint sets $V_{\min}$ and $V_{\max}$, such that the pair $(V, E)$ is a finite directed
graph without sinks.
The vertices in $V_{\max}$ (resp, $V_{\min}$) are controlled by Player Max or maximiser (resp, Player Min or minimiser) and $E \subseteq V \times V$ is the edge relation. Every edge has a weight represented by the function $w : E \to \mathbb{R}$, and a discount factor represented by the function $\lambda : E \to [0,1)$. When the discount factor is uniform, i.e. the same for every edge, it is represented by a constant value $\lambda \in [0,1)$.
For ease of notation, we write $w_e$ and $\lambda_e$ instead of $w(e)$ and $\lambda(e)$.
A play on $\mathcal{G}$ from a vertex $v$ is an infinite path, which can be represented as a sequence of edges $\rho=e_0 e_1 e_2 \ldots$ such that, for every $i \in \mathbb{N}^*$, $e_i=(v_i,v'_{i})\in E$, and, for all $i \in \mathbb{N}, v_{i+1}=v'_{i}$ and $v_0=v$.
By $\rho_i$ we refer to the i-th edge of the play.
The outcome of a discounted game $\mathcal{G} = (V_{\min}, V_{\max}, E, w, \lambda)$ for a play $\rho$ is $\out(\rho)=\sum_{i=0}^{\infty} w_{e_i} \prod_{j=0}^{i-1}\lambda_{e_j}$.
For games with a constant discount factor, this simplifies in $\out(\rho)=\sum_{i=0}^{\infty} w_{e_i} \lambda^i$.

A positional strategy for Max is a function $\sigma_{\max}:V_{\max}\to V$ that maps each Max vertex to a vertex according to the set of edges, i.e. $(v,\sigma_{\max}(v))\in E$.
Positional Min strategies are defined accordingly, and we call the set of positional Min and Max strategies $\Sigma_{\min}$ and $\Sigma_{\max}$, respectively.

A pair of strategies $\sigma_{\min}$ and $\sigma_{\max}$, one for each player, defines a unique run $\rho(v,\sigma_{\min},\sigma_{\max})$ from each vertex $v \in V$.
Discounted payoff games are positionally determined [39]:

\sup_{\sigma_{\max} \in \Sigma_{\max}} \inf_{\sigma_{\min} \in \Sigma_{\min}} \out(\rho(v,\sigma_{\min},\sigma_{\max}))
\inf_{\sigma_{\min} \in \Sigma_{\min}} \sup_{\sigma_{\max} \in \Sigma_{\max}} \out(\rho(v,\sigma_{\min},\sigma_{\max}))

holds for all $v\in V$, and neither the value, nor the optimal strategy for which it is taken, changes when we allow more powerful classes of strategies that allow for using memory and/or randomisation for one or both players.

The resulting value of $\mathcal G$, denoted by $\val(\mathcal G): V \rightarrow \mathcal R$, is defined as

$$ \val(\mathcal G): v \mapsto  \sup_{\sigma_{\max} \in \Sigma_{\max}} \inf_{\sigma_{\min} \in \Sigma_{\min}} \out(\rho(v,\sigma_{\min},\sigma_{\max}))\ .$$

The solution to a discounted payoff game is a valuation $\val = \val(\mathcal G)$ of $\mathcal G$ for the vertices such that, for every edge $e = (v,v')$, it holds that[These are the constraints represented in $H$ in Section <ref>.]

* $\val(v) \leq w_e + \lambda_e \val(v')$ if $v$ is a minimiser vertex and

* $\val(v) \geq w_e + \lambda_e \val(v')$ if $v$ is a maximiser vertex.

A positional maximiser (resp. minimiser) strategy $\sigma$ is optimal if, and only if, $\val(v) = w_{(v,\sigma(v))} + \lambda_{(v,\sigma(v))} \val(\sigma(v))$ holds for all maximiser (resp. minimiser) vertices.

Likewise, we define the value of a pair of strategies $\sigma_{\min}$ and $\sigma_{\max}$, denoted $\val(\sigma_{\min},\sigma_{\max}): V \rightarrow \mathcal R$, as
$ \val(\sigma_{\min},\sigma_{\max}): v \mapsto  \out(\rho(v,\sigma_{\min},\sigma_{\max}))$.

As we treat both players symmetrically in this paper, we define a pair of strategies $\sigma : V \mapsto V$ whose restriction to $V_{\min}$ and $V_{\max}$ are a minimiser strategy $\sigma_{\min}$ and a maximiser strategy  $\sigma_{\max}$, respectively.
We then write $\rho(v,\sigma)$ instead of $\rho(v,\sigma_{\min},\sigma_{\max})$ and $\val(\sigma)$ instead of $\val(\sigma_{\min},\sigma_{\max})$.

If both of these strategies are optimal, we call $\sigma$ a joint co-optimal strategy.
This is the case if, and only if, $\val(\mathcal G)= \val(\sigma)$ holds.

Note that we are interested in the value of each vertex, not merely if the value is greater or equal than a given threshold value.

§ OUTLINE AND MOTIVATION EXAMPLE

[node distance = 5em, bend angle = 22.5, inner sep = 0.3em, minimum size = 3.2em]
every loop/.style = max distance = 1.5em
[shape=circle,draw,thick] (max) at (0,0) b;
[shape=rectangle,draw,thick] (min) at (3,0) a;

[thick,->] (max) to node [above] $0$ (min);
[thick,->] (max) edge[loop above]node$0$ (max);
[thick,->] (min) edge[loop above]node$1$ (min);

A discounted Payoff Game. Maximiser vertices are marked by a circle, minimizer ones by a square.

We start with considering the simple discounted payoff game of Figure <ref>, assuming that it has some uniform discount factor $\lambda \in [0,1)$.
In this game, the minimiser (who owns the right vertex, $a$, marked by a square), has only one option: she always has to use the self-loop, which earns her an immediate reward of $1$.
The overall reward the minimiser reaps for a run that starts in her vertex is therefore
$1 + \lambda + \lambda^2 + \ldots = \frac{1}{1-\lambda}$.

The maximiser (who owns the left vertex, $b$, marked by a circle) can choose to either use the self-loop, or to move to the minimiser vertex (marked by a square), both yielding no immediate reward.

If the maximiser decides to stay forever in his vertex (using the self-loop), his overall reward in the play that starts at (and, due to his choice, always stays in) his vertex, is $0$.
If he decides to move on to the minimiser vertex the $n^{th}$-time,
then the reward is $\frac{\lambda^n}{1-\lambda}$.

The optimal decision of the maximiser is therefore to move on the first time, which yields him the maximal reward of $\frac{\lambda}{1-\lambda}$.

Every vertex $v$ has some outgoing edge(s) $e = (v,v')$ where $\val(v) = w_e + \lambda_e \val(v')$ holds [39];
these edges correspond to the optimal decisions for the respective player.

For our running example game of Figure <ref> with a fixed discount factor $\lambda \in [0,1)$, the inequations are

* $\val(a) \leq 1 + \lambda \val(a)\quad $ for the self-loop of the minimiser vertex;

* $\val(b) \geq \lambda \val(b)\qquad\ \ $ for the self-loop of the maximiser vertex; and

* $\val(b) \geq \lambda \val(a)\qquad\ \ $ for the transition from the maximiser to the minimiser vertex.

The unique valuation that satisfies these inequations and produces a sharp inequation (i.e. satisfied as equation) for some outgoing edge of each vertex assigns $\val(a)=\frac{1}{1-\lambda}$ and $\val(b)=\frac{\lambda}{1-\lambda}$.
This valuation also defines the optimal strategies of the players (to stay for the minimiser, and to move on for the maximiser).

Solving a discounted payoff game means finding this valuation and/or these strategies.

We discuss a symmetric approach to find this unique valuation.
Our approach adjusts linear programming in a natural way that treats both players symmetrically:
we maintain the set of inequations for the complete time, while approximating the goal of “one equality per vertex” by the objective function.
To do that, we initially fix an arbitrary outgoing edge for every vertex (a strategy), and minimise the sum of the distances between the left and right side of the inequations defined by these edges, which we call the offset of this edge. This means, for an edge $e = (v,v')$, to minimise the difference of $\val(v)$ (left side of the inequation) and $w_e + \lambda_e \val(v')$ (right side).

To make this clear, we consider again the example of Figure <ref> and use both self loops as the strategies for the players fixed at the beginning in our running example.
The offset for the selected outgoing edge of the minimiser vertex $a$ is equal to $1 -(1-\lambda)\val(a)$, while the offset for the selected outgoing edge of the maximiser vertex $b$ is equal to $(1-\lambda)\val(b)$.
The resulting overall objective consists, therefore, in minimising the value $1-(1-\lambda)\val(a) + (1-\lambda)\val(b)$.

This term is always non-negative, since it corresponds to the sum of the edges contributions that are all non-negative.
Moreover, when only optimal strategies are selected to form this objective function, the value $0$ can be taken, and where it is taken, it defines the correct valuation.

As the maximiser's choice to take the self-loop is not optimal, the resulting objective function the strategies define, that is $1-(1-\lambda)\val(a) + (1-\lambda)\val(b)$, cannot reach $0$.
But let us take a look at what an optimal solution w.r.t. this objective function looks like.

Optimal solutions can be taken from the corners of the polytope defined by the inequations.
In this case, the optimal solution (w.r.t. this initial objective function) is defined by making inequations (1) and (3) sharp: this provides the values $\val(a)=\frac{1}{1-\lambda}$ and $\val(b)=\frac{\lambda}{1-\lambda}$; the objective function takes the value $\lambda$ at this point.

For comparison, in the other corner of the polytope, defined by making inequations (2) and (3) sharp, we obtain the values $\val(a)=\val(b)=0$; the objective function takes the value $1$ at this point.
Finally, if we consider the last combination, making (1) and (2) sharp provides the values $\val(a)=\frac{1}{1-\lambda}$ and $\val(b)=0$, so that inequation (3) is not satisfied; this is therefore not a corner of the polytope.

Thus, in this toy example, while selecting the wrong edge cannot result in the objective function taking the value $0$, we still found the optimal solution.
In general, we might need to update the objective function.
To update the objective function, we change the outgoing edges of some (or all) vertices, such that the overall value of the objective function goes down.

Note that this can be done not only when the linear program returns an optimal solution, but also during its computation.
For example, when using a simplex method, updating the objective function can be used as an alternative pivoting rule at any point of the traversal of the polytope.

Unfortunately, the case in which the valuation returned as solution is computed using an objective function based on non-optimal strategies, is not the general case.
The simplest way of seeing this is to use different discount factors for the game of Figure <ref>
[Note that we can also replace the transitions with a smaller discount factor by multiple transitions with a larger discount factor. This would allow for keeping the discount factor uniform, but needlessly complicate the discussion and inflate the size of the example.], let's say $\frac{1}{3}$ for the self-loop of the maximiser vertex and $\frac{2}{3}$ for the other two transitions, so that the three equations are: (1) $\val(a) \leq 1 + \frac{2}{3} \val(a)$, (2) $\val(b) \geq \frac{2}{3} \val(b)$, and (3) $\val(b) \geq \frac{1}{3} \val(a)$.
Making the adjusted inequations (2) and (3) sharp still results in the values $\val(a)=\val(b)=0$, and the objective function still takes the value of $1$. While making inequations (1) and (3) sharp provides the values $\val(a)=3$ and $\val(b)=2$; the objective function takes the value $\frac{4}{3}$ at this point.
Finally, if we consider the last combination, making (1) and (2) sharp still conflicts with inequation (3).

Thus, $\val(a)=\val(b)= 0$ would be the optimal solution for the given objective function, which is not the valuation of the game.
We will then update the candidate strategies so that the sum of the offsets goes down.

§.§ Comparison to strategy improvement

The closest relative to our new approach are strategy improvement algorithms.
Classic strategy improvement approaches solve this problem of finding the valuation of a game (and usually also co-optimal strategies) by (1) fixing a strategy for one of the players (we assume w.l.o.g. that this is the maximiser), (2) finding a valuation function for the one player game that results from fixing this strategy (often together with an optimal counter strategy for their opponent), and (3) updating the strategy of the maximiser by applying local improvements.
This is repeated until no local improvements are available, which entails that the constraint system is satisfied.

Strategy Improvement
Inputinput Outputoutput

A discounted payoff game $\mathcal{G} = (V_{\min}, V_{\max}, E, w, \lambda)$
The valuation $\val$ of $\mathcal G$

$f \leftarrow{} \mathsf{ObjectiveFunction}(\mathcal{G})$

$\sigma_0 \leftarrow{} \mathsf{ChooseInitialStrategy}(\mathcal{G})$

$H \leftarrow{} \mathsf{Inequations}(\mathcal{G},\sigma_0)$

$\val \leftarrow{} \mathsf{LinearProgramming}(H, f)$

$\sigma_0$ is optimal$\val$
$\sigma_0 \leftarrow{} \mathsf{ChooseBetterStrategy}(\mathcal{G},\sigma_0)$

These steps can be identified in  Algorithm <ref>. The objective function is fixed at the beginning (Line 1). It simply maximises the sum of the values of all the vertices, and thus implicitly the value of all vertices. (1) The strategy of one of the two player (for convention the maximiser – if we want to instead fix the strategy of the minimiser, we would have to minimise the sum of the values for all vertices instead) is initialised at Line 2. (2) Before the computation of the valuation at Line 5, the set of constraints is updated accordingly to the selected strategy of the maximiser (Line 4). At this point, if the strategy is optimal w.r.t. the current valuation, then the algorithm ends. Otherwise, (3) there exist an improvement, which is applied at Line 7.

For Step (2) of this approach, we can use linear programming, which does invite a comparison with our technique.
The linear program for solving Step (2) would not use all inequations: it would, instead, replace the inequations defined by the currently selected edges of the maximiser by equations, while dropping the inequations defined by the other maximiser transitions.
The objective function would then be to maximise the values of all vertices while still complying with the remaining (in)equations.

Thus, while the constraints remain while the objective is updated  in our novel symmetric approach, in strategy improvement the objective remains, while the constraints are updated.

Moreover, the players and their strategies are treated quite differently in strategy improvement algorithms: while the candidate strategy of the maximiser results in making the inequations of the selected edges sharp (and dropping all other inequations of maximiser edges), the optimal counter strategy is found by minimising the objective. This is again in contrast to our novel symmetric approach, which treats both players equally.

A small further difference is in the valuations that can be taken: the valuations that strategy improvement algorithms can take are the valuations of strategies, while the valuations our objective improvement algorithm can take on the way are the corners of the polytope defined by the inequations.
Except for the only intersection point between the two (the valuation of the game), these corners of the polytope do not relate to the value of strategies.
Table <ref> summarises these observations.

Objective Improvement     Strategy Improvement

players      symmetric treatment     asymmetric treatment

constraints     remain the same:     change:

one inequation per edge     one inequation for each edge

defined by the current strategy for

the strategy player, one inequation

for every edge of their opponent

objective     minimise errors for selected edges     maximise values

update     objective:     strategy:

one edge for each vertex     one edge for each vertex

of the strategy player

valuations     corners of polytope     defined by strategies

A comparison of the novel objective improvement with classic strategy improvement.

§ GENERAL OBJECTIVE IMPROVEMENT

In this section, we present the approach outlined in the previous section more formally, while keeping the most complex step – updating the candidate strategy to one which is better in that it defines an optimisation function that can take a smaller value – abstract. (We will turn back to the question of how to find better strategies in Section <ref>.)
This allows for discussing the principal properties more clearly.

Objective Improvement
Inputinput Outputoutput

A discounted payoff game $\mathcal{G} = (V_{\min}, V_{\max}, E, w, \lambda)$
The valuation $\val$ of $\mathcal G$

$H \leftarrow{} \mathsf{Inequations}(\mathcal{G})$

$\sigma \leftarrow{} \mathsf{ChooseInitialStrategies}(\mathcal{G})$

$f_\sigma \leftarrow{} \mathsf{ObjectiveFunction}(\mathcal{G}, \sigma)$

$\val \leftarrow{} \mathsf{LinearProgramming}(H, f_\sigma)$

$f_\sigma(\val) = 0$$\val$
$\sigma \leftarrow{} \mathsf{ChooseBetterStrategies}(\mathcal{G},\sigma)$

A general outline of our objective improvement approach is reported in Algorithm <ref>.

Before describing the procedures called by the algorithm, we first outline the principle.

When running on a discounted payoff game $\mathcal{G}= (V_{\min}, V_{\max}, E, w, \lambda)$, the algorithm uses a set of inequations defined by the edges of the game and the owner of the source of each edge.
This set of inequations denoted by $H$ contains one inequation for each edge and (different to strategy improvement approaches whose set of inequations is a subset of $H$) $H$ never changes.

The inequations from $H$ are computed by a function called $\mathsf{Inequations}$ (Line 1)  that, given the discounted game $\mathcal{G}$, returns the set made of one inequation per edge $e=(v,v') \in E$, defined as follows:

\[ I_e =  \begin{cases}
\val(v) \geq w_{e} + \lambda_e \val(v') &\text{if }v \in V_{\max} \\
\val(v) \leq w_{e} + \lambda_e \val(v') &\text{otherwise .}
\end{cases}
\]

The set $H = \{I_e \mid e \in E\}$ is defined as the set of all inequations for the edges of the game.

The algorithm also handles strategies for both players, treated as a single strategy $\sigma$.
They are initialised (for example randomly) by the function $\mathsf{ChooseInitialStrategies}$ at Line 2.

This joint strategy is used to define an objective function $f_{\sigma}$ by calling function $\mathsf{ObjectiveFunction}$ at Line 4, whose value on an evaluation $\val$ is: $f_{\sigma}(\val)=\sum_{v \in V} f_\sigma(\val, v)$ with the following objective function components:

\[
f_\sigma(\val, v) = \off(\val,(v,\sigma(v)))\ ,
\]

where the offset of an edge $(v,v')$ for a valuation is defined as follows:

\[
\off(\val, (v,v')) =
\begin{cases}
\val(v) - (w_{(v,v')} + \lambda_{(v,v')} \val(v')) &\text{if } v \in V_{\max} \\
(w_{(v,v')} + \lambda_{(v,v')} \val(v')) - \val(v) &\text{otherwise}
\end{cases}
\]

This objective function $f_\sigma$ is given to a linear programming algorithm, alongside with the inequations set $H$.
We underline that, due to the inequation to $I_{(v,v')}$, the value of $\off(\val, (v,v'))$ is non-negative for all $(v,v')\in E$ in any valuation $\val$ (optimal or not) that satisfies the system of inequations $H$.
We put a further restriction on $\val$ in that we require it to be the solution to a basis $\mathbf{b}$ in $H$.
Such a basis consists of $|V|$ inequations that are satisfied sharply (i.e. as equations), such that these $|V|$ equations uniquely define the values of all vertices.
We refer to this valuation as the evaluation of $\mathbf{b}$, denoted $\val(\mathbf{b})$.

The call $\mathsf{LinearProgramming}(H, f_\sigma)$ to some linear programming algorithm then returns a valuation $\val$ of the vertices that minimise $f_\sigma$ while satisfying $H$ (Line 5), and for convenience require this valuation to also be $\val(\mathbf{b})$ for some base $\mathbf{b}$ of $H$. (Note that the simplex algorithm, for example, only uses valuations of this form in every step.)
We call this valuation a valuation associated to $\sigma$.

At Line 6 of Algorithm <ref>, the value of $f_\sigma(\val)$ is non-negative.

We say that a valuation $\val$ defines strategies of both players if, for every vertex $v\in V$, the inequation of (at least) one of the outgoing edges of $v$ is sharp.
These are the strategies defined by using, for every vertex $v \in V$, an outgoing edge for which the inequation is sharp.
Note that there can be more than one of these inequations for some of the vertices.

If, for a solution $\val$ of $H$, $f_\sigma(\val) = 0$ holds, then, for every vertex $v \in V$, the inequation $I_{(v,\sigma(v))}$ for the edge $(v,\sigma(v))$ is sharp, and $\val$ therefore defines strategies for both players – those defined by $\sigma$, for example.

We can use, alternatively, $f_\sigma(\val) = 0$ as a termination condition, as shown at Line 6 in Algorithm <ref>, since in this case $\sigma$ must define co-optimal strategies.

If $\sigma$ describes co-optimal strategies, then $f_\sigma(\val) = 0$ holds at Line 6 of Algorithm <ref>.
If $\val$ defines strategies for both players joint in $\sigma$ at Line 6 of Algorithm <ref>, then $\sigma$ is co-optimal and $\val$ is the valuation of $\mathcal G$.

The valuation $\val=\val(\mathcal G)$ of the game is the unique solution of $H$ for which, for all vertices $v$, the inequation to (at least) one of the outgoing edges of $v$ is sharp, and the edges for which they are sharp describe co-optimal strategies.
The valuation of the game is thus the only valuation that defines strategies for both players, which shows the second claim.

Moreover, if $\sigma$ describes co-optimal strategies, then $f_\sigma (\val)=0$ holds for $\val=\val(\mathcal G)$ (and for this valuation only), which establishes the first claim.

The theorem above ensures that, in case the condition at Line 6 holds, the algorithm terminates and provides the value of the game that then allows us to infer optimal strategies of both players.
Otherwise we have to improve the objective function and make another iteration of the while loop.
At Line 7, $\mathsf{ChooseBetterStrategies}$ can be any procedure that, for $f_\sigma(\val) \neq 0$, provides a pair of strategy $\sigma'$ better than $\sigma$ as defined in the following subsection.

Better strategies

A strategy $\sigma'$ for both players is better than a strategy $\sigma$ if, and only if, the minimal value of the objective function $f_{\sigma'}$ (computed by $\mathsf{LinearProgramming}(H, f_{\sigma'})$) is strictly lower than the minimal value of the objective function for $f_\sigma$ (computed by $\mathsf{LinearProgramming}(H, f_{\sigma})$). Formally, $f_{\sigma'}(\val') < f_\sigma(\val)$.

While we discuss how to implement this key function in the next section, we observe here that the algorithm terminates with a correct result with any implementation that chooses a better objective function in each round: correctness is due to it only terminating when $\val$ defines strategies for both players, which implies (cf. Theorem <ref>) that $\val$ is the valuation of $\mathcal G$ ($\val=\val(\mathcal G)$) and all strategies defined by $\val$ are co-optimal.
Termination is obtained by a finite number of positional strategies: by Observation <ref>, the value of the objective function of all of them is non-negative, while the objective function of an optimal solution to co-optimal strategies is $0$ (cf. Theorem <ref>), which meets the termination condition of Line 6 (cf. Observation <ref>).

Algorithm <ref> always terminates with the correct value.

§ CHOOSING BETTER STRATEGIES

In this section, we will discuss sufficient criteria for efficiently finding a procedure that implements $\mathsf{ChooseBetterStrategies}$.
For this, we make four observations described in the next subsections:

* All local improvements can be applied.
A strategy $\sigma'$ is a local improvement to a strategy $\sigma$ if $f_{\sigma'}(\val) < f_\sigma(\val)$ holds for the current valuation $\val$ (Section <ref>).

* If the current valuation $\val$ does not define a pair of strategies $\sigma$ for both players and has no local improvements, then a better strategy $\sigma'$ can be found by applying only switches from and to edges that already have offset $0$ (Section <ref>).

* The improvement mentioned in the previous point can be found for special games – the sharp and improving games defined in Section <ref> – by trying a single edge switch.

* Games can almost surely be made sharp and improving by adding random noise that retains optimal strategies (Section <ref>).

Together, these four points provide efficient means for finding increasingly better strategies, and thus to find the co-optimal strategies and the valuation of the discounted payoff game.

As a small side observation, when using a simplex based technique to implement $\mathsf{LinearProgramming}$ at Line 5 of Algorithm <ref>, then the pivoting of the objective function from point (1.) and the pivoting of the base can be mixed (this will be discussed in Section <ref>).

§.§ Local Improvements

The simplest—and most common—case of creating better strategies $\sigma'$ from a valuation for the objective $f_\sigma$ for a strategy $\sigma$ is to consider local improvements.
Much like local improvements in strategy iteration approaches, local improvements consider, for each vertex $v$, a successor $v' \neq \sigma(v)$, such that $\off(\val,(v,v')) < \off(\val,(v,\sigma(v))$ for the current valuation $\val$, which is optimal for the objective function $f_\sigma$.

To be more general, our approach does not necessarily requires to select only local improvements, but it can work with global improvements, though we cannot see any practical use of choosing differently.
For instance, if we treat the function as a global improvement approach, we can update the value for a vertex $v$ such that it increases by 1 and update the value of another vertex $v'$ such that it decreases by 2. The overall value of the function will decrease, even if locally some components increased their value. Interestingly, this cannot be done with a strategy improvement approach, as it requires to always locally improve the value of each vertex when updating.

If $\val$ is an optimal valuation for the linear programming problem at Line 5 of Algorithm <ref> and $f_{\sigma'}(\val) < f_\sigma(\val)$, then $\sigma'$ is better than $\sigma$.

The valuation $\val$ is, being an optimal solution for the objective $f_\sigma$, a solution to the system of inequations $H$. For a solution $\val'$ which is optimal for $f_{\sigma'}$, we thus have $f_{\sigma'}(\val') \leq f_{\sigma'}(\val) < f_\sigma(\val)$, which implies that $\sigma'$ is better than $\sigma$ accordingly to notion of better strategy provided at the end of Section 4.

§.§ No Local Improvements

The absence of local improvements means that, for all vertices $v \in V$ and all outgoing edges $(v,v') \in E$, $\off(\val,(v,v')) \geq \off(\val,(v,\sigma(v)))$.

We define for a valuation $\val$ optimal for a $f_\sigma$ (like the $\val$ produced in line 5 of Algorithm <ref>):

* $S_\val^\sigma = \{ (v,v') \in E \mid \off(\val,(v,v')) = \off(\val,(v,\sigma(v)))\}$ as the set of stale edges;
naturally, every vertex has at least one outgoing stale edge: the one defined by $\sigma$;

* $E_\val = \{ (v,v') \in E \mid \off(\val,(v,v')) =  0\}$ as the set of edges, for which the inequation for $\val$ is sharp;
in particular, all edges in the base of $H$ that defines $\val$ are sharp (and stale); and

* $E_\val^\sigma$ as any set of edges between $E_\val$ and $S_\val^\sigma$ (i.e. $E_\val \subseteq E_\val^\sigma \subseteq S_\val^\sigma$) such that $E_\val^\sigma$ contains an outgoing edge for every vertex $v \in V$;
we are interested to deal with sets that retain the game property that every vertex has a successor, we can do that by adding (non sharp) stale edges to $E_\val$.

Note that $S_\val^\sigma$ is such a set, hence, an adequate set is easy to identify.
We might, however, be interested in keeping the set small, and choosing the edges defined by $E_\val$ plus one outgoing edge for every vertex $v$ that does not have an outgoing edge in $E_\val$.
The most natural solutions is to choose the edge $(v,\sigma(v)) \in E_\val^\sigma$ defined by $\sigma$ for each such vertex $v$.

If $\mathcal{G}= (V_{\min}, V_{\max}, E, w, \lambda)$ is a DPG and $\sigma$ a strategy for both players such that $\val$ is an optimal solution for the objective $f_\sigma$ to the system of inequations $H$,
then $\mathcal G'= (V_{\min}, V_{\max}, E_\val^\sigma, w, \lambda)$ is also a DPG.

This simply holds because every vertex $v \in V$ retains at least one outgoing transition.

Let $\mathcal{G}= (V_{\min}, V_{\max}, E, w, \lambda)$ be a DPG, $\sigma$ a strategy for both players, $\val$ an optimal solution returned at Line 5 of Algorithm <ref> for $f_\sigma$, and let there be no local improvements of $\sigma$ for $\val$.
If $\val$ does not define strategies of both players, then there is a better strategy $\sigma'$ such that, for all $v \in V$, $(v,\sigma'(v)) \in E_\val^\sigma$.

By Observation <ref>,  $\mathcal G'=  (V_{\min}, V_{\max}, E_\val^\sigma, w, \lambda)$ is a DPG. Let $\val'$ be the valuation of $\mathcal G'$, and $\sigma'$ be the strategies for the two players defined by it.

If $\val'$ is also a valuation of $\mathcal G$, then we are done. However, this need not be the case, as the system of inequations $H'$ for $\mathcal G'$ is smaller than the set of inequations $H$ for $\mathcal G$, so $\val'$ might violate some of the inequations that are in $H$, but not in $H'$.
Given that $\val'$ is a valuation for $\mathcal G'$, it satisfies all inequations in $H'$.
Moreover, since $\val$ also satisfies all inequations of $H'$, it follows that the same inequations hold for every convex combination of $\val$ and $\val'$.

We now note that the inequations of $H$ that are not in $H'$ are not sharp for $\val$. Thus, there is an $\varepsilon \in (0,1]$ such that the convex combination $\val_\varepsilon = \varepsilon \cdot \val' + (1-\varepsilon) \val$ is a solution to those inequations.

We now have $f_{\sigma'}(\val) = f_\sigma(\val) > 0$ and $f_{\sigma'}(\val')=0$.
For an optimal solution $\val''$ of $H$ for the objective $f_{\sigma'}$, this provides $f_{\sigma'}(\val'') \leq f_{\sigma'}(\val_\varepsilon) < f_\sigma(\val)$.

Therefore $\sigma'$ is better than $\sigma$.

When using the most natural choice, $E_\val^\sigma = E_\val \cup \{(v,\sigma(v))\mid v \in V\}$, this translates in keeping all transitions, for which the offset is not $0$, while changing some of those, for which the offset already is $0$. This is a slightly surprising choice, since to progress one has to improve on the transitions whose offset is positive, and ignore those with offset 0.

§.§ Games with Efficient Objective Improvement

In this subsection, we consider sufficient conditions for finding better strategies efficiently.
Note that we only have to consider cases where the termination condition (Line 6 of Algorithm <ref>) is not met.

The simplest condition for efficiently finding better strategies is the existence of local improvements.
(In particular, it is easy to find, for a given valuation $\val$, strategies $\sigma'$ for both players such that $f_{\sigma'}(\val) \leq f_{\sigma''}(\val)$ holds for all strategies $\sigma''$).
When there are local improvements, we can obtain a better strategy simply by applying them.

This leaves the case in which there are no local improvements, but where $\val$ also does not define strategies for the two players.
We have seen that we can obtain a better strategy by only swapping edges, for which the inequations are sharp (Lemma <ref>).

We will now describe two conditions that, when both met, will allow us to efficiently find better strategies:
that games are sharp and improving.

§.§ Sharp games.

To do this efficiently, it helps if there are always $|V|$ inequations that are sharp: there must be at least $|V|$ of them for a solution returned by the simplex method, as it is the solution defined by making $|V|$ inequations sharp (they are called the base), and requiring that there are exactly $|V|$ many of them means that the valuation we obtain defines a base.

We call such a set of inequations $H$, and games that define them sharp DPGs.

§.§ Improving games.

The second condition, which will allow us to identify better strategies efficiently, is to assume that, for every strategy $\sigma$ for both players, if a valuation $\val$ defined by a base is not optimal for $f_\sigma$ under the constraints $H$, then there is a single base change that improves it.
We call such sharp DPGs improving.

We call a valuation $\val'$ whose base can be obtained from that of $\val$ by a single change to the base of $\val$ a neighbouring valuation to $\val$.
We will show that, for improving games, we can sharpen the result of Lemma <ref> so that the better strategy $\sigma'$ also guarantees $f_{\sigma'}(\val')<f_\sigma(\val)$ for some neighbouring valuation $\val'$ to $\val$.

This allows us to consider $O(|E|)$ base changes and, where they define a valuation, to seek optimal strategies for a given valuation.
Finding an optimal strategy for a given valuation is straightforward.

Let $\mathcal{G}= (V_{\min}, V_{\max}, E, w, \lambda)$ be an improving DPG, $\sigma$ a strategy for both players, $\val$ an optimal solution returned at Line 5 of Algorithm <ref> for $f_\sigma$, and let there be no local improvements of $\sigma$ for $\val$.
Then there is (at least) one neighbouring valuation $\val''$ to $\val$ such that there is a better strategy $\sigma'$ that satisfies $f_{\sigma'}(\val'')<f_\sigma(\val)$.

Such a strategy $\sigma'$ is better than $\sigma$, and it can be selected in a way that $(v,\sigma'(v)) \in E_\val^\sigma$ holds for all $v\in V$ for a given set $E_\val^\sigma$.

We apply Lemma <ref> for $E_\val^\sigma = E_\val \cup \{(v,\sigma(v)\mid v \in V\}$ and use the resulting better strategy $\sigma'$ for this set $E^\sigma_\val$.
Let $\val'$ be the optimal solution for $f_{\sigma'}$ that satisfies the constraints $H$ defined by $\mathcal G$.
Note that since $\sigma'$ is better than $\sigma$ by Lemma <ref>, we have that  $f_{\sigma'}(\val')<f_\sigma(\val)$ and $f_\sigma(\val) \leq f_\sigma(\val')$.

We now consider an arbitrary sequence of evaluations $\val = \val_0, \val_1,\ldots,\val_n = \val'$ along the edges of the simplex from $\val$ to $\val'$, such that the value of the new objective function $f_{\sigma'}$ only decreases.
Note that such a path must exist, as the simplex algorithm would pick it.

The sharpness of $\mathcal G$ implies that $\val_1 \neq \val_0$, and considering that $\mathcal G$ is improving provides $f_{\sigma'}(\val_1)<f_{\sigma'}(\val_0)$.

Thus, when only applying a single base change, we move to a fresh value, $\val_1$, such that $f_{\sigma'}(\val_1) < f_\sigma(\val)$ for some $\sigma'$.

Note that $\sigma'$ was supplied by Lemma <ref>, so that $(v,\sigma'(v)) \in E_\val^\sigma$ holds.

While we can restrict the selection of $\sigma'$ to those that comply with the restriction $(v,\sigma'(v)) \in E_\val^\sigma$, there is no particular reason for doing so; as soon as we have a neighbouring valuation $\val'$, we can identify a pair of strategies $\sigma'$ for which $f_{\sigma'}(\val')$ is minimal, and select $\sigma'$ if $f_{\sigma'}(\val')< f_\sigma(\val)$ holds.

§.§ Making Games Sharp and Improving

Naturally, not every game is improving, or even sharp. In this subsection, we first discuss how to almost surely make games sharp by adding sufficiently small random noise to the edge weights, and then discuss how to treat games that are not improving by assigning randomly chosen factors, with which the offsets of edges are weighted.
Note that these are `global' adjustments of the game that only need to be applied once, as it is the game that becomes sharp and improving, respectively.

Starting with the small noise to add on the edge weights, we first create notation for expressing how much we can change edge weights, such that joint co-optimal strategies of the resulting game are joint co-optimal strategies in the original game.
To this end, we define the gap of a game.

§.§ Gap of a game.

For a DPG  $\mathcal{G}= (V_{\min}, V_{\max}, E, w, \lambda)$, we call $\lambda^*=\max\{\lambda_e\mid e \in E\}$ its contraction. For a joint strategy $\sigma$ that is not co-optimal, we call $\gamma_\sigma = - \min \{\off(\val(\sigma),e) \mid e \in E\}$; note that $\gamma_\sigma >0$ holds.
We call the minimal
[This skips over the case where all strategies are co-optimal, but that case is trivial to check and such games are trivial to solve, so that we ignore this case in this subsection.]
such value $\gamma$ the gap of $\mathcal G$.

Note that $\val(\sigma)$ is the valuation of the joint strategy $\sigma$, not the outcome of the optimisation problem. This is because we use the gap of the game to argue that a non-co-optimal strategy remains non-co-optimal after a small distortion of the edge weights, so that the value of the joint strategy itself is useful. (It is much easier to access than the result of optimisation.) This also implies that the offsets can be negative.

We now use the gap of a game $\gamma$ to define the magnitude of a change to all weights, such that all strategies that used to have a gap still have one.

Let $\mathcal G = (V_{\min}, V_{\max}, E, w, \lambda)$ be a DPG with contraction $\lambda^*$ and gap $\gamma$, and let
$\mathcal G' = (V_{\min}, V_{\max}, E, w', \lambda)$ differ from $\mathcal G$ only in the edge weights such that, for all $e \in E$, $|w_e - w_e'| \leq \frac{1-\lambda^*}{3}\gamma$ holds.
Then a joint co-optimal strategy from $\mathcal G'$ is also co-optimal for $\mathcal G$.

The small weight disturbance, $|w_e - w_e'| \leq \frac{1-\lambda^*}{3}\gamma$ for all $e \in E$, immediately provides a small difference in the valuation: for all joint strategies $\sigma$, we have for $\val = \val(\sigma)$ on $\mathcal G$, and $\val' = \val(\sigma)$ on $\mathcal G'$, that $|\val(v) - \val'(v)| \leq \frac{1}{1-\lambda^*} \frac{1-\lambda^*}{3}\gamma = \frac{\gamma}{3}$, using the definition of $\val(\sigma)$ and triangulation.

More precisely, as $\sigma$ defines a run $\rho = e_0 e_1 e_2 \ldots$, and we have $\val(v) = \out(\rho)=\sum_{i=0}^{\infty} w_{e_i} \prod_{j=0}^{i-1}\lambda_{e_j}$
and $\val'(v)=\sum_{i=0}^{\infty} w_{e_i}' \prod_{j=0}^{i-1}\lambda_{e_j}$.
This provides
$$|\val(v) - \val'(v)| \leq \sum_{i=0}^{\infty} |w_{e_i}-w_{e_i}'| \prod_{j=0}^{i-1}\lambda_{e_j} < \frac{1-\lambda^*}{3}\gamma \sum_{i=0}^{\infty}\prod_{j=0}^{i-1}\lambda_{e_j} \leq \frac{1-\lambda^*}{3}\gamma \sum_{i=0}^{\infty} (\lambda^*)^i = \frac{\gamma}{3}. $$

If $\sigma$ is not co-optimal for $\mathcal G$, we have an edge $e$ with $-\off(\val,e)=\gamma_\sigma \geq \gamma$.
Triangulation provides
$$|\off(\val',e)-\off(\val,e)| < \frac{1+\lambda^*}{3}\gamma$$
and (using $\off'$ to indicate the use of $w_e'$ for $\mathcal G'$ instead of $w_e$ for $\mathcal G$),

$$|\off'(\val',e)-\off(\val,e)| \leq \frac{2+\lambda^*}{3}\gamma< \gamma \leq \gamma_\sigma\ ,$$

which, together with the fact that $-\off(\val,e) \geq \gamma$, provides $\off'(\val',e)<0$.

Thus, $\sigma$ is not co-optimal for $\mathcal G'$.

Given a DPGs $\mathcal{G}= (V_{\min}, V_{\max}, E, w, \lambda)$, the DPG $\mathcal G'= (V_{\min}, V_{\max}, E, w', \lambda)$ resulting from $\mathcal G$ by adding independently uniformly at random drawn values from an interval $(-\varepsilon,\varepsilon)$ to every edge weight, will almost surely result in a sharp game.

There are only finitely many bases, and it suffices to compare two arbitrary but fixed ones, say $b_1$ and $b_2$.

As they are different, there will be one edge $e = (v,v')$ that occurs in $b_1$, but not in $b_2$.
As all weight disturbances are drawn independently, we assume without loss of generality that the weight disturbance to this edge is drawn last.

Now, the valuation $\val_2$ defined by $b_1$ does not depend on this final draw.
For $\val_2$, there is a value $w_e' = \val_2(v)-\lambda_e\val_2(v')$ that defines the weight $w_e'$ $e$ would need to have such that the inequation for $e$ is sharp.

For the valuation $\val_1$ defined by $b_1$ to be equal to $\val_2$, the weight for the edge $e$ (after adding the drawn distortion) needs to be exactly $w_e'$.
There is at most one value for the disturbance that would provide for this, and this disturbance for weight of $e$ is sampled with a likelihood of $0$.

Putting these two results together, we get:

Given a pair of DPGs $\mathcal G = (V_{\min}, V_{\max}, E, w, \lambda)$ with contraction $\lambda^*$ and gap $\gamma$, and $\mathcal G' = (V_{\min}, V_{\max}, E, w', \lambda)$ obtained from $\mathcal G$ by adding independently uniformly at random drawn values from an interval $(-\varepsilon,\varepsilon)$ to every edge weight, for some $\varepsilon \leq \frac{1-\lambda^*}{3}\gamma$, then, a joint co-optimal strategy from $\mathcal G'$ is also co-optimal for $\mathcal G$, and $\mathcal G'$ is almost surely sharp.

Note that we can estimate the gap cheaply when all coefficients in $\mathcal G$ are rational.
The gap is defined as the minimum of $\gamma_\sigma$ over non-co-optimal joint strategies $\sigma$, and we start by fixing such a joint strategy.

For a given $v\in V$, $\sigma$ defines a run $\rho = e_0 e_1 e_2 \ldots$ in the form of a "lasso path", which consists of a (possibly empty) initial path $e_0,\ldots,e_k$, followed by an infinitely often repeated cycle $e_0',\ldots,e_\ell'$, where the only vertex that occurs twice on the path $e_0,\ldots,e_k,e_0',\ldots,e_\ell'$ is the vertex reached before $e_0'$ and after $e_\ell'$, while all other vertices occur only once.

In this run, an edge $e_i$ occurs only once and contributes $\prod_{j=0}^{i-1}\lambda_{e_j} w_{e_i}$ to the value of this run, while an edge $e_i'$ occurs infinitely often and contributes the value $\frac{\prod_{j=0}^{k}\lambda_{e_j} \cdot \prod_{j=0}^{i-1}\lambda_{e_j'}}{1-\prod_{j=0}^{\ell}\lambda_{e_j'}}w_{e_i'}$ to the value of the run.

Now all we need to do is to find a common denominator.
To do this, let $\denom(r)$ be the denominator of a rational number $r$.
It is easy to see that

$$\mathsf{common} = \prod\limits_{v\in V}\denom(\lambda_{(v,\sigma(v))})^2 \cdot \denom(w_{(v,\sigma(v))})$$

is a common denominator of the contributions of all of these weights, and thus a denominator that can be used for the sum.

Looking at an edge $e$ that defines $\gamma_\sigma$, then $\gamma_\sigma$ can be written with the denominator
$$\mathsf{common}\cdot \denom(\lambda_ew_e)\ .$$

Obviously, the nominator is at least $1$.

Estimating $\gamma$ can thus be done by using the highest possible denominators available in $\mathcal G$. The representation of the resulting estimate $\gamma$ is polynomial in the size of $\mathcal G$.

§.§ Biased sum of offsets.

We modify sharp games that are not improving. This can be done by redefining the function $\off$ as follows:

\[
\off'(\val, (v,v')) =
\alpha_{(v,v')} \cdot \off(\val, (v,v'))
\]

Such $\off$ are defined for every edge $e = (v,v')$, where all $\alpha_e$ are positive numbers, which we call the offset factor.
Based on this change, we re-define all offset definitions and the objective function with a primed version that uses these positive factors.

Let $\mathcal{G}= (V_{\min}, V_{\max}, E, w, \lambda)$ be an improving DPG for a given set of positive numbers $\{\alpha_e > 0 \mid e \in E\}$, $\sigma$ a strategy for both players, $\val$ an optimal solution returned at Line 5 of Algorithm <ref> for the adjusted function $f_\sigma'$, and let there be no local improvements of $\sigma$ for $\val$.
Then there is neighbouring valuation $\val''$ to $\val$ such that there is a better strategy $\sigma'$ that satisfies $f_{\sigma'}(\val'')<f_\sigma(\val)$.

Such a strategy $\sigma'$ is better than $\sigma$, and it can be selected in a way that $(v,\sigma'(v)) \in E_\val^\sigma$ holds for all $v\in V$ for a given set $E_\val^\sigma$.

All proofs can be repeated verbatim with the new offset definition.

If each offset factor $\alpha_e$ is selected independently uniformly at random from a bounded interval of positive numbers
[or from any other distribution over positive numbers that has $0$ weight for all individual points],
then a sharp DPG $\mathcal{G}= (V_{\min}, V_{\max}, E, w, \lambda)$ is almost surely improving for a sampled set of positive numbers $\{\alpha_e > 0 \mid e \in E\}$.

We show the claim for two arbitrary but fixed valuations $\val_1$ and $\val_2$ defined by two different bases, $b_1$ and $b_2$, respectively, that satisfy the inequations in $H$, and an arbitrary but fixed adjusted $f_\sigma$.
As there are finitely many bases and finitely many joint strategies, satisfying the requirement almost surely for them entails that the requirement is satisfied almost surely for the game.

As $\mathcal G$ is sharp, we have $\val_1 \neq \val_2$.

We first assume for contradiction that $\off(\val_1,(v,\sigma(v))) = \off(\val_2,(v,\sigma(v)))$ holds for all $v \in V$.
We pick a vertex $v$ such that $|\val_1(v) - \val_2(v)|>0$ is maximal, such a vertex exists since $\val_1 \neq \val_2$.
For this $v$, $\off(\val_1,(v,\sigma(v))) = \off(\val_2,(v,\sigma(v)))$ entails
$\val_1(v) - \val_2(v) = \lambda_{(v,\sigma(v))} (\val_1(\sigma(v)) - \val_2(\sigma(v)))$.
Using $\lambda_e \in [0,1)$, we get
$|\val_1(\sigma(v)) - \val_2(\sigma(v))|>|\val_1(v) - \val_2(v)|>0$, which contradicts the maximality of $v$. Note that neither $\lambda_e$, nor the difference of $\val_1(\sigma(v))$ and $\val_2(\sigma(v))$ can be equal to 0 since $\val_1(v) \neq \val_2(v)$. Hence the contradiction.

We therefore have that $\off(\val_1,(v,\sigma(v))) \neq \off(\val_2,(v,\sigma(v)))$ holds for some $v\in V$.
As the $\alpha_e$ are drawn independently, we can assume w.l.o.g. that $\alpha_{(v,\sigma(v))}$ is drawn last.
There is at most one value $\alpha_{(v,\sigma(v))}'$ for which the condition

$$\sum_{v\in V} \off'(\val_1,(v,\sigma(v))) \neq \sum_{v\in V} \off'(\val_2,(v,\sigma(v)))$$

is not satisfied.

It therefore holds almost surely for all strategies that all base-induced valuations have a pairwise distinct image by the objective function associated to the strategy.
This immediately implies that the game is improving.

Thus, we can almost surely obtain sharpness by adding small noise to the weights,
and almost surely make games improving by considering the offsets of the individual edges with a randomly chosen positive weight.
This guarantees cheap progress for the case where there are no local improvements.

§.§ Mixing Pivoting on the Simplex and of the Objective

When using a simplex based technique to implement $\mathsf{LinearProgramming}$ (Line 5 of Algorithm <ref>), then the algorithm mixes three
approaches that stepwise reduce the value of $f_\sigma(\val)$:

* The simplex algorithm updates the base, changing $\val$ (while retaining the objective function $f_\sigma$).

* Local updates, who change the objective function $f_\sigma$ (through updating $\sigma$)
and retain $\val$.

* Non-local updates.

Non-local updates are more complex than the other two, and the correctness proofs make use of the non-existence of the other two improvements. For both reasons, it seems natural to take non-local updates as a last resort.

The other two updates, however, can be freely mixed, as they both bring down the value of $f_\sigma(\val)$ by applying local changes.
That the improvements from (1) are given preference in the algorithm is a choice made to keep the implementation of the algorithm for using linear programs open, allowing, for example, to use ellipsoid methods [21] or inner point methods [20] to keep this step tractable.

§ EXPERIMENTAL EVALUATION

To evaluate the performance of the novel approach, we have implemented it in an experimental framework in C++. Together with the objective improvement algorithm (OI, for short) we have also implemented the classic asymmetric variant of the strategy improvement algorithm (SI, for short) that has been described in Section <ref>..

This comes with a number of difficulties. First, there are no actual concrete benchmarks for discounted payoff games.
We have therefore generated random games of various sizes.
We have considered games with rational weights in the interval $[-250,250]$ on the edges, as games with integer weights represent a restricted class of games.
The range of rational weights is not crucial as it suffice to multiply their values to scale the interval up or down.
Moreover, we use a uniform discount factor of $0.9$, since for games in which each vertex has different weights on the edges, non-uniform discount factors do not make games any easier or harder to solve.
Using a low discount factor ( 0.5 or below) make, instead, games easier to solve, because with small discount factors the solution ( valuation) of the vertices converges after few steps, while with a discount factor close to 1 the valuation requires many steps to converge.
Finally, it is worth noting that games with such random weights on the edges are also almost surely sharp, hence, it has not been necessarily to implement the sharpening technique described in Section <ref>.

The second obstacle is that, for an implementation, one has to choose how to update the current "state", both for SI and OI.
For SI, we use a greedy all switch rule: we update all local decisions where there is a local improvement available, and where there are multiple, we choose one with the maximal local improvement.
For OI, there are more choices to make.
As mentioned in Section <ref>, in simplex-based approaches, we can freely mix (1) the standard updates of the base for a fixed objective function, and (2) updates of the objective function itself, and in most steps, both options are available.
For (1), there are a plethora of update rules for the simplex, and for (2), there is also a range of ways of how to select the update.
We have dodged this question by not directly implementing a solver, but by, instead, solving the linear programs with an off-the-shelf solver. We have used the LP solver provided by the ALGLIB library[Library libalglib version 3.16.0] for both OI and SI.
This does not restrict us to the use of simplex-based solvers, while it would restrict simplex-based solutions to always giving priority to (1) over (2).
Where the solver does provide a solution for a given objective function, we use rule (2) with a greedy all switch rule.

One cost of doing this is that we do not have a similarly straight forward integration of (3) non-local updates, where we are in the optimal solution for an objective function that cannot be improved with rule (2).
Instead of using the method from Theorem <ref> to adjusting a simplex method slightly to finding an improvement for improving games (using that the games we produce are almost surely improving), we use the general rule from Lemma <ref>.
In principle, this might lead to large plateaux that are hard to exit, but we considered this very unlikely, at least for the improving games we produce, and our experiments have confirmed this.

This setup allows us to fairly compare OI with SI by counting the number of linear program problems that need to be solved on the way.

[scale=1.2,every node/.style=scale=0.85]
xmin=100, ymin=0,
ytick=0, 5, 10, 15, 20, 25, 30, 35, 40,
xtick=100, 200, 300, 400, 500, 600, 700, 800, 900, 1000,
enlarge x limits=false,
enlarge y limits=upper,
mark size=1.2pt,
ylabel=Number of iterations (avg),
xlabel=Game size,
yticklabel style = font=,xshift=-0.5ex,
xticklabel style = font=,yshift=-0.5ex,
legend style=nodes=scale=0.6, transform shape,
legend pos=north west
[color=red, mark=o] table [x=RUN, y=DSI_i] results2.txt;
[color=blue, mark=star, mark size=1.4] table [x=RUN, y=OI_i] results2.txt;

Comparisons of the average number of iterations (LP calls) on games with two successors for each vertex.

As our first benchmark set we selected games with two outgoing edges per vertex.
This type of games have a relatively small strategy space, which sould make them a relatively easy target for SI in that SI should require fewer steps to identify the optimal strategy than OI.
Figures <ref> and <ref> show the total number of iterations and total number of strategy updates required to solve 1000 games of size ranging from 100 to 1000 vertices. Each point in the graph shows the mean value for a cluster of 100 games of the corresponding size.

The number of iteration (Figure <ref>) represents how many times the linear programming solver has been called.
As expected, SI is more efficient than OI at solving these games in terms of LP calls.
What was less expected is how the advantage of SI over OI grows with the size of the game.

While it is the case that solving the linear programs is simpler for OI, at least when using a simplex style algorithm
[Simplex style algorithms operate in two phases: in the first phase, they look for any base that defines a solution to the constraint system, and in the second, they optimise.
For OI, the first phase can be skipped for all but the first call; this is because the constraint system does not change, so that the previous solution can be used as a starting point.
For SI, the constraint system changes; here, the previous solution is never a solution to the new linear program.].
We also note that only 55 (5.5%) of the 1000 games considered overall reached a non-improving state.
In these rare cases, this has been solved by choosing a stale switch.

The number of updates, instead, counts how many times each vertex changed its strategy before the next call to the LP solver, and then provides the sum of these switches.
If the ownership of the vertices of a game is not balanced ( one player owns 80% of the vertices), most of the solving effort is charged to the LP solver, while the SI algorithm itself needs to update very few strategies.
On the contrary, OI updates the strategies for both the players.
It would therefore stand to reason to expect that the number of local strategy updates would give an extra advantage to SI.
This is, however, not the case: Figure <ref> shows that, while OI needs to update the strategy for at least twice as many vertices, it needs only around a third more local updates for this.

[scale=1.2,every node/.style=scale=0.85]
xmin=100, ymin=0,
ytick=45, 100, 200, 300, 400, 500, 600, 700,
xtick=100, 200, 300, 400, 500, 600, 700, 800, 900, 1000,
y tick label style=/pgf/number format/fixed,
enlarge x limits=false,
enlarge y limits=upper,
mark size=1.2pt,
ylabel=Number of updates (avg),
xlabel=Game size,
yticklabel style = font=,yshift=-0.5ex,
xticklabel style = font=,yshift=-0.5ex,
legend style=nodes=scale=0.6, transform shape,
legend pos=north west
[color=red, mark=o] table [x=RUN, y=DSI_s] results2.txt;
[color=blue, mark=star, mark size=1.4] table [x=RUN, y=OI_s] results2.txt;

Comparisons of the average number of local strategy updates for games with two successors per vertex.

In the second benchmark set we selected games with more moves per vertex, in the range $[5,10]$. In this case, the space of strategies is much wider than one of the games of the first benchmark set, and algorithms based on SI find these games harder to solve.
Figures <ref> and <ref> show the comparison of OI and SI on the second benchmark set of 1000 games.

In Figure <ref> we can observe a slowly but consistently growing gap in the number of LP calls (iterations). In addition to the advantage of simpler LP problems, we see that in these slightly more complex games OI also requires fewer calls, with SI needing some 2.5 to 3 times as many.
For this benchmark set, only 7 (0.7%) of the games reached a non-improving state at any point.

Interestingly, Figure <ref>, instead, depicts a symmetric behaviour of the graph of Figure <ref>, but this time with the lanes of the two solvers swapped. Thus, although OI considers the strategy at all vertices (instead of at most half), the sum of local improvements is also slightly smaller.

[scale=1.2,every node/.style=scale=0.85]
xmin=100, ymin=0,
ytick=0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
xtick=100, 200, 300, 400, 500, 600, 700, 800, 900, 1000,
enlarge x limits=false,
enlarge y limits=upper,
mark size=1.2pt,
ylabel=Number of iterations (avg),
xlabel=Game size,
yticklabel style = font=,xshift=-0.5ex,
xticklabel style = font=,yshift=-0.5ex,
legend style=nodes=scale=0.6, transform shape,
legend pos=north west
[color=red, mark=o] table [x=RUN, y=DSI_i] results5.txt;
[color=blue, mark=star, mark size=1.4] table [x=RUN, y=OI_i] results5.txt;

Comparisons of the average number of iterations (LP calls) for games with many (5 to 10) successors per vertex.

[scale=1.2,every node/.style=scale=0.85]
xmin=100, ymin=0,
ytick=160, 300, 600, 900, 1200, 1500, 1800, 2100,
xtick=100, 200, 300, 400, 500, 600, 700, 800, 900, 1000,
y tick label style=/pgf/number format/fixed,
enlarge x limits=false,
enlarge y limits=upper,
mark size=1.2pt,
ylabel=Number of updates (avg),
xlabel=Game size,
yticklabel style = font=,xshift=-0.5ex,
xticklabel style = font=,yshift=-0.5ex,
legend style=nodes=scale=0.6, transform shape,
legend pos=north west
[color=red, mark=o] table [x=RUN, y=DSI_s] results5.txt;
[color=blue, mark=star, mark size=1.4] table [x=RUN, y=OI_s] results5.txt;

Comparisons of the average number of local strategy updates for games with many (5 to 10) successors per vertex.

When considering games with many transitions, namely games where the outdegree of every vertex is 10% of the number of vertices, the advantage of OI over SI grows further.
Figure <ref> shows a larger gap in the number of LP calls than Figure <ref>, and
Figure <ref> shows not only an advantage of OI over SI, but it also appears that the number of local strategy updates grows linearly for OI, but faster for SI.
Only 3 (0.3%) of the games reached a non-improving state at some point of the solving process.

[scale=1.2,every node/.style=scale=0.85]
xmin=100, ymin=0,
ytick=0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
xtick=100, 200, 300, 400, 500, 600, 700, 800, 900, 1000,
enlarge x limits=false,
enlarge y limits=upper,
mark size=1.2pt,
ylabel=Number of iterations (avg),
xlabel=Game size,
yticklabel style = font=,xshift=-0.5ex,
xticklabel style = font=,yshift=-0.5ex,
legend style=nodes=scale=0.6, transform shape,
legend pos=north west
[color=red, mark=o] table [x=RUN, y=DSI_i] resultsN.txt;
[color=blue, mark=star, mark size=1.4] table [x=RUN, y=OI_i] resultsN.txt;

Comparisons of the average number of iterations (LP calls) for games with a linear number of successors per vertex (10%).

[scale=1.2,every node/.style=scale=0.85]
xmin=100, ymin=0,
ytick=160, 500, 1000, 1500, 2000, 2500, 3000, 3500, 4000, 4500, 5000, 5500, 6000, 6500, 7000,
xtick=100, 200, 300, 400, 500, 600, 700, 800, 900, 1000,
y tick label style=/pgf/number format/fixed,
enlarge x limits=false,
enlarge y limits=upper,
mark size=1.2pt,
ylabel=Number of updates (avg),
xlabel=Game size,
yticklabel style = font=,xshift=-0.5ex,
xticklabel style = font=,yshift=-0.5ex,
legend style=nodes=scale=0.6, transform shape,
legend pos=north west
[color=red, mark=o] table [x=RUN, y=DSI_s] resultsN.txt;
[color=blue, mark=star, mark size=1.4] table [x=RUN, y=OI_s] resultsN.txt;

Comparisons of the average number of local strategy updates for games with a linear number of successors per vertex (10%).

§ DISCUSSION

There is widespread belief that mean payoff and discounted payoff games have two types of algorithmic solutions: value iteration [16, 23] and strategy improvement [26, 30, 6, 31, 34].
We have added a third method, which is structurally different and opens a new class of algorithms to attack these games.

Moreover, our new symmetric approach has the same proximity to linear programming as strategy improvement algorithms, which is an indicator of efficiency.

The lack of a benchmarking framework for existing algorithms prevents us from testing and compare an eventual implementation thoroughly, but we have compared OI against SI on random games in Section <ref>.
To keep this comparison fair (and simple), we have put as much as possible of both problems into LP calls, using greedy all switch updates in both cases.
We found that SI performs better on random games with very few (two) successors per vertex, while OI already comes out on top with few (five to ten), and shines with many (10% of the vertices) successors.
This was a bit unexpected to us, as we thought that such a naive implementation of the new concept could not possibly compete.

Our results for random games with a low (five to ten) outdegree suggests that the number of local updates seen grows linearly with the size of the game for both SI and OI, and that the number of iterations initially grows and later plateaus.
This may well be the same for games with a minimal outdegree of two, and the data clearly supports this for SI, but the number of LP calls growth almost linearly for OI. This might be an outlier in the behaviour and it is well possible that OI plateaus later, as it is unlikely that games with a low and very low outdegree behave fundamentally different.
For SI, this was entirely expected, and it is maybe not overly surprising for OI either.
Generally speaking, OI appears to do better than SI measured in the number of LP calls on random games, except where the outdegree is tiny.

Naturally, a fresh approach opens the door to much follow-up research.
A first target for such research is the questions on how to arrange the selection of better strategies to obtain fewer updates, either proven on benchmarks, or theoretically in worst, average, or smoothed analysis.
Intuitively, it would look like an implementation base on simplex style algorithms would update the objective function regularly, perhaps after every step on the simplex, which would also make sure that no vertex is ever visited twice
[This could happen in principle, as a step that is good for one objective function might not be good for its successor, but would be avoided if we always update to the objective function with the best local value.].
Note that this is the exact opposite of what we implemented, as we only considered improving the objective function when an optimal solution for the current objective function is found.
Implementing it would, however, make any comparison with strategy improvement meaningless.

From a theoretical perspective, it would in particular be interesting to establish non-trivial upper or lower bounds for various pivoting rules. Without such a study, a trivial bound for the proposed approach is provided by the number of strategies (exponential).

A second question is whether this method as whole can be turned into an inner point method.
If so, this could be a first step on showing tractability of discounted payoff games – which would immediately extend to mean-payoff and parity games.

§.§ Acknowledgements

This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 101032464.
It was supported by the EPSRC through the projects EP/X017796/1 (Below the Branches of Universal Trees) and
EP/X03688X/1 (TRUSTED: SecuriTy SummaRies for SecUre SofTwarE Development). We also thank Peter Austin from the University of Liverpool for providing an integration of the LP solver.

[1]
R. Alur, T.A. Henzinger, and O. Kupferman.
Alternating-Time Temporal Logic.
Journal of the ACM, 49(5):672–713, 2002.
URL: <https://doi.org/10.1145/585265.585270>.

[2]
A. Browne, E.M. Clarke, S. Jha, D.E. Long, and W.R. Marrero.
An Improved Algorithm for the Evaluation of Fixpoint Expressions.
Theoretical Computer Science, 178(1-2):237–255, 1997.
URL: <https://doi.org/10.1016/S0304-3975(96)00228-9>.

[3]
M. Benerecetti, D. Dell'Erba, and F. Mogavero.
Improving Priority Promotion for Parity Games.
In Haifa Verification Conference16, LNCS 10028, pages 1–17.
Springer, 2016.
URL: <https://doi.org/10.1007/978-3-319-49052-6_8>.

[4]
M. Benerecetti, D. Dell'Erba, and F. Mogavero.
A Delayed Promotion Policy for Parity Games.
Information and Computation, 262(2):221–240, 2018.
URL: <https://doi.org/10.1016/j.ic.2018.09.005>.

[5]
M. Benerecetti, D. Dell'Erba, and F. Mogavero.
Solving Mean-Payoff Games via Quasi Dominions.
In Tools and Algorithms for the Construction and Analysis of
Systems'20, LNCS 12079, pages 289–306. Springer, 2020.
URL: <https://doi.org/10.1007/978-3-030-45237-7_18>.

[6]
H. Björklund and S.G. Vorobyov.
A Combinatorial Strongly Subexponential Strategy Improvement
Algorithm for Mean-Payoff Games.
Discrete Applied Mathematics, 155(2):210–229, 2007.
URL: <https://doi.org/10.1016/j.dam.2006.04.029>.

[7]
C. S. Calude, S. Jain, B. Khoussainov, W .Li, and F .Stephan.
Deciding Parity Games in Quasi-polynomial Time.
SIAM Journal on Computing, 51(2):17–152, 2022.
URL: <https://doi.org/10.1137/17M1145288>.

[8]
Anne Condon.
On algorithms for simple stochastic games.
In Advances in Computational Complexity Theory, volume 13 of
DIMACS Series in Discrete Mathematics and Theoretical Computer Science,
pages 51–73. American Mathematical Society, 1993.
URL: <https://doi.org/10.1090/dimacs/013/04>.

[9]
L. de Alfaro, T.A. Henzinger, and R. Majumdar.
From Verification to Control: Dynamic Programs for Omega-Regular
In Logic in Computer Science'01, pages 279–290. IEEE Computer
Society, 2001.
URL: <https://doi.org/10.1109/LICS.2001.932504>.

[10]
D. Dell'Erba, A. Dumas, and S. Schewe.
An Objective Improvement Approach to Solving Discounted Payoff
In Games, Automata, Logics, and Formal Verification'23, EPTCS
390, pages 203–219, 2023.

[11]
D. Dell'Erba and S. Schewe.
Smaller progress measures and separating automata for parity games.
Frontiers in Computer Science, 4, 2022.
URL: <https://doi.org/10.3389/fcomp.2022.936903>.

[12]
E.A. Emerson and C.S. Jutla.
Tree Automata, muCalculus, and Determinacy.
In Foundation of Computer Science'91, pages 368–377. IEEE
Computer Society, 1991.
URL: <https://doi.org/10.1109/SFCS.1991.185392>.

[13]
E.A. Emerson, C.S. Jutla, and A.P. Sistla.
On Model-Checking for Fragments of muCalculus.
In Computer Aided Verification'93, LNCS 697, pages 385–396.
Springer, 1993.
URL: <https://doi.org/10.1007/3-540-56922-7_32>.

[14]
E.A. Emerson and C.-L. Lei.
Efficient Model Checking in Fragments of the Propositional
In Logic in Computer Science'86, pages 267–278. IEEE Computer
Society, 1986.

[15]
J. Fearnley.
Non-Oblivious Strategy Improvement.
In Logic for Programming Artificial Intelligence and
Reasoning'10, LNCS 6355, pages 212–230. Springer, 2010.
URL: <https://doi.org/10.1007/978-3-642-17511-4_13>.

[16]
N. Fijalkow, P. Gawrychowski, and P. Ohlmann.
Value Iteration Using Universal Graphs and the Complexity of Mean
Payoff Games.
In Mathematical Foundations of Computer Science'20, LIPIcs 170,
pages 1–15. Leibniz-Zentrum fuer Informatik, 2020.
URL: <https://doi.org/10.4230/LIPIcs.MFCS.2020.34>.

[17]
J. Fearnley, S. Jain, B. de Keijzer, S. Schewe, F. Stephan, and D. Wojtczak.
An Ordered Approach to Solving Parity Games in Quasi Polynomial Time
and Quasi Linear Space.
Software Tools for Technology Transfer, 21(3):325–349, 2019.
URL: <https://doi.org/10.1007/s10009-019-00509-3>.

[18]
M. Jurdziński and R. Lazic.
Succinct Progress Measures for Solving Parity Games.
In Logic in Computer Science'17, pages 1–9. Association for
Computing Machinery, 2017.
URL: <https://doi.org/10.1109/LICS.2017.8005092>.

[19]
M. Jurdziński.
Deciding the Winner in Parity Games is in UP $\cap$ co-UP.
Information Processing Letters, 68(3):119–124, 1998.
URL: <https://doi.org/10.1016/S0020-0190(98)00150-1>.

[20]
N. Karmarkar.
A new polynomial-time algorithm for linear programming.
In Symposium on Theory of Computing'84, pages 302–311.
Association for Computing Machinery, 1984.

[21]
L. G. Khachian.
A polynomial algorithm in linear programming.
Dokl. Akad. Nauk SSSR, 244:1093–1096, 1979.

[22]
D. Kozen.
Results on the Propositional muCalculus.
Theoretical Computer Science, 27(3):333–354, 1983.

[23]
A. Kozachinskiy.
Polyhedral Value Iteration for Discounted Games and Energy Games.
In Symposium on Discrete Algorithms'21, page 600–616. SIAM,
URL: <https://doi.org/10.1137/1.9781611976465.37>.

[24]
K. Lehtinen and U. Boker.
Register Games.
Logical Methods in Computer Science, 16(2), 2020.
URL: <https://doi.org/10.23638/LMCS-16(2:6)2020>.

[25]
K. Lehtinen, P. Parys, S. Schewe, and D. Wojtczak.
A Recursive Approach to Solving Parity Games in Quasipolynomial
Logical Methods in Computer Science, 18(1), 20220.
URL: <https://doi.org/10.46298/lmcs-18(1:8)2022>.

[26]
W. Ludwig.
A Subexponential Randomized Algorithm for the Simple Stochastic Game
Information and Computation, 117(1):151–155, 1995.
URL: <https://doi.org/10.1006/inco.1995.1035>.

[27]
R. McNaughton.
Infinite Games Played on Finite Graphs.
Annals of Pure and Applied Logic, 65:149–184, 1993.
URL: <https://doi.org/10.1016/0168-0072(93)90036-D>.

[28]
J. Obdrzálek.
Fast Mu-Calculus Model Checking when Tree-Width Is Bounded.
In Computer Aided Verification'03, LNCS 2725, pages 80–92.
Springer, 2003.
URL: <https://doi.org/10.1007/978-3-540-45069-6_7>.

[29]
N. Piterman.
From Nondeterministic Buchi and Streett Automata to Deterministic
Parity Automata.
In Logic in Computer Science'06, pages 255–264. IEEE Computer
Society, 2006.
URL: <https://doi.org/10.2168/LMCS-3(3:5)2007>.

[30]
A. Puri.
Theory of Hybrid Systems and Discrete Event Systems.
PhD thesis, University of California, Berkeley, USA, 1995.

[31]
S. Schewe.
An Optimal Strategy Improvement Algorithm for Solving Parity and
Payoff Games.
In Computer Science Logic'08, LNCS 5213, pages 369–384.
Springer, 2008.
URL: <https://doi.org/10.1007/978-3-540-87531-4_27>.

[32]
S. Schewe and B. Finkbeiner.
Satisfiability and Finite Model Property for the Alternating-Time
In Computer Science Logic'06, LNCS 6247, pages 591–605.
Springer, 2006.
URL: <https://doi.org/10.1007/11874683_39>.

[33]
S. Schewe and B. Finkbeiner.
Synthesis of Asynchronous Systems.
In Symposium on Logic-based Program Synthesis and
Transformation'06, LNCS 4407, pages 127–142. Springer, 2006.
URL: <https://doi.org/10.1007/978-3-540-71410-1_10>.

[34]
S. Schewe, A. Trivedi, and T. Varghese.
Symmetric Strategy Improvement.
In International Colloquium on Automata, Languages, and
Programming'15, LNCS 9135, pages 388–400. Springer, 2015.
URL: <https://doi.org/10.1007/978-3-662-47666-6_31>.

[35]
M.Y. Vardi.
Reasoning about The Past with Two-Way Automata.
In International Colloquium on Automata, Languages, and
Programming'98, LNCS 1443, pages 628–641. Springer, 1998.
URL: <https://doi.org/10.1007/BFb0055090>.

[36]
J. Vöge and M. Jurdziński.
A Discrete Strategy Improvement Algorithm for Solving Parity Games.
In Computer Aided Verification'00, LNCS 1855, pages 202–215.
Springer, 2000.
URL: <https://doi.org/10.1007/10722167_18>.

[37]
T. Wilke.
Alternating Tree Automata, Parity Games, and Modal muCalculus.
Bulletin of the Belgian Mathematical Society, 8(2):359–391,

[38]
W. Zielonka.
Infinite Games on Finitely Coloured Graphs with Applications to
Automata on Infinite Trees.
Theoretical Computer Science, 200(1-2):135–183, 1998.
URL: <https://doi.org/10.1016/S0304-3975(98)00009-7>.

[39]
U. Zwick and M. Paterson.
The Complexity of Mean Payoff Games on Graphs.
Theoretical Computer Science, 158(1-2):343–359, 1996.
URL: <https://doi.org/10.1016/0304-3975(95)00188-3>.