# Bounded-Memory Strategies in Partial-Information Games

Sougata Bose  0000-0003-3662-3915<EMAIL_ADDRESS>University of
LiverpoolLiverpoolUK ,  Rasmus Ibsen-Jensen  0000-0003-4783-0389 r.ibsen-
<EMAIL_ADDRESS>University of LiverpoolLiverpoolUK and  Patrick Totzke
0001-5274-8190<EMAIL_ADDRESS>University of LiverpoolLiverpoolUK

(2024)

###### Abstract.

We study the computational complexity of solving stochastic games with mean-
payoff objectives. Instead of identifying special classes in which simple
strategies are sufficient to play $\varepsilon$-optimally, or form
$\varepsilon$-Nash equilibria, we consider general partial-information
multiplayer games and ask what can be achieved with (and against) finite-
memory strategies up to a given bound on the memory.

We show ${\mathsf{NP}}$-hardness for approximating zero-sum values, already
with respect to memoryless strategies and for 1-player reachability games. On
the other hand, we provide upper bounds for solving games of any fixed number
of players $k$. We show that one can decide in polynomial space if, for a
given $k$-player game, $\varepsilon\geq 0$ and bound $b$, there exists an
$\varepsilon$-Nash equilibrium in which all strategies use at most $b$ memory
modes.

For given $\varepsilon>0$, finding an $\varepsilon$-Nash equilibrium with
respect to $b$-bounded strategies can be done in
${\mathsf{FNP}}^{{\mathsf{NP}}}$. Similarly for 2-player zero-sum games,
finding a $b$-bounded strategy that, against all $b$-bounded opponent
strategies, guarantees an outcome within $\varepsilon$ of a given value, can
be done in ${\mathsf{FNP}}^{{\mathsf{NP}}}$. Our constructions apply to parity
objectives with minimal simplifications.

Our results improve the status quo in several well-known special cases of
games. In particular, for $2$-player zero-sum concurrent mean-payoff games,
one can approximate ordinary zero-sum values (without restricting admissible
strategies) in ${\mathsf{FNP}}^{{\mathsf{NP}}}$.

Finite-memory strategies, Equilibria, Approximation, Imperfect information
games

††copyright: acmlicensed††ccs: Theory of computation Algorithmic game
theory††ccs: Theory of computation Exact and approximate computation of
equilibria

##  1\. Introduction

We study stochastic games of infinite duration, where $k$ players jointly move
a pebble through a finite directed graph. In every round, all players
independently select, possibly at random, one out of finitely many actions.
The pebble is moved according to a fixed distribution for the current state
and chosen action vector, the players receive an associated reward and the
next round begins. In general partial-information games, players do not
observe the choices or rewards of other players nor the current state of the
pebble. Instead, at the beginning of each round, they receive a signal that
may or may not include that information. This subsumes classical settings such
as perfect-information games (signals include the current state, rewards, and
actions of others), turn-based games (in every round only one player’s action
affects the outcome), and non-stochastic games (all distributions are Dirac).
We focus on games with mean-payoff (aka limit-average, where players aim to
maximise their expected long-term average rewards). We discuss in Section 8.1
how our constructions can be applied to parity games as well with minor
simplifying adjustments.

We want to solve such games, i.e., compute ($\varepsilon$)-Nash equilibria,
zero-sum values and witnessing strategies. However, partial-information games
are very expressive and not guaranteed to have (Nash, or $\varepsilon$-Nash)
equilibria or zero-sum values (Solan and Ziliotto, 2016). Moreover, already
for rather restricted subclasses that do admit $\varepsilon$-optimal
strategies, finding them is undecidable: this is the case for single-player,
reachability games with a unique signal, aka partially observable Markov
decision processes (POMDPs) (Madani et al., 1999; Chatterjee et al., 2022).
Here, finding the best finite-memory strategy (one that is representable by a
finite automaton) without providing a bound on its size up front is complete
for the recursive-enumerable problems (Chatterjee et al., 2022). For the case
of partial-information stochastic parity games, where one player has perfect-
information, finding the best finite-memory strategy is EXPTIME-complete
(Chatterjee et al., 2014). Even for perfect-information games such as the
classic “Big Match” (Gillette, 1957; Blackwell and Ferguson, 1968), finite-
memory strategies can be much worse than general ones (Hansen et al., 2023).
For this reason, and motivated by applications, much work has focused on
identifying special cases of games in which simple strategies are sufficient
to play $\varepsilon$-optimally, or to guarantee the existence of
$\varepsilon$-Nash equilibria (Gillette, 1957; Ehrenfeucht and Mycielski,
1973; Mertens and Neyman, 1981; Filar et al., 1991; Puterman, 1994; Mansour
and Singh, 1999; Secchi and Sudderth, 2002; Gimbert and Zielonka, 2005; Hansen
et al., 2011; Hunter et al., 2018; Bouyer et al., 2022, 2023).

In this paper, we study the complexity of solving games _with respect to
bounded-memory strategies_ , meaning that all players are required to play
according to a finite-memory strategy where the number of distinct memory
modes is bounded a priori. We ask what outcomes players can still guarantee,
and how, if one assumes that only strategies up to the given bound are
admissible. This approach lets us study “realistic” scenarios that require
bounded representations for strategies. Moreover, for many classes of games,
values/equilibria with respect to $b$-bounded strategies coincide with
ordinary zero-sum values/equilibria. For example, concurrent reachability
games (Hansen et al., 2009, 2011; Frederiksen and Miltersen, 2013; Hansen et
al., 2014) admit $\varepsilon$-optimal strategies that are memoryless ($b=1$).
Consequently, our upper bounds directly apply to such special cases.

There remain significant challenges for solving games even with known bounds
on the number of states and memory modes in admissible strategies: (1) optimal
strategies/Nash-equilibria might not exist (Everett, 1957), (2)
values/outcomes of equilibria can be irrational (Etessami and Yannakakis,
2008) and can therefore at best be approximated, and (3) strategies with
rational distributions may require double-exponentially small probabilities to
be ($\varepsilon$-)optimal (Hansen et al., 2009). This last point is
especially problematic since it means it requires more than polynomial time to
guess/write down a good strategy with binary encoded values.

#### Contributions

We provide new complexity bounds for approximating $\varepsilon$-optimal
strategies and $\varepsilon$-equilibria in partial-information games with
bounded strategies. We give an overview here; precise claims are delayed to
Section 3 after introducing notations.

First, we give ${\mathsf{NP}}$ and ${\mathsf{coNP}}$ lower bounds for
approximating the value achievable by bounded strategies under very weak
assumptions. More precisely, we show that it is $\mathsf{NP}$-hard to check if
in a given 1-player reachability game the value achieved by memoryless
strategies exceeds a given threshold. This holds even if the threshold is
unary encoded, and even though the games we construct admit optimal memoryless
strategies that do not require randomisation. As a simple corollary, we obtain
$\mathsf{coNP}$-hardness for $2$-player, zero-sum games. An ${\mathsf{NP}}$
lower bound for checking the existence of a memoryless winning strategy for
$2$-player, partial-information, non-stochastic games was shown by Amoussou-
Guenou et al.(Amoussou-Guenou et al., 2021). Our result uses stochasticity but
works for any bounded-memory strategies. Moreover, the
${\mathsf{NP}}$-hardness holds already for the $1$-player case.

As a second and main contribution, we propose a framework that yields simple
approximation algorithms low in the polynomial hierarchy (at level $\leq 2$).
These ultimately work by guessing polynomial representations of witnessing
strategies and then approximating outcomes in the resulting Markov chains.
Inspired by (Frederiksen and Miltersen, 2013), we use fixed precision
floating-point notations to polynomially represent and manipulate doubly-
exponentially small values in probability distributions.

The key new ingredient is an iterative state-space reduction scheme for Markov
chains. By way of encoding this in $\mathrm{FO}(\mathbb{R})$, the first-order
theory of the reals(Basu et al., 2006), we derive (1) a ${\mathsf{PSPACE}}$
algorithm for checking the existence, and computing representations of,
$\varepsilon$-equilibria for $\varepsilon\geq 0$; (2) that if suitable
equilibria/strategies exist for $\varepsilon>0$, then also ones that are
polynomially representable and verifiable; (3) that the loss of precision
incurred by implementing the reduction scheme approximately can be bounded.
The latter two points use a fixed-precision floating-point representation
allowing us to represent doubly-exponentially small values in strategies using
a polynomial number of bits.

Our results have direct consequences for solving several well-known types of
games including partial-information parity and mean-payoff games (Hunter et
al., 2018), stay-in-a-set games (Secchi and Sudderth, 2002), quitting games
(Solan and Vieille, 2001) and concurrent reachability, Büchi and parity games
(Bordais et al., 2021; Bouyer et al., 2021; Bordais et al., 2022, 2023). In
particular, we show how to approximate values/equilibria for $2$-player, zero-
sum concurrent mean-payoff games (not discounted and with no assumptions on
strategies - in particular, allowing infinite memory ones as is sometimes
required) (Mertens and Neyman, 1981; Chatterjee et al., 2008; Hansen et al.,
2009, 2011; Oliu-Barton, 2021). Our algorithm is in
${\mathsf{FNP}}^{\mathsf{NP}}$, improving on the state-of-the-art algorithms
that use polynomial space based on reductions to the existential theory of the
reals (Hansen et al., 2011; Etessami and Yannakakis, 2008).

#### Paper structure

We start by introducing notations in Section 2 before stating our results
formally in Section 3. In Section 4 we give ${\mathsf{NP}}$\- and
${\mathsf{coNP}}$-lower bounds. Section 5 presents a value-preserving state-
space reduction procedure for Markov Chains that forms the basis for our upper
bounds.

In Section 6, we show how to express games and questions about strategies, in
the first-order theory of the reals and derive ${\mathsf{PSPACE}}$ upper
bounds for checking the existence of $\varepsilon$-equilibria and good zero-
sum strategies. In Section 7 we present our main approximation scheme and the
resulting upper bounds. This relies on an encoding into
$\mathrm{FO}(\mathbb{R})$ to derive polynomial bounds on the representations
of witnessing strategies and an argument that small perturbations of
strategies lead to only small changes in values (Section 7.2). In Section 7.3
we show how to approximate values in the Markov chains resulting from fixing
candidate strategy profiles. In Section 7.4 we tie the above together into an
algorithm to approximate values or equilibria in
${\mathsf{FNP}}^{\mathsf{NP}}$. We conclude by discussing applications and new
results for related classes of games in Section 8.

##  2\. Notations

For a set $X$, we write $X^{k}$ for its $k$-fold Cartesian product and $a[i]$
for the $i$th component of a vector $a\in X^{k}$. Let $X^{*}$ and $X^{\omega}$
denote the sets of finite and infinite sequences with elements in $X$,
respectively. We write $\mathbb{D}(X)$ for the set of all probability
distributions over $X$.

#### Partial-information Games

A $k$-player game is given by finite sets of states $V$, actions $A$, signals
$S$, rewards $C$, and a transition function $\Delta:V\times
A^{k}\to\mathbb{D}(C^{k}\times S^{k}\times V)$ that maps the current state and
action vector to a probability distribution over triples describing rewards,
next signals, and the next state. The game is played in stages
$i\in\\{0,1,2,\dots\\}$, in each of which every player receives a signal,
selects an action and receives a reward. At stage $i$, the game is in a vertex
$v_{i}$. Each player $j$ is sent the signal $s_{i}[j]$ and selects an action
$a_{i}[j]$. Then a triple of rewards, signals, and successor state
$(c_{i+1},s_{i+1},v_{i+1})$ is drawn randomly according to
$\Delta(v_{i},a_{i})$ and the game moves to the next stage in vertex
$v_{i+1}$. This random process goes on forever and describes an infinite
sequence
$\rho=(v_{0},s_{0},a_{0},c_{0}),(v_{1},s_{1},a_{1},c_{1})\dots\in(V\times
S^{k}\times A^{k}\times C^{k})^{\omega}$. We call such an infinite sequence a
_play_ and let ${\mathop{Plays}\nolimits}$ denote the set of all plays.

Note that games as described above are _partial-_ (aka.  _imperfect_)
information games: the players do not directly observe the current state, the
actions selected by other players nor the rewards obtained (not even their
own). All they get to see is the signals sent to them. We call a game
_perfect-information_ if, at every stage $i>0$, every player receives as a
signal the full action vector $a_{i-1}$, reward vector $c_{i-1}$ and the
current state $v_{i}$. A game is _turn-based_ (as opposed to _concurrent_) if
in any stage, only one player’s action influences the next state and signals.
That is, for every vertex $v\in V$ there is some player $j$ so that
$\Delta(v,a)=\Delta(v,a^{\prime})$ whenever $a[j]=a^{\prime}[j]$.

#### Plays and Strategies

A _strategy_ is a function $\sigma:S^{*}\to\mathbb{D}(A)$, that determines,
for every sequence of signals, a probability distribution over the action set.
It is based on a set $M$ of memory modes if it can be described by an initial
memory mode $m_{0}\in M$ and a pair of functions
${\sigma}_{\mathop{act}\nolimits}:M\times S\rightarrow\mathbb{D}(A)$ and
${\sigma}_{\mathop{up}\nolimits}:M\times S\rightarrow\mathbb{D}(M)$ that
select actions and update the memory mode, respectively. That is, for any
signal sequence, $s=s_{0}s_{1}s_{2}\ldots s_{j}\in S^{*}$,
$\sigma(s)={\sigma}_{\mathop{act}\nolimits}(m_{j},s_{j})$ and
$m_{j+1}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}{\sigma}_{\mathop{up}\nolimits}(m_{j},s_{j})$.

A strategy is called _finite-memory_ if it is based on a finite memory set $M$
and _memoryless_ if it is based on a singleton set $M$. A strategy is
_discrete_ (also _pure_) if all its choices are Dirac. In perfect-information
games, we call a strategy _stationary_ if its choices only depend on the
current state (and not previous actions or rewards).

#### Strategy profiles, Probability measures

A _strategy profile_ is a family $\sigma=(\sigma[j])_{j\leq k}$ of strategies,
one for each player. Together with an initial state $v_{0}$ and signal
$s_{0}$, it uniquely induces a probability measure
$\mathbb{P}^{\sigma}_{v_{0},s_{0}}\in\mathbb{D}({\mathop{Plays}\nolimits})$
over infinite plays (see (Billingsley, 1995) for details). We will write
${\mathbb{E}}^{\sigma}_{v_{0},s_{0}}\left[{X}\right]$ for the derived expected
value of a random variable $X$ and drop indices when clear from the context.

#### Objectives

Each player $j\leq k$ has an objective, a measurable function
$\mathcal{O}_{j}:{\mathop{Plays}\nolimits}\to\mathbb{R}$ and selects their
strategy to maximise the expectation of this objective, against any possible
opponent strategies. A game is _zero-sum_ if $\sum_{j\leq
k}\mathcal{O}_{j}(\rho)=0$ for every $\rho\in{\mathop{Plays}\nolimits}$.

In this paper, we consider mean-payoff objectives as well as the special case
of reachability objectives. A _mean-payoff_ objective (for player $j\leq k$)
assigns play $\rho=(v_{0},s_{0},a_{0},c_{0}),(v_{1},s_{1},a_{1},c_{1})\dots$
the value

$\underline{\mathop{MP}}(\rho)=\liminf_{N\to\infty}\frac{1}{N}\sum_{i=0}^{N}c_{i}[j].$

The _reachability_ objective for a target set $T\subseteq V$ of states assigns
play $\rho$ as above the value $1$ if $v_{i}\in T$ for some round $i\geq 0$
and $0$ otherwise.

#### Optimality criteria

The player in a 1-player game $G$ plays to maximise the expectation of the
given objective $\mathcal{O}$. Here, the _value_ of the game is
${\mathtt{val}(G)}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\sup_{\sigma\in\Sigma}{\mathbb{E}}^{\sigma}_{v_{0},s_{0}}\left[{\mathcal{O}}\right]$
and for $\varepsilon\geq 0$, a strategy $\sigma$ is called _$\varepsilon$
-optimal_ if
${\mathtt{val}(G)}-{\mathbb{E}}^{\sigma}_{v_{0},s_{0}}\left[{\mathcal{O}}\right]\leq\varepsilon$.

For 2-player zero-sum games $G$, let $\Sigma$ and $\Pi$ denote the set of
strategies for players 1 and 2, respectively. Then the _lower value_ and
_upper value_ are defined as
${\overline{\mathtt{val}}({G})}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\sup_{\sigma\in\Sigma}\inf_{\pi\in\Pi}{\mathbb{E}}^{\sigma,\pi}_{v_{0},s_{0}}\left[{\mathcal{O}}\right]$
and
${\underline{\mathtt{val}}({G})}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\inf_{\pi\in\Pi}\sup_{\sigma\in\Sigma}{\mathbb{E}}^{\sigma,\pi}_{v_{0},s_{0}}\left[{\mathcal{O}}\right]$.
By definition, it holds that
${\overline{\mathtt{val}}({G})}\leq{\underline{\mathtt{val}}({G})}$. If the
two are equal then this quantity is called the _value_ of the game, denoted by
${\mathtt{val}(G)}$. For $\varepsilon\geq 0$, a strategy $\sigma\in\Sigma$ is
called _$\varepsilon$ -optimal_ if
${\mathtt{val}(G)}-\inf_{\pi\in\Pi}{\mathbb{E}}^{\sigma,\pi}_{v_{0},s_{0}}\left[{\mathcal{O}}\right]\leq\varepsilon$
(and similar for player 2 strategies $\pi$).

For general $k$-player games $G$ and any $\varepsilon\geq 0$, an
_$\varepsilon$ -Nash equilibrium_ (NE) is a strategy profile
$(\sigma_{j})_{j\leq k}$ so that any unilateral deviation by a player $j$
increases their expected outcome by at most $\varepsilon$. That is, for any
profile $\sigma^{\prime}$ where $\sigma^{\prime}[i]=\sigma[i]$ for all $i\neq
j$, it holds that
${\mathbb{E}}^{\sigma^{\prime}}\left[{\mathcal{O}_{j}}\right]\leq{\mathbb{E}}^{\sigma}\left[{\mathcal{O}_{j}}\right]+\varepsilon$.

#### Complexity classes

Function problems are given by a relation
$R\subseteq\\{0,1\\}^{*}\times\\{0,1\\}^{*}$ where for some polynomial $p$,
every $(x,y)\in R$ implies ${\left|y\right|}\leq p({\left|x\right|})$. For a
class $\mathcal{X}$ of decision problems, $R$ is in the corresponding function
class ${\mathsf{F\mathcal{X}}}$ if and only if the language $\\{(x,y)\mid
R(x,y)\\}$ is in $\mathcal{X}$, meaning the question if $R(x,y)$ is true for
given $x$ and $y$ is decidable in $\mathcal{X}$. This corresponds to the
search problem where for given $x$, one can either stop and output $y$ so that
$R(x,y)$, or correctly state that no such $y$ exists. In particular, we are
concerned with the classes ${\mathsf{FNP}}^{\mathsf{NP}}$, at level $2$ of the
polynomial hierarchy.

#### Floating-point Representations of Distributions

For any number $u\in\mathbb{N}$, let $\mathbb{Q}(u)$ denote the set of non-
negative dyadic rationals with a $u$-bit mantissa

$\mathbb{Q}(u)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{0\\}\cup\\{x2^{-i}~{}\mid~{}x\in\\{2^{u-1},2^{u-}+1,\dots,2^{u}-1\\},i\in\mathbb{Z}\\}.$

The $u$-bit floating point representation of $x2^{-i}$ is $\langle
1^{u},[{x}]_{2},[{i}]_{2}\rangle$, where $[{\cdot}]_{2}$ is the binary
expansion. The floating point representation of $0$ is $\langle
1^{u},0\rangle$. The _relative distance_ between two non-negative real numbers
$x$ and $x^{\prime}$ as
$\mathop{dist}(x,x^{\prime})=\frac{\max(x,x^{\prime})}{\min(x,x^{\prime})}-1$
with the convention that $0/0=1$ and $c/0=+\infty$ for any $c>0$. Two non-
negative reals $x$ and $x^{\prime}$ are _$(u,i)$ -close_ if
$\mathop{dist}(x,x^{\prime})\leq\left(\frac{1}{1-2^{-u+1}}\right)^{i}-1$. Let
$\mathbb{P}(u)$ denote the set of finite probability distributions
$(p_{1},p_{2},\ldots,p_{n})$ so that there exist numbers
$(p^{\prime}_{1},p^{\prime}_{2},\ldots,p^{\prime}_{n})\in\mathbb{Q}(u)$ with
$p_{i}=p^{\prime}_{i}/\sum_{j}p^{\prime}_{j}$ for all $i=1,\ldots,n$ and so
that $\sum_{j}p^{\prime}_{j}$ is $(u,n)$-close to $1$. We call the primed
vector the ($u$-bit) _approximately normalised representation_ of the unprimed
distribution.

##  3\. Overview of Our Results

We consider the problem of approximating $\varepsilon$-Nash equilibria and
zero-sum values with respect to bounded-memory strategies.

###### Definition 3.1.

Consider some $k$-player game with objectives $(\mathcal{O}_{j})_{j\leq k}$
and a set $\mathcal{S}$ of admissible strategy profiles. Let $\varepsilon\geq
0$.

An $\varepsilon$-Nash equilibrium _with respect to_ $\mathcal{S}$ is a
strategy profile $(\sigma_{j})_{j\leq k}\in\mathcal{S}$ so that any unilateral
deviation by a player $j$ that yields another profile in $\mathcal{S}$ can at
most increase their expected outcome by $\varepsilon$. That is, for any
profile $\sigma^{\prime}\in\mathcal{S}$ where $\sigma^{\prime}[i]=\sigma[i]$
for all $i\neq j$, it holds that
${\mathbb{E}}^{\sigma^{\prime}}\left[{\mathcal{O}_{j}}\right]\leq{\mathbb{E}}^{\sigma}\left[{\mathcal{O}_{j}}\right]+\varepsilon$.

In the $2$-player zero-sum case, we say a strategy $\sigma$ for player $1$
_$\varepsilon$ -achieves_ value $v\in\mathbb{R}$ with respect to $\mathcal{S}$
if it guarantees expected outcome of at least $v-\varepsilon$ against all
admissible opponent strategies. That is, if
$\inf_{\pi~{}\mid~{}(\sigma,\pi)\in\mathcal{S}}{\mathbb{E}}_{\sigma,\pi}\left[{\mathcal{O}_{1}}\right]\geq
v-\varepsilon$.

For instance, an $\varepsilon$-Nash equilibrium with respect to finite-memory
strategies, is a profile consisting of finite-memory strategies, so that no
player can, by switching to another finite-memory strategy, improve their
expected payout by more than $\varepsilon$.

We are interested in approximating such equilibria and zero-sum strategies
with respect to finite memory strategies with bounded memory. Formally, we are
given a $k$-player partial-information game $G$, some $\varepsilon\in[0,1]$
and a vector ${\bf b}\in\mathbb{N}^{k}$ of memory bounds, one for each player
$i\leq k$. Write $\mathcal{B}_{i}({\bf b})$ for the set of player $i$
strategies that are based on a set $M$ of size ${\left|M\right|}\leq{\bf
b}[i]$ and let $\mathcal{B}({{\bf b}})$ be all strategy profiles wherein each
player $i$ uses a strategy in $\mathcal{B}_{i}({\bf b}[i])$. For multiplayer
games ($k\geq 2$) we ask if there exists an $\varepsilon$-Nash equilibrium
with respect to (wrt) $\mathcal{B}({{\bf b}})$ and if so, we want to compute
one. For $2$-player zero-sum games, we ask if there exists a strategy that
$\varepsilon$-achieves a given value $v$ with respect to (wrt)
$\mathcal{B}({{\bf b}})$.

Throughout, we assume that the number $k$ of players is fixed; The inputs
$\varepsilon$, $v$ and rewards are given in binary and the bounds ${\bf b}$ in
unary encoding111This assumption is natural as we want to compute
representations of strategies, in particular, which mixed action to play for
any combination of game and memory state.. The probability distributions
dictated by the transition function $\Delta$ are assumed to be given in
$u$-bit approximately normalised floating point notation.

###### Theorem 3.2.

For every fixed $k\geq 1$ the following is in $\mathsf{PSPACE}$.

  1. (1)

Given a $k$-player game, bounds ${\bf b}\in\mathbb{N}^{k}$ and
$\varepsilon\geq 0$, check whether an $\varepsilon$-Nash equilibrium exists
with respect to $\mathcal{B}({{\bf b}})$.

  2. (2)

Given a $2$-player zero-sum game, bounds ${\bf b}\in\mathbb{N}^{2}$, a number
$v\in\mathbb{R}$ and $\varepsilon\geq 0$, check whether there exists a player
$1$ strategy that $\varepsilon$-achieves value $v$ with respect to
$\mathcal{B}({{\bf b}})$.

Our proof is by an effective polynomial reduction of the problem to the
satisfiability problem of $\mathrm{FO}(\mathbb{R})$ formula so that the size
of the constructed formula is only polynomial in the input, has fixed
alternation depth of $2$, and solutions dictate values and witnessing
strategies/equilibria. At its core, our encoding relies on a state reduction
technique for finite Markov chains, that results from fixing a strategy
profile. This requires only polynomially many collapses and can therefore be
“implemented” as a small system of polynomial equations.

We show that equilibria, zero-sum values and witnessing strategies can be
approximated, up to an exponential additive error, at level 2 of the
polynomial hierarchy.

###### Theorem 3.3.

For every fixed $k\geq 1$ the following are in ${\mathsf{FNP}}^{\mathsf{NP}}$.

  1. (1)

Given a $k$-player game, bounds $b\in\mathbb{N}^{k}$ and
$\varepsilon\in(0,1/2)$, find an $\varepsilon$-Nash equilibrium with respect
to $\mathcal{B}({{\bf b}})$ (if for some
$\varepsilon^{\prime}\in[0,\varepsilon/3)$, an $\varepsilon^{\prime}$-Nash
equilibrium with respect to $\mathcal{B}({{\bf b}})$ exists);

  2. (2)

Given a $2$-player zero-sum game, bounds $b\in\mathbb{N}^{k}$,
$\varepsilon\in(0,1/2)$ and $v\in\mathbb{R}$, find a strategy that
$\varepsilon$-achieves $v$ with respect to $\mathcal{B}({{\bf b}})$ (if for
some $\varepsilon^{\prime}\in[0,\varepsilon/3)$, some strategy
$\varepsilon^{\prime}$-achieves $v$ with respect to $\mathcal{B}({{\bf b}})$).

Using the second point and binary search one can $\varepsilon$-approximate the
lower and upper values wrt $\mathcal{B}({{\bf b}})$ in $2$-player zero-sum
games. These complexity upper bounds above directly apply to many classes of
games that admit memoryless $\varepsilon$-optimal strategies
($\mathcal{B}({{\bf 1}})$).

In addition to the approximation algorithms, we provide an ${\mathsf{NP}}$\-
and ${\mathsf{co}}{\mathsf{NP}}$-lower bound for approximating zero-sum values
for partial-information games. This already holds for a very restricted class
of games, as follows. Let us call a game _simple_ if it is a 1-player
reachability game so that the underlying transition graph is acyclic (except
for target states); the motion from the initial state $v_{0}$ is uniformly at
random over a set of successor states; and for all actions $a$ and states
$v\neq v_{0}$ the distributions $\Delta(v,a)$ are Dirac.

We show that it is hard to check if the value achieved by memoryless
strategies exceeds a given threshold. We state this in the form of a gap
problem (cf. (Goldreich, 2006)).

###### Theorem 3.4.

The following decision problem is $\mathsf{NP}$-hard. Given $0\leq l<u\leq 1$
in unary encoding and a simple game in which the zero-sum value is not in
$(l,u)$ and in which there exists an optimal memoryless deterministic
strategy. Is the value greater than or equal to $u$?

This lower bound directly applies to threshold problems regarding the values
of zero-sum games, approximating zero-sum values and witnessing strategies,
and to approximating $\varepsilon$-equilibria in multiplayer games, wrt
memoryless strategies ($\mathcal{B}({{\bf 1}})$).

$i,j$$i,j+1$$w,j$$w,j+1$$\mathop{true},\mathop{false}$$\mathop{true}$$\mathop{false}$
(a) $C_{i}$ contains $X_{j}$.

$i,j$$i,j+1$$w,j$$w,j+1$$\mathop{true}$$\mathop{true},\mathop{false}$$\mathop{false}$
(b) $C_{i}$ contains $\lnot X_{j}$.

$i,j$$i,j+1$$w,j$$w,j+1$$\mathop{true},\mathop{false}$$\mathop{true},\mathop{false}$
(c) $C_{i}$ contains neither $X_{j}$ nor $\lnot X_{j}$

Figure 1. Stages $0<j\leq m$ in game $G_{\varphi}$. In step $j\leq m$ the
player receives signal $j$ and the pebble is moved out of some state $(*,j)$.

##  4\. Lower Bound

We prove Theorem 3.4 by reduction from the Boolean satisfiability problem: an
instance of 3SAT with $n$ clauses and $m$ variables variables
$X_{1},X_{2},\ldots,X_{m}$ is a conjunction

$\varphi=\bigwedge_{i=1}^{n}\bigvee_{j=1}^{3}L_{i,j}$

where each conjunct is called a clause and each $L_{i,j}$ is either a positive
literal (a variable in $\\{X_{k}\mid k\leq m\\}$) or a negative literal (the
negation of a positive literal). W.l.o.g., assume that no variable appears
both positively and negatively in any clause. An _interpretation_ is a mapping
$\nu:\\{1,\ldots,m\\}\to\\{\mathop{true},\mathop{false}\\}$ assigning a truth
value to each variable. The ($\mathsf{NP}$-hard) decision problem is if there
exists an interpretation $\nu$ under which the given conjunction is true,
meaning that for every clause $i$ there is some $j$ such that either
$L_{i,j}=X_{k}$ and $\nu(k)=\mathop{true}$ or $L_{i,j}=\neg X_{k}$ and
$\nu(k)=\mathop{false}$. Analogously, it is $\mathsf{coNP}$-hard to check if,
for a given 3SAT instance, no interpretation satisfies the given conjunction.

We proceed to describe a game $G_{\varphi}$ for a given instance $\varphi$.
This game is set up so that in the first round, independently of the player’s
action, a random clause is selected to be checked. In the following $m$
rounds, the player’s actions determine an interpretation, one variable per
round and without knowing which clause is being checked.

Formally, for every $0\leq j\leq m+1$ the game has a state $(w,j)$ as well as
states $(i,j)$ for all $0\leq i\leq n$. The available actions are
$A=\\{\mathop{true},\mathop{false}\\}$. The game starts in $v_{0}=(0,0)$ and
in the first round, under both actions, moves uniformly at random into a state
in $\\{(i,1)\mid 0\leq i\leq n\\}$, thereby selecting the clause $i$ to be
checked.

In round $0<j\leq m$, the player picks an action $\mathop{true}$ or
$\mathop{false}$ to indicate that variable $X_{j}$ has that value in his
chosen interpretation. From state $(w,j)$, the pebble moves surely to
$(w,j+1)$, regardless of this choice. Otherwise, from state $(i,j)\neq(w,j)$,
there are three cases depending on whether clause $C_{i}$ is satisfied by
setting the value of $X_{j}$ as indicated by the player’s action (cf. Figure
1).

  1. (a)

If $C_{i}$ contains $X_{j}$ positively, then upon action $\mathop{true}$ the
pebble surely moves to $(w,j+1)$ and upon action $\mathop{false}$, it surely
moves to $(i,j+1)$.

  2. (b)

If $C_{i}$ contains $X_{j}$ negatively, then the roles are reversed: upon
action $\mathop{false}$ the pebble surely moves to $(w,j+1)$ and upon action
$\mathop{true}$, it surely moves to $(i,j+1)$.

  3. (c)

If $C_{i}$ does not contain $X_{j}$, then upon both actions the pebble surely
to $(i,j+1)$.

In every round from a state $(*,j)$, the player receives signal $j$. This ends
the description of game $G_{\varphi}$.

The player only knows the current round number $j$ up to $m+1$, but not in
which state the pebble resides, i.e., which clause is being checked and
whether it is already satisfied. By his actions in rounds $1,\ldots,m$, he
picks a distribution over the possible variable interpretations.

Let us write
$W\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\text{Reach}({\\{(w,m+1)\\}})$
for the set of plays that reach state $(w,m+1)$. The following formalises the
key property of the game $G_{\varphi}$.

###### Lemma 4.1.

Let $\nu$ be an interpretation that satisfies $b$ out of $n$ clauses and let
$\sigma$ be a strategy that plays action $\nu(X_{j})$ in round $0<j\leq m$.
Then $\mathbb{P}^{\sigma}_{v_{0},0}(W)=b/n$.

###### Proof.

In the first round, nature picks uniformly at random a state $(i,1)$ for some
$0<i\leq n$. Then in exactly $b$ out of $n$ many cases (the ones where clause
$C_{i}$ is satisfied by the assignment), the play leads to $(w,m+1)$. ∎

###### Proof of Theorem 3.4.

To show the $\mathsf{NP}$-hardness, we reduce from 3SAT. Given an instance
$\varphi$ with $n$ clauses and $m$ variables, let $c$ be the maximal number of
clauses satisfied by any interpretation.

Let $G$ be the game $G_{\varphi}$ where the player receives reward $1$
whenever the pebble is in state $(w,m+1)$ and $0$ otherwise. This game is
_simple_ ; in particular, it is a 1-player reachability game with target
$(w,m+1)$, encoded as a mean-payoff game.

We show that the value in $G$ is $1$ if $\varphi$ is satisfiable and at most
$1-1/n$ otherwise. Suppose first that $\varphi$ is satisfiable. Then there
exists an interpretation that satisfies $c=n$ clauses and the value is $1$, by
Lemma 4.1. Otherwise, if $\varphi$ is not satisfiable, every interpretation
satisfies at most $c$ clauses and thus witnesses at most value $c/n$. As the
history of signals is the same for all infinite plays, every (arbitrary)
strategy $\sigma$ defines a distribution over all possible variable
interpretations. The value it witnesses is the linear combination of the
values witnessed by discrete strategies, and so also at most $c/n\leq 1-1/n$.

Let $l\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}1-1/n$ and
$u\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}1$. By the argument above,
the value of the game is not in $(l,u)$ and $\geq u$ if, and only if,
$\varphi$ is satisfiable. ∎

By the argument above, it is $\mathsf{coNP}$-hard to check if the value of a
simple game is less than or equal to a threshold $l$ given in unary.
Similarly, one can introduce a passive second player that receives inverted
rewards ($-r$ whenever player 1 gets $r$). This shows that it is
$\mathsf{coNP}$-hard to check if the value of a $2$-player zero-sum safety
game exceeds a threshold $u$.

The games constructed above all admit memoryless optimal strategies.
Therefore, approximating the value wrt memoryless ($\mathcal{B}({b={\bf 1}})$)
strategies is at best $\mathsf{FNP}$, even for simple games.

##  5\. Mean-Payoff Values for Markov Chains

We demonstrate how to iteratively collapse Markov chains with the aim of
computing the expected mean-payoff value of a fixed initial state. The
underlying idea is to simultaneously summarise the expected reward and
duration (number of steps) of paths between two nodes and adjust these
summaries consistently during collapses. Once an irreducible chain is produced
it is trivial to read off the mean-payoff values.

A Markov chain is a $1$-player game with only a single, unique action $a\in A$
for the player in every state (the player is just there to collect the rewards
and cannot influence the outcome). To simplify notations, we will assume that
a Markov chain $M$ has states $V=\\{1,\dots,n\\}$ and for every edge from
states $i$ to $j$, let $\mathop{p}\nolimits(i,j)$ and
$\mathop{r}\nolimits(i,j)\in\mathbb{R}$ be the associated probability and
reward respectively. Each edge from $i$ to $j$ also has a duration denoted by
$\mathop{d}\nolimits(i,j)$. We define the _mean-payoff ratio_ of an infinite
play $\rho=s_{0}s_{1}\ldots$ as the limit of total reward by the total
duration of expanding prefixes:

(1)
${\mathop{MPR}}(\rho)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\liminf_{N\to\infty}\frac{\sum_{i=0}^{N-1}\mathop{r}\nolimits(s_{i},s_{i+1})}{\sum_{i=0}^{N-1}\mathop{d}\nolimits(s_{i},s_{i+1})}$

Notice that this coincides with the usual mean-payoff
$\underline{\mathop{MP}}({\rho})$ if all edges have duration $1$.

Let’s recall a few notions about Markov chains. Write $i\to j$ to denote that
there is a path from state $i$ to $j$ with non-zero probability. We say $i$
and $j$ _communicate_ if both $i\to j$ and $j\to i$. A set $S\subseteq V$ of
states is communicating if all its elements are pairwise communicating. $S$ is
closed if $i\to j$ and $i\in S$ implies $j\in S$. Closed communicating sets
(CCSs) are also called bottom strongly connected components. A state $i$ is
_recurrent_ if it belongs to a CCS and _transient_ otherwise. It is
_absorbing_ if $\mathop{p}\nolimits(i,i)=1$. That is, an absorbing state
describes its own (singleton) CSS.

We introduce two operations on Markov chains that will preserve the expected
mean-payoff ratio ${\mathbb{E}}_{s}\left[{{\mathop{MPR}}}\right]$ from any
state $s$. Proofs of their correctness (Lemmas 5.2 and 5.4) are in Appendix A.

###### Definition 5.1 (State Elimination).

Let $M=(V,\mathop{p}\nolimits)$ be a Markov chain with states
$\\{1,\dots,n\\}$ and probability matrix $\mathop{p}\nolimits$ so that
$\mathop{p}\nolimits(n,n)=0$ (state $n$ does not have a self-loop). The Markov
chain $M^{\prime}=(V^{\prime},\mathop{p}\nolimits^{\prime})$ results from $M$
by eliminating state $n$ if it has states $V^{\prime}=V\setminus\\{n\\}$ and,
for every two states $i,j\neq n$, the values of probabilities, rewards, and
durations are updated as follows (see Figure 2).

$\displaystyle\mathop{p}\nolimits^{\prime}(i,j)$
$\displaystyle~{}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}~{}\mathop{p}\nolimits(i,j)+\mathop{p}\nolimits(i,n)\cdot\mathop{p}\nolimits(n,j)$
$\displaystyle\mathop{r}\nolimits^{\prime}(i,j)$
$\displaystyle~{}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}~{}\mathop{p}\nolimits(i,j)\mathop{r}\nolimits(i,j)+(\mathop{p}\nolimits(i,n)\cdot\mathop{p}\nolimits(n,j))(\mathop{r}\nolimits(i,n)+\mathop{r}\nolimits(n,j))$
$\displaystyle\mathop{d}\nolimits^{\prime}(i,j)$
$\displaystyle~{}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}~{}\mathop{p}\nolimits(i,j)\mathop{d}\nolimits(i,j)+(\mathop{p}\nolimits(i,n)\cdot\mathop{p}\nolimits(n,j))(\mathop{d}\nolimits(i,n)+\mathop{d}\nolimits(n,j))$

$i$$n$$j$$\mathop{p}\nolimits(n,i)$$\mathop{r}\nolimits(n,i)$$\mathop{d}\nolimits(n,i)$$\mathop{p}\nolimits(n,j)$$\mathop{r}\nolimits(n,j)$$\mathop{d}\nolimits(n,j)$$\mathop{p}\nolimits(n,j)$$\mathop{r}\nolimits(n,j)$$\mathop{d}\nolimits(n,j)$$\leadsto$$i$$j$$\mathop{p}\nolimits^{\prime}(n,j)$$\mathop{r}\nolimits^{\prime}(n,j)$$\mathop{d}\nolimits^{\prime}(n,j)$
Figure 2. Elimination of state $n$: every length-two path via state $n$ in $M$
(on the left) is removed and the corresponding direct edge re-weighted in
$M^{\prime}$ (right). The expected reward and duration of going from $i$ to
$j$ remains the same.

###### Lemma 5.2.

Suppose $M^{\prime}$ results from $M$ by eliminating state $n$. Then
${\mathbb{E}}^{M}_{s}\left[{{\mathop{MPR}}}\right]={\mathbb{E}}^{M^{\prime}}_{s}\left[{{\mathop{MPR}}}\right]$
for every state $s\neq n$ .

$n$j$i$$\mathop{p}\nolimits(n,n)$$\mathop{r}\nolimits(n,n)$$\mathop{d}\nolimits(n,n)$
$\mathop{p}\nolimits(n,i)$$\mathop{r}\nolimits(n,i)$$\mathop{d}\nolimits(n,i)$$\mathop{p}\nolimits(n,j)$$\mathop{r}\nolimits(n,j)$$\mathop{d}\nolimits(n,j)$$\leadsto$$n$$j$$i$$\mathop{p}\nolimits^{\prime}(n,i)$$\mathop{r}\nolimits^{\prime}(n,i)$$\mathop{d}\nolimits^{\prime}(n,i)$$\mathop{p}\nolimits^{\prime}(n,j)$$\mathop{r}\nolimits^{\prime}(n,j)$$\mathop{d}\nolimits^{\prime}(n,j)$
Figure 3. Elimination of loop $n$ in $M$ (left). In $M^{\prime}$ (right), the
corresponding edge has probability $0$ and all other edges from $n$ are re-
weighted to match the expected duration and expected reward of paths that
start by iterating the loop.

###### Definition 5.3 (Loop Elimination).

Let $M=(V,\mathop{p}\nolimits)$ be a Markov chain with states
$\\{1,\dots,n\\}$ and probability matrix $\mathop{p}\nolimits$ so that
$0<\mathop{p}\nolimits(n,n)<1$ (state $n$ is not absorbing and has a self-
loop). Eliminating loop $n$ results in a Markov chain
$M^{\prime}=(V^{\prime},\mathop{p}\nolimits^{\prime})$ with $V^{\prime}=V$
where for any edge from state $i\neq n$ to $j$, the probability, reward, and
duration are as in $M$. For edges going out of state $n$ they are
$\mathop{p}\nolimits^{\prime}(n,n)=\mathop{r}\nolimits^{\prime}(n,n)=\mathop{d}\nolimits^{\prime}(n,n)=0$
and for all $j\neq n$,

$\displaystyle\mathop{p}\nolimits^{\prime}(n,j)$
$\displaystyle~{}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}~{}\frac{\mathop{p}\nolimits(n,j)}{1-\mathop{p}\nolimits(n,n)}$
$\displaystyle\mathop{r}\nolimits^{\prime}(n,j)$
$\displaystyle~{}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}~{}\frac{1}{1-\mathop{p}\nolimits(n,n)}\mathop{r}\nolimits(n,n)+\frac{\mathop{p}\nolimits(n,j)}{1-\mathop{p}\nolimits(n,n)}\mathop{r}\nolimits(n,j)$
$\displaystyle\mathop{d}\nolimits^{\prime}(n,j)$
$\displaystyle~{}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}~{}\frac{1}{1-\mathop{p}\nolimits(n,n)}\mathop{d}\nolimits(n,n)+\frac{\mathop{p}\nolimits(n,j)}{1-\mathop{p}\nolimits(n,n)}\mathop{d}\nolimits(n,j).$

The intuition behind this definition is that iterating the loop $n\to n$ and
then going to $j\neq n$ is replaced by a direct step that preserves the
probability of ending in that particular state $j$, as well as the expected
sum of rewards and durations on the way. Recall that the expected number of
times the loop is used is ${1}/{1-\mathop{p}\nolimits(n,n)}$.

###### Lemma 5.4.

Suppose $M^{\prime}$ results from $M$ by eliminating loop $n$. Then
${\mathbb{E}}^{M}_{s}\left[{{\mathop{MPR}}}\right]={\mathbb{E}}^{M^{\prime}}_{s}\left[{{\mathop{MPR}}}\right]$
for every state $s\leq n$ .

The two elimination operations can be used to determine mean-payoff ratio
values in finite Markov chains. Indeed, suppose we want to determine
${\mathbb{E}}^{M}_{s}\left[{{\mathop{MPR}}}\right]$. Exhaustively eliminating
all loops and states except $s$ results in a Markov chain $M^{\prime}$ where
every original CCS is collapsed into a single absorbing state. By Lemmas 5.2
and 5.4, the expected mean-payoff ratio of state $s$ is the same in $M$ and
$M^{\prime}$. Now, if $M^{\prime}$ contains only a single absorbing state $s$,
then trivially
${\mathbb{E}}^{M^{\prime}}_{s}\left[{{\mathop{MPR}}}\right]=\mathop{r}\nolimits^{\prime}(s,s)/\mathop{d}\nolimits^{\prime}(s,s)$.
Otherwise, if $s$ is the only transient state in $M^{\prime}$ then
${\mathbb{E}}^{M^{\prime}}_{s}\left[{{\mathop{MPR}}}\right]=\sum_{i\neq
s}\mathop{p}\nolimits^{\prime}(s,i)\left(\mathop{r}\nolimits^{\prime}(i,i)/\mathop{d}\nolimits^{\prime}(i,i)\right)$.

Notice that the number of elimination steps is at most $2{\left|V\right|}$. We
will implement this procedure symbolically in $\mathrm{FO}(\mathbb{R})$ in the
next section, and approximately, in Section 7.4, to prove our main results.

##  6\. Expressibility in $\mathrm{FO}(\mathbb{R})$

We fix a $k$-player game $G$, bounds ${\bf b}\in\mathbb{N}^{k}$ and let

$N\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}{\left|V\right|}\cdot{\left|S\right|}^{k}\cdot\prod_{i=1}^{k}{\bf
b}[i].$

We show how to express $\varepsilon$-Nash equilibria wrt $\mathcal{B}({{\bf
b}})$ (in the multiplayer case) and strategies that $\varepsilon$-achieve some
value $v$ wrt $\mathcal{B}({{\bf b}})$ (in the $2$-player zero-sum case) in
$\mathrm{FO}(\mathbb{R})$. The steps to do this are as follows. We will
elaborate on each step in subsequent paragraphs.

  1. (1)

We existentially guess a strategy profile (in the multiplayer case), or a
strategy for player $1$ (in the $2$-player, zero-sum case), such that the
probability distributions used in the strategies are encoded in the variables.

  2. (2)

For any player $i$, we have a formula that depends on variables encoding a
strategy profile, and the formula encodes the outcome for the player $i$ in
the Markov chain induced by the strategy profile.

  3. (3)

We encode that the strategies guessed in step $1$ satisfy the desired
criteria.

##### Step 1: Guessing strategies and strategy profiles

Encoding a strategy in $\mathcal{B}_{i}({\bf b})$ for any player $i$ (and thus
strategy profiles in $\mathcal{B}({{\bf b}})$), in $\mathrm{FO}(\mathbb{R})$
is straightforward. Indeed, a strategy in $\mathcal{B}_{i}({\bf b})$ consists
of an action function ${\sigma}_{\mathop{act}\nolimits}:M\times
S\rightarrow\mathbb{D}(A)$ and a memory update function
${\sigma}_{\mathop{up}\nolimits}:M\times S\rightarrow\mathbb{D}(M)$. For the
action function, we have for each signal, each memory state and each of the
player’s possible actions under that signal, a variable. Specifically, if the
actions with signal $s$ and memory $m$ are $a_{1},\dots,a_{{\left|A\right|}}$,
we have variables $q_{1}^{s,m,i},\dots,q_{{\left|A\right|}}^{s,m,i}$. To
express that they should form a probability distribution, we have inequalities
$0\leq q_{j}^{s,m,i}\leq 1$, for each $j\in\\{1,\dots,{\left|A\right|}\\}$ and
$\sum_{j=1}^{{\left|A\right|}}q_{j}^{s,m,i}=1$.

Similarly, for the memory update function ${\sigma}_{\mathop{up}\nolimits}$,
we just, for each signal $s$, each memory $m$, and each action vector $a$ in
that state have variables $b_{1}^{s,m,a,i},\dots,b_{{\bf b}[i]}^{s,m,a,i}$. To
express that they should form a probability distribution, we have inequalities
$0\leq b_{j}^{s,m,a,i}\leq 1$ for each $j\in\\{1,\dots,{\bf b}[i]\\}$ and
$\sum_{j=1}^{{\bf b}[i]}b_{j}^{s,m,a,i}=1$. This gives us the following lemma.

###### Lemma 6.1.

For any $k$-player game $G$ and $i\leq k$, one can construct a
$\mathrm{FO}(\mathbb{R})$ formula $\text{Strat}_{i}({\bf x_{i}})$, with $|{\bf
x_{i}}|=({\left|S\right|}\cdot{\bf b}[i])({\left|A\right|}+{\bf b}[i])$
variables, such that there is a one-to-one correspondence between satisfying
assignments of ${\bf x_{i}}$ and strategies in $\mathcal{B}_{i}({\bf b})$ for
player $i$.

##### Step 2: Evaluating the induced Markov chain

Once the strategy profile is fixed, we obtain an induced Markov chain. The
following lemma shows that there is an $\mathrm{FO}(\mathbb{R})$ formula that
uses variables to identify a strategy profile and encodes the value obtained
by the strategy profile by encoding the loop and state elimination procedure
from Section 5. The proof, showing how this formula is constructed is in
Appendix B. In essence, the loop/state elimination procedures are iteratively
implemented in FO(R) by introducing lots (but polynomially many) existentially
quantified variables to represent intermediate Markov chains in the
reductions.

###### Lemma 6.2.

For any $k$-player game $G$, and a player $i$, one can construct a formula
$\text{Val}_{i}({\bf x}_{1},\dots,{\bf x}_{k},y)$, such that ${\bf x}_{j}$
encodes strategy $\sigma_{j}$ of a strategy profile
$\sigma\in\mathcal{B}({{\bf b}})$, and the formula uses a set of Boolean
combination of $100N^{3}+40N$ polynomials with at most $8N^{3}+3N$ variables,
each of degree at most $2k$, and coefficients coming from $G$ and $y$ encode
the outcome of $\sigma$ for player $i$.

##### Step 3: Finding $\varepsilon$-achieving strategy/$\varepsilon$-Nash
equilibria

The last step requires unfolding the definition of $\varepsilon$-achieving
strategy/$\varepsilon$-Nash equilibria in a formula. We first do this for the
$2$-player zero-sum case where we are interested in strategies that
$\varepsilon$-achieves a given value $v$, for $\varepsilon\geq 0$. The formula
guesses the $\varepsilon$-achieving strategy, and checks for each of the
opponent’s strategies, that the outcome is $\geq v-\varepsilon$.

$\begin{split}\exists{\bf x_{1}}\forall{\bf x_{2}}\forall
y.\quad&\text{Strat}_{1}({\bf x_{1}})\land\text{Strat}_{2}({\bf
x_{2}})\land\text{Val}_{1}({\bf x_{1}},{\bf x_{2}},y)\\\ &\implies(y\geq
v-\varepsilon)\end{split}$

Note that one can use existentially quantified auxiliary variables to
implement repeated squaring and thereby encode the (binary) numbers $v$ and
$\varepsilon$ succinctly.

For the case of $\varepsilon$-Nash equilibria wrt $\mathcal{B}({{\bf b}})$, we
guess the strategy profile $\sigma$ and check against all possible deviations
by a single player.

$\begin{split}\exists&{\bf x_{1}},\dots,{\bf
x_{k}},y_{1},\dots,y_{k}\forall{\bf x^{\prime}_{1}},\dots,{\bf
x^{\prime}_{k}},y^{\prime}.\\\ &\left(\bigwedge_{i=1}^{k}\text{Strat}_{i}({\bf
x_{i}})\right)\wedge\left(\bigwedge_{i=1}^{k}\text{Val}_{i}({\bf
x_{1}},\dots,{\bf x_{k}},y_{i})\right)\wedge\\\
&\bigwedge_{j=1}^{k}\left(\text{Strat}_{j}({\bf
x^{\prime}_{j}})\implies(\text{Val}_{j}({\bf x_{1}},\dots,{\bf
x^{\prime}_{j}},\dots,{\bf x_{k}},y^{\prime})\wedge y_{j}+\varepsilon\geq
y^{\prime})\right)\end{split}$

###### Lemma 6.3.

Given a $k$-player game, and $v$, $\varepsilon\geq 0$, one can construct an
$\mathrm{FO}(\mathbb{R})$ formula that encodes a strategy that
$\varepsilon$-achieves $v$/ is a $\varepsilon$-Nash equilibrium. Furthermore,
the formula uses at most $(k+1)+k(|S|\prod_{i=1}^{k}{\bf
b}[i])(|A|+\sum_{i=1}^{k}{\bf b}[i])+8N^{3}+3N$ variables, and at most
$(100N^{3}+40N)2k$ polynomials.

The terms in the number of variables correspond to variables for guessing
values, strategies and the variables used to describe the values in Lemma 6.2.

###### Proof of Theorem 3.2.

From Lemma 6.3, we can express strategies encoding an $\varepsilon$-Nash
equilibrium using an $\mathrm{FO}(\mathbb{R})$ formula. Note that this uses
$2$ alternations of quantifiers. Checking if a formula with bounded quantifier
alternation is in the first-order theory of the reals can be done in
${\mathsf{PSPACE}}$ as shown by Basu et al.(Basu et al., 2006, Remark 13.10).
∎

The following will be used later applied to the formulae provided by Lemma
6.3. For the proof, we assume familiarity with $\mathrm{FO}(\mathbb{R})$, the
first order theory of the reals (Basu et al., 2006).

###### Lemma 6.4.

Consider a satisfiable $\mathrm{FO}(\mathbb{R})$ expression,

$\exists x_{1}^{1},\dots,x_{n_{1}}^{1}\forall
x_{1}^{2},\dots,x_{n_{2}}^{2}\exists\dots
x_{1}^{k}\dots,x_{n_{k}}^{k}.\varphi(x_{1}^{1},\dots,x_{n_{1}}^{1},x_{1}^{2}\dots,x_{n_{k}}^{k})$

where $\varphi$ consists of boolean combinations over $s$ polynomial
inequalities, where each polynomial is of degree at most $d$, has integer
coefficients and the bit-size of each coefficient is at most $\tau$. Then
there exists $x_{1}^{\prime},\dots,x_{n_{1}}^{\prime}$, such that,

$\forall x_{1}^{2},\dots,x_{n_{2}}^{2}\exists\dots\exists
x_{1}^{k}\dots,x_{n_{k}}^{k}.\varphi(x_{1}^{\prime},\dots,x_{n_{1}}^{\prime},x_{1}^{2}\dots,x_{n_{k}}^{k})$

is satisfiable and such that for each $i$, either
$2^{-\tau(2d)^{\prod_{i=1}^{k}O(n_{i})}}\leq|x_{i}^{\prime}|\leq
2^{\tau(2d)^{\prod_{i=1}^{k}O(n_{i})}}$ or $x_{i}^{\prime}=0$.

###### Proof.

We apply (Basu et al., 2006, Thm 14.16) to

$\displaystyle\phi(x_{1}^{1},\dots,x_{n_{1}}^{1})\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}$
$\displaystyle\forall x_{1}^{2},\dots,x_{n_{2}}^{2}$
$\displaystyle\exists\dots
x_{1}^{k}\dots,x_{n_{k}}^{k}:\varphi(x_{1}^{1},\dots,x_{n_{1}}^{1},x_{1}^{2}\dots,x_{n_{k}}^{k})$

which gives us a quantifier-free expression of $\phi$. This expression of
$\phi$ uses polynomials of degree at most
$d^{\prime}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}d^{\prod_{i=2}^{k}O(n_{i})}$
with integer coefficients, each of bit-size at most
$\tau^{\prime}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\tau
d^{\prod_{i=1}^{k}O(n_{i})}$. We then apply (Basu et al., 2006, Thm 13.10) to
$\phi$, giving us a “univariate representation” of each of the numbers we will
use for $x_{i}^{\prime}$ (the theorem itself only states that we get
approximations, but the complexity analysis of the algorithm states that it is
equally fast to get exact solutions, using some additional steps). For each
$i$, this univariate representation for $x_{i}$ consists of a fraction of two
polynomials $p_{i}(x)/q(x)$ and an additional polynomial $f$ ($q$ and $f$ are
coprime). The number $x_{i}$ is then $p_{i}(t)/q(t)$ where $t$ is a root of
$f$. These polynomials each is of degree at most
$d^{\prime\prime}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}(2d^{\prime}+6)^{n_{1}}\leq(2d)^{\prod_{i=1}^{k}O(n_{i})}$
(we get to ignore the $6$ because of the $O$’s. We can’t ignore the 2 in case
$d$ was 1) with integer coefficients of bit-size at most
$\tau^{\prime\prime}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\tau
d^{\prod_{i=1}^{k}O(n_{i})}$. For each $i$, we apply (Basu et al., 2006, Lem.
15) to $f$, $p_{i}$ and $q$, giving us a square-free univariate polynomial
$p^{\prime}_{i}$ such that $p^{\prime}_{i}(x_{i})=0$. This polynomial has
degree at most
$d^{\prime\prime\prime}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}2d^{\prime\prime}=(2d)^{\prod_{i=1}^{k}O(n_{i})}$
and the bitsize representation of the integer coefficients is at most
$\tau^{\prime\prime\prime}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}2d^{\prime\prime}\tau^{\prime\prime}+7d^{\prime\prime}\log
d^{\prime\prime}=\tau(2d)^{\prod_{i=1}^{k}O(n_{i})}$.

For any univariate polynomial
$p(x)=a_{n}x^{n-1}+a_{n-1}x^{n-2}+\dots+a_{1}x+a_{0}$, then $r\neq 0$ is a
root iff $1/r\neq 0$ is a root of
$a_{n}1/(x^{n-1})+a_{n-1}(1/x^{n-2})+\dots+a_{1}1/x+a_{0}$ or equally
$p^{\prime}(x)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}a_{n}+a_{n-1}x+\dots+a_{1}x^{n-2}+a_{0}x^{n-1}$.
Therefore, if $U$ is an upper bound on the absolute largest root in $p$, then
$1/U$ is a lower bound for how small the absolute smallest non-zero root can
be in $p^{\prime}$. We can bound $U\leq
1+\max\left({\left|\frac{a_{n-1}}{a_{n}}\right|},{\left|\frac{a_{n-2}}{a_{n}}\right|},\dots\left|\frac{a_{0}}{a_{n}}\right|\right)$
(Cauchy, 1828) and so get that
$2^{-\tau^{\prime\prime\prime}}\leq|x_{i}^{\prime}|\leq
2^{\tau^{\prime\prime\prime}}$, because the largest integer represented with
$x$ bits is $2^{x}-1$. ∎

##  7\. Approximation Algorithms

In this section, we present the proof of Theorem 3.3. Our approach is to
repeat the steps leading to $\mathrm{FO}(\mathbb{R})$ representations in the
previous section but use floating point representations and associated lossy
arithmetic. To do this, we need two ingredients: (1) we need to guess
candidate profiles in polynomial space; and (2) we need to compute
approximations of the mean-payoff values in the induced Markov chains in
polynomial time.

We focus first on the existence of small candidate profiles.

###  7.1. Floating point representations

###### Definition 7.1.

A strategy profile $\sigma=(\sigma[j])_{j\leq k}\in\mathcal{B}({{\bf b}})$ is
_$u$ -bit representable_ if all its distributions (selecting mixed actions and
memory updates for all players, memory modes and signals) are in
$\mathbb{P}(u)$. The profile $\sigma$ is _represented_ in $u$-bits if it is
$u$-bit representable and all exponents are written in binary using $u$ many
bits.

Let

$\displaystyle p(\sigma,{\bf m},s,{\bf m^{\prime}},{\bf
a})\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\prod_{j=1}^{k}$
$\displaystyle{\sigma[j]}_{\mathop{act}\nolimits}({\bf m}[j],s[j])({\bf
a}[j])\cdot$ $\displaystyle{\sigma[j]}_{\mathop{up}\nolimits}({\bf
m}[j],s[j])(m^{\prime}[j])$

denote the probability of that starting with memory states ${\bf m}$ and
having previously received signal vector $s$, the players jointly pick the
action profile ${\bf a}$, and update the memory vector to ${\bf m^{\prime}}$.

For any two profiles $\sigma,\sigma^{\prime}\in\mathcal{B}({{\bf b}})$, the
_distance_ between the strategy profiles is

$\mathop{dist}(\sigma,\sigma^{\prime})~{}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}~{}\max_{{\bf
m},s,{\bf m^{\prime}},{\bf a}}\mathop{dist}(p(\sigma,{\bf m},s,{\bf
m^{\prime}}{\bf a}),p(\sigma^{\prime},{\bf m},s,{\bf m^{\prime}},{\bf a})).\ $

###  7.2. Polynomial witnesses

We now show the existence of suitably small profiles to witness approximate
equilibria and zero-sum values. Our claim that small profiles exist is stated
in Lemma 7.5. This relies on the following two lemmas, proofs of which can be
found in the appendix.

For the remainder of the section, fix a $k$-player game $G$ with $n$ states
and where $C\in\mathbb{N}$ is the largest absolute value of any reward. Also,
fix some vector ${\bf b}\in\mathbb{N}^{k}$ of memory bounds. Let
$N\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}n\cdot|S|^{k}\cdot\prod_{j}{\bf
b}[j]$.

The first lemma states that if there are witnesses at all, then there are also
ones where all probabilities are at most double exponentially small.

###### Lemma 7.2 (Lower-bounded probabilities).

There is $u_{0}\in\mathbb{N}$, polynomial in the size of the game and
$\varepsilon$, so that the following is true for all $u\geq u_{0}$.

If there exists a profile $\sigma\in\mathcal{B}({{\bf b}})$ that witnesses
values ${\bf v}\in\mathbb{R}^{k}$ then there is such a profile $\sigma$ where
all probabilities (for any signal, action and memory mode) are at least
${1}/{2^{2^{u}}}$.

###### Proof.

By Lemmas 6.3 and 6.4. ∎

Secondly, we show that small perturbations of probabilities only lead to small
changes in (mean-payoff) values for all players.

###### Lemma 7.3 (small perturbations).

Consider any two profiles $\sigma,\sigma^{\prime}\in\mathcal{B}({{\bf b}})$
and let ${\bf v},{\bf v^{\prime}}\in\mathbb{R}^{k}$ denote the values they
witness.

If $\mathop{dist}(\sigma,\sigma^{\prime})<(4N)^{-1}$ then ${\bf
v^{\prime}}\in[{\bf v}-\gamma,{\bf v}+\gamma]$, where $\gamma=9\cdot
N\cdot\mathop{dist}(\sigma,\sigma^{\prime})C$.

###### Proof.

After fixing the game’s strategies to be $\sigma$ it turns into a Markov chain
$M$ and similar let $M^{\prime}$ be the Markov chain obtained by fixing the
strategies to be $\sigma^{\prime}$. The state space of $M$ and $M^{\prime}$ is
the product of the states of the original game, the memory states for each
player and the set of signals vectors, i.e, at most $N$ states. Let
$\overline{r}$ be the reward function in $M$ and let $\overline{r}^{\prime}$
be the one in $M^{\prime}$.

We will apply (Solan, 2003, Thm. 5).This applies generally to two-player,
zero-sum concurrent limit-average game s and bounds the change in (limit
average) values if one changes the reward function additively and the
transition function multiplicatively. Here, we apply it to the special case of
Markov chains. This is because we are interested in what happens if we change
the players strategies slightly (which corresponds to changing the transition
and cost functions slightly as we will see). The following claim states that
the reward functions and transition functions differ additively and
multiplicatively respectively in the two chains.

###### Claim 7.4.

Let $(v,{\bf m},s)\to(v^{\prime},{\bf m^{\prime}},s^{\prime})$ be an edge of
the Markov chains $M$ and $M^{\prime}$.

  * •

The difference in rewards in the edge $(v,{\bf m},s)\to(v^{\prime},{\bf
m^{\prime}},s^{\prime})$ in $M$ and $M^{\prime}$ is at most
$C\cdot\delta(\sigma,\sigma^{\prime})$.

  * •

Let $P$ and $P^{\prime}$ be the probability to go from $(v,{\bf m},s)$ to
$(v^{\prime},{\bf m^{\prime}},s^{\prime})$ in $M$ and $M^{\prime}$
respectively. Then, $\delta(P,P^{\prime})\leq\delta(\sigma,\sigma^{\prime})$.

The proof of 7.4 can be found in Section C.1.

We can now apply (Solan, 2003, Thm 5), using the claim above and that the
maximum absolute reward in $M$ and $M^{\prime}$ are bounded by $C$, and the
number of states in $M$ and $M^{\prime}$ are $N$. We get that the value of $M$
differs from the value of $M^{\prime}$ by at most
$Y\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\frac{4\cdot
N\cdot\delta(\sigma,\sigma^{\prime})}{1-2\cdot
N\cdot\delta(\sigma,\sigma^{\prime})}C+C\cdot\delta(\sigma,\sigma^{\prime})$.
Since we assume that $\delta(\sigma,\sigma^{\prime})<(4N)^{-1}$, we have that
$Y<9\cdot N\cdot\delta(\sigma,\sigma^{\prime})C$. ∎

###### Lemma 7.5 (small candidates).

There exists $u\in\mathbb{N}$, polynomial in the size of the game and
$\varepsilon$, so that the following is true.

  1. (1)

If there exists a $\varepsilon$-NE $\sigma$ wrt $\mathcal{B}({{\bf b}})$ then
there exists a $2\varepsilon$-NE $\sigma^{\prime}$ wrt $\mathcal{B}({{\bf
b}})$ that is $u$-bit representable .

  2. (2)

If there exists a strategy $\sigma$ for player $j$ that $\varepsilon$-achieves
${v}$ wrt $\mathcal{B}({{\bf b}})$ then there exists a strategy
$\sigma^{\prime}$ for player $j$ that $2\varepsilon$-achieves ${v}$ wrt
$\mathcal{B}({{\bf b}})$ and is $u$-bit representable.

###### Proof.

By Lemmas 7.2 and 7.3. ∎

###### Lemma 7.6 (Best response).

Given a game $G$, an $\varepsilon>0$, an $u$-bit represented strategy profile
and a player $i$, there is a $u^{\prime}$ polynomial in the size of the game,
$\varepsilon$ and $u$, and a $u^{\prime}$-bit represented strategy
$\sigma^{\prime}$ for player $i$ that $\varepsilon$-achieves $v$ wrt
$\mathcal{B}({{\bf b}})$ if there is a strategy for player $i$ that witnesses
value $v$ wrt $\mathcal{B}({{\bf b}})$

###### Proof.

For a strategy $\sigma_{i}$ for player $i$, let

$\sigma[\sigma_{i}]=(\sigma[1],\sigma[2],\dots,\sigma[i-1],\sigma_{i},\sigma[i+1],\dots,\sigma[k]).$

Given a $u$-bit represented strategy profile $\sigma$ we can write a
$\mathrm{FO}(\mathbb{R})$ expression for the strategy $\sigma^{*}$ that
maximizes the outcome for player $i$ of playing $\sigma[\sigma^{*}]$ in $G$.

Specifically, that expression could be

$\displaystyle\exists\sigma^{*},y^{*}\forall\sigma^{\prime\prime},y^{\prime\prime}:\text{Strat}_{i}(\sigma^{*})\wedge\text{Val}_{i}(\sigma[\sigma^{*}],y^{*})\wedge$
$\displaystyle((\text{Strat}_{i}(\sigma^{\prime\prime})\wedge\text{Val}_{i}(\sigma[\sigma^{\prime}],y^{\prime\prime}))\Rightarrow
y^{*}\geq y^{\prime\prime}),$

assuming we can express the strategy profile $\sigma$ in a polynomial-sized
$\mathrm{FO}(\mathbb{R})$ expression. We do that as follows: For each
probability $p$ used by $\sigma$, it is expressed in $u$-bit representation,
$x\cdot 2^{i}$, where $x$ and $i$ are a $u$-bit numbers (and $i$ is not
positive, because it is a probability). We can simply write $x$ down, but we
need to be more careful with $2^{i}$. We can write down the expressions

$v_{1}=1/2\wedge v_{2}=v_{1}\cdot v_{1}\wedge v_{3}=v_{2}\cdot
v_{2}\wedge\dots\wedge v_{u}=v_{u-1}\cdot v_{u-1}$

Observe that $v_{\ell}=2^{-2^{\ell}}$. Let $i_{j}$ be the $j$-th bit set to 1
in the binary expression of $i$ (clearly $j\leq u$) and there are $K$ such
bits set for some $K$. We then see that

$2^{i}=v_{i_{1}}\cdot v_{i_{2}}\cdot\dots\cdot v_{i_{K}}.$

We can therefore write $p$ as $x\cdot v_{i_{1}}\cdot v_{i_{2}}\cdot\dots\cdot
v_{i_{K}}$ (using another $K$ variables, we can also make these products
binary) and we get the full $\mathrm{FO}(\mathbb{R})$ expression by simply
doing this for each of the probabilities.

Similar to Lemma 7.2, this lets us lower bound the probabilities used for
strategy $\sigma^{*}$, by $1/2^{2^{u^{\prime}}}$ for some polynomial
$u^{\prime}$. We can also apply Lemma 7.3, similar to Lemma 7.5, from which it
follows that there is a $u^{\prime}$-bit representation of a strategy
$\sigma^{\prime}$ that $\varepsilon$-achieves $v$. ∎

###  7.3. Computing Approximations for Markov chains

The second ingredient in proving Theorem 3.3 is to approximate mean-payoff
values for Markov chains in polynomial time.

Recall that fixing a strategy profile $\sigma\in\mathcal{B}({{\bf b}})$ for a
game yields a finite Markov chain where the transition probabilities encode
the players’ choices and edges dictate the stepwise rewards for all players.
We aim to approximate the expected mean-payoff
${\mathbb{E}}^{\sigma}_{v_{0},s_{0}}\left[{\underline{\mathop{MP}}[i]}\right]$
for a given player $i\leq k$, initial state $v_{0}$ and signal $s_{0}$.

Towards this, consider a Markov chain as discussed in Section 5, with states
$\\{1,\dots,n\\}$, and where $\mathop{p}\nolimits(i,j)$,
$\mathop{r}\nolimits(i,j)\in\mathbb{R}$ and
$\mathop{d}\nolimits(i,j)\in\mathbb{R}$ denote the probability, reward (for
the chosen player), and duration of an edge $i\to j$. Recall that it suffices
to compute the expected mean-payoff ratio (see Equation 1) as initially, the
duration of every step is $1$.

We propose an algorithm that exhaustively applies the loop and state-
elimination procedures of Definitions 5.1 and 5.3, which is correct by Lemmas
5.2 and 5.4. However, to deal with the necessarily double-exponentially small
values in input and output Markov chains, we replace the precise arithmetic
operands by approximate ones that use floating point representations with
polynomial many bits. We show that the error this introduces can be bounded
polynomially.

###### Definition 7.7.

A Markov chain is _represented in $u$-bits_ if all probabilities, rewards and
durations are in $\mathbb{Q}(u)$ and given in $u$-bit floating point
representation.

In particular, all distributions $(\mathop{p}\nolimits_{ij})_{j\in V}$ of a
state $i$ is in $\mathbb{P}(u)$ given in $u$-bit approximately normalised
representation using $u$-bit floating point numbers.

We now state the bounds on approximate variants of state and loop
eliminations. Let $\oplus^{u},\oslash^{u},\otimes^{u}$ be the $u$-bit finite
precision variant of addition, division and multiplication, respectively.
These map values $\mathbb{Q}(u)^{2}$ to $\mathbb{Q}(u)$ by rounding down the
result of the corresponding arithmetic operation to the nearest value in
$\mathbb{Q}(u)$. We drop the superscript $u$ for readability.

###### Lemma 7.8 (State Elimination).

There is a polynomial $\delta_{1}$ so that the following holds for all
$u\in\mathbb{N}$.

Let $M=(V,\mathop{p}\nolimits,\mathop{r}\nolimits,\mathop{d}\nolimits)$ and
$M^{\prime}=(V,\mathop{p}\nolimits^{\prime},\mathop{r}\nolimits^{\prime},\mathop{d}\nolimits^{\prime})$
be Markov chains represented in $u$-bits so that $M^{\prime}$ results from $M$
by eliminating a transient state $n$ as in Definition 5.3 but using $u$-bit
floating point arithmetic. That is, for all $i,j\neq n$,

$\displaystyle\mathop{p}\nolimits^{\prime}(i,j)$
$\displaystyle=\mathop{p}\nolimits(i,j)\oplus(\mathop{p}\nolimits(j,n)\otimes\mathop{p}\nolimits(n,j))$
$\displaystyle\mathop{r}\nolimits^{\prime}(i,j)$
$\displaystyle=(\mathop{p}\nolimits(i,j)\otimes\mathop{r}\nolimits(i,j))$
$\displaystyle\quad\oplus((\mathop{p}\nolimits(i,n)\otimes\mathop{p}\nolimits(n,j))\otimes(\mathop{r}\nolimits(i,n)\oplus\mathop{r}\nolimits(n,j)))$
$\displaystyle\mathop{d}\nolimits^{\prime}(i,j)$
$\displaystyle=(\mathop{p}\nolimits(i,j)\otimes\mathop{d}\nolimits(i,j))$
$\displaystyle\quad\oplus((\mathop{p}\nolimits(i,n)\otimes\mathop{p}\nolimits(n,j))\otimes(\mathop{d}\nolimits(i,n)\oplus\mathop{d}\nolimits(n,j)))$

Then,

  1. (1)

The smallest (negative) exponent among all floating point numbers in
${M^{\prime}}$ is at most one smaller than that in $M$.

  2. (2)

Then
${\left|{\mathbb{E}}^{M}_{1}\left[{{\mathop{MPR}}}\right]-{\mathbb{E}}^{M^{\prime}}_{1}\left[{{\mathop{MPR}}}\right]\right|}\leq\delta_{1}2^{-u}$.

###### Lemma 7.9 (Loop Elimination).

There is a polynomial $\delta_{2}$ so that the following holds for all
$u\in\mathbb{N}$.

Let $M=(V,\mathop{p}\nolimits,\mathop{r}\nolimits,\mathop{d}\nolimits)$ and
$M^{\prime}=(V,\mathop{p}\nolimits^{\prime},\mathop{r}\nolimits^{\prime},\mathop{d}\nolimits^{\prime})$
be Markov chains represented in $u$-bits so that $M^{\prime}$ results from $M$
by eliminating a loop in state $n$ as in Definition 5.3 but using $u$-bit
floating point arithmetic. That is, $\mathop{p}\nolimits^{\prime}(n,n)=0$; and
for all $i,j\neq n$ let
$\mathop{p}\nolimits^{\prime}(i,j)=\mathop{p}\nolimits(i,j)$,
$\mathop{r}\nolimits^{\prime}(i,j)=\mathop{r}\nolimits(i,j)$,
$\mathop{d}\nolimits^{\prime}(i,j)=\mathop{d}\nolimits(i,j)$ and

$\displaystyle\mathop{p}\nolimits^{\prime}(n,j)$
$\displaystyle=\mathop{p}\nolimits(n,j)\oslash(\oplus_{k\neq
i}\mathop{p}\nolimits(n,k))$ $\displaystyle\mathop{r}\nolimits^{\prime}(n,j)$
$\displaystyle=((\mathop{r}\nolimits(n,j)\otimes\mathop{p}\nolimits(n,j))\oplus({\mathop{p}\nolimits}_{ii}\otimes\mathop{r}\nolimits_{ii}))$
$\displaystyle\quad\oslash(\oplus_{k\neq i}\mathop{p}\nolimits(n,k))$
$\displaystyle\mathop{d}\nolimits^{\prime}(n,j)$
$\displaystyle=((\mathop{d}\nolimits(n,j)\otimes\mathop{p}\nolimits(n,j))\oplus({\mathop{p}\nolimits}(n,n)\otimes\mathop{d}\nolimits(n,n)))$
$\displaystyle\quad\oslash(\oplus_{k\neq i}\mathop{p}\nolimits(n,k)).$

Then,

  1. (1)

The smallest (negative) exponent among all floating point numbers in
${M^{\prime}}$ is at most one smaller than that in $M$.

  2. (2)

Then
${\left|{\mathbb{E}}^{M}_{1}\left[{{\mathop{MPR}}}\right]-{\mathbb{E}}^{M^{\prime}}_{1}\left[{{\mathop{MPR}}}\right]\right|}\leq\delta_{2}2^{-u}$.

We now show that one can approximate the mean-payoff ratio in polynomial time
and sufficiently closely.

###### Lemma 7.10.

There is a polynomial time algorithm for the following problem. Given a Markov
chain with $n$ states represented in $u$-bits and error $\varepsilon\in(0,1)$
in binary.

Output a value in $[v,v+\varepsilon)$, where
$v={\mathbb{E}}^{M}_{1}\left[{{\mathop{MPR}}}\right]$ is the expected mean-
payoff value from the initial state of $M$.

###### Proof.

W.l.o.g., we can assume that $u\geq 1000n^{2}$ and
$\varepsilon>n(\delta_{1}+\delta_{2})2^{-u}$. Otherwise, one can increase $u$
to $\log_{2}((\delta_{1}+\delta_{2})n)\cdot\ell$, where $\ell$ is the number
of bits used in the denominator of $\varepsilon$, i.e, $\varepsilon\geq
1/2^{\ell}$. Since all the constants used are polynomial in the size of the
input, so will be $u$.

The algorithm will alternate between

  1. (1)

exhaustively applying Lemma 7.9 to remove self-loops in all transient states,
and

  2. (2)

applying Lemma 7.8 to remove a transient state $n\neq 1$.

This will result in a Markov chain $M^{\prime}$ where each original CCS is
collapsed into a single absorbing state. Now, if $M^{\prime}$ contains only a
single absorbing state $s$, then
${\mathbb{E}}^{M^{\prime}}_{1}\left[{{\mathop{MPR}}}\right]=\mathop{r}\nolimits^{\prime}(s,s)/\mathop{d}\nolimits^{\prime}(s,s)$,
so we output
$\mathop{r}\nolimits^{\prime}(s,s)\oslash\mathop{d}\nolimits^{\prime}(s,s)$.
Otherwise, $1$ is the only transient state in $M^{\prime}$ and we output
$\oplus_{i\neq
1}\mathop{p}\nolimits^{\prime}(1,i)\left(\mathop{r}\nolimits^{\prime}(i,i)\oslash\mathop{d}\nolimits^{\prime}(i,i)\right)$.

Notice that at most $n-1$ many transient states can be removed, which bounds
the number of times we invoke Lemma 7.8. Similarly, in between removing
states, step (1) results in at most $n$ many applications of Lemma 7.9.

Therefore, by Lemma 7.9(1) and Lemma 7.8(1), the largest exponent in any
floating point representation of $M^{\prime}$ has at most increased by
$n(n+1)$ compared to $M$. Moreover, the total error introduced by these
operations is at most

$\displaystyle{\left|{\mathbb{E}}^{M}_{1}\left[{{\mathop{MPR}}}\right]-{\mathbb{E}}^{M^{\prime}}_{1}\left[{{\mathop{MPR}}}\right]\right|}$
$\displaystyle\leq n(\delta_{1}+\delta_{2})2^{-u})$

by Lemma 7.9(2) and Lemma 7.8(2).

By plugging in the value of $u$, we get the error is at most $2^{-\ell}$,
therefore at most $\varepsilon$. ∎

###  7.4. Proof of Theorem 3.3

We are now ready to prove Theorem 3.3.

See 3.3

We therefore want to make two algorithms in ${\mathsf{FNP}}^{\mathsf{NP}}$.
Because the algorithms are quite similar, we state them both first before
proving correctness.

##### First algorithm (for (1))

First, for (1), we want to find a $3\varepsilon$-Nash equilibrium wrt
$\mathcal{B}({{\bf b}})$ (if an $\varepsilon$-Nash equilibrium wrt
$\mathcal{B}({{\bf b}})$ exists). To do so, we use an oracle that solves the
following question: Given a game $G$, $\varepsilon>0$ and an $u$-bit
represented strategy profile $\sigma$, guess an $u^{\prime}$-bit represented
strategy profile $\sigma^{\prime}$. For each player $i$, construct the induced
Markov chain $MC_{1}^{i}$ for $\sigma$ and the induced Markov chain
$MC_{2}^{i}$ for
$(\sigma[1],\dots,\sigma[i-1],\sigma^{\prime}[i],\sigma[i+1],\dots,\sigma[k])$,
each with rewards for player $i$. Apply the algorithm from Lemma 7.10, with
the value of $\varepsilon$ being $\varepsilon/3$ and $u$ being $u^{\prime}$,
to each Markov chain, giving approximated values $v_{1}^{i}$ and $v_{2}^{i}$
respectively. If $v_{2}^{i}-v_{1}^{i}>\frac{7}{3}\varepsilon$, then return
“yes”. If “yes” has not been returned for any player, return “no”.

The ${\mathsf{FNP}}^{\mathsf{NP}}$algorithm (for (1)) that uses the oracle is
then as follows: Given a game $G$ and an $\varepsilon>0$, guess an $u$-bit
represented strategy profile $\sigma$ and apply the oracle with $G$,
$\varepsilon$ and $\sigma$. If the oracle returns “yes”, return “no” and
otherwise return $\sigma$.

##### Second algorithm (for (2))

Next, for (2), given a value $v$, we want to find a strategy that
$3\varepsilon$-achieves $v$ wrt $\mathcal{B}({{\bf b}})$ (if a strategy that
$\varepsilon$-achieves $v$ wrt $\mathcal{B}({{\bf b}})$ exists). To do so, we
use an oracle that solves the following question: Given a game $G$,
$\varepsilon>0$ and an $u$-bit represented strategy $\sigma$ for player $1$,
guess an $u^{\prime}$-bit represented strategy $\sigma^{\prime}$ for player 2.
Apply the algorithm from Lemma 7.10, with $\varepsilon$ being $\varepsilon/3$
and $u$ being $u^{\prime}$, to the Markov chain induced by
$(\sigma,\sigma^{\prime})$, given an approximated value $v^{\prime}$. If
$v-v^{\prime}>\frac{7}{3}\varepsilon$, then return “yes”, otherwise, return
“no”.

The ${\mathsf{FNP}}^{\mathsf{NP}}$algorithm (for (2)) that uses the oracle is
then as follows: Given a game $G$ and an $\varepsilon>0$, guess an $u$-bit
represented strategy $\sigma$ and apply the oracle with $G$, $\varepsilon$ and
$\sigma$. If the oracle returns “yes”, return “no” and otherwise return
$\sigma$.

##### Running time and correctness of the algorithms

Because the running time of the algorithm from Lemma 7.10 is polynomial and
every $u$-bit represented strategy is also of polynomial size, the oracles are
in $\mathsf{NP}$ and the algorithms are in ${\mathsf{FNP}}^{\mathsf{NP}}$.

We thus just need to argue that the algorithms are correct.

###### Lemma 7.11.

We have the following:

  1. (1)

The first algorithm (for (1)) returns either “no” or a $3\varepsilon$-Nash
equilibrium wrt $\mathcal{B}({{\bf b}})$. Also, if an $\varepsilon$-Nash
equilibrium wrt $\mathcal{B}({{\bf b}})$ exists it will not return “no”.

  2. (2)

The second algorithm (for (2)) returns either “no” or a strategy that
$3\varepsilon$-achieve $v$ wrt $\mathcal{B}({{\bf b}})$. Also, if a strategy
that $\varepsilon$-achieve $v$ wrt $\mathcal{B}({{\bf b}})$ exists it will not
return “no”.

###### Proof.

First for (1): We start by arguing that if the algorithm guessed an $u$-bit
representable $2\varepsilon$-Nash equilibrium wrt $\mathcal{B}({{\bf b}})$,
$\sigma$, which exists if an $\varepsilon$-Nash equilibrium wrt
$\mathcal{B}({{\bf b}})$ exists by Lemma 7.5, then the oracle will necessarily
return “no” and therefore such a strategy profile can be returned. Consider
first that if we use the real value of $MC_{1}^{i}$, then it must be at least
the real value of $MC_{2}^{i}-2\varepsilon$, because $\sigma$ is a
$2\varepsilon$-Nash equilibrium. The approximated value of $MC_{1}^{i}$ is at
most $\varepsilon/3$ smaller than the real value. Similar for $MC_{2}^{i}$.
This means that the approximated value of $MC_{1}^{i}$ must be at least the
approximated value of $MC_{2}^{i}-\frac{7}{3}\varepsilon$ and therefore the
oracle will necessarily return “no”. Because at least one guess would result
in an output different from “no”, the algorithm must return some such value.

Next, consider that the algorithm guessed some $u$-bit representable strategy
profile $\sigma$, which was not a $3\varepsilon$-Nash equilibrium wrt
$\mathcal{B}({{\bf b}})$ and we will argue that the oracle will be able to
return “yes”. Let $v$ be the outcome of $\sigma$ for player $i$. By definition
of $3\varepsilon$-Nash equilibrium wrt $\mathcal{B}({{\bf b}})$, there must be
some player $i$ and strategy wrt $\mathcal{B}({{\bf b}})$,
$\sigma^{\prime\prime}$, for player $i$, so that value $v^{\prime\prime}$ of
the Markov chain induced by
$(\sigma[1],\dots,\sigma[i-1],\sigma^{\prime\prime},\sigma[i+1],\dots,\sigma[k])$
with rewards for player $i$ must be strictly greater than $v+3\varepsilon$. By
Lemma 7.6, applied with $\varepsilon$ being $\varepsilon/3$ we can then find
an $u^{\prime}$-bit representable strategy $\sigma^{\prime\prime\prime}$ so
that
$(\sigma[1],\dots,\sigma[i-1],\sigma^{\prime\prime\prime},\sigma[i+1],\dots,\sigma[k])$
with rewards for player $i$ must have a value strictly greater than
$v+\frac{8}{3}\varepsilon$. The oracle can then non-deterministically guess a
strategy profile in which $\sigma^{\prime}[i]=\sigma^{\prime\prime\prime}$,
the approximated values $v_{1}^{i}$ and $v_{2}^{i}$ would then be such that
$v_{2}^{i}-v_{1}^{i}>\frac{7}{3}\varepsilon$ (because each is at most
$\varepsilon/3$ smaller than the real value) and thus, the oracle will return
“yes”.

Next, we will argue that the algorithm for (2) is correct. The argument is
similar to the above argument but included for completeness. We start by
arguing that if the algorithm guessed a $u$-bit represented strategy $\sigma$
that $2\varepsilon$-achieves $v$ wrt $\mathcal{B}({{\bf b}})$ (which exists if
a strategy that $\varepsilon$-achieves $v$ wrt $\mathcal{B}({{\bf b}})$ exists
by Lemma 7.5), then the oracle will return “no” and therefore, the algorithm
can return such $\sigma$. Consider first that if we use the real value of the
induced Markov chain, then it must be at least $v-2\varepsilon$, because the
strategy $\sigma$ $2\varepsilon$-achieves $v$. Because we used an
approximation of that value, called $v^{\prime}$, that is at most
$\varepsilon/3$ smaller than the real value, we get that $v\leq
v^{\prime}+\frac{7}{3}\varepsilon$ and thus the oracle will necessarily return
“no”. Because at least one guess would result in an output different from
“no”, the algorithm must return some such value.

Next, consider that the algorithm guessed some $u$-bit representable strategy
$\sigma$, which did not $3\varepsilon$-achieve $v$ wrt $\mathcal{B}({{\bf
b}})$ and we will argue that the oracle will be able to return “yes”. By
definition of $3\varepsilon$-achieve $v$ wrt $\mathcal{B}({{\bf b}})$, there
must be some strategy $\sigma^{\prime\prime}$ wrt $\mathcal{B}({{\bf b}})$ for
player $2$, so that value $v^{\prime\prime}$ of the Markov chain induced by
$(\sigma,\sigma^{\prime\prime})$ with rewards for player $1$ must be strictly
smaller than $v-3\varepsilon$. By Lemma 7.6, applied with $\varepsilon$ being
$\varepsilon/3$ we can then find an $u^{\prime}$-bit representable strategy
$\sigma^{\prime\prime\prime}$ so that $(\sigma,\sigma^{\prime\prime\prime})$
with rewards for player $1$ must have a value strictly smaller than
$v-\frac{8}{3}\varepsilon$. The oracle can non-deterministically guess that
strategy in which $\sigma^{\prime}=\sigma^{\prime\prime\prime}$, the
approximated value $v^{\prime}$ is then such that
$v>v^{\prime}+\frac{7}{3}\varepsilon$ (because the approximated value is at
most $\varepsilon/3$ smaller than the real value) and thus, the oracle will
return “yes”. ∎

##  8\. Applications

We discuss the implications of our results for some well-known classes of
games.

###  8.1. Multi-player partial-information parity games

A _parity_ objective (for player $j\leq k$) assigns a play
$\rho=~{}(v_{0},s_{0},$ $a_{0},c_{0}),(v_{1},s_{1},a_{1},c_{1})\dots$ the
value $1$ if $\limsup_{N\to\infty}c_{i}[j]$, the maximal reward seen
infinitely often, is even and $0$ otherwise.

In perfect-information turn-based games, this condition can be translated into
a mean-payoff condition, based on the observation that the game effectively
ends after a cycle is formed (see e.g. (Fijalkow and Monmege, 2023, Theorem
40)). However, no such simple reduction can generalise even to concurrent
games, because the most significant reward may occur arbitrarily rarely. In
concurrent games, as opposed to the simpler turn-based ones,
$\varepsilon$-optimal strategies might require infinite memory (Hansen et al.,
2023) and mixed actions with double exponentially small probabilities (Hansen
et al., 2009).

We now argue that one can adapt our constructions to parity objectives as
follows. First, state and loop elimination (Section 5) are simpler for parity
since one does not need to keep track of the duration or of the exact reward
but can instead just set the new reward to be the maximum of the old ones.

The only non-trivial change required is the proof of Lemma 7.3, which bounds
the change in values achieved by strategy profiles under small perturbations.
Specifically, our argument relies on (Solan, 2003, Theorem 5), which only
applies to mean-payoff games and not parity games. To adapt our proof, we
consider the Markov chain induced by any fixed strategy profile where each
player uses finite memory. Now almost surely, some CCS is entered and then
every reward contained is seen infinitely often. Therefore a player gets
overall parity reward 1 in a CCS within which their largest reward is even
(and 0 otherwise). Therefore, for each CCS, any perturbation of the
probabilities in the corresponding states (i.e. state in the original game and
memory vector) that have the same support will not change the outcome of that
CCS. We can therefore define an equivalent mean-payoff Markov chain in which
each CSS is collapsed to an absorbing chain with reward $1$ or $0$
accordingly. The claim of Lemma 7.3 (parity) then follows from Lemma 7.3 as
stated for mean-payoff.

We conclude that Theorems 3.2 and 3.3 hold as stated also for (multi-player,
partial-information) games with parity objectives.

###  8.2. Multi-player concurrent games

We consider different classes of perfect-information games that are
_concurrent_ games, meaning the motion is determined by simultaneously chosen
actions of all players, as opposed to the _turn-based_ games where in each
round only the choice of one player matters.

When considering bounded strategies, it is instructive to distinguish
_private_ memory (accessible only by the respective player as used throughout
this paper) from _public_ memory, which is visible to all players.
Essentially, public memory is shared among all players (but can only be
updated by its owner) (see (Hansen et al., 2023, Section 5.1) for details).

The important difference for us is that fixing public memory strategies for
all but one player results in an ordinary MDP (a perfect-information 1-player
game) for the remaining player. On the other hand, fixing private memory
strategies for all but one player, results in a _partial-information_ MDP, as
the player cannot know their opponents’ memory modes.

####  8.2.1. Computing $\varepsilon$-Nash Equilibria

Our technique allows us to compute general $\varepsilon$-Nash equilibria,
i.e., without restricting the set of admissible strategies, assuming that
there exist equilibria with bounded public memory. Formally, for a $k$-player
game and vector ${\bf b}\in\mathbb{N}^{k}$, let $\mathcal{P}({{\bf b}})$
denote the set of all strategy profiles wherein each player $i$ uses a public
finite memory strategy with at most ${\bf b}[i]$ modes.

###### Corollary 8.1.

For any fixed $k\geq 1$, we get the following: Given a $k$-player concurrent
mean-payoff game, bounds ${\bf b}\in N^{k}$ (in unary), and $\varepsilon>0$
(in binary), we can

  1. (1)

find an $\varepsilon$-Nash equilibrium (and output it) in exponential time, if
an $\varepsilon$-Nash equilibrium wrt $\mathcal{P}({{\bf b}})$ exists

  2. (2)

find an $\varepsilon$-Nash equilibrium (and output it) in
${\mathsf{FNP}}^{\mathsf{NP}}$, if there exists an $\varepsilon^{\prime}$-Nash
equilibrium wrt $\mathcal{P}({{\bf b}})$, for some
$\varepsilon^{\prime}\in[0,\varepsilon/2)$.

###### Proof.

This follows from Theorems 3.2 and 3.3, using the observation that any
$\varepsilon$-Nash equilibrium in $\mathcal{P}({{\bf b}})$ is also an
$\varepsilon$-Nash equilibrium without restriction, ie., where unilateral
deviations to any strategy are considered, because of the following. Each
player $i$, no matter which bounded and public memory strategy each of the
other players picked, player $i$ cannot deviate to a bounded and public memory
strategy ensuring more than $\varepsilon$ than what player $i$ received
before, by definition of $\varepsilon$-Nash equilibria with respect to
$\mathcal{P}({{\bf b}})$. Finite MDPs with mean-payoff objectives have
memoryless $\varepsilon$-optimal strategies (Puterman, 1994). Therefore,
player $i$ cannot get more than what can be ensured by a memoryless strategy
which is a special case of bounded and public memory strategies. ∎

It is an open question whether $\varepsilon$-Nash equilibria always exist for
concurrent mean-payoff games. We point to two special cases: stay-in-a-set
games (Secchi and Sudderth, 2002) and quitting games (Solan and Vieille, 2001,
2003). For both, it was known that finite (and as we will argue: public)
memory $\varepsilon$-Nash equilibria exist, but so far, no algorithm was known
to compute them.

####  8.2.2. Stay-In-a-set games

These are multi-player concurrent games where each player has a separate
safety objective, that is, wants the play to remain in a given subset of the
states. Secchi and Sudderth (Secchi and Sudderth, 2002) showed that stay-in-a-
set games always have finite memory $\varepsilon$-Nash equilibria, but the
players might need to remember who has already lost. Such strategies are
finite memory public strategies (with the number of memories equal to $2^{k}$,
where $k$ is the number of players). For a fixed number of players $k$, our
technique can be used to compute $\varepsilon$-Nash equilibria with strategies
using public memory and optimise the necessary memory bounds. That is, we can
find public-memory equilibria with the least amount of memory.

###### Corollary 8.2.

For every $k\geq 1$ the following is in ${\mathsf{FNP}}^{\mathsf{NP}}$. Given
a $k$-player stay-in-a-set game, find an $\varepsilon$-Nash equilibria.

###### Proof.

One first encodes the safety conditions as a mean-payoff condition, so that a
player receives reward $1$ as long as their set is never left, and $0$ forever
once it is. Using a subset construction, this results in a game with states
$V\times 2^{k}$ (a polynomial blow-up since $k$ is fixed). In order to keep a
one-to-one correspondence of equilibria it is necessary to construct a
partial-information game here. In particular, in the original game, it is
sufficient for players to remember who has already lost. Our reduction encodes
this information into the states, and so it must be hidden from players (by
having any state $(s,{\bf m})$ give the signal $s$) because otherwise,
memoryless strategies suffice, even if they did not in the original game. The
claim now follows by Theorem 3.3, bounding the number of memory modes for each
player by $b=2^{k}$, similar to the proof of Corollary 8.1, because, if each
player is playing a public and finite-memory strategy, one just needs ${\bf
m}$ in memory (requiring $2^{k}$ memory states) to have all information about
the state of the game. ∎

####  8.2.3. Quitting games

Quitting games (Solan and Vieille, 2001, 2003) are concurrent mean-payoff
games in which there is only one non-absorbing state and the players each have
two actions in that state: Continue or Stop. The play goes to an absorbing
state (effectively stops) in the first round when at least one player plays
their stop action.

Under mild assumptions on the payoffs222 They ask that (i) Each player prefers
to be the only quitter rather than having the game continue forever, and (ii)
if a player quits, he prefers to be the only quitter., Solan and Vieille
(Solan and Vieille, 2001) show the existence of “cyclic” $\varepsilon$-NE, in
which players’ behaviour repeat after some number of stages. Any such
equilibrium can be represented as one consisting of public finite memory
strategies. Specifically, we need to have a state of memory corresponding to
each stage in the “cyclic” $\varepsilon$-NE, from stage one up to the first
repetition, where we just in each stage move to the next memory state and then
loop back at the end. While they do not provide a bound directly, they prove
the existence of such ‘cyclic” $\varepsilon$-NE and their proof implies a
bound: The proof of (Solan and Vieille, 2001, Prop. 2.3) uses a partitioning
of $[-R,R]^{k}$ (if each reward is bounded absolutely by $R$) into regions, so
that any two elements in one region differ by no more than $\varepsilon^{2}$
(in one-norm). For fixed $k$, this gives on the order of
$\mathcal{O}\left(\frac{R^{k}}{\varepsilon^{2k}}\right)$ many regions. Each
region is then mapped to some (perhaps other) region and the cyclic
$\varepsilon$-Nash equilibrium is then formed from the sequence obtained by
the regions encountered by repeatedly following the mapping. The length of
such a sequence can therefore not exceed the number of encountered regions,
bounded as above.

Our algorithm can therefore find such an $\varepsilon$-Nash equilibrium, using
Corollary 8.1, assuming that both rewards and $\varepsilon$ are encoded in
unary.

###### Corollary 8.3.

For any fixed $k\geq 1$, we get the following: Given a $k$-player quitting
game (with rewards in unary), satisfying the conditions in (Solan and Vieille,
2001), and $\varepsilon>0$ (in unary), we can find an $\varepsilon$-Nash
equilibrium (and output it) in ${\mathsf{FNP}}^{\mathsf{NP}}$.

Similarly, given a game and a cyclic $\varepsilon$-Nash equilibrium, one can
compute a finite memory $\varepsilon$-Nash equilibrium that uses less memory
if it exists.

###  8.3. $2$-player, zero-sum concurrent mean-payoff games

####  8.3.1. Checking the existence of memoryless ($\varepsilon$-)optimal
strategies

Recent work by Bordais et al. (Bordais et al., 2021, 2022, 2023) studies how
to restrict the topology of the game graph to ensure the existence of
memoryless optimal strategies for both players. They show that it is decidable
(in exponential time) whether their properties hold, and thus
$\varepsilon$-optimal strategies exist. The constructions are based on
effective reductions to the first-order theory of the reals, which also yields
an exponential time algorithm to compute ($\varepsilon$-)optimal memoryless
strategies if they exist. This has been done for reachability (Bordais et al.,
2021) Büchi and coBüchi (Bordais et al., 2022), and parity (Bordais et al.,
2023) conditions.

We improve on these results in several ways: Our constructions are directly
applicable to not only zero-sum concurrent parity games (see Section 8.1) but
to more general settings, such as with mean-payoff objectives or where
bounded-, finite- and public-memory strategies are sought instead of just
memoryless ones. We can decide the existence of ($\varepsilon$-)optimal
memoryless strategies for both players without the proxy of deciding
sufficient criteria. Finally, for $\varepsilon>0$, our technique results in a
lower complexity: ${\mathsf{FNP}}^{\mathsf{NP}}$instead of exponential time.

###### Corollary 8.4.

For two-player, zero-sum concurrent mean-payoff games,

  1. (1)

checking if, for any given game and $\varepsilon\geq 0$, there exist
$\varepsilon$-optimal memoryless strategies for both players (and output one
for each player if so) can be done in exponential time.

  2. (2)

checking if, for any given game and $\varepsilon>0$, there exist
$\varepsilon$-optimal memoryless strategies for both players (and output one
for each player if so), if there exists an $\varepsilon^{\prime}$-optimal
memoryless strategy for each player, for some
$\varepsilon^{\prime}\in[0,\varepsilon/2)$ is in
${\mathsf{FNP}}^{\mathsf{NP}}$.

###### Proof.

If you have an $\varepsilon/2$-optimal strategy for each player in a zero-sum,
two-player game, then the strategies form an $\varepsilon$-Nash equilibrium
and given an $\varepsilon$-Nash equilibrium, it must be made up of two
strategies that are each $\varepsilon$-optimal. Because the strategies are
memoryless ($b=1$), they are in particular public memory. The two claims thus
follow by Corollary 8.1 instantiated for $k=2$ and $b=1$. ∎

##### Approximating zero-sum values

We consider the problem of approximating ordinary (zero-sum) values for two-
player concurrent mean-payoff games. Recall that all strategies getting close
to ensuring the value might require infinite memory (Hansen et al., 2023).

Different methods (see eg. (Mertens and Neyman, 1981; Chatterjee et al., 2008;
Hansen et al., 2011; Oliu-Barton, 2021)) have been proposed for this. The most
well-known approach is the value iteration algorithm of Mertens and Neyman
(Mertens and Neyman, 1981), which has later been show to take double-
exponentially many iterations to $\varepsilon$-approximate the values, see
(Hansen et al., 2011, 2009). The current best complexity upper bound is
$\mathsf{PSPACE}$: As shown by (Hansen et al., 2011; Mertens and Neyman, 1981)
using a double exponentially small discount factor, the corresponding
discounted game to a mean-payoff game will have the same value
$\pm\varepsilon$. As shown by (Etessami and Yannakakis, 2008) a discounted
game can be solved in $\mathsf{PSPACE}$ by reduction333Etessami and Yannakakis
(Etessami and Yannakakis, 2008) show how to construct
$\exists$$\mathrm{FO}(\mathbb{R})$ formulae for games with fixed discount
factors, but one can create double-exponential values using repeated squaring
in the existential fragment. to the existential fragment of
$\mathrm{FO}(\mathbb{R})$.

Our technique yields the current best algorithm for this problem.

###### Corollary 8.5.

The following is in ${\mathsf{FNP}}^{\mathsf{NP}}$. Given a two-player, zero-
sum concurrent mean-payoff game and $\varepsilon>0$, find the value of the
game within an additive error of $\varepsilon$.

###### Proof.

As shown already in (Mertens and Neyman, 1981), the value of a mean-payoff
game is equal to the limit of values of the same game but with discount $d$
for $d$ going to $0$. Hansen et al. (Hansen et al., 2011) show that for any
discount $d$ below some double exponentially small number, the value of the
mean-payoff game differs by less than $\varepsilon$ from that of the
discounted game with discount factor $d$. For a formal definition of
discounted-payoff games, we refer to (Hansen et al., 2011; Solan and Vieille,
2001).

There is a well-known reduction from discounted games to (non-discounted)
mean-payoff games already present in (Shapley, 1953): Given a $d$-discounted
game $G$, replace each action $a$ from $s$ to $t$ with a stochastic action
that goes to an absorbing state with reward $r(a)$ with probability $d$ and
otherwise (with the remaining probability of $1-d$) proceeds to $t$ (it works
the same way if $a$ was part of a stochastic action: If it occurred with
probability $p$, then you instead go to the absorbing state with probability
$pd$ and to $t$ with probability $p(1-d)$). This results in a mean-payoff game
$G^{\prime}$, with transition probabilities in the order of $d$. Importantly,
the value and witnessing strategies are the same in both games. As any
concurrent discounted game has optimal memoryless strategies for both
players(Shapley, 1953), the same is true for $G^{\prime}$. Such strategies are
in particular public memory strategies. As is well-known, in a two-player,
zero-sum game, a Nash equilibrium must be made up of two optimal strategies
and an optimal strategy for each player forms an Nash equilibrium.

The claim now follows from Corollary 8.1. Note that the corollary is
applicable even though $d$ is double-exponentially small because our algorithm
allows transition probabilities to be represented in floating point notation.
∎

## References

  * (1)
  * Amoussou-Guenou et al. (2021) Yackolley Amoussou-Guenou, Souheib Baarir, Maria Potop-Butucaru, Nathalie Sznajder, Léo Tible, and Sébastien Tixeuil. 2021.  On the Encoding and Solving of Partial Information Games. In _Networked Systems_. 60–76.  https://doi.org/10.1007/978-3-030-67087-0_5
  * Basu et al. (2006) Saugata Basu, Richard Pollack, and Marie-Françoise Roy. 2006\.  _Algorithms in Real Algebraic Geometry_ (2nd ed.).  https://doi.org/10.1007/3-540-33099-2
  * Billingsley (1995) Patrick Billingsley. 1995\.  _Probability and Measure_.
  * Blackwell and Ferguson (1968) David Blackwell and Tom S Ferguson. 1968.  The Big Match.  _The Annals of Mathematical Statistics_ 39, 1 (1968), 159–163.  https://doi.org/10.1214/aoms/1177698513
  * Bordais et al. (2022) Benjamin Bordais, Patricia Bouyer, and Stéphane Le Roux. 2022\.  Playing (Almost-)Optimally in Concurrent Büchi and Co-Büchi Games. In _IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)_ , Vol. 250. 33:1–33:18.  https://doi.org/10.4230/LIPIcs.FSTTCS.2022.33
  * Bordais et al. (2021) Benjamin Bordais, Patricia Bouyer, and Stéphane Le Roux. 2021\.  From Local to Global Determinacy in Concurrent Graph Games. In _IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)_ _(LIPIcs, Vol. 213)_. 41:1–41:14.  https://doi.org/10.4230/LIPIcs.FSTTCS.2021.41
  * Bordais et al. (2023) Benjamin Bordais, Patricia Bouyer, and Stéphane Le Roux. 2023\.  From Local To Global Optimality in Concurrent Parity Games.  arXiv:2311.14373 [cs.GT]
  * Bouyer et al. (2021) Patricia Bouyer, Youssouf Oualhadj, Mickael Randour, and Pierre Vandenhove. 2021.  Arena-Independent Finite-Memory Determinacy in Stochastic Games. In _International Conference on Concurrency Theory (CONCUR)_ _(LIPIcs, Vol. 203)_. 26:1–26:18.  https://doi.org/10.4230/LIPIcs.CONCUR.2021.26
  * Bouyer et al. (2023) Patricia Bouyer, Mickael Randour, and Pierre Vandenhove. 2023\.  Characterizing Omega-Regularity through Finite-Memory Determinacy of Games on Infinite Graphs.  _TheoretiCS_ 2 (2023).  https://doi.org/10.46298/theoretics.23.1
  * Bouyer et al. (2022) Patricia Bouyer, Stéphane Le Roux, Youssouf Oualhadj, Mickael Randour, and Pierre Vandenhove. 2022.  Games Where You Can Play Optimally with Arena-Independent Finite Memory.  _Logical Methods in Computer Science_ 18, 1 (2022).  https://doi.org/10.46298/lmcs-18(1:11)2022
  * Cauchy (1828) A.L. Cauchy. 1828\.  _Exercices de Mathematiques (1828)_.
  * Chatterjee et al. (2014) Krishnendu Chatterjee, Laurent Doyen, Sumit Nain, and Moshe Y. Vardi. 2014.  The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies. In _International Conference on Foundations of Software Science and Computational Structures (FoSSaCS)_. 242–257.  https://doi.org/10.1007/978-3-642-54830-7_16
  * Chatterjee et al. (2008) Krishnendu Chatterjee, Rupak Majumdar, and Thomas Henzinger. 2008\.  Stochastic limit-average games are in EXPTIME.  _International Journal of Game Theory_ 37 (06 2008), 219–234.  https://doi.org/10.1007/s00182-007-0110-5
  * Chatterjee et al. (2022) Krishnendu Chatterjee, Raimundo Saona, and Bruno Ziliotto. 2022\.  Finite-Memory Strategies in POMDPs with Long-Run Average Objectives.  _Mathematics of Operations Research_ 47, 1 (feb 2022), 100–119.  https://doi.org/10.1287/moor.2020.1116
  * Ehrenfeucht and Mycielski (1973) Andrzej Ehrenfeucht and Jan Mycielski. 1973.  Positional games over a graph.  _Notices of the American Mathematical Society_ 20 (1973), A–334.  https://doi.org/10.1007/BF01768705
  * Etessami and Yannakakis (2008) Kousha Etessami and Mihalis Yannakakis. 2008.  Recursive Concurrent Stochastic Games.  _Logical Methods in Computer Science_ 4, 4 (11 Nov. 2008).  https://doi.org/10.2168/LMCS-4(4:7)2008
  * Everett (1957) Hugh Everett. 1957\.  Recursive games.  In _Contributions to the Theory of Games, Volume III_. Annals of Mathematics Studies, Vol. 39. 47–78.  https://doi.org/10.1515/9781400829156-014
  * Fijalkow and Monmege (2023) Nathanaël Fijalkow and Benjamin Monmege. 2023.  Games with Payoffs.  In _Games on Graphs_.  https://doi.org/10.48550/arXiv.2305.10546
  * Filar et al. (1991) Jerzy A. Filar, Todd A. Schultz, Frank Thuijsman, and O. J. Vrieze. 1991.  Nonlinear programming and stationary equilibria in stochastic games.  _Math. Program._ 50 (1991), 227–237.  https://doi.org/10.1007/BF01594936
  * Frederiksen and Miltersen (2013) Søren Kristoffer Stiil Frederiksen and Peter Bro Miltersen. 2013.  Approximating the Value of a Concurrent Reachability Game in the Polynomial Time Hierarchy. In _International Symposium on Algorithms and Computation (ISAAC)_. 457–467.  https://doi.org/10.1007/978-3-642-45030-3_43
  * Gillette (1957) Dean Gillette. 1957\.  Stochastic games with zero stop probabilities.  _Contributions to the Theory of Games_ 3 (1957), 179–187.  https://doi.org/10.1515/9781400882151-011
  * Gimbert and Zielonka (2005) Hugo Gimbert and Wiesław Zielonka. 2005.  Games Where You Can Play Optimally Without Any Memory. In _International Conference on Concurrency Theory (CONCUR)_. 428–442.
  * Goldreich (2006) Oded Goldreich. 2006\.  _On Promise Problems: A Survey_.  254–290.  https://doi.org/10.1007/11685654_12
  * Hansen et al. (2014) Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, and Peter Bro Miltersen. 2014.  The Complexity of Solving Reachability Games Using Value and Strategy Iteration.  _Theory Comput. Syst._ 55, 2 (2014), 380–403.  https://doi.org/10.1007/s00224-013-9524-6
  * Hansen et al. (2023) Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, and Abraham Neyman. 2023.  The Big Match with a Clock and a Bit of Memory.  _Mathematics of Operations Research_ 48, 1 (2023), 419–432.  https://doi.org/10.1287/moor.2022.1267
  * Hansen et al. (2011) Kristoffer Arnsfelt Hansen, Michal Koucky, Niels Lauritzen, Peter Bro Miltersen, and Elias P. Tsigaridas. 2011.  Exact Algorithms for Solving Stochastic Games: Extended Abstract. In _Symposium on Theory of Computing (STOC)_. 205–214.  https://doi.org/10.1145/1993636.1993665
  * Hansen et al. (2009) Kristoffer Arnsfelt Hansen, Michal Koucky, and Peter Bro Miltersen. 2009.  Winning Concurrent Reachability Games Requires Doubly-Exponential Patience. In _ACM/IEEE Symposium on Logic in Computer Science (LICS)_. 332–341.  https://doi.org/10.1109/LICS.2009.44
  * Hunter et al. (2018) Paul Hunter, Arno Pauly, Guillermo A. Pérez, and Jean-François Raskin. 2018.  Mean-payoff games with partial observation.  _Theoretical Computer Science_ 735 (2018), 82–110.  https://doi.org/10.1016/j.tcs.2017.03.038
  * Madani et al. (1999) Omid Madani, Steve Hanks, and Anne Condon. 1999.  On the Undecidability of Probabilistic Planning and Infinite-Horizon Partially Observable Markov Decision Problems. In _AAAI/IAAI_.  https://doi.org/10.5555/315149.315395
  * Mansour and Singh (1999) Yishay Mansour and Satinder Singh. 1999.  On the Complexity of Policy Iteration. In _UAI ’99: Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, Stockholm, Sweden, July 30 - August 1, 1999_. 401–408.  https://doi.org/10.5555/2073796.2073842
  * Mertens and Neyman (1981) J-F Mertens and Abraham Neyman. 1981.  Stochastic games.  _International Journal of Game Theory_ 10, 2 (1981), 53–66.
  * Oliu-Barton (2021) Miquel Oliu-Barton. 2021\.  New Algorithms for Solving Zero-Sum Stochastic Games.  _Mathematics of Operations Research_ 46, 1 (2021), 255–267.  https://doi.org/10.1287/moor.2020.1055
  * Puterman (1994) Martin L. Puterman. 1994\.  _Markov Decision Processes: Discrete Stochastic Dynamic Programming_ (1st ed.).  https://doi.org/10.1002/9780470316887
  * Secchi and Sudderth (2002) Piercesare Secchi and William D. Sudderth. 2002.  Stay-in-a-set games.  _International Journal of Game Theory_ 30 (2002), 479–490.  https://doi.org/10.1007/s001820200092
  * Shapley (1953) Lloyd S. Shapley. 1953\.  Stochastic Games.  _Proceedings of the National Academy of Sciences_ 39 (1953), 1095 – 1100.  https://doi.org/10.1073/pnas.39.10.1095
  * Solan (2003) Eilon Solan. 2003\.  Continuity of the Value of Competitive Markov Decision Processes.  _Journal of Theoretical Probability_ 16 (10 2003), 831–845.  https://doi.org/10.1023/B:JOTP.0000011995.28536.ef
  * Solan and Vieille (2001) Eilon Solan and Nicolas Vieille. 2001.  Quitting Games.  _Mathematics of Operations Research_ 26, 2 (2001), 265–285.  https://doi.org/10.1287/moor.26.2.265.10549
  * Solan and Vieille (2003) Eilon Solan and Nicolas Vieille. 2003.  Quitting Games – An Example.  _International Journal of Game Theory_ 31, 3 (2003), 365–381.  https://doi.org/10.1007/s001820200125
  * Solan and Ziliotto (2016) Eilon Solan and Bruno Ziliotto. 2016.  _Stochastic Games with Signals_.  77–94.

##  Appendix A Proofs for Section 5

###### Definition A.1 (Cycle values).

For a set $C\subseteq V$ of target states let
${\mathop{H}\nolimits_{C}}:\Omega\to\mathbb{N}\cup\\{\infty\\}$ be the random
variable denoting the least non-zero number of steps until state in $C$ is
reached. That is, ${\mathop{H}\nolimits_{C}}(s_{0}s_{1}\ldots)=\inf\\{k\geq
1\mid s_{k}\in C\\}$. Further, let
${\mathop{R}\nolimits_{t}},{\mathop{D}\nolimits_{t}}:\Omega\to\mathbb{R}\cup\\{\infty\\}$
denote the sum of rewards, and durations respectively, accumulated up until
state $t$ is first reached. That is,
${\mathop{R}\nolimits_{t}}=\sum_{k=1}^{{\mathop{H}\nolimits_{t}}}\mathop{r}\nolimits(s_{k-1},s_{k})$
and
${\mathop{D}\nolimits_{t}}=\sum_{k=1}^{{\mathop{H}\nolimits_{t}}}\mathop{d}\nolimits(s_{k-1},s_{k})$.

###### Lemma A.2.

If $s$ is recurrent then
${\mathbb{E}}_{s}\left[{{\mathop{MPR}}}\right]={\mathbb{E}}_{s}\left[{{\mathop{R}\nolimits_{s}}}\right]/{\mathbb{E}}_{s}\left[{{\mathop{D}\nolimits_{s}}}\right]$.

###### Proof.

Let $s$ belong to some CCS $S$ with $n$ states. Let $p$ be the smallest non-
zero probability associated to any edge between vertices in $S$. Let $R$
(resp. $r$) be the most positive (resp. most negative) reward per step and $D$
(resp. $d$) be the largest (resp. smallest) duration of a step.

By definition of CCS, there is always a path between any two states in $S$ and
thus in particular, a simple one (i.e. with no state occurring twice). This
means that there is a simple path consisting of at most $n-1$ edges between
the states. Each edge has probability of at least $p$ of occurring, so the
path has a probability of at least $p^{n-1}$ to be followed. From each
$s^{\prime}$ consider a shortest (in number of steps) directed path
$P_{s^{\prime}}$ from $s^{\prime}$ to $s$. We start an attempt whenever we
visit $s$ or just after we have moved along an edge not in $P_{s^{\prime}}$,
where $s^{\prime}$ was the last state in which we started an attempt. In
particular, we start a new attempt every at most $n$ steps. Each attempt
reaches $s$ with probability at least $p^{n-1}$. Therefore, in expectation, we
need at most $p^{1-n}$ many attempts. Each attempt took at most $n$ steps.

This means that almost all plays visits $s$ infinitely many times. Let $s_{i}$
be the random variable denoting the step in which the play visits $s$ the
$i$th time. We view the steps inbetween $s_{i}$ and $s_{i+1}$ as a trial and
we thus have infinitely many trials.

Consider any $\varepsilon>0$ . We partition plays into two sets,
${\mathop{G}}$ and ${\mathop{N}}$. A play is in ${\mathop{G}}$, if the average
reward of the trials is within $(1\pm\varepsilon)$ of
${\mathbb{E}}_{s}\left[{{\mathop{R}\nolimits_{s}}}\right]$ (unless
${\mathbb{E}}_{s}\left[{{\mathop{R}\nolimits_{s}}}\right]=0$, in which case,
we have that the average reward of the trials is in
$[-\varepsilon,\varepsilon]$ for a play to be in ${\mathop{G}}$) and the
average duration of the trials is within $(1\pm\varepsilon)$ of
${\mathbb{E}}_{s}\left[{{\mathop{D}\nolimits_{s}}}\right]$. The remaining
plays are in ${\mathop{N}}$.

By linearity of expectation, we have that

${\mathbb{E}}_{s}\left[{{\mathop{MPR}}}\right]={\mathbb{E}}_{s}\left[{{\mathop{MPR}}\mid{\mathop{N}}}\right]\mathbb{P}_{s}\left({{\mathop{N}}}\right)+{\mathbb{E}}_{s}\left[{{\mathop{MPR}}\mid{\mathop{G}}}\right]\mathbb{P}_{s}\left({{\mathop{G}}}\right).$

For any play, ${\mathop{MPR}}$ is in $[\min(r/d,r/D),\max(R/d,R/D)]$, because
that is the bound on the stepwise fraction. In particular, it is true for
${\mathbb{E}}_{s}\left[{{\mathop{MPR}}\mid{\mathop{N}}}\right]$. By law of
large numbers, $\mathbb{P}_{s}\left({{\mathop{N}}}\right)<\varepsilon$.

By definition of ${\mathop{G}}$ we see as follows. If
${\mathbb{E}}_{s}\left[{{\mathop{R}\nolimits_{s}}}\right]>0$, we have that

${\mathbb{E}}_{s}\left[{{\mathop{MPR}}\mid{\mathop{G}}}\right]\in\left[\frac{(1-\varepsilon){\mathbb{E}}_{s}\left[{{\mathop{R}\nolimits_{s}}}\right]}{(1+\varepsilon){\mathbb{E}}_{s}\left[{{\mathop{D}\nolimits_{s}}}\right]},\frac{(1+\varepsilon){\mathbb{E}}_{s}\left[{{\mathop{R}\nolimits_{s}}}\right]}{(1-\varepsilon){\mathbb{E}}_{s}\left[{{\mathop{D}\nolimits_{s}}}\right]}\right]$

Conversely, if ${\mathbb{E}}_{s}\left[{{\mathop{R}\nolimits_{s}}}\right]<0$,
we have that

${\mathbb{E}}_{s}\left[{{\mathop{MPR}}\mid{\mathop{G}}}\right]\in\left[\frac{(1+\varepsilon){\mathbb{E}}_{s}\left[{{\mathop{R}\nolimits_{s}}}\right]}{(1-\varepsilon){\mathbb{E}}_{s}\left[{{\mathop{D}\nolimits_{s}}}\right]},\frac{(1-\varepsilon){\mathbb{E}}_{s}\left[{{\mathop{R}\nolimits_{s}}}\right]}{(1+\varepsilon){\mathbb{E}}_{s}\left[{{\mathop{D}\nolimits_{s}}}\right]}\right]$

Finally, if ${\mathbb{E}}_{s}\left[{{\mathop{R}\nolimits_{s}}}\right]=0$, we
have that

${\mathbb{E}}_{s}\left[{{\mathop{MPR}}\mid{\mathop{G}}}\right]\in\left[-\frac{\varepsilon}{(1-\varepsilon){\mathbb{E}}_{s}\left[{{\mathop{D}\nolimits_{s}}}\right]},\frac{\varepsilon}{(1-\varepsilon){\mathbb{E}}_{s}\left[{{\mathop{D}\nolimits_{s}}}\right]}\right]$

In any case, since this is true for any $\varepsilon>0$, we have that
${\mathbb{E}}_{s}\left[{{\mathop{MPR}}}\right]=\frac{{\mathbb{E}}_{s}\left[{{\mathop{R}\nolimits_{s}}}\right]}{{\mathbb{E}}_{s}\left[{{\mathop{D}\nolimits_{s}}}\right]}$,
as wanted. ∎

###### Definition A.3.

Let $M=(V,\mathop{p}\nolimits,\mathop{r}\nolimits,\mathop{d}\nolimits)$ and
$M^{\prime}=(V^{\prime},\mathop{p}\nolimits^{\prime},\mathop{r}\nolimits^{\prime},\mathop{d}\nolimits^{\prime})$
be two Markov chains with associated rewards and durations, where
$V,V^{\prime}\subseteq\mathbb{N}_{\leq n}$. We call $M^{\prime}$ a _summary_
$M$ if

  1. (1)

There is a one-to-one correspondence between CCSs $C_{0},C_{1},\ldots$ in $M$
and and $C^{\prime}_{0},C^{\prime}_{1},\ldots$ in $M^{\prime}$ that agrees on
states in $V\cap V^{\prime}$. That is, for any pair $C_{j}$ and
$C^{\prime}_{j}$ of corresponding CCSs, it holds that $C_{j}\cap
V^{\prime}=C^{\prime}_{j}\cap V$.

  2. (2)

The probability of reaching any a CCS $C_{j}$ in $M$ is the same as reaching
the corresponding $C^{\prime}_{j}$ in $M^{\prime}$.

That is,
$\mathbb{P}^{M}_{s}\left({{{\mathop{H}\nolimits_{C_{j}}}}<\infty}\right)=\mathbb{P}^{M^{\prime}}_{s}\left({{{\mathop{H}\nolimits_{C^{\prime}_{j}}}}<\infty}\right)$
for any $s\in V\cap V^{\prime}$.

  3. (3)

The expected cumulative rewards and durations on cycles from and to recurrent
states are preserved.

That is, for all $s$ recurrent,
${\mathbb{E}}^{M}_{s}\left[{{\mathop{R}\nolimits_{s}}}\right]={\mathbb{E}}^{M^{\prime}}_{s}\left[{{\mathop{R}\nolimits_{s}}}\right]$
and
${\mathbb{E}}^{M}_{s}\left[{{\mathop{D}\nolimits_{s}}}\right]={\mathbb{E}}^{M^{\prime}}_{s}\left[{{\mathop{D}\nolimits_{s}}}\right].$

The following lemma shows that summaries preserve the expected mean-payoff
ratio values.

###### Lemma A.4.

If $M^{\prime}$ is a summary of $M$ and $s\in V\cap V^{\prime}$. Then
${\mathbb{E}}^{M}_{s}\left[{{\mathop{MPR}}}\right]={\mathbb{E}}^{M^{\prime}}_{s}\left[{{\mathop{MPR}}}\right]$.

###### Proof.

Let $B\subseteq V$ be a maximal set of recurrent states that do not
communicate pairwise. That is, $B$ consists of representative states, one for
each CCS of $M$. Then

(2) ${\mathbb{E}}^{M}_{s}\left[{{\mathop{MPR}}}\right]=\sum_{b\in
B}\mathbb{P}^{M}_{s}\left({{{\mathop{H}\nolimits_{{b}}}}<\infty}\right)\cdot{\mathbb{E}}^{M}_{b}\left[{{\mathop{MPR}}}\right].$

This holds because in finite Markov chains the absorption probability is $1$,
i.e., almost-surely eventually a state in $B$ will be reached, and that the
${\mathop{MPR}}$ objective is prefix-independent. Now from the assumption that
$M^{\prime}$ is a summary of $M$ we get the following. Notice that a state
$b\in B$ represents a CCS both in $M$ and $M^{\prime}$ by point 1 of
Definition A.3.

$\displaystyle{\mathbb{E}}^{M}_{s}\left[{{\mathop{MPR}}}\right]$
$\displaystyle=\sum_{b\in
B}\mathbb{P}^{M}_{s}\left({{{\mathop{H}\nolimits_{{b}}}}<\infty}\right)\cdot{\mathbb{E}}^{M}_{b}\left[{{\mathop{MPR}}}\right]$
$\displaystyle=\sum_{b\in
B}\mathbb{P}^{M}_{s}\left({{{\mathop{H}\nolimits_{{b}}}}<\infty}\right)\cdot\frac{{\mathbb{E}}^{M}_{b}\left[{{\mathop{R}\nolimits_{b}}}\right]}{{\mathbb{E}}^{M}_{b}\left[{{\mathop{R}\nolimits_{b}}}\right]}$
$\displaystyle=\sum_{b\in
B}\mathbb{P}^{M^{\prime}}_{s}\left({{{\mathop{H}\nolimits_{{b}}}}<\infty}\right)\cdot\frac{{\mathbb{E}}^{M^{\prime}}_{b}\left[{{\mathop{R}\nolimits_{b}}}\right]}{{\mathbb{E}}^{M^{\prime}}_{b}\left[{{\mathop{R}\nolimits_{b}}}\right]}$
$\displaystyle=\sum_{b\in
B}\mathbb{P}^{M^{\prime}}_{s}\left({{{\mathop{H}\nolimits_{{b}}}}<\infty}\right)\cdot{\mathbb{E}}^{M}_{b}\left[{{\mathop{MPR}}}\right]={\mathbb{E}}^{M^{\prime}}_{s}\left[{{\mathop{MPR}}}\right]$
Equation 2.

It remains to show that the operations of eliminating loops and states create
summaries.

###### Lemma A.5 (Edge Collapse).

Let $M$ be a Markov chain, $i,j\in V$ two states with
$\mathop{p}\nolimits(i,j)=0$ and $S\subseteq V$ be a set of intermediate
states $x$ all satisfying $\mathop{p}\nolimits(x,j)=1$ and
$\mathop{p}\nolimits(k,x)=0$ for all $k\neq i$. Let $M^{\prime}$ be the Markov
chain obtained by simultaneously replacing all length-2-paths from $i$ to $j$
via $S$ by just one direct edge with the same expected reward and duration.
That is, in $M^{\prime}$ we have that

  * •

$\mathop{p}\nolimits^{\prime}(i,j)=\sum_{x\in S}\mathop{p}\nolimits(i,x)$

  * •

$\mathop{r}\nolimits^{\prime}(i,j)=\sum_{x\in
S}\mathop{p}\nolimits(i,x)(\mathop{r}\nolimits(x,i)+\mathop{r}\nolimits(x,j))$

  * •

$\mathop{d}\nolimits^{\prime}(i,j)=\sum_{x\in
S}\mathop{p}\nolimits(i,x)(\mathop{d}\nolimits(x,i)+\mathop{d}\nolimits(x,j))$

Then $M^{\prime}$ is a summary of $M$.

###### Proof.

For condition (1) in Definition A.3, notice that any two states $s,t\in V$
communicate in $M$ iff they do in $M^{\prime}$.

For point (2), recall that the probabilities $R:V\to\mathbb{R}$ of reaching a
set $C\subseteq V\setminus S$ of states are the least fixed-point satisfying

$R(s)=\begin{cases}1&\mbox{if }s\in C\\\ \inf\\{\sum_{k\in
V}\mathop{p}\nolimits(s,k)R(k)\\}&\mbox{otherwise}\\\ \end{cases}$

By definition of $M^{\prime}$ the sum in the second case can be rewritten as

$\displaystyle\sum_{k\in V}\mathop{p}\nolimits(i,k)R(k)$
$\displaystyle=\sum_{\begin{subarray}{c}s\neq i\\\ k\in
V\end{subarray}}\mathop{p}\nolimits(s,k)R(k)+\sum_{\begin{subarray}{c}s=i\\\
k\in V\setminus
S\end{subarray}}\mathop{p}\nolimits(i,k)R(k)+\sum_{\begin{subarray}{c}s=i\\\
k\in S\end{subarray}}\mathop{p}\nolimits(i,k)R(k)$
$\displaystyle=\sum_{\begin{subarray}{c}s\neq i\\\ k\in
V\end{subarray}}\mathop{p}\nolimits^{\prime}(s,k)R(k)+\sum_{\begin{subarray}{c}s=i\\\
k\in V\setminus
S\end{subarray}}\mathop{p}\nolimits^{\prime}(i,k)R(k)+\mathop{p}\nolimits^{\prime}(i,j)R(j)=\sum_{k\in
S}\mathop{p}\nolimits^{\prime}(s,k)R(k)$

We conclude that a least solution of the system of equations is the same for
$M$ and $M^{\prime}$, which implies the claim.

For (3), we show the claim for rewards only; the proof that expected total
durations on cycles is analogous. Pick a recurrent state $s$ and consider the
expectation Clearly, if state $i$ is not part of the same CCS as $s$ then
${\mathbb{E}}^{M}_{s}\left[{{\mathop{R}\nolimits_{s}}}\right]={\mathbb{E}}^{M^{\prime}}_{s}\left[{{\mathop{R}\nolimits_{s}}}\right]$.
So suppose now that $s,i$ and $j$ are part of the same CCS.

Note that by assumption on $M$, for every state $k\neq i$ in the same CCS it
holds that
${\mathbb{E}}^{M}_{k}\left[{{\mathop{H}\nolimits_{i}}}\right]<{\mathbb{E}}^{M}_{k}\left[{{\mathop{H}\nolimits_{S}}}\right]$
and therefore

(3)
${\mathbb{E}}^{M}_{k}\left[{{\mathop{R}\nolimits_{i}}}\right]={\mathbb{E}}^{M^{\prime}}_{k}\left[{{\mathop{R}\nolimits_{i}}}\right]$

We can split ${\mathbb{E}}^{M}_{i}\left[{{\mathop{R}\nolimits_{i}}}\right]$
into two parts, according to the disjoint cases or not a state of $S$ is
visited in the first step.

The first case is

(4)
${\mathbb{E}}^{M}_{i}\left[{{\mathop{R}\nolimits_{i}}\mid{\mathop{H}\nolimits_{S}}=1}\right]=\sum_{k\in
S}\mathop{p}\nolimits(i,k)\mathop{r}\nolimits(i,k)+{\mathbb{E}}^{M}_{k}\left[{{\mathop{R}\nolimits_{i}}}\right]=\mathop{p}\nolimits^{\prime}(i,j)+{\mathbb{E}}^{M}_{j}\left[{{\mathop{R}\nolimits_{i}}}\right]={\mathbb{E}}^{M^{\prime}}_{i}\left[{{\mathop{R}\nolimits_{i}}\mid{\mathop{H}\nolimits_{j}}=1}\right]$

The second case is

(5)
${\mathbb{E}}^{M}_{i}\left[{{\mathop{R}\nolimits_{i}}\mid{\mathop{H}\nolimits_{S}}>1}\right]=\sum_{k\notin
S}\mathop{p}\nolimits(i,k)\mathop{r}\nolimits(i,k)+{\mathbb{E}}^{M}_{k}\left[{{\mathop{R}\nolimits_{i}}}\right]=\sum_{k\notin
S}\mathop{p}\nolimits^{\prime}(i,k)\mathop{r}\nolimits(i,k)+{\mathbb{E}}^{M^{\prime}}_{k}\left[{{\mathop{R}\nolimits_{i}}}\right]={\mathbb{E}}^{M^{\prime}}_{i}\left[{{\mathop{R}\nolimits_{i}}\mid{\mathop{H}\nolimits_{j}}>1}\right]$

Using that the two events are disjoint we get

(6)
$\displaystyle{\mathbb{E}}^{M}_{i}\left[{{\mathop{R}\nolimits_{i}}}\right]$
$\displaystyle={\mathbb{E}}^{M}_{i}\left[{{\mathop{R}\nolimits_{i}}\mid{\mathop{H}\nolimits_{S}}=1}\right]+{\mathbb{E}}^{M}_{i}\left[{{\mathop{R}\nolimits_{i}}\mid{\mathop{H}\nolimits_{S}}>1}\right]$
$\displaystyle={\mathbb{E}}^{M^{\prime}}_{i}\left[{{\mathop{R}\nolimits_{i}}\mid{\mathop{H}\nolimits_{j}}=1}\right]+{\mathbb{E}}^{M^{\prime}}_{i}\left[{{\mathop{R}\nolimits_{i}}\mid{\mathop{H}\nolimits_{j}}>1}\right]={\mathbb{E}}^{M^{\prime}}_{i}\left[{{\mathop{R}\nolimits_{i}}}\right]$

For arbitrary $s$ we can write

(7) ${\mathbb{E}}^{M}_{s}\left[{{\mathop{R}\nolimits_{s}}}\right]=\sum_{n\geq
0}{\mathbb{E}}^{M}_{s}\left[{{\mathop{R}\nolimits_{i}}\mid{\mathop{N}\nolimits_{t}^{i}}=n}\right]$

where ${\mathop{N}\nolimits_{t}^{i}}$ denotes the number of times state $i$ is
visited between time $1$ and ${\mathop{H}\nolimits_{t}}$. Clearly the expected
reward sum is the same in $M$ and $M^{\prime}$ on paths that do not visit
state $i$.That is,
${\mathbb{E}}^{M}_{s}\left[{{\mathop{R}\nolimits_{t}}\mid{\mathop{N}\nolimits_{t}^{i}}=0}\right]={\mathbb{E}}^{M^{\prime}}_{s}\left[{{\mathop{R}\nolimits_{t}}\mid{\mathop{N}\nolimits_{t}^{i}}=0}\right]$.
Now each summand on the RHS of Equation 7 can be written as

$\displaystyle{\mathbb{E}}^{M}_{s}\left[{{\mathop{R}\nolimits_{i}}\mid{\mathop{N}\nolimits_{t}^{i}}=n}\right]$
$\displaystyle={\mathbb{E}}^{M}_{s}\left[{{\mathop{R}\nolimits_{i}}\mid{\mathop{N}\nolimits_{t}^{i}}=0}\right]+{\mathbb{E}}^{M}_{i}\left[{{\mathop{R}\nolimits_{i}}\mid{\mathop{N}\nolimits_{t}^{i}}=n}\right]+{\mathbb{E}}^{M}_{i}\left[{{\mathop{R}\nolimits_{t}}\mid{\mathop{N}\nolimits_{t}^{i}}=0}\right]$
$\displaystyle={\mathbb{E}}^{M}_{s}\left[{{\mathop{R}\nolimits_{i}}\mid{\mathop{N}\nolimits_{t}^{i}}=0}\right]+n\cdot{\mathbb{E}}^{M}_{i}\left[{{\mathop{R}\nolimits_{i}}}\right]+{\mathbb{E}}^{M}_{i}\left[{{\mathop{R}\nolimits_{t}}\mid{\mathop{N}\nolimits_{t}^{i}}=0}\right]$
$\displaystyle={\mathbb{E}}^{M^{\prime}}_{s}\left[{{\mathop{R}\nolimits_{i}}\mid{\mathop{N}\nolimits_{t}^{i}}=0}\right]+n\cdot{\mathbb{E}}^{M^{\prime}}_{i}\left[{{\mathop{R}\nolimits_{i}}}\right]+{\mathbb{E}}^{M^{\prime}}_{i}\left[{{\mathop{R}\nolimits_{t}}\mid{\mathop{N}\nolimits_{t}^{i}}=0}\right]$
$\displaystyle={\mathbb{E}}^{M^{\prime}}_{s}\left[{{\mathop{R}\nolimits_{t}}\mid{\mathop{N}\nolimits_{t}^{i}}=n}\right]$

where the second equality uses the Markov property and the third one is due to
Equations 6 and 7. This concludes the proof that $M^{\prime}$ is a summary of
$M$. ∎

$s$$n$$t$$\mathop{p}\nolimits(n,s)$$\mathop{r}\nolimits(n,s)$$\mathop{d}\nolimits(n,s)$$\mathop{p}\nolimits(n,t)$$\mathop{r}\nolimits(n,t)$$\mathop{d}\nolimits(n,t)$$\mathop{p}\nolimits(n,t)$$\mathop{r}\nolimits(n,t)$$\mathop{d}\nolimits(n,t)$$s$$[s,n,t]$$[s,t]$$t$$\mathop{p}\nolimits(s,n)\mathop{p}\nolimits(n,t)$$\mathop{r}\nolimits(s,n)+\mathop{r}\nolimits(n,t)$$\mathop{d}\nolimits(s,n)+\mathop{d}\nolimits(n,t)$$1$$0$$0$$\mathop{p}\nolimits(n,t)$$\mathop{r}\nolimits(n,t)$$\mathop{d}\nolimits(n,t)$$1$$0$$0$$s$$t$$\mathop{p}\nolimits^{\prime}(n,t)$$\mathop{r}\nolimits^{\prime}(n,t)$$\mathop{d}\nolimits^{\prime}(n,t)$
Figure 4. State elimination: On the left is (part of a) Markov chain $M$
before removing state $n$ and on the right is the corresponding part of Markov
chain $M^{\prime}$. In the middle is the intermediate step $M^{\prime\prime}$
as constructed in the proof of Lemma 5.2. The probability, and expected
duration and reward, of moving from state $i$ to $j$ remains untouched.

###### Proof of Lemma 5.2.

To show that eliminating states preserves the mean-payoff ratio values we
split the transformation from $M$ to $M^{\prime}$ in two steps via an
intermediate Markov chain $M^{\prime\prime}$ and argue that $M^{\prime}$ is a
summary of $M^{\prime\prime}$ which in turn is a summary of $M$. The claim
then follows from Lemma A.4.

We define $M^{\prime\prime}$ from $M$ by introducing new intermediate states
$[s,n,t]$ and $[s,t]$ between any two states $s,t\in V$ of $M$, replacing
length-two paths from $s$ to $t$ via $n$ by paths via $[s,n,t]$, and length-
one paths from $s$ to $t$ by paths via $[s,t]$. See Figure 4 for an
illustration. Formally,

$\displaystyle\mathop{p}\nolimits^{\prime\prime}(s,n)$
$\displaystyle=0;\quad\mathop{p}\nolimits^{\prime\prime}(s,[s,n,t])=\mathop{p}\nolimits(s,n)\mathop{p}\nolimits(n,t);\quad\mathop{p}\nolimits^{\prime\prime}([s,n,t],t)=1;\text{
and }\quad\mathop{p}\nolimits^{\prime\prime}(k,[s,n,t])=0\text{ for all $k\neq
s$}.$

The rewards and durations incurred on those steps are

$\displaystyle\mathop{r}\nolimits^{\prime\prime}(s,[s,n,t])$
$\displaystyle=\mathop{r}\nolimits(s,t)+\mathop{r}\nolimits(n,t);$
$\displaystyle\mathop{d}\nolimits^{\prime\prime}(s,[s,n,t])$
$\displaystyle=\mathop{d}\nolimits(s,t)+\mathop{d}\nolimits(n,t);\quad\text{
and }$ $\displaystyle\mathop{r}\nolimits^{\prime\prime}([s,n,t],t)$
$\displaystyle=\mathop{d}\nolimits^{\prime\prime}([s,n,t],t)=0.$

Any path from $s$ to $t$ via the new state $[s,t]$ in $M^{\prime}$ directly
corresponds to a length-one path $s\to t$ in $M^{\prime}$.

$\displaystyle\mathop{p}\nolimits^{\prime\prime}(s,[s,t])=\mathop{p}\nolimits(s,t);\text{
and }\quad\mathop{p}\nolimits^{\prime\prime}([s,t],t)=1$

The rewards and durations incurred on those steps are

$\displaystyle\mathop{r}\nolimits^{\prime\prime}(s,[s,t])=\mathop{r}\nolimits(s,t);\quad\mathop{d}\nolimits^{\prime\prime}(s,[s,t])=\mathop{d}\nolimits(s,t)\text{
and
}\quad\mathop{r}\nolimits^{\prime\prime}([s,t],t)=\mathop{d}\nolimits^{\prime\prime}([s,t],t)=0.$

Notice that for any fixed pair $i,j\neq n$ of states, $S=\\{[i,j],[i,n,j]\\}$
satisfies the assumption of Lemma A.5 and $M^{\prime}$ is result of collapsing
them accordingly. So by multiple applications of Lemma A.5 we observe that
$M^{\prime}$ is a summary of $M^{\prime\prime}$. It remains to show that
$M^{\prime\prime}$ is a summary of $M$.

For (1), just notice that going from $M$ to $M^{\prime\prime}$ does not change
which states in $s,t\in V$ communicate: they do in $M$ iff they do in
$M^{\prime\prime}$. The newly introduced states $[s,t]$ and $[s,n,t]$ are in a
CCS $C$ iff $s,n\in C$.

For (2), first recall that reaching a set $C\subseteq V$ is an open objective
and thus can be expressed as the countable sum

(8)
$\mathbb{P}^{M}_{s}\left({{{\mathop{H}\nolimits_{C}}}<\infty}\right)=\sum_{\begin{subarray}{c}\pi=s_{0}s_{1}\ldots
s_{k}\in V^{*}\\\ s_{0}=s\land s_{k}\in
C\end{subarray}}\mathop{p}\nolimits(\pi)$

where
$\mathop{p}\nolimits(\pi)=\prod_{i=1}^{k}\mathop{p}\nolimits(s_{i-1},s_{i})$
is the product of probabilities along $\pi$. We observe that there is an
obvious isomorphism $f:V^{*}\to V(V^{\prime\prime})^{*}V$ between finite paths
in $M$ that lead from $s$ to $C$, and those in $M^{\prime\prime}$ that lead
from $s$ to $C$, which preserves probability mass: simply let
$f(inj)=i[i,n,j]j$ and $f(ij)=i[ij]j$. Then
$\mathop{p}\nolimits(\pi)=\mathop{p}\nolimits^{\prime\prime}(f(\pi))$. We can
decompose
$\mathbb{P}^{M^{\prime\prime}}_{s}\left({{{\mathop{H}\nolimits_{C}}}<\infty}\right)$
as in Equation 8 but since neither source nor target consists of states in
$V^{\prime\prime}\setminus V$ we have that

$\mathbb{P}^{M}_{s}\left({{{\mathop{H}\nolimits_{C}}}<\infty}\right)=\sum_{\begin{subarray}{c}\pi=s_{0}s_{1}\ldots
s_{k}\in V^{*}\\\ s_{0}=s\land s_{k}\in
C\end{subarray}}\mathop{p}\nolimits(\pi)=\sum_{\begin{subarray}{c}\pi=s_{0}s_{1}\ldots
s_{k}\in V^{*}\\\ s_{0}=s\land s_{k}\in
C\end{subarray}}\mathop{p}\nolimits^{\prime\prime}(f(\pi))=\sum_{\begin{subarray}{c}\pi^{\prime\prime}=s_{0}s_{1}\ldots
s_{k}\in V(V^{\prime\prime})^{*}V\\\ s_{0}=s\land s_{k}\in
C\end{subarray}}\mathop{p}\nolimits^{\prime\prime}(\pi^{\prime\prime})=\mathbb{P}^{M^{\prime\prime}}_{s}\left({{{\mathop{H}\nolimits_{C}}}<\infty}\right).$

Point (3) follows analogously to point (2) above. We have that

${\mathbb{E}}^{M}_{s}\left[{{\mathop{R}\nolimits_{s}}}\right]=\sum_{\begin{subarray}{c}\pi=s_{0}s_{1}\ldots
s_{k}\in V^{*}\\\
s_{0}=s=s_{k}\end{subarray}}\mathop{p}\nolimits(\pi)\cdot\mathop{r}\nolimits(\pi)=\sum_{\begin{subarray}{c}\pi=s_{0}s_{1}\ldots
s_{k}\in V^{*}\\\
s_{0}=s=s_{k}\end{subarray}}\mathop{p}\nolimits^{\prime\prime}(f(\pi))\cdot\mathop{r}\nolimits^{\prime\prime}(f(\pi))={\mathbb{E}}^{M^{\prime\prime}}_{s}\left[{{\mathop{R}\nolimits_{s}}}\right]$

where
$\mathop{r}\nolimits(\pi)=\sum_{i=1}^{{\left|\pi\right|}}\mathop{r}\nolimits(s_{i-1},s_{i})$
is the total reward along path $\pi$. ∎

$n$i$j$$\mathop{p}\nolimits(n,n)$$\mathop{r}\nolimits(n,n)$$\mathop{d}\nolimits(n,n)$
$\mathop{p}\nolimits(n,j)$$\mathop{r}\nolimits(n,j)$$\mathop{d}\nolimits(n,j)$$\mathop{p}\nolimits(n,i)$$\mathop{r}\nolimits(n,i)$$\mathop{d}\nolimits(n,i)$$n$$[n,\ell,i]$$[n,\ell,j]$$i$$j$$\mathop{p}\nolimits(n,n)^{\ell}\mathop{p}\nolimits(n,j)$$\ell\cdot\mathop{r}\nolimits(n,n)$$\ell\cdot\mathop{d}\nolimits(n,n)$$1$$\mathop{r}\nolimits(n,j)$$\mathop{d}\nolimits(n,j)$$\mathop{p}\nolimits(n,n)^{\ell}\mathop{p}\nolimits(n,i)$$\ell\cdot\mathop{r}\nolimits(n,n)$$\ell\cdot\mathop{d}\nolimits(n,n)$$1$$\mathop{r}\nolimits(n,i)$$\mathop{d}\nolimits(n,i)$$n$$i$$j$$\mathop{p}\nolimits^{\prime}(n,j)$$\mathop{r}\nolimits^{\prime}(n,j)$$\mathop{d}\nolimits^{\prime}(n,j)$$\mathop{p}\nolimits^{\prime}(n,i)$$\mathop{r}\nolimits^{\prime}(n,i)$$\mathop{d}\nolimits^{\prime}(n,i)$
Figure 5. Loop elimination: On the left is (part of the) Markov chain $M$
before eliminating the self-loop in vertex $n$; On the right is the resulting
chain $M^{\prime}$. In the middle is the intermediate chain $M^{\prime\prime}$
with the countably infinite edges between $n$ and auxiliary state
$n^{\prime}$. Taking the $\ell$th edge represents taking the loop $\ell$
times.

###### Proof of Lemma 5.4.

Consider the Markov chain $M$ and let $n$ be the state whose loop is
eliminated. We define an intermediate Markov chain $M^{\prime\prime}$ that
replaces the self-loop by a countably infinite number of new states, each of
which represents a fixed number of iterations of the loop.

That is $M^{\prime\prime}$ is obtained from $M$ as follows. For every
$\ell\geq 0$ and $j\neq n$ there is a new state $[n,\ell,j]$. We let

$\displaystyle\mathop{p}\nolimits^{\prime\prime}(n,[n,\ell,j])$
$\displaystyle\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\mathop{p}\nolimits(n,n)^{\ell}\mathop{p}\nolimits(n,j)$
$\displaystyle\mathop{r}\nolimits^{\prime\prime}(n,[n,\ell,j])$
$\displaystyle\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\ell\cdot\mathop{r}\nolimits(n,n)$
$\displaystyle\mathop{d}\nolimits(n,[n,\ell,j])$
$\displaystyle\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\ell\cdot\mathop{d}\nolimits(n,n)$

and
$\mathop{p}\nolimits^{\prime\prime}([n,\ell,j],j)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}1$
and
$\mathop{r}\nolimits^{\prime\prime}([n,\ell,j],j)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\mathop{d}\nolimits^{\prime\prime}([n,\ell,j],j)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}0$.

Every original edge between states $i,j\neq n$ has the same probability,
reward and duration as in $M$. See also Figure 5 in the middle.

Intuitively, $M^{\prime\prime}$ is the (countably infinite) unfolding of the
self-loop around state $n$. Every path in $M$ that goes from $n$ to $j$ has