6.1. FIXED POINT CHARACTERISATION AND POSITIONAL DETERMINACY227

for all $j \ge 1$. Hence, by the induction assumption we get

$$ \mathbb{E}_{\sigma, \tau}^{u}[\lambda^{k+1}\mu(\pi_{k+1}) + (1-\lambda)\sum_{i=1}^{k+1} \lambda^{i-1}\mathbb{Q}\mathbb{R}_{\le k+1-i}(\pi) | \pi_1 = v] \ge \lambda\mu^*(v). $$

Therefore,

$$ \mathbb{E}_{\sigma, \tau}^{u}[\lambda^{k+1}\mu(\pi_{k+1}) + (1-\lambda)\sum_{i=1}^{k+1} \lambda^{i-1}\mathbb{Q}\mathbb{R}_{\le k+1-i}(\pi)] \ge \lambda \mathbb{E}_{\sigma, \tau}^{u}[\mu(\pi_1)] $$

and the right-hand side is equal to $\mathbb{E}_{\sigma, \tau}^{u}[\lambda\mu(\pi_1) + (1-\lambda)\mathbb{Q}\mathbb{R}_{\le 0}(\pi)] \ge \mu^*(u)$ because $\mathbb{E}_{\sigma, \tau}^{u}[\mathbb{Q}\mathbb{R}_{\le 0}(\pi)] = 0$. To finish the proof, we want to show that the limit

$$ \lim_{k \to \infty} \mathbb{E}_{\sigma, \tau}^{u}[\lambda^k \mu^*(\pi_k) + (1-\lambda) \sum_{i=1}^{k} \lambda^{i-1} \mathbb{Q}\mathbb{R}_{\le k-i}(\pi)] $$

exists and is equal to $\mathbb{E}_{\sigma, \tau}^{u}[\mathbb{Q}\mathbb{R}(\pi)]$. Since $0 \le \mu^*(u) \le 1$ for all $u$, we get the equality $\lim_{k \to \infty} \mathbb{E}_{\sigma, \tau}^{u}[\lambda^k \mu^*(\pi_k)] = 0$. Since $\mathbb{E}_{\sigma, \tau}^{u}[\mathbb{Q}\mathbb{R}_{\le k-i}(\pi)] \le \mathbb{E}_{\sigma, \tau}^{u}[\mathbb{Q}\mathbb{R}(\pi)]$ for all $k, i$, we get

$$ \mathbb{E}_{\sigma, \tau}^{u}[(1-\lambda)\sum_{i=1}^{k} \lambda^{i-1}\mathbb{Q}\mathbb{R}_{\le k-i}(\pi)] \le (1-\lambda^k)\mathbb{E}_{\sigma, \tau}^{u}[\mathbb{Q}\mathbb{R}(\pi)]. $$

This shows that

$$ \limsup_{k \to \infty} \mathbb{E}_{\sigma, \tau}^{u}[\lambda^k \mu^*(\pi_k) + (1-\lambda) \sum_{i=1}^{k} \lambda^{i-1} \mathbb{Q}\mathbb{R}_{\le k-i}(\pi)] \le \mathbb{E}_{\sigma, \tau}^{u}[\mathbb{Q}\mathbb{R}(\pi)]. $$

Furthermore, the monotone convergence theorem gives the equality $\mathbb{E}_{\sigma, \tau}^{u}[\mathbb{Q}\mathbb{R}(\pi)] = \lim_{k \to \infty} \mathbb{E}_{\sigma, \tau}^{u}[\mathbb{Q}\mathbb{R}_{\le k}(\pi)]$. Fix $\varepsilon > 0$ and $k_0$ such that $\mathbb{E}_{\sigma, \tau}^{u}[\mathbb{Q}\mathbb{R}(\pi)] - \varepsilon \le \mathbb{E}_{\sigma, \tau}^{u}[\mathbb{Q}\mathbb{R}_{\le k_0}(\pi)]$. Then, for every $k > k_0$ we have the bound

$$ \mathbb{E}_{\sigma, \tau}^{u}[\sum_{i=1}^{k} \lambda^{i-1} \mathbb{Q}\mathbb{R}_{\le k-i}(\pi)] \ge \mathbb{E}_{\sigma, \tau}^{u}[\sum_{i=1}^{k-k_0} \lambda^{i-1} \mathbb{Q}\mathbb{R}_{\le k-i}(\pi)], $$

so $\mathbb{E}_{\sigma, \tau}^{u}[\sum_{i=1}^{k} \lambda^{i-1} \mathbb{Q}\mathbb{R}_{\le k-i}(\pi)] \ge \frac{1-\lambda^{k-k_0}}{1-\lambda}(\mathbb{E}_{\sigma, \tau}^{u}[\mathbb{Q}\mathbb{R}(\pi)] - \varepsilon)$. By taking $k$ to infinity, we get $\mathbb{E}_{\sigma, \tau}^{u}[\mathbb{Q}\mathbb{R}(\pi)] - \varepsilon \le \liminf_{k \to \infty} \mathbb{E}_{\sigma, \tau}^{u}[\lambda^k \mu^*(\pi_k) + (1-\lambda) \sum_{i=1}^{k} \lambda^{i-1} \mathbb{Q}\mathbb{R}_{\le k-i}(\pi)]$. Since $\varepsilon$ was arbitrary, we get the existence of the limit. Therefore, we have shown that $\mathbb{E}_{\sigma, \tau}^{u}[\mathbb{Q}\mathbb{R}(\pi)] \ge \mu^*(u)$ for every $\tau$. The proof for Min is analogous, proving that $\mu^*$ is the value of the game. Since the value is unique, $\mathcal{O}^{\mathcal{G}}$ has a unique fixed point. Moreover, our proof shows the optimality of the strategies $(\sigma, \tau)$ constructed as in the statement of the theorem. $\square$

We can now use stochastic quantitative reachability games to prove the positional determinacy of reachability games.
*Proof of Theorem 72.* Let $\mathcal{G}$ be a stochastic reachability game. By Theorem 73, $\mathcal{G}$ has a value and an optimal pure positional strategy for Min. We need to show that Max also has such a strategy. To do so, for $0 < \lambda < 1$, let $\mathcal{G}_\lambda$ be the quantitative stochastic reachability game with parameter $\lambda$ played on the same arena as $\mathcal{G}$. By Theorem 74, $\mathcal{G}_\lambda$ is positionally determined. Furthermore, we have $0 \le \text{val}^{\mathcal{G}_\lambda}(u) \le 1$ for every $u$. Therefore, we can find an increasing sequence $\lambda_1 < \lambda_2 < \dots$ such that $\lim_{k \to \infty} \lambda_k = 1$, $\text{val}^{\mathcal{G}_\lambda}_k$ converges to some point, and every game $\mathcal{G}_\lambda$ has the same optimal pure positional strategy $\sigma$ of Max. We will show that $\sigma$ is optimal in $\mathcal{G}$. Let $\tau$ be any strategy of Min. Observe that for every $u$ and every $k$ we have

$$ \begin{aligned} \text{val}^{\mathcal{G}_k}(u) &\le \mathbb{E}_{\sigma, \tau}^{u}[\text{QuantitativeReach}(\pi)] = \sum_{i=0}^{\infty} \lambda^i \mathbb{P}_{\sigma, \tau}^{u}(\text{Reach}_i(\text{Win})) \\ &\le \mathbb{P}_{\sigma, \tau}^{u}(\text{Reach}(\text{Win})), \end{aligned} $$

where $\text{Reach}_i(\text{Win}) = \{\pi: \pi_i = \text{Win}, \pi_j \ne \text{Win} \text{ for } j < i\}$. By taking $\tau$ to be the optimal pure positional strategy for Min in $\mathcal{G}$, we get $\lim_{k \to \infty} \text{val}^{\mathcal{G}_k}(u) \le \text{val}^{\mathcal{G}}(u)$. Furthermore, note that for every $\xi: V \to [0, 1]$, we have $\|\mathcal{O}^{\mathcal{G}_\lambda}(\xi) - \mathcal{O}^{\mathcal{G}}(\xi)\|_{\infty} \le (1-\lambda)$. Since $\text{val}^{\mathcal{G}_k}$ is the fixed point of $\mathcal{O}^{\mathcal{G}_\lambda}$ by Theorem 73, we get $\|\text{val}^{\mathcal{G}_k} - \mathcal{O}^{\mathcal{G}}(\text{val}^{\mathcal{G}_k})\|_{\infty} \le (1-\lambda_k)$ for all $k$. Hence, the continuity of $\mathcal{O}^{\mathcal{G}}$ implies that $\text{val}^{\mathcal{G}_k}$ converges to a fixed point of $\mathcal{O}^{\mathcal{G}}$. Therefore, by Theorem 74, we get $\lim_{k \to \infty} \text{val}^{\mathcal{G}_k} = \text{val}^{\mathcal{G}}$, which implies that $\mathbb{P}_{\sigma, \tau}^{u}(\text{Reach}(\text{Win})) \ge \text{val}^{\mathcal{G}}(u)$ for any $\tau$. $\square$

## 6.2 Normalisation: stopping, binary, simple

### 6.2.1 Normalised games

We say that $\sigma$ is almost-surely winning from $u$ is for all strategies $\tau$ of Min, we have $\mathbb{P}_{\sigma, \tau}^{u}(W) = 1$. The almost-sure winning region is the set of vertices from where Max has an almost-surely winning strategy. Similarly, $\sigma$ is positively winning from $u$ if for all strategies $\tau$ of Min, we have $\mathbb{P}_{\sigma, \tau}^{u}(W) > 0$, and the positive winning region is the set of vertices from where Max has a positively winning strategy. Let us write $W_{>0}(\mathcal{G})$ for the positively winning region, and $W_{=1}(\mathcal{G})$ for the almost surely winning region.

**Theorem 75.** There exists an algorithm for computing the positively winning region of stochastic reachability games in time $O(m)$.

Analogously to attractor computations in reachability games (cf. Section 2.1), we define a one-step positive probability predecessor operator $\text{Pre}_{>0}$ as follows: for $X \subseteq V$ we put

$$ \text{Pre}_{>0}(X) = \{u \in V_{\text{Max}} : \exists u \to v \in E, v \in X\} \\ \cup \{u \in V_{\text{Min}} : \forall u \to v \in E, v \in X\} \\ \cup \{u \in V_{\text{Random}} : \exists u \to v \in E, v \in X \text{ and } \delta(u)(u \to v) > 0\}. $$

Let us define an operator on subsets of vertices:

$$ X \mapsto \text{Win} \cup \text{Pre}_{>0}(X). $$
We note that this operator is monotonic when equipping the powerset of vertices with the inclusion preorder: if $X \subseteq X'$ then $\text{Pre}_{>0}(X) \subseteq \text{Pre}_{>0}(X')$. Hence Theorem 4 applies: this operator has a least fixed point computed by the following sequence: we let $X_0 = \emptyset$ and $X_i = \text{Win} \cup \text{Pre}_{>0}(X_{i-1})$. This constructs a sequence $(X_i)_{i \in \mathbb{N}}$ of non-decreasing subsets of $V$. Hence the sequence stabilises after at most $n-1$ steps, let us write $\text{Attr}_{>0}(\text{Win})$ for the limit. We have the following simple characterization of the positively winning set:

**Lemma 79 (Characterisation of the positively winning set).** Let $\mathcal{G}$ a stochastic reachability game. The positively winning region is the least fixed point of the operator $X \mapsto \text{Win} \cup \text{Pre}_{>0}(X)$.

*Proof.* We show two properties:

* For all $i$, we have $X_i \subseteq W_{>0}(\mathcal{G})$.

* $W_{>0}(\mathcal{G})$ is a pre-fixed point of $\text{Pre}_{>0}$.

The first property implies that $\text{Attr}_{>0}(\text{Win}) \subseteq W_{>0}(\mathcal{G})$, and the second the converse implication.

We prove the first property by induction on $i$. The case $i=0$ is clear. Let $v \in X_{i+1}$, either $v \in \text{Win}$ and then it is in $W_{>0}(\mathcal{G})$, or $v$ in $\text{Pre}_{>0}(X_i)$. In each of the three cases ($v \in V_{\text{Max}}, V_{\text{Min}}, V_{\text{Random}}$) we have a positive probability to land in $X_i$ at the next step. By induction hypothesis, $X_i \subseteq W_{>0}(\mathcal{G})$. Hence we have constructed a strategy winning positively from $v$, implying that $v \in W_{>0}(\mathcal{G})$.

We now prove the second property: $W_{>0}(\mathcal{G}) \subseteq \text{Win} \cup \text{Pre}_{>0}(W_{>0}(\mathcal{G}))$. Let $v \in W_{>0}(\mathcal{G})$, by definition either $v \in \text{Win}$ or there exists a move which yields a positive probability of winning after the next step, implying that $v \in \text{Pre}_{>0}(W_{>0}(\mathcal{G}))$. $\square$

Similarly as Section 2.1, we can compute the least fixed point of the operator $X \mapsto \text{Win} \cup \text{Pre}_{>0}(X)$ in time and space $O(m)$. To avoid repetitions, let us note that we can actually directly reduce to non-stochastic reachability games. Let $\mathcal{G}$ a stochastic reachability game, we construct a (non-stochastic) reachability game $\mathcal{G}'$ as follows. Max controls the vertices of Max and the random vertices, and Min the vertices of Min. This means that for each random vertex, Max chooses an outgoing edge with positive probability. We claim that Max has a positively winning strategy in $\mathcal{G}$ from $u$ if and only if Max has a winning strategy in $\mathcal{G}'$ from $u$. Indeed, the attractor computation in $\mathcal{G}'$ is exactly the positive attractor computation in $\mathcal{G}$.

**Theorem 76.** There exists an algorithm for computing the almost surely winning region of stochastic reachability games in time $O(n \cdot m)$.

**Lemma 80 (Fixed point characterisation of the almost surely winning region for stochastic reachability games).** Let $\mathcal{G}$ be a stochastic reachability game.

* If $\text{Attr}_{>0}(\text{Win}) = V$, then $W_{>0}(\mathcal{G}) = V$.

* If $\text{Attr}_{>0}(\text{Win}) \neq V$, we define $\mathcal{G}' = \mathcal{G} \setminus \text{Attr}_{\text{Min}}(V \setminus \text{Attr}_{>0}(\text{Win}))$, then $W_{>0}(\mathcal{G}) = W_{>0}(\mathcal{G}')$.
**Proof.** We prove the first item. Let $\sigma$ be a positively winning pure and positional strategy from $\text{Attr}_{>0}(\text{Win}) = V$. We argue that $\sigma$ wins almost surely everywhere. Note that there exists $N \in \mathbb{N}$ and $\eta > 0$ such that $\sigma$ ensures to reach Win within $N$ steps with probability at least $\eta$. A play consistent with $\sigma$ can be divided into infinitely many finite plays of length $N$. Since each of them has probability at least $\eta$ to reach Win, the infinite play has probability 1 to reach Win by the Borel-Cantelli lemma.

We now look at the second item. We first prove that $\text{Attr}_{\text{Min}}(V \setminus \text{Attr}_{>0}(\text{Win})) \subseteq W_{=0}(\mathcal{G})$, the set of vertices where Min can ensure to reach Win with probability 0. Let $\tau_a$ denote an attractor strategy ensuring to reach $V \setminus \text{Attr}_{>0}(\text{Win})$ from $\text{Attr}_{\text{Min}}(V \setminus \text{Attr}_{>0}(\text{Win}))$, and $\tau_c$ a strategy ensuring reach Win with probability 0. We construct the strategy $\tau$ as the disjoint union of $\tau_a$ and $\tau_c$:

$$ \tau(v) = \begin{cases} \tau_a(v) & \text{if } v \in \text{Attr}_{\text{Min}}(V \setminus \text{Attr}_{>0}(\text{Win})) \setminus (V \setminus \text{Attr}_{>0}(\text{Win})), \\ \tau_c(v) & \text{if } v \in V \setminus \text{Attr}_{>0}(\text{Win}). \end{cases} $$

Any play consistent with $\tau$ is first consistent with $\tau_a$ until reaching $V \setminus \text{Attr}_{>0}(\text{Win})$ and then is consistent with $\tau_c$ and stays there forever. Thus we have proved that $\text{Attr}_{\text{Min}}(V \setminus \text{Attr}_{>0}(\text{Win})) \subseteq W_{=0}(\mathcal{G})$, implying $W_{>0}(\mathcal{G}) \subseteq V \setminus \text{Attr}_{\text{Min}}(V \setminus \text{Attr}_{>0}(\text{Win}))$.

We now show that $W_{>0}(\mathcal{G}') \subseteq W_{>0}(\mathcal{G})$, which implies the converse inclusion. Consider a positively winning strategy from $W_{>0}(\mathcal{G}')$ in $\mathcal{G}'$, it induces a positively winning strategy in $\mathcal{G}$. $\square$

The algorithm is presented in pseudocode in Algorithm 6.1. For the complexity analysis, the algorithm performs at most $n$ recursive calls and each of them involves two positive attractor computations, implying the time complexity $O(n \cdot m)$.

<caption>**Algorithm 6.1:** The quadratic time algorithm for the almost-sure winning region in stochastic reachability games.</caption>

**Data:** A stochastic reachability game.

**Function** Solve($\mathcal{G}$):
$X \leftarrow \text{Attr}_{>0}(\text{Win})$
if $X = V$ then
  $\lfloor$ return $V$
else
  Let $\mathcal{G}' = \mathcal{G} \setminus \text{Attr}_{\text{Min}}(V \setminus X)$
  $\lfloor$ return Solve($\mathcal{G}'$)

Another point of view on this algorithm is to directly reduce the problem to Büchi games. Let $\mathcal{G}$ a stochastic reachability game, we construct a (non-stochastic) Büchi game $\mathcal{G}'$ as follows. Max controls the vertices of Max, and Min the vertices of Min and the random vertices. For each random vertex, Min can either choose an outgoing edge, or let Max choose one herself. If he chooses, the edge has priority 2, and if she does, the edge has priority 1. We add a self-loop over Win with priority 2. We claim that Max has an almost-surely winning strategy in $\mathcal{G}$ from $u$ if and only if Max has a winning strategy in $\mathcal{G}'$ from $u$. Indeed, a closer look at the fixed point computations reveals that the algorithm for Büchi games in $\mathcal{G}'$ performs the exact same steps as Algorithm 6.1.
**Definition 20** (Normalised stochastic reachability games). We say that a stochastic reachability game is normalised if there is a unique almost-surely winning vertex Win and a unique vertex Lose which is not positively winning, and both are sinks.

**Lemma 81** (Reduction to normalised games). Let $\mathcal{G}$ a stochastic reachability game, we can compute a normalised game $\mathcal{G}'$ in time $O(n \cdot m)$ so that for all vertices $u$ from $\mathcal{G}$, we have $\text{val}^{\mathcal{G}}(u) = \text{val}^{\mathcal{G}'}(u)$ (unless it is 0 or 1, and then it is merged into Win or Lose).

We compute both the almost-surely and positively winning regions, and replace the set of almost-surely vertices by Win, and the complement of the set of positively winning vertices by Lose.

### 6.2.2 Simple stochastic games

**Definition 21** (Binary stochastic games). We say that a stochastic game is binary if:

* it is normalised,

* every vertex except for Win and Lose have out-degree two,

* for every random vertex $u \in V_{\text{Random}}$ we have $\delta(u) = \frac{1}{2} \cdot v + \frac{1}{2} \cdot v'$ for some $v, v'$.

**Lemma 82** (Reduction from stochastic games to simple stochastic games). Let $\mathcal{G}$ a stochastic reachability game, we can compute a simple stochastic game in polynomial time such that for all vertices $u$ from $\mathcal{G}$, we have $\text{val}^{\mathcal{G}}(u) = \text{val}^{\mathcal{G}'}(u)$. The game $\mathcal{G}'$ has $O(n \cdot (\log(n) + k))$ vertices, where $k$ is the number of bits required to represent probabilities in $\mathcal{G}$.

*Proof.* Let $v \in V_{\text{Random}}$ a random vertex with $k$ outgoing edges, with probabilities $p_1, \dots, p_k$, leading to $v_1, \dots, v_k$. We first introduce intermediary vertices in order to build a binary tree, whose leaves are $v_1 \dots v_k$, root is $v$, and probabilities are set at each level of the tree in order to recover $p_1, \dots, p_k$ on the respective branches. This introduces $O(\log(k))$ fresh vertices, and is illustrated on an example on Figure 6.3.

The same process can be applied to vertices in $V_{\text{Max}}$ and $V_{\text{Min}}$ (without probabilities) to reduce to out-degree 2.

<figure><img src="image_52.png" /><figcaption>Figure 6.3: From general random vertices to binary ones.</figcaption></figure>
It remains to explain how to simulate a distribution $\delta(u) = \frac{p}{q} \cdot v + \frac{q-p}{q} \cdot v'$ using only probabilities $\frac{1}{2}$. Let us denote the binary encodings (with most significant bit first) of $p$ and $q-p$ as $a_1 \cdots a_t$ resp. $b_1 \cdots b_t$. We build the following gadget. The input vertex is $u$ and for every $i \in [2, t+1]$, it has two exit edges with accumulated probabilities $2^{-i}$. Now, if $a_i = 1$, one outgoing edge leads to $v$, and similarly if $b_i = 1$, then one outgoing edge leads to $v'$. The remaining edges are redirected to $u$.

The transformation is illustrated in Figure 6.4, with $p = 11$ and $q = 14$. The binary encodings are 1011 for $p$ and 0011 for $p-q=3$. For simplicity some vertices are represented several times to avoid intricate transitions. One can check that this gadget indeed simulates probabilities $\frac{p}{q}$ to $v$ and $\frac{q-p}{q}$ to $v'$.

<figure><img src="image_53.png" /><figcaption>Figure 6.4: From binary random vertices to binary uniform ones.</figcaption></figure>

<figure><img src="image_54.png" /></figure>

### 6.2.3 Stopping games

The next lemmas will be useful in multiple proofs throughout the next sections. Note that if $(\sigma, \tau)$ is a pair of pure positional strategies of Max and Min, then the stochastic process induced on $V$ by fixing $(\sigma, \tau)$ is a Markov chain in which the state Win is absorbing. We denote by $C^{\sigma, \tau}$ the set of recurrent states in this Markov chain and we put $C^{\sigma} = \bigcup_{\tau} C^{\sigma, \tau}$.

**Lemma 83.** Let $\mathcal{G}$ be a stochastic reachability game and $\mu: V \to \mathbb{R}$ be any function. Take a pair of pure positional strategies $(\sigma, \tau)$ such that

$$ \forall u \in V_{\text{Max}} : \sigma(u) \in \operatorname{argmax} \{\mu(v) : u \to v \in E\}, $$

$$ \forall u \in V_{\text{Min}} : \tau(u) \in \operatorname{argmin} \{\mu(v) : u \to v \in E\}. $$

Then, we have the following two properties.

1. If $\mu$ satisfies $\mu \le \mathcal{O}^{\mathcal{G}}(\mu)$, $\mu(\text{Win}) = 1$, and $\mu(u) = 0$ for all $u \in C^{\sigma} \setminus \text{Win}$, then $\text{val}^{\mathcal{G}} \ge \text{val}^{\sigma} \ge \mu$.

2. If $\mu$ satisfies $\mu \ge \mathcal{O}^{\mathcal{G}}(\mu)$ and $\mu \ge 0$, then $\text{val}^{\mathcal{G}} \le \text{val}^{\tau} \le \mu$.

Before giving a proof, we note that in this lemma the operator $\mathcal{O}^{\mathcal{G}}$ is defined not only on functions $\mu: V \to [0, 1]$, but more generally on functions $\mu: V \to \mathbb{R}$.
**Proof.** We start by proving the first property. If $C^\sigma = V$, then the claim is trivial. Otherwise, let $\tau'$ be any pure positional strategy of Min and P be the transition matrix of the Markov chain obtained by fixing $(\sigma, \tau')$. By definition of $\mu$ and $\sigma$ we have $\mu \le \mathcal{O}^\mathcal{G}(\mu) \le P\mu$. Let $Q$ denote the matrix obtained from P by removing the rows and columns indexed by $C^{\sigma, \tau'}$. Furthermore, let $z$ be the vector defined as $z_u = P_{u, \text{Win}}$ for all $u \in V \setminus C^{\sigma, \tau'}$. Then, the theory of absorbing Markov chains, see, e.g., [KS76, Chapter III], implies that $Q^N \to 0$, $(I-Q)^{-1} = I+Q+Q^2+\dots$, and $\mathbb{P}_{\sigma, \tau'}^u(\text{Reach}(\text{Win})) = ((I-Q)^{-1}z)_u$ for every $u \in V \setminus C^{\sigma, \tau'}$. Let $\rho : (V \setminus C^{\sigma, \tau'}) \to \mathbb{R}$ denote the function obtained by restricting $\mu$ to the vertices in $V \setminus C^{\sigma, \tau'}$. Then, $\mu \le P\mu$ implies that $\rho \le z+Q\rho$ (note that here we use the fact that $\mu(\text{Win}) = 1$ and $\mu(u) = 0$ for $u \in C^{\sigma, \tau'}$). Hence, for every $N \ge 1$ we get $\rho \le (I+Q+\dots+Q^N)z+Q^{N+1}\rho \to (I-Q)^{-1}z$. In particular, $\mathbb{P}_{\sigma, \tau'}^u(\text{Reach}(\text{Win})) \ge \mu(u)$ for all $u$. Since $\tau'$ was arbitrary, positional determinacy implies that $\text{val}^\mathcal{G} \ge \text{val}^\sigma \ge \mu$.

The proof of the second property is analogous. Note that $\mu(\text{Win}) \ge 1$ by definition. Let $\sigma'$ be any pure positional strategy of Max and P be the transition matrix of the Markov chain obtained by fixing $(\sigma', \tau)$. If $C^{\sigma', \tau} = V$, then $\mathbb{P}_{\sigma', \tau}^u(\text{Reach}(\text{Win})) = 0$ for all $u \ne \text{Win}$ so $\mu(u) \ge \mathbb{P}_{\sigma', \tau}^u(\text{Reach}(\text{Win}))$ for all $u$. Otherwise, let $Q, z, \rho$ be defined as in the previous proof. By definition of $\tau, \mu$ we get $\mu \ge P\mu$, which implies that $\rho \ge z+Q\rho$ (note that this implication only uses the fact that $\mu(\text{Win}) \ge 1$ and $\mu \ge 0$). As previously, this inequality implies that $\mu(u) \ge \mathbb{P}_{\sigma', \tau}^u(\text{Reach}(\text{Win}))$ for all $u$, which gives the claim. $\square$

The second lemma characterises absorption probabilities in Markov chains with rational transition probabilities. We refer to [Sko21, AdMS21] for the proof.

**Lemma 84.** Suppose that P is a square stochastic matrix with rational entries whose common denominator is D. Furthermore, let K denote the number of rows of P with at least two nonzero entries and suppose that $P_{vv} = 1$ for some index v. Consider a Markov chain with transition matrix given by P. Then, there exists a natural number $M \le D^K$ such that for every state u the probability that the chain starting at u reaches v is a rational number of the form $a_{uv}/M$, where $a_{uv} \in \mathbb{N}$.

To apply the lemma above to stochastic reachability games, we use the following notation. We suppose that D is the common denominator of all transition probabilities of $\mathcal{G}$ and that K is the number of significant random vertices, i.e., random vertices u such that $\delta(u)(v) > 0$ for at least two different v.

**Corollary 18.** The value of the game $\mathcal{G}$ is a vector of rational numbers whose lowest common denominator is not greater than $D^K$.

**Proof.** Let $(\sigma, \tau)$ be a pair of optimal pure positional strategies in $\mathcal{G}$. Then, $\text{val}^\mathcal{G}(u) = \mathbb{P}_{\sigma, \tau}^u(\text{Reach}(\text{Win}))$ for all $u$. Hence, the claim follows from Lemma 84. $\square$

**Remark 11.** We note that, as discussed in [Sko21, AdMS21], the bound $M \le D^K$ in Lemma 84 and Corollary 18 can be improved in the following way: if we denote by $d_u$ the lowest common denominator of the transition probabilities of a random vertex $u$, then $M \le \prod_u d_u \le D^K$. For the sake of simplicity, we use the bound $M \le D^K$ in our proofs, but this can be replaced by $M \le \prod_u d_u$.
We now define the stopping stochastic reachability games. To do so, we suppose that the graph of the game is equipped with a special state Lose that is distinct from Win and that has only one outgoing edge, which is a loop going back to Lose. In particular, if a game reaches Lose, then it never leaves this state, and player Max cannot reach Win any more.

**Definition 22** (Stopping stochastic reachability games). A stochastic reachability game is stopping if for every vertex $u \in V$ and every pair of pure positional strategies $(\sigma, \tau)$ we have $\mathbb{P}_{\sigma, \tau}^{u}(\text{Reach}(\{\text{Win}, \text{Lose}\})) = 1$.

The following lemma shows that the condition of Definition 22 can be replaced by a seemingly weaker one.

**Lemma 85.** A stochastic reachability game is stopping if for every vertex $u \in V$ and every pair of pure positional strategies $(\sigma, \tau)$ we have $\mathbb{P}_{\sigma, \tau}^{u}(\text{Reach}(\{\text{Win}, \text{Lose}\})) > 0$.

*Proof.* Suppose that a Markov chain defined by $(\sigma, \tau)$ can reach the set $\{\text{Win}, \text{Lose}\}$ from any starting state $u$. Since the states Win, Lose are absorbing, this implies that they are the only recurrent states of the chain, so $\mathbb{P}_{\sigma, \tau}^{u}(\text{Reach}(\{\text{Win}, \text{Lose}\})) = 1$. $\square$

**Theorem 77** (Fixed point characterisation for stopping simple stochastic games). Let $\mathcal{G}$ be a stopping stochastic reachability game. Then, the operator $\mathcal{O}^{\mathcal{G}}$ has a unique fixed point $\mu$ such that $\mu(\text{Lose}) = 0$, namely $\mu = \text{val}^{\mathcal{G}}$. Moreover, pure positional strategies $(\sigma, \tau)$ of Max and Min are optimal if and only if they satisfy

$$ \begin{aligned} \forall u \in V_{\text{Max}} : & \sigma(u) \in \operatorname*{argmax}_{\mathcal{G}} \{\text{val}^{\mathcal{G}}(v) : u \to v \in E\}, \\ \forall u \in V_{\text{Min}} : & \tau(u) \in \operatorname*{argmin}_{\mathcal{G}} \{\text{val}^{\mathcal{G}}(v) : u \to v \in E\}. \end{aligned} $$

*Proof.* Let $\mu$ be any fixed point of $\mathcal{O}^{\mathcal{G}}$ such that $\mu(\text{Lose}) = 0$ (by Theorem 73, $\text{val}^{\mathcal{G}}$ is one such point). Let $\sigma, \tau$ be a pair of pure positional strategies such that $\sigma(u) \in \operatorname*{argmax}_{\mathcal{G}} \{\mu(v) : u \to v \in E\}$ for all $u \in V_{\text{Max}}$ and $\tau(u) \in \operatorname*{argmin}_{\mathcal{G}} \{\mu(v) : u \to v \in E\}$ for all $u \in V_{\text{Min}}$. Since the game is stopping, we have $C^{\sigma} = \{\text{Win}, \text{Lose}\}$. In particular, the pair $(\mu, \sigma)$ satisfies the conditions of Lemma 83 and therefore $\mu \le \text{val}^{\mathcal{G}}$. Likewise, the pair $(\mu, \tau)$ satisfies the conditions of Lemma 83, so $\mu \ge \text{val}^{\mathcal{G}}$. Thus, $\mu = \text{val}^{\mathcal{G}}$ and Lemma 83 show that $\sigma, \tau$ are optimal. Suppose now that $\tau$ is a pure positional strategy of Min such that $\tau(u) \notin \operatorname*{argmin}_{\mathcal{G}} \{\text{val}^{\mathcal{G}}(v) : u \to v \in E\}$ for some $u \in V_{\text{Min}}$. Then, $\text{val}^{\mathcal{G}} \neq \mathcal{O}^{\mathcal{G}}[\tau](\text{val}^{\mathcal{G}})$. Hence, by Theorem 73, $\text{val}^{\tau} \neq \text{val}^{\mathcal{G}}$ and $\tau$ is not optimal. The proof for player Max is analogous. $\square$

**Lemma 86** (Reduction to stopping games). Let $\mathcal{G}$ be a stochastic reachability game. We can compute a stopping game $\mathcal{G}'$ such that any pair of optimal pure stationary strategies in $\mathcal{G}'$ is also optimal in $\mathcal{G}$. Moreover, for all vertices $u$ in $\mathcal{G}$, we have $\text{val}^{\mathcal{G}}(u) > \frac{1}{2}$ if and only if $\text{val}^{\mathcal{G}}(u) > \frac{1}{2}$.

*Proof.* For every $0 < \varepsilon < 1$, we construct the game $\mathcal{G}^{\varepsilon}$ in the following way. First, we add a state Lose to $\mathcal{G}$. Then, for every edge $u \to v \in E$ such that $u \neq \text{Lose}$ we add a new random vertex $w_{uv}$ to the graph. We remove the edge $u \to v$ and add the edges $u \to w_{uv}$, $w_{uv} \to v$, and $w_{uv} \to \text{Lose}$, as in Figure 6.5. We also define the transition function $\delta^{\varepsilon}$
of the new game as follows. For every random state $u$ of the original game we put $\delta^\epsilon(u)(w_{uv}) = \delta(u)(v)$ for all $v$, and for every new state $w_{uv}$ we put $\delta^\epsilon(w_{uv})(\text{Lose}) = \epsilon$ and $\delta^\epsilon(w_{uv})(v) = 1 - \epsilon$.

<figure><img src="image_55.png" /><figcaption>Figure 6.5: From reachability games to stopping games.</figcaption></figure>

We also consider the game $\mathscr{G}^0$ obtained by putting $\epsilon = 0$, i.e., a game that is identical to the original game $\mathscr{G}$ except for the fact that we added an isolated vertex Lose to the graph and we put a dummy vertex on every edge of the graph. In particular, the game $\mathscr{G}^0$ has the same optimal pure stationary strategies as $\mathscr{G}$. Furthermore, every vertex of $\mathscr{G}$ has the same value in $\mathscr{G}$ and in $\mathscr{G}^0$. Let $D$ denote the lowest common denominator of all transition probabilities in $\mathscr{G}$. Furthermore, let $K$ be the number of random vertices in $\mathscr{G}$. By Corollary 18, the values of the game $\mathscr{G}^0$ are rational numbers with lowest common denominator not higher than $D^K$. Let $\epsilon = \min\{\frac{1}{4}, D^{-2K}\}$. We will show that $\mathscr{G}' = \mathscr{G}^\epsilon$ satisfies the claim.

To begin, note that $\mathscr{G}'$ is stopping. Indeed, if we fix any pair of pure positional strategies $(\sigma, \tau)$ in $\mathscr{G}'$ and suppose that the resulting Markov starts at some state $u$, then this chain can reach the set $\{\text{Win}, \text{Lose}\}$, so $\mathscr{G}'$ is stopping by Lemma 85. Furthermore, note that if $\xi$ is any vector with entries in $[0, 1]$ and such that $\xi_{\text{Lose}} = 0$, then $\mathscr{O}^{\mathscr{G}'}(\xi) \le \mathscr{O}^{\mathscr{G}^0}(\xi) \le \epsilon + \mathscr{O}^{\mathscr{G}'}(\xi)$, where the notation $\epsilon + \mathscr{O}^{\mathscr{G}'}(\xi)$ means that we add $\epsilon$ to all coordinates of $\mathscr{O}^{\mathscr{G}'}(\xi)$. Let $\xi = \text{val}^{\mathscr{G}'}$ and suppose that $\sigma, \tau$ are optimal pure positional strategies of Max and Min in $\mathscr{G}'$. We want to show that $(\sigma, \tau)$ are also optimal in $\mathscr{G}^0$. By Theorem 77, we have $\sigma(u) \in \text{argmax}\{\xi(v) : u \to v \in E\}$ for all $u \in V_{\text{Max}}$ and $\tau(u) \in \text{argmin}\{\xi(v) : u \to v \in E\} = \text{argmin}\{\epsilon + \xi(v) : u \to v \in E\}$ for all $u \in V_{\text{Min}}$. Since $\xi \ge 0$, Lemma 83 implies that $\text{val}^{\mathscr{G}^0} \le \epsilon + \xi$ and that the same is true if Min uses $\tau$ in $\mathscr{G}^0$. Suppose that $u$ is any state in $\mathscr{G}^0$ different than Win and that there exists a pure positional strategy $\tau'$ of Min such that $u$ is recurrent in the Markov chain induced by fixing $(\sigma, \tau')$ in $\mathscr{G}^0$. In this situation, the chain starting at $u$ cannot reach Win. Hence, if we consider the Markov chain induced by fixing $(\sigma, \tau')$ in $\mathscr{G}'$, then this chain also cannot reach Win from $u$. By optimality of $\sigma$ this implies that $\xi_u = 0$. Since $\xi_{\text{Win}} = 1$, Lemma 83 implies that $\text{val}^{\mathscr{G}'} \le \text{val}^{\mathscr{G}^0}$ and the same is true if Max uses $\sigma$ in $\mathscr{G}^0$. Hence, we established the inequality $\text{val}^{\mathscr{G}'} \le \text{val}^{\mathscr{G}^0} \le \epsilon + \text{val}^{\mathscr{G}'}$. Let $u$ be any state. Note that, by definition of $\epsilon$, the interval $[\text{val}^{\mathscr{G}'}(u), \epsilon + \text{val}^{\mathscr{G}'}(u)]$ can contain at most one rational number of denominator at most $D^K$. Moreover, $\text{val}^{\mathscr{G}^0}(u)$ is such a number. If we now consider the one-player game obtained from $\mathscr{G}^0$ by fixing $\tau$, then Corollary 18 shows that the values of this game are also rational numbers of denominator at most $D^K$. Moreover, as shown above, these values are between $\text{val}^{\mathscr{G}^0}$ and $\epsilon + \text{val}^{\mathscr{G}'}$. Hence,
they must be equal to $val_{\mathcal{G}^0}$ and $\tau$ is optimal in $\mathcal{G}^0$. By the same reasoning, $\sigma$ is optimal in $\mathcal{G}^0$. To show the last claim, note that $val_{\mathcal{G}'}(u) > \frac{1}{2}$ implies $val_{\mathcal{G}^0}(u) > \frac{1}{2}$. Conversely, since $val_{\mathcal{G}^0}(u)$ has denominator at most $D^K$, if $val_{\mathcal{G}^0}(u) > \frac{1}{2}$, then $val_{\mathcal{G}^0}(u) > \varepsilon + \frac{1}{2}$, so $val_{\mathcal{G}'}(u) > \frac{1}{2}$. $\square$

## 6.3 A value iteration algorithm

We now present a value iteration algorithm for stochastic reachability games. This algorithm will rely on an appropriate rounding procedure. In this procedure, we want to approximate a given rational number from above by a number with bounded denominator. To make this more precise, given a positive natural number $M$, we denote by $\mathcal{Q}_M$ the set

$$ \mathcal{Q}_M = \left\{ \frac{p}{q} : p \in \{0, 1, \dots, M\}, q \in \{1, 2, \dots, M\} \right\}. $$

**Theorem 78.** Given a rational number $\alpha \in [0, 1]$ and $M \ge 1$ we can find the smallest number $\beta \in \mathcal{Q}_M$ that satisfies $\alpha \le \beta$ in $O(\log M)$ arithmetic operations.

*Proof.* Let $\beta$ be the smallest number in $\mathcal{Q}_M$ that satisfies $\alpha \le \beta$. Note that if $\gamma$ is any number in $\mathcal{Q}_M$, then it is trivial to decide if $\beta \le \gamma$. Indeed, if $\alpha \le \gamma$, then $\beta \le \gamma$ and if $\alpha > \gamma$, then $\beta > \gamma$. Hence, the exact value of $\beta$ can be found in $O(\log M)$ operations using the rational search technique described in [KM03]. $\square$

We denote by $\text{ROUNDUP}(\mu, M)$ the procedure that takes as an input $M \ge 1$ and a function $\mu: V \to [0, 1] \cap \mathbb{Q}$ and rounds up all values of $\mu$ using the procedure from Theorem 78. The pseudocode of the value iteration algorithm for stochastic reachability games is given in Algorithm 6.2.

<caption>**Algorithm 6.2:** The value iteration algorithm.</caption>

**Data:** A stochastic reachability game.
Choose $\mu$ such that $\mu \le val_{\mathcal{G}}$ and $\mu \le \mathcal{O}^{\mathcal{G}}(\mu)$
**repeat**
| $\mu \leftarrow \text{ROUNDUP}(\mathcal{O}^{\mathcal{G}}(\mu), D^K)$
**until** $\mathcal{O}^{\mathcal{G}}(\mu) = \mu$
**return** $\mu$

To analyze the algorithm, we use the following lemmas. To simplify the notation, we denote $\mathbb{B}(\mu) = \text{ROUNDUP}(\mathcal{O}^{\mathcal{G}}(\mu), D^K)$ for every function $\mu: V \to [0, 1] \cap \mathbb{Q}$.

**Lemma 87.** The operator $\mu \mapsto \mathbb{B}(\mu)$ is monotonic.

*Proof.* Suppose that $0 \le \alpha_1 \le \alpha_2 \le 1$ are two rational numbers. If $\beta_i \in \mathcal{Q}_M$ is the smallest number such that $\beta_i \ge \alpha_i$ for $i \in \{1, 2\}$, then we have $\beta_2 \ge \alpha_2 \ge \alpha_1$, so $\beta_2 \ge \beta_1$ by definition. Hence, the operator $\mu \to \text{ROUNDUP}(\mu, D^K)$ is monotonic. Therefore, $\mathbb{B}(\mu)$ is monotonic as a composition of monotonic operators. $\square$
**Lemma 88.** If $\mu_0 \le \mathcal{O}^\mathcal{G}(\mu)$, then the sequence $\mu_{k+1} = \mathbb{B}(\mu_k)$ produced by the value iteration algorithm is nondecreasing, $\mu_k \le \mu_{k+1}$.

*Proof.* We have $\mu_0 \le \mathcal{O}^\mathcal{G}(\mu_0) \le \mathbb{B}(\mu_0) = \mu_1$ by the assumption. Hence, the monotonicity of $\mathbb{B}$ gives $\mu_k \le \mu_{k+1}$ for all $k$. $\square$

**Theorem 79 (Starting condition for value iteration).** Suppose that $\mu_0 = 0$ or $\mu_0 = \text{val}^\sigma$ for some pure positional strategy $\sigma$ of Max. Then, $\mu_0$ satisfies the initial condition of value iteration, i.e., $\mu_0 \le \text{val}^\mathcal{G}$ and $\mu_0 \le \mathcal{O}^\mathcal{G}(\mu)$.

*Proof.* Both claims are trivial if $\mu_0 = 0$. Moreover, $\text{val}^\sigma \le \text{val}^\mathcal{G}$ by positional determinacy. To prove the last claim, note that $\text{val}^\sigma = \mathcal{O}^\mathcal{G}[\sigma](\text{val}^\sigma)$ by Theorem 73 and $\mathcal{O}^\mathcal{G}[\sigma](\text{val}^\sigma) \le \mathcal{O}^\mathcal{G}(\text{val}^\sigma)$ by definition of $\mathcal{O}^\mathcal{G}$. $\square$

**Theorem 80 (Correctness of value iteration).** The value iteration algorithm halts in at most $nD^{2K}$ iterations and outputs a function $\mu$ such that $\mu = \text{val}^\mathcal{G}$.

*Proof.* Let $\mu_0$ be such that $\mu_0 \le \text{val}^\mathcal{G}$ and $\mu_0 \le \mathcal{O}^\mathcal{G}(\mu_0)$. By Lemma 88, the sequence $\mu_{k+1} = \mathbb{B}(\mu_k)$ is nondecreasing. Furthermore, by Theorem 73, $\text{val}^\mathcal{G}$ is a fixed point of $\mathcal{O}^\mathcal{G}$ and by Corollary 18 it is also a fixed point of $\text{ROUNDUP}(x, D^K)$, so it is a fixed point of $\mathbb{B}$. Hence, by the monotonicity of $\mathbb{B}$ we have $\mu_k \le \text{val}^\mathcal{G}$ for all $k$. In particular, if the algorithm halts, then it outputs a fixed point of $\mathcal{O}^\mathcal{G}$ that is not higher than $\text{val}^\mathcal{G}$. Therefore, by Theorem 73, the algorithm outputs $\text{val}^\mathcal{G}$ when it halts. To show that the algorithm halts, consider a sequence $\xi_k$ defined as $\xi_0 = \mu_0$ and $\xi_{k+1} = \mathcal{O}^\mathcal{G}(\xi_k)$, i.e., a sequence produced by value iteration without rounding. The monotonicity of $\mathcal{O}^\mathcal{G}$ shows that $\xi_k$ is nondecreasing, $\xi_k \le \xi_{k+1}$, and Theorem 73 shows that $\xi_k \le \text{val}^\mathcal{G}$ for all $k$. In particular, the sequence $\mu_k$ converges to $\mu^* = \sup_k \mu_k$ (where we apply the supremum to all coordinates of the sequence), $\xi_k$ converges to $\xi^* = \sup_k \xi_k$, and we have $\mu^* \le \text{val}^\mathcal{G}$ and $\xi^* \le \text{val}^\mathcal{G}$. Furthermore, by induction we have $\xi_k \le \mu_k$ for all $k$. Indeed, $\xi_0 \le \mu_0$ by definition, and if $\xi_k \le \mu_k$, then $\xi_{k+1} = \mathcal{O}^\mathcal{G}(\xi_k) \le \mathcal{O}^\mathcal{G}(\mu_k) \le \mathbb{B}(\mu_k) = \mu_{k+1}$. Hence, we get $\xi^* \le \mu^* \le \text{val}^\mathcal{G}$. Moreover, by continuity of $\mathcal{O}^\mathcal{G}$, the sequence $\xi_k$ also converges to $\mathcal{O}^\mathcal{G}(\xi^*)$, which means that $\xi^*$ is a fixed point of $\mathcal{O}^\mathcal{G}$. Since $\xi^* \le \text{val}^\mathcal{G}$, Theorem 73 shows that $\xi^* = \mu^* = \text{val}^\mathcal{G}$. To finish the proof, note that $\mu_k$ is a vector of rational numbers in $[0, 1]$ with denominators bounded by $D^K$. Since there are only finitely many such numbers, the sequence $(\mu_k)$ stabilizes after finitely many steps, i.e., there exists the smallest $k^*$ such that $\mu_k = \mu^* = \text{val}^\mathcal{G}$ for all $k \ge k^*$. Hence, the algorithm halts in $k^*$ iterations. To bound $k^*$ note that for $k < k^*$ we have $\mu_k \le \mu_{k+1}$ and $\mu_k \ne \mu_{k+1}$. Therefore, at least one coordinate of $\mu_{k+1}$ is strictly larger than in $\mu_k$. Since these coordinates are rational numbers of denominator at most $D^K$, they differ by at least $D^{-2K}$. Given that the coordinates of $\mu_k$ are in $[0, 1]$, we conclude that $k^* \le nD^{2K}$. $\square$

## 6.4 A strategy improvement algorithm

Let us consider a stochastic reachability game $\mathcal{G}$ and set as a goal to construct an optimal strategy for Max. The key idea behind strategy improvement is to use $\text{val}^\sigma$ to improve the strategy $\sigma$ by switching edges, which is an operation that creates a new
strategy. This involves defining the notion of improving edges: let us consider a vertex $u \in V_{\text{Max}}$, we say that $e: u \to v$ is an improving edge if

$$ \text{val}^{\sigma}(v) > \text{val}^{\sigma}(u). $$

Intuitively: according to $\text{val}^{\sigma}$, playing $e$ is better than playing $\sigma(u)$.

Given a strategy $\sigma$ and a set of improving edges $S$ (for each $u \in V_{\text{Max}}$, $S$ contains at most one outgoing edge of $u$), we write $\sigma[S]$ for the strategy

$$ \sigma[S](u) = \begin{cases} e & \text{if there exists } e = u \to v \in S, \\ \sigma(v) & \text{otherwise.} \end{cases} $$

The difficulty is that an edge being improving does not mean that it is a better move than the current one in any context, but only according to the value function $\text{val}^{\sigma}$, so it is not clear that $\sigma[S]$ is better than $\sigma$. Strategy improvement algorithms depend on the following two principles:

* **Progress**: updating a strategy using improving edges is a strict improvement,

* **Optimality**: a strategy which does not have any improving edges is optimal.

The pseudocode of the algorithm is given in Algorithm 6.3. The algorithm is non-deterministic, in the sense that both the initial strategy and at each iteration, the choice of improving edge can be chosen arbitrarily. A typical choice, called the “greedy all-switches” rule, choosing for each $u \in V_{\text{Max}}$ a maximal improving edge, meaning

$$ \operatorname{argmax} \{\text{val}^{\sigma}(v) : u \to v \in E\}. $$

<caption>**Algorithm 6.3:** The strategy improvement algorithm.</caption>

Choose an initial strategy $\sigma_0$ for Max
**for** $i = 0, 1, 2, \dots$ **do**
&nbsp;&nbsp;&nbsp;&nbsp;Compute $\text{val}^{\sigma_i}$ and the set of improving edges
&nbsp;&nbsp;&nbsp;&nbsp;**if** $\sigma_i$ does not have improving edges **then**
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** $\sigma_i$
&nbsp;&nbsp;&nbsp;&nbsp;Choose a non-empty set $S_i$ of improving edges
&nbsp;&nbsp;&nbsp;&nbsp;$$ \sigma_{i+1} \leftarrow \sigma_i[S_i] $$

Before proving the correctness of this algorithm, we show that computing $\text{val}^{\sigma_i}$ at each iteration can be done in polynomial time. Note that the opposite problem (computing $\text{val}^{\tau}$ given $\tau$) is the reachability problem in a MDP as discussed in Chapter 5. In particular, Theorem 67 gives a polynomial-time algorithm for this problem based on linear programming. Finding $\text{val}^{\sigma}$ given $\sigma$ is similar.
**Lemma 89.** Let $\sigma$ be a pure positional strategy of player Max. Then, $\text{val}^{\sigma}$ is the solution of the linear program

$$
\begin{array}{lll}
\text{maximise} & \sum_{u \in V} x_u & \\
\text{subject to} & x_u = 1 & \text{if } u = \text{Win}, \\
& x_u = x_{\sigma(u)} & \text{if } u \in V_{\text{Max}}, \\
& x_u \le x_v & \text{if } u \in V_{\text{Min}}, u \to v \in E, \\
& x_u = \sum_v \delta(u)(v)x_v & \text{if } u \in V_{\text{Random}}, \\
& x_u = 0 & \text{if } u \in V \setminus W_{>0}(\mathcal{G}[\sigma]).
\end{array}
$$

In particular, $\text{val}^{\sigma}$ can be found in polynomial time.

*Proof.* By applying Theorem 73 to $O^{\mathcal{G}[\sigma]}$ we get that $\text{val}^{\sigma}$ is a feasible solution of the program. Moreover, note that every feasible solution $x$ satisfies $x \le O^{\mathcal{G}[\sigma]}(x)$, $x_{\text{Win}} = 1$, and $x_u = 0$ for all $u \in V \setminus W_{>0}(\mathcal{G}[\sigma])$. Since $(C^{\sigma} \setminus \text{Win}) \subset (V \setminus W_{>0}(\mathcal{G}[\sigma]))$, Lemma 83 shows that $x \le \text{val}^{\sigma}$. Hence, $\text{val}^{\sigma}$ can be found by computing $W_{>0}(\mathcal{G}[\sigma])$ (Theorem 75) and solving the linear program. $\square$

Let us write $\sigma \le \sigma'$ if for all vertices $u$ we have $\text{val}^{\sigma}(u) \le \text{val}^{\sigma'}(u)$, and $\sigma < \sigma'$ if additionally $\neg(\sigma' \le \sigma)$. We make the following observation.

**Lemma 90.** Let $\sigma$ be any strategy of Max and $S$ a set of improving edges. We let $\sigma' = \sigma[S]$. Then, we have $\text{val}^{\sigma} \le O^{\mathcal{G}[\sigma']}(\text{val}^{\sigma}) \le O^{\mathcal{G}}(\text{val}^{\sigma})$. Furthermore, the inequality $\text{val}^{\sigma}(u) \le O^{\mathcal{G}}(\text{val}^{\sigma})(u)$ is strict if and only if $u$ is a vertex of Max that has at least one improving edge. Likewise, the inequality $\text{val}^{\sigma}(u) \le O^{\mathcal{G}[\sigma']}(\text{val}^{\sigma})(u)$ is strict if $u$ has an outgoing edge in $S$. Moreover, if $S$ is constructed by the greedy all-switches rule, then $O^{\mathcal{G}[\sigma']}(\text{val}^{\sigma}) = O^{\mathcal{G}}(\text{val}^{\sigma})$.

*Proof.* By Theorem 73 we have $\text{val}^{\sigma} = O^{\mathcal{G}[\sigma]}(\text{val}^{\sigma})$. Hence, the inequality $\text{val}^{\sigma}(u) \le O^{\mathcal{G}}(\text{val}^{\sigma})(u)$ follows from the definition of $O^{\mathcal{G}}$ and this inequality is strict if and only if $u$ is a vertex of Max that has at least one improving edge. Furthermore, the definition of $\sigma'$ implies that $O^{\mathcal{G}[\sigma']}(\text{val}^{\sigma})$ is sandwiched between $\text{val}^{\sigma}$ and $O^{\mathcal{G}}(\text{val}^{\sigma})$ and that it satisfies $\text{val}^{\sigma}(u) < O^{\mathcal{G}[\sigma']}(\text{val}^{\sigma})(u)$ for every $u$ that has an outgoing edge in $S$. The last claim follows from the definition of the greedy all-switches rule. $\square$

**Theorem 81** (Progress property for the strategy improvement). Let $\sigma$ a strategy and $S$ a set of improving edges. We let $\sigma' = \sigma[S]$. Then $\sigma < \sigma'$.

*Proof.* By Lemma 90, we have $\text{val}^{\sigma} \le O^{\mathcal{G}[\sigma']}(\text{val}^{\sigma})$ and this inequality is strict for at least one coordinate. Hence, by Theorem 73, $\text{val}^{\sigma'} \ne \text{val}^{\sigma}$. It remains to prove that $\text{val}^{\sigma'} \ge \text{val}^{\sigma}$. To do so, we use Lemma 83. Denote $\mu = \text{val}^{\sigma}$, let $\tau$ be any pure positional strategy of Min and let $P$ be the transition matrix of the Markov chain induced by fixing $(\sigma', \tau)$. By definition, we have $\mu \le O^{\mathcal{G}[\sigma']}(\mu) \le P\mu$. Suppose that $C \ne \{\text{Win}\}$ is a recurrent class of this Markov chain. Then, this class has a stationary distribution (see, e.g., [KS76, Chapter V]). In other words, there exists a nonnegative vector $\pi \ge 0$ such that $\pi_u > 0$ for $u \in C$, $\pi_u = 0$ for $u \notin C$, and $\pi^T P = \pi$. Since $\pi^T \mu \le \pi^T P\mu = \pi^T \mu$ we get $\mu(u) = O^{\mathcal{G}[\sigma']}(\mu)(u) = (P\mu)_u$ for all $u \in C$. In particular, the strategies $\sigma'$ and $\sigma$ are the same on all vertices in $C \cap V_{\text{Max}}$. Hence, $C$ is also a recurrent class in the
Markov chain obtained by fixing $(\sigma, \tau)$ and so $\text{val}^{\sigma}(u) = 0$ for every $u \in C$. Since $\tau$ was arbitrary, we get $\mu(u) = 0$ for all $u \in C^{\sigma'} \setminus \{\text{Win}\}$. We also have $\mu(\text{Win}) = 1$ and by Lemma 83 we conclude that $\mu \le \text{val}^{\sigma'}$. $\square$

**Theorem 82** (Optimality property for the strategy improvement). Let $\sigma$ be a strategy that has no improving edges, then $\sigma$ is optimal.

*Proof.* Let $\sigma$ be a strategy that has no improving edges. Then, by Lemma 90 we have $\text{val}^{\sigma} = \mathcal{O}^{\mathcal{G}}(\text{val}^{\sigma})$, and so, by Theorem 73, $\text{val}^{\sigma} \ge \text{val}^{\mathcal{G}}$, which gives $\text{val}^{\sigma} = \text{val}^{\mathcal{G}}$. $\square$

**Theorem 83** (Comparison of strategy improvement and value iteration algorithms). Let us write $\sigma_0 < \sigma_1 < \sigma_2 < \dots$ for the sequence of positional strategies in an execution of the strategy improvement algorithm with the greedy all-switches rule over $\mathcal{G}$ and $\mu_0 \le \mu_1 \le \mu_2 \le \dots$ for the sequence of functions computed by the corresponding value iteration algorithm over $\mathcal{G}$ initialised at $\text{val}^{\sigma_0}$: for all $k$, we have $\mu_0 = \text{val}^{\sigma_0}$ and $\mu_{k+1} = \mathbb{B}(\mu_k)$.

Then for all $k$, we have $\mu_k \le \text{val}^{\sigma_k}$.

*Proof.* For every $k$ we have $\text{val}^{\sigma_k} \le \text{val}^{\sigma_{k+1}}$. Hence, by Theorem 73 and the monotonicity of $\mathcal{O}^{\mathcal{G}}[\sigma_{k+1}]$ we get $\mathcal{O}^{\mathcal{G}}[\sigma_{k+1}](\text{val}^{\sigma_k}) \le \text{val}^{\sigma_{k+1}}$. Furthermore, by Lemma 90 we have $\mathcal{O}^{\mathcal{G}}[\sigma_{k+1}](\text{val}^{\sigma_k}) = \mathcal{O}^{\mathcal{G}}(\text{val}^{\sigma_k})$. Thus $\mathcal{O}^{\mathcal{G}}(\text{val}^{\sigma_k}) \le \text{val}^{\sigma_{k+1}}$ for all $k$. Moreover, by Corollary 18, $\text{val}^{\sigma_k}$ is a fixed point of $x \mapsto \text{ROUNDUP}(x, D^K)$ for all $k$. Therefore, $\mathbb{B}(\text{val}^{\sigma_k}) \le \text{val}^{\sigma_{k+1}}$ for all $k$. By induction and the monotonicity of $\mathbb{B}$, if $\mu_k \le \text{val}^{\sigma_k}$, then $\mu_{k+1} = \mathbb{B}(\mu_k) \le \mathbb{B}(\text{val}^{\sigma_k}) \le \text{val}^{\sigma_{k+1}}$. $\square$

By combining Theorems 80 and 83, we get an $n \cdot D^{2K}$ bound on the number of iterations of the strategy improvement algorithm using the greedy all-switches rule. The following theorem improves this bound for all switching rules.

**Theorem 84.** The strategy improvement algorithm stops in at most $|V_{\text{Max}}| \cdot D^K$ iterations.

*Proof.* Let $\sigma_0 < \sigma_1 < \sigma_2 < \dots$ be the sequence of positional strategies in an execution of the strategy improvement algorithm. We have $\text{val}^{\sigma_k} \le \text{val}^{\sigma_{k+1}}$ for all $k$. As in the proof of Theorem 83, by Theorem 73 and the monotonicity of $\mathcal{O}^{\mathcal{G}}[\sigma_{k+1}]$ we get $\mathcal{O}^{\mathcal{G}}[\sigma_{k+1}](\text{val}^{\sigma_k}) \le \text{val}^{\sigma_{k+1}}$. Furthermore, Lemma 90 shows that $\text{val}^{\sigma_k} \le \mathcal{O}^{\mathcal{G}}[\sigma_{k+1}](\text{val}^{\sigma_k})$ and that this inequality is strict for every vertex of Max that has an outgoing edge in S. Let $u$ be such a vertex. We claim that $\mathcal{O}^{\mathcal{G}}[\sigma_{k+1}](\text{val}^{\sigma_k})(u) - \text{val}^{\sigma_k}(u) \ge D^{-K}$. Indeed, by Corollary 18, $\text{val}^{\sigma}$ is a vector of rational numbers with common denominator at most $D^K$. Since $\mathcal{O}^{\mathcal{G}}[\sigma_{k+1}](\text{val}^{\sigma_k})(u) = \text{val}^{\sigma_k}(v)$ for some vertex $v$, we get $\mathcal{O}^{\mathcal{G}}[\sigma_{k+1}](\text{val}^{\sigma_k})(u) - \text{val}^{\sigma_k}(u) \ge D^{-K}$. In particular, $\text{val}^{\sigma_{k+1}}(u) \ge \text{val}^{\sigma_k}(u) + D^{-K}$. Therefore, the strategy improvement algorithm increases the value of at least one vertex of Max by at least $D^{-K}$. Since the value is bounded by 1, the algorithm must stop within $|V_{\text{Max}}| \cdot D^K$ iterations. $\square$
## 6.5 Algorithms based on permutations of random vertices

We present two algorithms, both based on the same key idea: to order the random vertices and to restrict ourselves to strategies aiming at reaching the best random vertices (with respect to the order on random vertices). For the remainder of this section we fix a stochastic normalised reachability game $\mathscr{G}$.

### Permutation of random vertices

Let us write $V_{Random} = \{v_1, \dots, v_k\}$. We represent total orders on $V_{Random}$ using permutations $\pi: V_{Random} \to V_{Random}$. We write $\pi_i = \pi^{-1}(v_i)$ for the $i$-th element in the order defined by $\pi$. Intuitively, $\pi$ represents a preference order for Max on random vertices.

A permutation $\pi$ induces what we call the $\pi$-regions:

$$ 
\left\{ 
\begin{array}{l}
W_{\pi}^{k+1} = \{\text{Win}\} \\
W_{\pi}^{i} = \text{Attr}_{\text{Max}}(\{\pi_i, \dots, \pi_k, \text{Win}\}) \setminus \bigcup_{j>i} W_{\pi}^{j} \quad i \in [1, k] \\
W_{\pi}^{0} = V \setminus \bigcup_{j>0} W_{\pi}^{j}
\end{array}
\right. 
$$

The idea is that once we fix the order on random vertices, the rest of the game is deterministic: Max and Min only aim at the best (with respect to the permutation $\pi$) random vertex they can get. More precisely, $W_{\pi}^i$ is the set of vertices where Max can ensure to reach $\{\pi_i, \dots, \pi_k, \text{Win}\}$ before any other random vertex (but no subset $\{\pi_j, \dots, \pi_k, \text{Win}\}$).

**Fact 19.** We have $W_{\pi}^0 = \{\text{Lose}\}$.

Indeed, recall that Lose is the unique vertex with value 0. We write $W_{\pi}^{\ge i}$ for $\bigcup_{j \ge i} W_{\pi}^j$. The $\pi$-regions induce the $\pi$-strategies $\sigma_{\pi}$ (for Max) and $\tau_{\pi}$ (for Min):

* on $W_{\pi}^i$, $\sigma_{\pi}$ is a pure and positional attractor strategy to $\{\pi_i, \dots, \pi_k, \text{Win}\}$;

* on $W_{\pi}^j$, $\tau_{\pi}$ is a pure and positional counter-attractor strategy ensuring never to reach $\{\pi_{i+1}, \dots, \pi_k, \text{Win}\}$.

We can then define for every $u \in V$:

$$ \text{val}_{\pi}(u) = \mathbb{P}_{\sigma_{\pi}, \tau_{\pi}}^{u}(\text{Reach}(\text{Win})). $$

It can be easily computed using systems of linear equations.

The key property of permutation-based algorithms is stated below:

**Theorem 85 (Existence of an optimal permutation).** There exists a permutation $\pi$ such that $\sigma_{\pi}$ is optimal for Max and $\tau_{\pi}$ is optimal for Min.

The remainder of this section is devoted to a proof of Theorem 85. We later explore how this yields algorithms.
## Live and self-consistent permutations

**Definition 23 (Live and self-consistent permutations).** Let $\pi$ a permutation.

* We say that $\pi$ is self-consistent if

$$ val_{\pi}(\pi_1) \leq val_{\pi}(\pi_2) \leq \dots \leq val_{\pi}(\pi_k). $$

* We say that $\pi$ is live if for every $i \in [1, k]$:

$$ \delta(\pi_i)(W_{\pi}^{\ge i+1}) > 0. $$

Intuitively, if $\pi$ is self-consistent the order given by $\pi$ coincides with the preference of Max, and if $\pi$ is live there is a positive probability to reach a preferable (for Max) $\pi$-region. The following result directly implies Theorem 85.

**Lemma 91.** The following properties hold.

* If a permutation $\pi$ is live and self-consistent, then the $\pi$-strategies are optimal.

* There exists a live and self-consistent permutation.

## Live and self-consistent permutations induce optimal strategies

We prove the first item of Lemma 91.

**Lemma 92 (Correctness of live and self-consistent permutations).** If $\pi$ is self-consistent, then $val_{\pi}$ is a fixed point of the operator $\mathcal{O}$. Consequently, $val_{\pi}^{\mathcal{O}} \leq val_{\pi}$.

*Proof.* We prove the following properties:

1. For $i \in [1, k]$ and $u \in W_{\pi}^i$ we have $val_{\pi}(u) = val_{\pi}(\pi_i)$.

2. For $u \in V_{\text{Max}}$ we have $val_{\pi}(u) = val_{\pi}(\sigma_{\pi}(u)) = \max\{val_{\pi}(v) : u \to v \in E\}$.

3. For $u \in V_{\text{Min}}$ we have $val_{\pi}(u) = val_{\pi}(\tau_{\pi}(u)) = \min\{val_{\pi}(v) : u \to v \in E\}$.

For $v \in W_{\pi}^i$, up to the first visit to a random vertex, the strategy profile $(\sigma_{\pi}, \tau_{\pi})$ generates a unique path. So we can speak of the first random vertex encountered from $u$ when applying $(\sigma_{\pi}, \tau_{\pi})$. By definition of $\sigma_{\pi}$ (attractor to $\{\pi_i, \dots, \pi_k, \text{Win}\}$) and $\tau_{\pi}$ (counter-attractor strategy avoiding $\{\pi_{i+1}, \dots, \pi_k, \text{Win}\}$), this random vertex can only be $\pi_i$. According values follow, proving the first item.

Assume $u \in V_{\text{Max}} \cap W_{\pi}^i$. By definition of $\sigma_{\pi}$ (being an attractor strategy), $\sigma_{\pi}(u) \in W_{\pi}^i \cup \{\pi_i, \dots, \pi_k, \text{Win}\}$. Dually, since $u \notin W_{\pi}^{\ge i+1}$, we have $\sigma_{\pi}(u) \notin \{\pi_{i+1}, \dots, \pi_k, \text{Win}\}$. Hence, $\sigma_{\pi}(u) \in W_{\pi}^i \cup \{\pi_i\} = W_{\pi}^i$, and we get that $val_{\pi}(u) = val_{\pi}(\pi_i) = val_{\pi}(\sigma_{\pi}(u))$. Assume towards contradiction that there exists $u \to v \in E$ such that $val_{\pi}(v) > val_{\pi}(u)$. Since we know that $val_{\pi}(u) = val_{\pi}(\pi_i)$, by self-consistence this implies that $v \in W_{\pi}^j$ with $j > i$ (with $val_{\pi}(v) = val_{\pi}(\pi_j)$). But then, we can deduce that $u \in \text{Attr}_{\text{Max}}(v) \subseteq \text{Attr}_{\text{Max}}(\{\pi_j, \dots, \pi_k, \text{Win}\})$, which is not the case, since $u \notin W_{\pi}^{\ge i+1} \supseteq W_{\pi}^j$. Contradiction.

The reasoning is symmetric for $u \in V_{\text{Min}}$. $\square$
## 6.5. ALGORITHMS BASED ON PERMUTATIONS OF RANDOM VERTICES 243

The converse inequality $val_{\mathcal{G}} \geq val_{\pi}$ is not true for general or self-consistent permutations, but it does hold when adding the liveness property. A key technical property of the $\pi$-strategies $\sigma_{\pi}$ when $\pi$ is live is that it induces a stopping MDP: Min cannot prevent the game converging to Lose or Win.

**Lemma 93 (Live permutations imply stopping MDPs).** Let $\pi$ be a live permutation. Then, for every strategy $\tau$ of Min, for every $u$, we have $\mathbb{P}_{\sigma_{\pi}, \tau}^{u}(\text{Reach}(\{\text{Lose}, \text{Win}\})) = 1$.

*Proof.* Let $\alpha = \min_{i \in [1,k]} \delta(\pi_i) (W_{\pi}^{\ge i+1})$. By definition of a live permutation we have $\alpha > 0$. We write $V_i$ for the random variable representing the $i$-th state of a run. By definition of $\alpha$, for $i \in [1,k]$ and $\ell \ge 0$, we have $\mathbb{P}_{\sigma_{\pi}, \tau}^{u}(V_{\ell+1} \in W_{\pi}^{\ge i+1} | V_{\ell} = \pi_i) \ge \alpha$ and $\mathbb{P}_{\sigma_{\pi}, \tau}^{u}(\exists h < |W_{\pi}^{i}|, V_{\ell+h} \in \{\pi_i, \dots, \pi_k, \text{Win}\} | V_{\ell} \in W_{\pi}^{i}) = 1$, since $\sigma_{\pi}$ plays according to attractor strategies in the corresponding $\pi$-regions, where $n$ is the number of vertices in the game. This implies that $\mathbb{P}_{\sigma_{\pi}, \tau}^{u}(V_{\ell+n} = \text{Win} | V_{\ell} \neq \text{Lose}) \ge \alpha^k$, which we can rewrite as: $\mathbb{P}_{\sigma_{\pi}, \tau}^{u}(\forall \ell' \in [\ell, \ell+n], V_{\ell'} \neq \text{Win} | V_{\ell} \neq \text{Lose}) \le 1 - \alpha^k$. Iterating, we get that for every $i$,

$$ \mathbb{P}_{\sigma_{\pi}, \tau}^{u}(\forall \ell \in [0, i \cdot n], V_{\ell} \notin \{\text{Win}, \text{Lose}\} | V_{0} \neq \text{Lose}) \le (1 - \alpha^k)^i. $$

Hence by taking the limit $\mathbb{P}_{\sigma_{\pi}, \tau}^{u}(\forall \ell \ge 0, V_{\ell} \notin \{\text{Win}, \text{Lose}\}) = 0$, which equivalently reads $\mathbb{P}_{\sigma_{\pi}, \tau}^{u}(\exists \ell \ge 0, V_{\ell} \in \{\text{Win}, \text{Lose}\}) = 1$. $\square$

We can now show that if $\pi$ is a live and self-consistent permutation, then $val_{\pi} = val_{\mathcal{G}}$. Indeed, by Lemma 92 $val_{\pi}$ is a fixed point of the operator $\mathcal{O}^{\mathcal{G}}$, hence of $\mathcal{O}^{\mathcal{G}}[\sigma_{\pi}]$. By Lemma 93, the MDP obtained when restricting to $\sigma_{\pi}$ is stopping, hence (the special case for MDPs of) Theorem 77 implies that $\mathcal{O}^{\mathcal{G}}[\sigma_{\pi}]$ has a unique fixed point, which is $val_{\mathcal{G}}$. Hence $val_{\pi} = val_{\mathcal{G}}$.

### Existence of a live and self-consistent permutation

We now prove the second item of Lemma 91.

**Lemma 94 (Live and value non-decreasing imply self-consistent).** Let $\pi$ be a live permutation such that $val_{\mathcal{G}}(\pi_1) \le val_{\mathcal{G}}(\pi_2) \le \dots \le val_{\mathcal{G}}(\pi_k)$. Then $\pi$ is self-consistent.

*Proof.* We show that for every vertex $u$ we have $val_{\mathcal{G}}(u) = val_{\pi}(u)$, which implies the result. We first note that for every $i \in [1,k]$, for every $u \in W_{\pi}^{i}$ we have $val_{\mathcal{G}}(u) = val_{\mathcal{G}}(\pi_i)$.

Let us define a $\sigma^*$ from $u$: it plays the attractor strategy to $\{\pi_i, \dots, \pi_k, \text{Win}\}$ until Win or a random vertex is reached, and in the latter case, switch to an optimal strategy. Clearly for every strategy $\tau$ for Min we have $\mathbb{P}_{\sigma^*, \tau}^{u}(\text{Reach}(\{\text{Win}\})) \ge \min_{i \in [i,k]} val_{\mathcal{G}}(\pi_i) = val_{\mathcal{G}}(\pi_i)$. Hence $val_{\mathcal{G}}(u) \ge val_{\mathcal{G}}(\pi_i)$.

Conversely, let us define a strategy $\tau^*$ from $u$: it plays the counter-attractor strategy to $\{\pi_{i+1}, \dots, \pi_k, \text{Win}\}$ until Lose or a random vertex is reached, and in the latter case, switch to an optimal strategy. It may never hit Lose or a random vertex, but this is
good to Min. Clearly for every strategy $\sigma$ for Max we have $\mathbb{P}_{\sigma, \tau^*}^u (\text{Reach}(\{\text{Win}\})) \le \max_{j \in [1, i]} \text{val}^g(\pi_j) = \text{val}^g(\pi_i)$. Hence $\text{val}^g(u) \le \text{val}^g(\pi_i)$.

Now we can conclude: both $\text{val}^g$ and $\text{val}_\pi$ are fixed points of the operator $\mathcal{O}^g[\sigma_\pi]$, which is unique because $\pi$ is live (Lemma 93 and Theorem 77). $\square$

It remains to show that there always exists a live permutation satisfying the hypothesis of Lemma 94. To do so, we show the following structural property of the game, which will help building an appropriate live permutation.

**Lemma 95.** Let $X \subseteq V$ such that $\text{Win} \in X$, and $Y = V \setminus \text{Attr}_{\text{Max}}(X)$. Then either $Y = \{\text{ Lose}\}$, or there exists a random vertex $u \in Y$ such that $\text{val}^g(u) = \max\{\text{val}^g(v) : v \in Y\}$ and $\delta(u)(\text{Attr}_{\text{Max}}(X)) > 0$.

*Proof.* Let $m = \max\{\text{val}^g(u) : u \in Y\}$, we write $Z = \{u \in Y : \text{val}^g(u) = m\}$. We show that if there are no random vertices $u \in Z$ such that $\delta(u)(\text{Attr}_{\text{Max}}(X)) > 0$, then $Z = \{\text{ Lose}\}$. To do so, we show that if $u \in Z$, then $\text{val}^g(u) = 0$. Let us assume towards a contradiction that $\text{val}^g(u) > 0$.

Let $\tau$ be a counter-attractor (pure and positional) strategy for Min to stay safe of $\text{Attr}_{\text{Max}}(X)$ from $Y$. The following properties are direct consequences of the definitions: for any $u \in Z$,

* if $u \in V_{\text{Min}}$ and $\tau(u) = u \to v \in E$, then $v \in Z$,

* if $u \in V_{\text{Max}}$ and $u \to v \in E$, then $v \in Y$,

* if $u \in V_{\text{Random}}$ and $\delta(u)(v) > 0$, then $v \in Z$.

We now define a strategy $\tau'$ which plays from $v$ as $\tau$ until $Z$ is left, and then switches to an optimal strategy for Min. Let $\sigma$ a strategy for Max. Thanks to the properties above, a play consistent with $\sigma$ and $\tau'$ from $v$ either stays forever in $Z$, or reaches a vertex $v$ such that $\text{val}^g(v) < \text{val}^g(u) = m$. Let us write $\beta = \max\{\text{val}^g(v) \mid v \in Y \setminus Z\} < m$. We then have that $\mathbb{P}_{\sigma, \tau'}^{\nu}(\text{Reach}(\{\text{Win}\})) \le \beta$, because the probability to reach Win if staying forever in $Z$ is 0. Hence $\text{val}^g(v) \le \beta < \text{val}^g(v)$, a contradiction. $\square$

We can now prove the existence of a live permutation such that $\text{val}^g(\pi_1) \le \text{val}^g(\pi_2) \le \dots \le \text{val}^g(\pi_k)$. We define the permutation $\pi$ inductively, by repeatedly using Lemma 95. For every $i \in [k, 1]$ we define $\pi_i$ by applying Lemma 95 to $X = \{\pi_{i+1}, \dots, \pi_k, \text{Win}\}$. By construction,

* $\text{val}^g(\pi_i) = \max\{\text{val}^g(v) \mid v \in V \setminus \text{Attr}_{\text{Max}}(\{\pi_{i+1}, \dots, \pi_k, \text{Win}\})\}$;

* $\delta(\pi_i)(\text{Attr}_{\text{Max}}(\{\pi_{i+1}, \dots, \pi_k, \text{Win}\})) > 0$.

It follows that $\pi$ is live, and the hypothesis of Lemma 94 is satisfied. Hence $\pi$ is self-consistent. This concludes the proof of the second item of Lemma 91.
**Strategy enumeration algorithm**

Theorem 85 induces a simple algorithm for computing the values and optimal strategies for both players in a stochastic reachability game: enumerate all permutations of random vertices, and for each of them, check whether it is live and self-consistent; stop when one is found. Note that indeed given $\pi$, it is easy to compute the $\pi$-regions and strategies and check for liveness and self-consistency, in polynomial time. However, as such, this requires to enumerate all permutations of random vertices, and there are $|V_{Random}|!$ of them. Hence the overall complexity of finding the values and the optimal strategies is exponential.

**Strategy improvement algorithm**

We will describe a strategy improvement algorithm, which may avoid enumerating all permutations. Note that there is nevertheless no guarantee that the overall complexity will be better than the strategy enumeration algorithm.

The algorithm consists in the following steps:

* Initialization step: Compute a live permutation $\pi$

* Improvement step: Given a live permutation $\pi$, compute a live and self-consistent permutation in $\mathcal{G}[\sigma_{\pi}]$.

We argue (not in full details) that the following properties are satisfied:

1. We can compute an initial live permutation in polynomial time.

2. For every live permutation $\pi$, we can compute in polynomial time a live and self-consistent permutation $\pi'$ in $\mathcal{G}[\sigma_{\pi}]$.

3. The above mentioned permutation $\pi'$ is live in $\mathcal{G}$ as well.

4. The improvement step is an improvement:

* $\text{val}^{\mathcal{G}[\sigma_{\pi}]} \le \text{val}^{\mathcal{G}[\sigma_{\pi'}]}$, and

* If $\text{val}^{\mathcal{G}[\sigma_{\pi}]} = \text{val}^{\mathcal{G}[\sigma_{\pi'}]}$, then $\pi'$ is self-consistent in $\mathcal{G}$.

The first property is based on the inductive construction following Lemma 95.

For the second property, we know as a consequence of Theorem 85 that there exists a live and self-consistent permutation $\pi'$ in $\mathcal{G}[\sigma_{\pi}]$. Note that for this we need to argue that $\mathcal{G}[\sigma_{\pi}]$ is normalized.

For the third property, we note that the $\pi$'-regions in $\mathcal{G}[\sigma_{\pi}]$ are included in the $\pi$'-regions in $\mathcal{G}$, which implies the result.

The last property is harder to argue; it expresses the fact that the new permutation $\pi'$ improves over $\pi$.

This last property ensures both termination of the algorithm: indeed, it is ensured by the finiteness of the number of permutations, and by the improvement characterization above. Note that it may be the case that in the worst-case, all permutations will be enumerated. No lower nor upper bound is known.
## 6.6 Reductions to simple stochastic games

The rest of this chapter focused on stochastic reachability games. As we will see in this section, they are powerful enough to encode other classes of games, such as non-stochastic discounted payoff games, and stochastic parity, mean payoff, and discounted payoff games.

### 6.6.1 From discounted payoff games to stochastic reachability games

**Theorem 86** (Reducing discounted payoff games to stochastic reachability games). *Solving (non-stochastic) discounted payoff games reduces in polynomial time to solving stochastic reachability games.*

<figure><img src="image_56.png" /><figcaption>Figure 6.6: From discounted payoff games to stochastic reachability games.</figcaption></figure>

*Proof.* Let $\mathcal{G}$ a discounted payoff game. Using a linear transformation we can assume that all weights are rational numbers in $[0, 1]$. We construct $\mathcal{G}'$ a stochastic reachability game by adding to vertices $v_{Win}$ and $v_{Lose}$, and each edge $e = u \xrightarrow{w} v$ in $\mathcal{G}$ is redirected to a new random vertex $v_e$ with probabilistic distribution

$$ \delta(v_e) = \lambda \cdot v + (1 - \lambda) \cdot w \cdot \text{Win} + (1 - \lambda) \cdot (1 - w) \cdot \text{Lose}. $$

The reachability condition is Reach(Win). (Note that the game $\mathcal{G}'$ is stopping.)
We claim that for every $u \in V$, we have

$$ \mathrm{val}^{\mathcal{G}}(u) = \mathrm{val}^{\mathcal{G}'}(u). $$

To this end, we rely on Lemma 38, which states that the discounted payoff values are the unique fixed point of the operator $\mathcal{O}^{\mathcal{G}}: F_V \to F_V$ defined by

$$ \mathcal{O}^{\mathcal{G}}(\mu)(u) = \begin{cases} \max\{\lambda \cdot \mu(v) + (1-\lambda) \cdot w : u \xrightarrow{w} v \in E\} & \text{if } u \in V_{\text{Max}}, \\ \min\{\lambda \cdot \mu(v) + (1-\lambda) \cdot w : u \xrightarrow{w} v \in E\} & \text{if } u \in V_{\text{Min}}. \end{cases} $$
We show that $(\mathrm{val}^{\mathcal{G}'}(u))_{u \in V}$ is a fixed point of the operator $\mathcal{O}^{\mathcal{G}}$.

Thanks to Theorem 73, the values in $\mathcal{G}'$ satisfy the following:

$$ 
\left\{ 
\begin{array}{lll}
\mathrm{val}^{\mathcal{G}'}(\mathrm{Win}) & = & 1, \\
\mathrm{val}^{\mathcal{G}'}(\mathrm{ Lose}) & = & 0, \\
\mathrm{val}^{\mathcal{G}'}(u) & = & \max \{ \mathrm{val}^{\mathcal{G}'}(v) : u \to v \in E \} \quad \text{if } u \in V_{\mathrm{Max}}, \\
\mathrm{val}^{\mathcal{G}'}(u) & = & \min \{ \mathrm{val}^{\mathcal{G}'}(v) : u \to v \in E \} \quad \text{if } u \in V_{\mathrm{Min}}, \\
\mathrm{val}^{\mathcal{G}'}(v_e) & = & \lambda \cdot \mathrm{val}^{\mathcal{G}'}(v) \\
& & + (1-\lambda) \cdot w \cdot \mathrm{val}^{\mathcal{G}'}(\mathrm{Win}) \\
& & + (1-\lambda) \cdot (1-w) \cdot \mathrm{val}^{\mathcal{G}'}(\mathrm{Lose})
\end{array}
\right. 
$$

Eliminating the values $\mathrm{val}^{\mathcal{G}'}(v_e)$ from these equations, we obtain

$$ 
\left\{ 
\begin{array}{ll}
\mathrm{val}^{\mathcal{G}'}(u) & = \max \left\{ \lambda \cdot \mathrm{val}^{\mathcal{G}'}(v) + (1-\lambda) \cdot w : u \to v \in E \right\} & \text{if } u \in V_{\mathrm{Max}}, \\
\mathrm{val}^{\mathcal{G}'}(u) & = \min \left\{ \lambda \cdot \mathrm{val}^{\mathcal{G}'}(v) + (1-\lambda) \cdot w : u \to v \in E \right\} & \text{if } u \in V_{\mathrm{Min}}.
\end{array}
\right. 
$$

Hence $(\mathrm{val}^{\mathcal{G}'}(u))_{u \in V}$ is a fixed point of the operator $\mathcal{O}^{\mathcal{G}}$. Since $\mathcal{O}^{\mathcal{G}}$ has a unique fixed point $\mathrm{val}^{\mathcal{G}}$, this implies the desired equality. $\square$

We note that Theorem 86 easily extends to discounted stochastic games: from a discounted stochastic game, one can build a stochastic reachability game with the same values.

### 6.6.2 From stochastic mean payoff games to stochastic discounted payoff games

Both positional determinacy for mean payoff games and the reduction to discounted payoff games (presented in Theorem 47) can be lifted to stochastic games.

**Theorem 87** (Stochastic mean payoff games are positionally determined). *Stochastic mean payoff games are uniformly purely and positionally determined.*

**Theorem 88** (Reducing stochastic mean payoff games to stochastic discounted payoff games). Let $\mathcal{G}$ a stochastic mean payoff game. Let $\lambda \in (0,1)$, we define $\mathcal{G}_{\lambda}$ the stochastic discounted payoff game obtained from $\mathcal{G}$. There exists a discount factor $\lambda$ computable in polynomial time such that any pair of optimal pure positional strategies in the discounted payoff game with discount factor $\lambda$ is also a pair of optimal strategies in the mean payoff game.

### 6.6.3 From stochastic parity to stochastic mean payoff

Both positional determinacy for parity games and the reduction to mean payoff games (presented in Theorem 40) can be lifted to stochastic games.

**Theorem 89** (Stochastic parity games are positionally determined). *Stochastic parity games are uniformly purely and positionally determined.*
**Theorem 90** (Reducing stochastic parity games to stochastic mean payoff games). *Solving stochastic parity games reduces in polynomial time to solving stochastic mean payoff games.*

The reduction is similar as the one presented in Theorem 40, but requires additional
technical care. In particular, it relies on the fact that we can compute the almost-surely
and positively winning regions.

**Theorem 91.** *The following holds.*

* There exists a polynomial time algorithm for computing the positively winning region of stochastic parity games.

* There exists a polynomial time algorithm for computing the almost-surely winning region of stochastic parity games.

Let $\mathcal{G}$ a stochastic parity game. We let $p_{\min}$ the minimal non-zero probability that appears in $\mathcal{G}$, and $n$ the number of vertices.

We construct $\mathcal{G}'$ a stochastic mean payoff game. As a first step, we compute the almost-sure and positive winning regions, we replace the almost-sure winning region with a sink vertex. Win with a self-loop with weight 1, and the complement of the positive winning region with a sink vertex. Lose with a self-loop with weight $-1$. For

each edge $u \xrightarrow{p} v$ in $\mathcal{G}$, we have an edge $u \xrightarrow{(-2n \cdot p_{\min}^{-n})^k} v$ in $\mathcal{G}'$.

We claim without proof that for all $u \in V$, we have

$$
\mathrm{val}_{\mathcal{G}}(u) = \frac{1}{2} \cdot (\mathrm{val}_{\mathcal{G}'}(u) + 1).
$$

**Bibliographic references**

The study of stochastic games started long before the algorithmic perspectives we develop here. This chapter took inspiration from the reference survey chapter by Kučera [Kuč11]. The introduction of stochastic games is due to Condon [Con92], where she proves (a weak form of) positional determinacy, and constructs strategy improvement algorithms. Moving back in time, positional determinacy for stochastic discounted payoff games was already proved (as a special case) by Shapley [Sha53], and for stochastic mean payoff games by Liggett and Lippman [LL69]. The Borel de-terminacy result for stochastic games was proved by Maitra and Sudderth [MS98]. The last section about reductions to stochastic reachability games is inspired by [AM09], which clarifies a lot the relationships between the different classes.

As for parity games, mean payoff games, and discounted payoff games, the major
open question is whether stochastic reachability games can be solved in polynomial
time. Strongly polynomial bound for strategy improvement have been obtained when
the discount factor is fixed [HMZ13]. The best complexity to date is sub-exponential
time randomised algorithms. A very general point of view on these algorithms is given
by reducing them to LP-type problems [Hal07].
A more general point of view on strategy improvement algorithms was developed by Auger, de Montjoye, and Strozecki [AdMS21]. Constructing strategy improvement algorithms for more general classes of stochastic games is non-trivial, see for instance the case of stochastic mean payoff games [ACTDG13].

The permutation-based algorithm is due to Gimbert and Horn [GH08]. There is a wealth of algorithms we did not cover in this chapter, let us mention the accelerated value iteration for stochastic reachability games [IJM12], the value iteration algorithm for ergodic mean payoff games [AGKS22], and the pumping algorithm for stochastic mean payoff games [BEGM19].

Stochastic games have also been related to other models of computations, for instance constraint satisfaction problems [BM16], and complexity classes related to fixed point computations [EY10, FGMS20].
# Part III

## Information
<figure><img src="image_57.png" /></figure>
CONCURRENT
GAMES

<figure><img src="image_58.png" /></figure>

<figure><img src="image_59.png" /></figure>
Chapter 7

# Concurrent Games

RASMUS IBSEN-JENSEN

This chapter considers concurrent games. The concurrent games we consider are ex-
tensions of the games considered in Chapter 2 and Chapter 4, but where the choice of
which edge to choose in a round is determined not by the choice of the owner of the
vertex (indeed the vertices in concurrent games have no owners), but by the outcome
of a matrix game corresponding to the vertex and played in that round. A matrix game
is in turn a generalization of rock-paper-scissors, where each player picks an action
simultaneously and then their pair of actions determines the outcome.

We will consider concurrent discounted, reachability and mean payoff games and the definitions of the different objectives is as in the introduction. The chapter is divided into four sections:

1. Matrix games

2. Concurrent discounted payoff games

3. Concurrent reachability games

4. Concurrent mean payoff games

As we go through the sections in this chapter, the complexity of the strategies and the computational complexity of solving the games rises: indeed, since the games are generalizations of rock-paper-scissors, the strategies used requires randomness, but towards the end, no optimal or finite-memory ε-optimal strategies exists in general and even the principle of sunken cost does not apply! Even with all this, the related questions about values are solvable in polynomial space and thus also in exponential time even in the last section. The results we will focus on characterizes the complexity of the both the strategies as well as the computational complexity. In each section we first give some positive result and some number of negative results. Each negative result also applies to the classes of games considered in the latter sections and each positive
result applies to the classes considered in earlier sections (however, the positive re-
sults of latter sections will have worse complexity than the positive results from earlier
sections). As mentioned, the strategies for this chapter require randomness and not
too surprisingly, this implies that there is little difference between having stochastic or
deterministic transition functions.

## 7.1 Notations

The definition of arena $\mathcal{A}$ in this chapter is $\mathcal{A} = (G, \Delta)$, where $G = (V, E)$ is a graph and $\Delta: V \times A \times A \rightarrow \mathcal{D}(E)$. In particular, we are not using the sets $V_{\text{Adam}}$ and $V_{\text{Eve}}$. The games are played similarly to before and formally as follows: There is a token, initially on the initial vertex. Whenever the token is on some vertex $v$, Eve selects an action $r$ in $A$ and Adam selects an action $c$ in $A$. The edge $e = (v, c, w)$ is then drawn from the distribution $\Delta(v, r, c)$ and the token is pushed from $v$ to $w$. In general, the game continues like that forever.

We will use the following simplifying assumptions in this chapter:

1. We will assume that all colors are in $\{0,1\}$, except for the section on Matrix games where we additionally also allow $-1$ (to be able to easily illustrate the game rock-paper-scissors). This simplifies some expressions, but generally, the dependency on the number of colors is not too bad comparatively.

2. To make illustrations easier, we assume that for any pair of edges $e, e'$ in $\Delta(v, a, a')$ for any $v, a, a'$, we have that $c(e) = c(e')$, i.e. the color does not depend on which edge is picked from $\Delta(v, a, a')$, but only $v, a, a'$. This assumption does not matter for the types of games considered.

We will overload the notation slightly for notational convenience, in that for any $v, a, a'$, we will write $c(v, a, a')$ for $c(e)$ where $e \in \Delta(v, a, a')$ (note that the second assumption ensures that this is well-defined, i.e. there is only one such color).

A vertex $v$ is absorbing if and only if each player has only 1 action in $v$ and $\Delta(v, 1, 1) = v$.

To describe the complexity of good stationary strategies in concurrent games, we will use the notion of patience. Given a probability distribution $d \in \mathcal{D}$ the distribution has patience $p$ if $p = \min_{i \in \text{supp}(d)} d(i)$ (i.e. the patience is the smallest, non-zero probability that an event may happen according to $d$). In essence, if you have low enough patience you can typically guess the strategy and check whether it is a good strategy (when you fix a strategy, the game becomes a Markov decision process, which are relative easy to work with), the game can be solved in NP $\cup$ coNP. However, some times the patience is huge and writing down a good strategy, in binary, cannot be done in polynomial space (it is quite surprising in some sense that even with this property, finding the values in the games remain in PSPACE).

We will illustrate a stochastic arena $\mathcal{A} = (G, \Delta)$ as follows: For each non-absorbing vertex $v$, there is matrix. Entry $(i, j)$ of the matrix illustrating $v \in V$ describes what happens if, when the token is on $v$, Eve plays $i$ and Adam $j$. The entry contains a color $c$, which is $c(v, i, j)$, and there is an arrow from entry $(i, j)$ of $v$ to $w$ if there is
<table><caption>Figure 7.1: Rock-paper-scissors. The color is 1 if Eve wins, 0 if they draw and -1 if Adam wins. Also, the actions are ordered as in the name of the game</caption><tr><td>0</td><td>-1</td><td>1</td></tr><tr><td>1</td><td>0</td><td>-1</td></tr><tr><td>-1</td><td>1</td><td>0</td></tr></table>

an edge $e = (v, c, w)$ in $\Delta(v, i, j)$. The arrow corresponding to $e$ is denoted with the probability $\Delta(v, i, j)(e)$. Especially, to simplify the illustrations we will do as follows: If $|\text{supp}(\Delta(v, i, j))| = 1$, we do not include the probability (which is 1). Also, in that case, let $e = (v, c, w) = \Delta(v, i, j)$ and if $v = w$, we omit the arrow and if $w$ is absorbing we write $c^*$ in entry $i, j$ of $v$, where $c$ is the color $c(w, 1, 1)$ (in this case, we omit the number $c(e)$ from the illustration, but in none of our illustrations does this number matter for what we try to illustrate).

## 7.2 Matrix games

A matrix game is a game defined from a $(R \times C)$-matrix $M$ of numbers for some $R, C$. The game is played as follows: Eve picks a row $r$ and Adam picks a column $c$ simulations like in rock-paper-scissors. Adam then pays Eve $M[r, c]$, i.e. the content of the entry defined by being in row $r$ and column $c$. A strategy in such a game for Eve (resp. Adam) consists of a distribution over the rows (resp. columns). There is an illustration of rock-paper-scissors as a matrix game in Figure 7.1.

The following theorem lists some known results for matrix games:

**Theorem 92.** Each $(m \times n)$-matrix game $M$ is determined and there exists optimal strategies for each player.

* The value and an optimal strategy for each player can be found in polynomial time and the problem is equivalent to linear programming.

* Let $c > 0$ be some constant. Consider the matrix $cM$ where each entry of $M$ has been multiplied by $c$. Then, the value of $cM$ is $cv$.

* Let $c$ be some constant. Consider the matrix $M + c$ where each entry of $M$ is $c$ larger (additively). Then, the value of $M + c$ is $v + c$.

* The value of matrix games are monotone in the entries.

We will omit the proof of the existence of values, optimal strategies and the first bullet. The second bullet can be viewed as changing currency and clearly, this does not affect the optimal strategy. The third bullet can be viewed as getting a reward before playing the game, and again, clearly this does not affect how to play it. The last bullet
can be seen from that each pair of strategies must give a higher reward if the entries of
the matrix is higher. This is especially true if you consider the optimal strategy for Eve
in M together with an arbitrary strategy for Adam, which then shows that the value is
higher.

Given a matrix $M$, we will by $\text{val}[M]$ denote the value of the matrix game $M$.

Perhaps interestingly, an illustration of a matrix $M$ can be viewed as a game arena $\mathcal{A}$ (for concurrent games) with only one non-absorbing vertex. In each type of games considered in this section (apart from concurrent reachability games, where no game can be illustrated as a matrix with non-star entries different from 0), the value of the game with that arena matches $\text{val}[M]$ and the optimal strategies for each player is to play an optimal strategy from $M$ in each round. One can also consider a game arena $\mathcal{A}^*$ with an illustration similar to $M$, but where there is a star in each entry (and $c(v, i, j) = 0$ for the unique non-absorbing state $v$ and any pair of actions $i, j$). Again, the value is $\text{val}[M]$ (except for the case of discounted objectives, where the value is $(1 - \delta)\text{val}[M]$) and the optimal strategies for each player is again to play an optimal strategy from $M$.

One could easily be lead to believe that in games (called repeated games with ab-
sorbing states) that can be illustrated as a single matrix $M$ with some entries stared
and others not, the value would be similar to $\text{val}[M]$ and the optimal strategy would
again be to play the optimal strategy from $M$. However, this is very much not true and
indeed, many of the games in this chapter, illustrating how complex concurrent games
can be, are repeated games with absorbing states! In particular repeated games with
absorbing states may (1) have irrational values and probabilities in optimal strategies
(with any objective), (2) have no optimal strategies (for reachability and mean payoff
objectives) and (3) have no $\varepsilon$-optimal finite-memory or $\varepsilon$-optimal Markov strategies
(for mean payoff objectives)!

7.3 Concurrent discounted payoff games

In this section we focus on concurrent discounted payoff games. The key property of
these games is that to a high degree, only the relative early part of the play matters.
We will first argue that the value iteration algorithm works and especially converges to
the value of the game and then that there are stationary optimal strategies in concurrent
discounted payoff games. While the value iteration algorithm also works for the games
considered in the latter sections, we will not explicitly show it there, since the proofs
become much more complex. The argument here however will allow us to show quite a
few more statements in essence as corollaries of the theorem that value iteration works.

The value iteration algorithm is based on the concept of finite-horizon (or time
limited) games. It is also sometimes referred to as dynamic programming. Specifically,
apart from the usual definition of a game, there is an additional integer $T$, denoting how
many rounds are remaining initially, and a vector $v$, assigning a reward to each node if
the game ends in that node with 0 rounds remaining. After round $T$ the reward is 0. I.e.
for $T = 0$, the outcome reward from node $x$ is $v_x$ in the first round and 0 in each later
round. Let $\text{valOp}^T(v)$ be the vector that assigns to each node its value in the game with
time-limit $T$ with vector $v$.

In general this formulation leads to a simple dynamic algorithm that computes
valOp$^T(v)$ inductively in $T$. We have that $valOp^0(v) = v$ and given $valOp^{T-1}(v)$ it is easy to compute $valOp^T(v)$ because, if Eve selects row $i$ and Adam column $j$ in node $x$ in the first round, the outcome is

$$ \sum_{v \in V} \mathrm{valOp}^{T-1}(v) \Delta(x, i, j)(v) $$

and thus $(valOp^T(v))_x$ is the value of the matrix $M^{T,x,v}$, where entry $i, j$ is

$$ \sum_{v \in V} \mathrm{valOp}^{T-1}(v) \Delta(x, i, j)(v) $$

It is common to start with the all-0 vector for $v$ when using the value iteration algorithm.

The following lemma shows many interesting properties of concurrent discounted payoff games.

**Lemma 96 (Concurrent discounted payoff games).** Concurrent discounted payoff games have the following properties:

* The value iteration algorithm converges for any initial vector $v$.

* The value iteration algorithm has an unique fixed point, independent of the initial vector $v$.

* There are optimal stationary strategies in concurrent discounted payoff games and the unique fixed point of the value iteration algorithm is the value (thus, the games are determined).

* The value of a concurrent discounted game can approximated in PPAD.

* There are $\epsilon$-optimal stationary strategies with patience below $\frac{m \log(\epsilon/2)}{\log(1-\gamma)\epsilon}$.

*Proof.* The first item comes from considering the vectors $v$ and $valOp^1(v)$. We thus have that $valOp^{T+1}(v) \in [valOp^T(v) - (1-\gamma)^T, valOp^T(v) + (1-\gamma)^T]$ for all $T$. The statement then comes from that $\sum_{i=1}^{\infty} (1-\gamma)^i$ is a converging sum.

The second item comes from considering two fixed points, $u, v$. I.e., $valOp^1(v) = v$ and thus $valOp^T(v) = v$ for all $T$. Similar for $u$. But, $v = valOp^T(v) \in [valOp^T(u) - (1-\gamma)^T, valOp^T(u) + (1-\gamma)^T] = [u - (1-\gamma)^T, u + (1-\gamma)^T]$. Since it is true for all $T$, we have that $u = v$.

**Claim 1.** Consider some $T$ and the strategy for Eve that plays the first $T$ steps following an optimal strategy in the finite-horizon game of length $T$ with vector $v$, followed by playing arbitrarily. Then, the outcome is above $valOp^T(v) - (1-\gamma)^T \max_i v_i$.

*Proof.* For any strategy for Adam, the expected reward for the first $T$ rounds is at least the expected reward in the finite-horizon game. In each remaining round, the reward is at least 0 in the real game, but $v_i$ in round $T$ for some $i$ followed by 0's in the finite-horizon game. Since the outcome is $valOp^T(v)$ in the finite-horizon game, the real outcome is then as described. $\square$
One can show a similar statement for Adam. For any $\epsilon > 0$ one can pick a big enough $T$ such that $(1 - \gamma)^T \max_i v_i \le \epsilon$.

Let $v^*$ be the unique fixed point of the value iteration algorithm. Thus, $v^* = \text{valOp}^T(v^*)$ for all $T$. Pick some optimal strategies $\sigma_x, \tau_x$ in $M^{T,x,v^*}$ for each $x$. Let $\sigma^*, \tau^*$ be the strategies that play $\sigma_x, \tau_x$ whenever in node $x$ in each round. The strategy $\sigma, \tau$ are optimal in $\text{valOp}^T(v^*)$ for each $T$, because $v^*$ is a fixed point. But, for each $\epsilon > 0$, the strategy $\sigma$ ensures outcome at least $v - \epsilon$ and $\tau$ ensures outcome at most $v + \epsilon$ using the claim. Hence, the third item follows.

The fourth item follows from that the value iteration algorithm is a contraction.

For the fifth item, consider the strategy used in the claim. Let $T$ be $\log(\epsilon/2)/\log(1-\gamma)$, i.e. $T$ is such that

$$ \gamma \sum_{i=T}^{\infty} (1 - \gamma)^i = \epsilon/2 $$

or in words, $T$ is such that the total outcome of each step after the $T$-th step is at most $\epsilon/2$. Intuitively, if we modify the strategy very little, then the change is unlikely to come up in the first $T$ steps. More precisely, we will modify our strategy so that the probability that change will matter is less than $\epsilon/2$. That implies that the outcome differs by at most $\epsilon$ from the value. We will use this intuition together with the argument for the third item to give a bound on the patience of $\epsilon$-optimal strategies. Fix some optimal stationary strategy $\sigma$ for Eve and an arbitrary stationary strategy $\tau$ for Adam. Let $\sigma'$ be a stationary strategy obtained from $\sigma$ rounded greedily so that each probability is a rational number with denominator

$$ q = mT/\epsilon = \frac{m \log(\epsilon/2)}{\log(1-\gamma)\epsilon} $$

We will argue that $\sigma'$ is $\epsilon$-optimal.

The rounding proceeds inductively as follows for each node $x$: The numbers $p_i$ are the original probability and the numbers $p'_i$ are the new probabilities. For each $i$, the number $p'_i$ is defined as follows: If $\sum_{j=1}^{i-1} (p_i - p'_i) > 0$, then round up (i.e. $p'_i$ is the smallest rational with denominator $q$ so that $p_i < p'_i$) and otherwise round down, except the last number $p'_i$, which is such that $\sum_{j=1}^{i} p'_i = 1$. Note that this ensures that $-1/q < \sum_{j=1}^{i-1} (p_i - p'_i) < 1/q$. It also ensures that $|p_i - p'_i| < 1/q$ for all $i$ (including for $i = 0$).

For all nodes $x$ and rounds $T' \le T$ we will define some random variables. Specifically, the random variables denote what happen in round $T'$ if in node $x$. The random variable $X_{x,T'}$ (resp. $Y_{x,T'}$) denotes the action picked by Eve if Eve follows $\sigma$ (resp. $\sigma'$). The random variable $Z_{x,T'}$ denotes the action picked by Adam. For each action pair $(i, j)$ the random variable $W_{x,i,j,T'}$ denotes the node entered in round $T' + 1$, if Eve picks $i$ and Adam $j$. (As a side note: Each of the random variables are distributed the same way independent of $T'$). Each of these random variables are independent of each other, except that (as we will define later) the random variables $X_{x,T'}$ and $Y_{x,T'}$ for each $x, T'$ are very much not independent of each other.

We see that we can view the first $T$ steps of the play when Eve follows $\sigma$ by only considering the outcome of $X_{x,T'}$, $Z_{x,T'}$ and $W_{x,i,j,T'}$ for all $T'$ and $x$ (even stronger: We only need to consider one $x, i, j$ for each $T'$, because the token is on only one node
at a time). Similarly, for $\sigma'$, but using $Y_{x,T'}$ instead of $X_{x,T'}$. For this to work, note that each random variable should be independent, except that the random variables $X_{x,T'}$ and $Y_{x',T''}$ need not be independent of each other for any $x', T''$. This is precisely the property we had for them! For each $x, T'$, we will then use a coupling $C_{x,T'} = (X'_{x,T'}, Y'_{x,T'})$, a distribution over $[m]^2$, such that $X'_{x,T'}$ is distributed as $X_{x,T'}$ and $Y'_{x,T'}$ is distributed as $Y_{x,T'}$. We will use a classic result for distributions, called the Coupling Lemma.

To introduce the Coupling Lemma, first, we need the notion of total variation distance. Given two distributions, $\Delta$ and $\Delta'$ over a set $S$, the total variation distance $t$ between $\Delta$ and $\Delta'$ is

$$t(\Delta, \Delta') = \frac{1}{2} \sum_{x \in S} |\Delta(x) - \Delta'(x)|$$

**Lemma 97.** For any distributions $\Delta$ and $\Delta'$ over a set $S$, we have

* for all couplings $(X, Y)$ of $\Delta$ and $\Delta'$, that

$$t(\Delta, \Delta) \leq \Pr[X \neq Y]$$

* that there is a coupling $(X', Y')$ of $\Delta$ and $\Delta'$ satisfying that

$$t(\Delta, \Delta) = \Pr[X' \neq Y']$$

Because of our rounding, we have that $t(X'_{x,T'}, Y'_{x,T'}) < \frac{m}{2q}$. Using that with the coupling lemma (the second part to be precise), lets us find a coupling $C_{x,T'} = (X'_{x,T'}, Y'_{x,T'})$ such that $\Pr[X'_{x,T'} \neq Y'_{x,T'}] < \frac{m}{2q}$.

Consider the plays $\pi_1, \pi_2$ for when Eve follows $\sigma$ or $\sigma'$ respectively. We can view the first $T$ steps of these plays by considering $X'_{x,T'}$ instead of $X_{x,T'}$ and similar when Eve follows $\sigma'$. We can therefore see that the first $T$ steps two plays are different with probability $= p < \frac{mT}{2q} = \varepsilon/2$ using union bounds.

We therefore see that the value for the path $\pi_1$ cannot differ from the value of $\pi_2$ with more than $p\gamma\sum_{i=1}^T (1-\gamma)^i = p$. I.e. in the worst case, if $\pi_1$ and $\pi_2$ differs, the reward is 1 in each step for $\pi_1$ but 0 in each step for $\pi_2$. Also, the rewards in the steps after step $T$ can also differ by at most 1 and by our choice of $T$, we have that outcome contributed from these remaining steps are worth less than $\varepsilon/2$ as well. Hence, we see that $\sigma'$ obtains the same as $\sigma$ except for $\varepsilon$ against any strategy $\tau$ and is thus $\varepsilon$-optimal. $\square$

There is a classic problem in geometry called the sum-of-square-roots problem. The problem is defined as follows: Let $a, b_1, b_2, \dots, b_n$ be natural numbers. Is $\sum_{i=1}^n \sqrt{b_i} > a$?

The problem comes up for decision problems about distances in Euclidean space. It is not known to be in P or NP for that matter, but is in the fourth level of the countering hierarchy, slightly inside PSPACE. The issue is in essence that it is not known how good an approximation of $\sqrt{b_i}$ is necessary to decide the strict inequality.

We will use the sum-of-square-roots problem to give an informal hardness argument, in that finding the exact value of a concurrent game is in general harder than solving the sum-of-square-roots problem.
<figure><img src="image_60.png" /><figcaption>Figure 7.2: Concurrent discounted game with value $v_s = -2 + \sqrt{4+2(1-\gamma)}$</figcaption></figure>

Consider the following game $G$: There are three vertices, $\{0, 1, s\}$ where 0 and 1 are absorbing, with color 0 and 1 respectively. The vertex $s$ is such that $(1) c(s, i, j) = 0$, $(2) \Delta(s, i, i) = 1$ (for $i \in \{1, 2\}$), $(3) \Delta(s, 2, 1) = 0$ and $(4) \Delta(s, 1, i)$ is the uniform distribution over $s$ and 0. The game is illustrated in Figure 7.2.

Consider an optimal stationary strategy in $G$ for Eve. Let $p$ be the probability with which she plays the first action. If Adam knows that Eve will follow this strategy, the game devolves into a MDP. We know from that for such there exists optimal positional strategies and thus Adam is either going to play the left or right column always. Clearly, $0 < p < 1$ because $p = 0$ or 1 means that either playing the left or right column with probability 1 would ensure that no positive reward ever happens.

Let $v_0 = 0, v_1 = 1, v_s$ be the values of the three vertices. If he plays the left column, the outcome is $p(1-\gamma)$. If he plays the right column, the outcome is $p/2(1-\gamma)v_s + (1-p)(1-\gamma)$. Observe that the former is increasing in $p$ and the latter is decreasing (since clearly, $0 < (1-\gamma)v_s < v_s$). Also, both are continues. Thus, the optimum is for $p(1-\gamma)$ to be equal to $p/2(1-\gamma)v_s + (1-p)(1-\gamma)$ and both equal to $v_s$. We will first isolate $v_s$ in $v_s = p/2(1-\gamma)v_s + (1-p)(1-\gamma)$.

$$v_s = p/2(1-\gamma)v_s + (1-p)(1-\gamma) \Rightarrow (1-p/2(1-\gamma))v_s = (1-p)(1-\gamma) \Rightarrow \\ v_s = \frac{(1-p)(1-\gamma)}{1-p/2(1-\gamma)}.$$

Note that $p, \gamma < 1$ thus, $1-p/2(1-\gamma) \neq 0$. We then have the equality

$$\begin{align*} \frac{(1-p)(1-\gamma)}{1-p/2(1-\gamma)} &= p(1-\gamma) \Rightarrow \\ (1-p)(1-\gamma) &= p(1-\gamma)(1-p/2(1-\gamma)) \Rightarrow \\ 0 &= \frac{1-\gamma}{2}p^2 + 2p - 1 \Rightarrow \\ p &= \frac{-2 \pm \sqrt{4+2(1-\gamma)}}{1-\gamma}. \end{align*}$$

We see that $\frac{-2-\sqrt{4+2(1-\gamma)}}{1-\gamma} < 0$. Thus, $p = \frac{-2+\sqrt{4+2(1-\gamma)}}{1-\gamma}$. Also,

$$v_s = -2 + \sqrt{4+2(1-\gamma)}.$$

It is straightforward to modify the construction to get any square-root desired for a fixed $\gamma$.
<table><caption>Figure 7.3: Alternate concurrent discounted game with value $v_s = -2 + \sqrt{4 + 2(1 - \gamma)}$</caption><tr><td></td><td>1*</td><td>0</td><td>0*</td></tr><tr><td>s :</td><td>1*</td><td>0*</td><td>0</td></tr><tr><td></td><td>0*</td><td>1*</td><td>1*</td></tr></table>

By making such a construction for each number $\sqrt{b_i}$, we can make another vertex $s^*$ that has the value of $(1 - \gamma) \sum_{i=1}^{n} \frac{\sqrt{b_i}}{n}$ with a single action for each player and that goes to a uniformly random vertex. Observe that decreasing each reward by $x$, reduces the value of each vertex by $x$. Reduce each reward by $\frac{an}{1-\gamma}$. We can then decide the sum-of-square-roots problem by deciding whether the value of $s^*$ is strictly above 0.

We get the following lemma.

**Lemma 98.** The (exact) decision problem for the value is sum-of-square-root hard for concurrent discounted payoff games.

We will use this game $G$ as an example to illustrate how to make the $\Delta$-function deterministic for concurrent games while having the same value and a similar optimal strategy.

Consider the following game $G'$: There are three vertices, $\{0, 1, s\}$ where 0 and 1 are absorbing, with color 0 and 1 respectively. The vertex $s$ is such that $(1) c(s, i, j) = 0$ for all $i, j$, $(2) \Delta(s, i, j) = s$ for $i+1 = j$ (i.e. for $(i, j) \in \{(1, 2), (2, 3)\})$, $(3) \Delta(s, i, j) = 0$ for $i + j = 4$ (i.e. the “other” diagonal, $(i, j) \in \{(3, 1), (2, 2), (1, 3)\})$ and $(4) \Delta(s, i, j) = 1$ otherwise (i.e. for $(i, j) \in \{(1, 1), (2, 1), (3, 2), (3, 3)\}$). The game is illustrated in Figure 7.3.

We will argue that the value of $G'$ is equal to that of $G$. We clearly have that the value of $s$ is in $(0, 1)$. Consider a stationary strategy $\sigma$ for Eve such that $\sigma(1) \neq \sigma(2)$. Let $p_i = \sigma(i)$ for $i \in \{1, 2, 3\}$. Let $\sigma'$ be such that $\sigma'(3) = p_3$ and otherwise, $\sigma'(i) = \frac{p_1+p_2}{2}$ for $i \in \{1, 2\}$. Let $p'_i = \sigma'(i)$ for $i \in \{1, 2, 3\}$.

**Claim 2.** The strategy $\sigma'$ is at least as good as $\sigma$.

*Proof.* If Adam plays 1, then the expected outcome is $p_1 + p_2 = p'_1 + p'_2$ no matter if Eve plays $\sigma$ or $\sigma'$. If he plays $i$ for $i \in \{2, 3\}$, the expected outcome is $\frac{p_{4-i}}{1-p_{i-1}}$ if Eve plays $\sigma$ and otherwise, if she plays $\sigma'$, the expected outcome is $\frac{p'_1}{1-p'_2} = \frac{p'_2}{1-p'_1}$. Note that $\frac{p'_1}{1-p'_2} > \min_{i \in \{2, 3\}} \frac{p_{4-i}}{1-p_{i-1}}$ and thus, $\sigma'$ is at least as good a strategy as $\sigma$. $\square$

A similar argument shows that for any strategy $\tau$ for Adam the similar strategy $\tau'$ where $\tau'(1) = \tau(1)$ and $\tau'(i) = \frac{\tau(2)+\tau(3)}{2}$ for $i \in \{2, 3\}$ is at least as good as $\tau$. Consider
<figure><img src="image_61.png" /><figcaption>Figure 7.4: Concurrent discounted game that implies that if there is an exponential lower bound on patience, then the sum-of-square-roots problem is in P</figcaption></figure>

that the players follows such stationary strategies $\sigma'$ and $\tau'$. Let $\sigma$ be

$$ \sigma(i) = \begin{cases} \sigma'(1) + \sigma'(2) & \text{if } i = 1 \\ \sigma'(3) & \text{if } i = 2. \end{cases} $$

Similarly, let $\tau$ be

$$ \tau(i) = \begin{cases} \tau'(1) & \text{if } i = 1 \\ \tau'(2) + \tau'(3) & \text{if } i = 2. \end{cases} $$

But playing $\sigma$ and $\tau$ in $G$ gives the same outcome as playing $\sigma'$ and $\tau'$ in $G'$ as can be seen as follows: In either game, with probability

$$ \sigma'(1)\tau'(2) + \sigma'(2)\tau'(3) = \frac{\sigma(1)\tau(2)}{2} $$

we play again with a reward of 0, with probability

$$ \sigma'(1)\tau'(3) + \sigma'(2)\tau'(2) + \sigma'(3)\tau'(1) = \frac{\sigma(1)\tau(2)}{2} + \sigma(2)\tau(1) $$

we get absorbed in 0 after a reward of 0 and with probability

$$ (\sigma'(1) + \sigma'(2))\tau'(1) + (\tau'(2) + \tau'(3))\sigma'(3) $$

we get absorbed in 1 after a reward of 0. But this is in particular the case if the players play optimally and thus, the value is the same in the two games.

Before, in Corollary Lemma 96, we argued that the patience of $\epsilon$-optimal stationary strategies was $q = \frac{m\log(\epsilon/2)}{\log(1-\gamma)\epsilon}$. Giving a similar exponential bound for the optimal stationary strategies is harder than solving the sum-of-square-roots problem, as we will argue next. Assume that we had an exponential bound for optimal stationary strategies.

Consider an arbitrary yes-instance of the sum-of-square-roots problem, giving a vertex $s^*$. Reduce each reward by $a$ and in the new game let $s_a^*$ be the vertex corresponding to $s^*$. We will now create a game that uses the previous game as a sub-game. The game has 1 additional vertex $s'$, which is a 2x2-matrix, such that $c(s', i, j) = 0$ and $\Delta(s, 1, 1) = 1$ and $\Delta(s, 2, 2) = s^*$ and $\Delta(s, i, j) = 0$ for $i \neq j$. There is an illustration in Figure 7.4, using the vertex $s^*$ as above. Using an argument like above, we see that the probability $p$ to play the top action in the vertex $s'$ is such that $p(1 - \gamma) =$
<figure><img src="image_62.png" /><figcaption>Figure 7.5: The snowball game or purgatory 1, in which no optimal strategy exists for Eve</figcaption></figure>

$(1-p)(1-\gamma)x$, where $x$ is the value of $s^*$. Thus, $x = \frac{p}{1-p}$. If $p$ only needs to be exponential small, then $x$ is exponentially small as well. This is true for any yes-instance of the sum-of-square-roots problem and thus, we only need polynomially many digits to decide the problem. We can find polynomially many digits of $\sqrt{b_i}$ for each $i$ in polynomial time. We get the following lemma.

**Lemma 99.** *Giving an exponential lower-bound on patience for optimal stationary strategies in concurrent discounted payoff games implies that the sum-of-square-roots problem is in P*

## 7.4 Concurrent reachability games

In this section we consider concurrent reachability games. Intuitively, unlike concurrent discounted payoff games, these games cares only about the final part of the play. This, while perhaps not clear directly from the definitions, makes the games somewhat harder. For instance, the value iteration algorithm requires double-exponential time. Note that like for concurrent discounted payoff games, if we force Eve to follow some strategy, the game reduces to a MDP and there exists optimal positional strategies.

We will not prove the following known lemma. We will however, show the weaker statement that the decision problem for the value can be done in PSPACE.

**Lemma 100 (Properties of concurrent reachability games).** *Concurrent reachability games are determined. Also, finding the value of a concurrent reachability game can be done in TFNP[NP].*

We will argue that there might not be optimal strategies for Eve in concurrent reachability games. The game we will use will later be a member of a family of games that requires high patience to play well.

The snowball game (or purgatory 1) is defined as follows: There are 3 vertices, the goal vertex Win, $\perp$ (an absorbing vertex) and a vertex 1, which has a 2x2 matrix, such that $\Delta(x, r, c)$ is a Dirac distribution over (1) Win for $r=c$, (2) 1 for $r < c$ and (3) $\perp$ for $r > c$. When we illustrate the game, we write view the goal vertex Win as being an absorbing vertex with color 1. There is an illustration of the snowball game in Figure 7.5.

For any $\epsilon > 0$, consider the stationary strategy for Eve that plays the first action with probability $1 - \epsilon$. If Adam plays the left column always, play will reach Win with
pr. $1 - \varepsilon$. If Adam plays the right column always, play reaches Win with pr. 1. Hence, the strategy for Eve is $\varepsilon$-optimal and the value of the vertex is 1.

On the other hand, if Adam plays the right column whenever Eve plays the first action with pr. 1, and otherwise plays the first action, then in the last round in the vertex there must be a positive pr. that play goes to vertex 0. Hence, Eve has no optimal strategy.

**Lemma 101** (No optimal strategies in concurrent reachability games). *Eve need not have an optimal strategy in a concurrent reachability game.*

The following lemma states some classical results for concurrent reachability games that we will not prove.

**Lemma 102** (Classical results for concurrent reachability games). *For any $\varepsilon > 0$, there are always $\varepsilon$-optimal stationary strategies for Eve and optimal stationary strategies for Adam.*

* The value iteration algorithm converges to the optimal value and is defined exactly like for concurrent discounted payoff games, except that $\gamma = 0$ and the target vertex has value 1 in the first iteration.

* The values $v$ are the least fixed point (i.e., every other fixed point $v'$ is such that for all $i$ $v_i \le v'$) of the value iteration operator $\text{valOp}$.

(Note that the games are not symmetric, in that Eve tries to reach a node and Adam tries to stay away from it, and in particular, even though Eve need not have an optimal strategy in a concurrent reachability game, Adam always has one.)

The decision problem for the existential first order theory over the reals is the following decision problem: Given a function $F: \mathbb{R}^n \to \{\text{true, false}\}$, is there an vector $v$ such that $F(v)$ is true? The function $F$ must be a well-formed (i.e. connected with logical ‘and’, ‘or’ and ‘not’) quantifier-free formula over polynomial inequalities. E.g. $x^2y + z \ge 5 \wedge \neg(xz \le 3)$ would be such a function.

**Lemma 103.** *The decision problem for the existential theory over the reals is in PSPACE*

We will now, given a number $c$, encode the problem whether the value in a concurrent reachability game is $< c$, starting from some vertex $x$. The idea is that we can describe a fixed point of the value iteration operator, i.e. we can describe that $v_i = \text{val}[M^i(v)]_i$. Since we know that the values are the least fixed point, we can then just add the condition that $v_x < c$. We can describe the value of a matrix game by guessing a strategy for each player, $\sigma$ for Eve and $\tau$ for Adam, and then checking that these strategies are optimal by showing that the outcome obtained by following Eve's strategy is equal to what is obtained by following Adam's. I.e. we check that for Eve's strategy, the least outcome obtained when Adam plays any given column is $v_i$ and similar for Adam. We describe that as $v_i = \min_{a \in [m]} (\sigma M_{*,a}^i(v))$ and $v_i = \max_{a \in [m]} (\tau M_{*,*}^i(v))$, where $M_{*,j}^i(v)$ is the $j$-th column of $M^i(v)$ and $M_{j,*}^i(v)$ is the $j$-th row for all $j$. We can express that $x = \min(a_1, a_2, \dots, a_n)$ for any number $n$ and any polynomials $a_1, a_2, \dots, a_n$, in the first order theory of the reals by stating that

$$x \le a_1 \wedge x \le a_2 \wedge \dots \wedge x \le a_n \wedge (x = a_1 \vee x = a_2 \vee \dots \vee x = a_n).$$
Similarly, one can also describe that $x = \max(a_1, a_2, \dots, a_n)$ for any number $n$ and any polynomials $a_1, a_2, \dots, a_n$.

We can similarly make a statement that $v_x \le c$. Using that PSPACE is equal to co-PSPACE, we also get that we can find if $v_x \ge c$ and $v_x > c$ and therefore also $v_x = c$ and $v_x \ne c$, all in PSPACE.

**Lemma 104.** *Decision problems for the values in a concurrent reachability game is in PSPACE.*

The set of vertices that have value 0 can be found in polynomial time. This is because, the set of vertices that have value 0 in the time limited game of length $n$ has also value 0 in all other time limited games. That this is so is easy to see by considering that Eve plays an $\varepsilon$-optimal strategy for $v > \varepsilon$, where $v$ is the value of the vertex with the lowest value. The game then devolves to a MDP for Adam, and the statement is true for such.

**Lemma 105 (Value 0 vertices in concurrent reachability games).** *The set of vertices of value 0 in a concurrent reachability game can be found in polynomial time.*

Next, we argue that we can find the set of vertices $S_1$ that have value 1 in polynomial time as well. For notational convenience, for stationary strategies $\sigma, \tau$ we will, for a set $x$ and a set of vertices $S$ use

$$F^{\sigma, \tau}(x, S) := \sum_{r \in A_1} \sum_{c \in A_2} \sum_{x' \in S} \sigma(x)(r)\tau(x)(c)\delta(x, r, c)(x'),$$

i.e. the probability when the players follows $\sigma, \tau$ to go from $x$ directly to a vertex in $S$.

For a set $S$, containing Win and a non-empty subset $S' \subseteq (S \setminus \{\text{Win}\})$ and a vertex $x \in S'$, let the *subset property* be the following: For each $\varepsilon > 0$, there is a strategy $\sigma$ for Eve, such that for any strategy $\tau$ for Adam, $F^{\sigma, \tau}(x, S \setminus S') \cdot \varepsilon > F^{\sigma, \tau}(x, V \setminus S)$.

For a set $S$, containing Win, let the *value-1-property* be that the subset property is satisfied for each $S' \subseteq (S \setminus \{\text{Win}\})$ (with some $x \in S'$). For a set $S$ satisfying the value-1-property, we will define some subsets. Let $S^0$ be the set consisting of Win. Let $S^i$, for each $i \ge 1$ be the set of vertices such that for each $x \in S^i$, the vertex $x$ satisfies the subset property for $S'$ and $S = \cup_{j=0}^{i-1} S^j$. Let $\ell$ be the largest number such that $S^\ell$ is non-empty (note that $S^i$, for $i > \ell$ must then be empty).

We will be using the following lemma.

**Lemma 106.** *The set of vertices $S_1$ of value 1 satisfies the value-1-property.*

*Proof.* The proof is by contradiction. Thus, there is an $S$ (not containing Win) such that $S_1$ and $S$ does not satisfy the subset property for any $x \in S$. I.e. for some constant $\varepsilon > 0$, $F^{\sigma, \tau}(x, S_1 \setminus S)\varepsilon \le F^{\sigma, \tau}(x, V \setminus S_1)$ for any strategy $\sigma$ for Eve and some strategy $\tau_\sigma$ for Adam and for every $x \in S$. But then, all vertices in $S$ have value $\le (1 - \varepsilon) + \varepsilon V_{\max}$ where $v_{\max} < 1$ is the largest value of a vertex in $V \setminus S_1$. This is because to get to Win from $S$, it must leave $S$ and in that step, the probability to go to a vertex in $V \setminus S_1$ (from which one cannot obtain more than $v_{\max}$) is at least the constant $\varepsilon$. $\square$

We will argue that this is a precise characterization of $S_1$ next.
**Lemma 107.** Consider a set $S'$ satisfying the value-1-property, then each vertex of $S'$ has value 1.

*Proof.* We will for all $i$ and any $\epsilon > 0$ construct a strategy $\sigma_{i,\epsilon}$ for Eve that starting from a vertex in $\bigcup_{j=i}^n S^j$ will eventually get to $S^{i-1}$ with probability at least $1 - \epsilon$ (especially, the strategy $\sigma_{1,\epsilon}$ is $\epsilon$-optimal). We will do it using backwards induction in $i$ and thus start from $i = \ell$.

Note that the base case for $i = \ell$ follows directly from the condition. We now for any $\epsilon > 0$ will find a strategy $\sigma_{i,\epsilon}$, given that we have a strategy $\sigma_{i+1,\epsilon'}$ for any $\epsilon' > 0$. The idea is that the subset property gives a strategy $\sigma$ such that for all $\tau$, $F^{\sigma,\tau}(x, S' \setminus S)\epsilon/2 > F^{\sigma,\tau}(x, V \setminus S')$, for $S = \bigcup_{j=i}^n S^j$. Note that in expectation, following this strategy, we go to some other vertex in $S$ with at least some fixed probability $p$ (that could be quite close to 1). Hence, in expectation, we need to be in such a vertex $1/(1-p)$ times before entering either $S' \setminus S$ or $V \setminus S'$. We therefore follow the strategy $\sigma_{i+1,\epsilon'}$ in $\bigcup_{j=i+1}^n S^j$, where $\epsilon' = \epsilon/(2(1-p))$. The inductive construction then follows by applying union bound over the $1/(1-p)$ times we are in $S^i$. $\square$

Note that the lemmas together show that $S_1$ is the largest set satisfying the value-1-property.

Our algorithm, $\mathcal{A}_1$, for finding $S_1$ is then as follows: Assign to each vertex $x$ a rank $rk_x$, a value in $0, 1, \dots, n, \perp$, starting with $rk_x = 0$. Let $\bar{S}^i$ be the set of vertices of rank $i$. Let $\bar{S}_1 = V \setminus S^\perp$. We increment (where a rank is less than another if it is a smaller number. Also, all other ranks are below $\perp$) the rank of a non-goal vertex $x \in \bar{S}^i$, whenever it does not satisfy the subset property for $S = \bar{S}_1$ and $S' = \bigcup_{j=i}^n \bar{S}^j$. Note that no vertex can satisfy the subset property for rank 0, since $S'$ is all vertices. Whenever a stable configuration is reached, output $\bar{S}_1$.

**Lemma 108.** The output of the $\mathcal{A}_1$ algorithm is correct.

*Proof.* The idea is that we want $S^i = \bar{S}^i$ at termination. Note that the subset property is harder to satisfy for a vertex $x$ if we remove vertices from $S$ or from $(S \setminus S')$. Thus, if at some time we have that $x$ does not satisfy the subset property for $S = \bar{S}_1$ and $S' = \bigcup_{j=i}^n \bar{S}^j$, then it does not do so for $S$ being any subset of $\bar{S}_1$ or $(S \setminus S')$ being any subset of $\bigcup_{j=0}^{i-1} \bar{S}^j$. However, initially $S_1 \supseteq \bar{S}_1$ (being all vertices) and $\bigcup_{j=i}^n S^j \supseteq \bigcup_{j=0}^{i-1} \bar{S}^j$ for all $i$. But we must have that $S_1 \supseteq \bar{S}_1$ and $\bigcup_{j=i}^n S^j \supseteq \bigcup_{j=0}^{i-1} \bar{S}^j$ for all $i$, at all latter points as well, since in the last iteration it was satisfied, for all $i$ and all $x \in S^i$, we have that the subset property is satisfied for $S = \bar{S}_1$ and $S' = \bigcup_{j=i}^n \bar{S}^j$, because we have that $S \supseteq S_1$ and $(S \setminus S') = \bigcup_{j=1}^{i-1} \bar{S}^j \supseteq \bigcup_{j=1}^{i-1} S^j$. On the other hand, eventually no vertex gets it rank incremented (since there are a finite number of ranks and vertices) and the algorithm terminates with a set $\bar{S}_1 \supseteq S_1$ satisfying the value-1-property. Since $S_1$ is the largest such set, we have that $\bar{S}_1 = S_1$. $\square$

We will now consider the running time of the algorithm. We will consider that we can decide whether a pair of sets $S$ and $S'$ satisfies the subset property for a vertex $x$ can be solved in $O(k)$ time. Let $S_x$ be the set of vertices that can be visited in a play
immediately after $x$. Observe that $|S_x|$ is a lower bound on the number of arrows from matrix $x$ in our illustration of the game. Consider a vertex $x$ and a rank $i$, and we want to find an upper bound on the computation we do on $x$ while it has rank $i$. Clearly, we only need to consider incrementing the rank of $x$ whenever a vertex in $S_x$ has changed its value and only if it is changed to either $i$ (from $i-1$) or to $\perp$ (from $n$), because otherwise, the sets $S$ and $S'$ have not changed. Thus, we only do at most $2|S_x| + 1$ checks whether $x$ satisfies the subset property. There are $n+1$ ranks, so in total for $x$, we use at most $(n+1)(2|S_x| + 1)$ checks. Hence, in total over all $x$, we do $O(n\sum_x |S_x|)$ checks.

**Lemma 109.** *The runtime of the $\mathcal{A}_1$ algorithm is $O(nk\sum_x |S_x|)$.*

We will then finally consider how to check whether $x$ satisfies the subset property for a pair of sets $S$ and $S'$. We will do so by constructing a strategy $\sigma = \sigma(\varepsilon)$ for Eve satisfying the property for any fixed $\varepsilon > 0$. We will construct the strategy $\sigma$ from some sequence of pairs of sets (of rows and columns) $(R_1, C_1)$, $(R_2, C_2)$, ..., $(R_\ell, C_\ell)$. We will let $C_i^* = \cup_{j=1}^i C_j$ and similar for $R_i^*$. For convenience, we also define $C_0^*$ as the empty set of columns. We will define $R_i$ from $C_{i-1}^*$ as each row $r \notin R_{i-1}^*$ such that, for all $c \notin C_{i-1}^*$, we have that $F^{r,c}(x, V \setminus S) = 0$. We will define $C_i \notin C_{i-1}^*$ from $R_i$ as each column $c$ such that there is a $r \in R_i$ such that $F^{r,c}(x, S \setminus S') > 0$. The set $R_\ell^*$ is the first set such that $R_{\ell+1}^*$ is empty (clearly, by construction all sets $R_i, C_i$ for $i > \ell$ would also be empty).

**Lemma 110.** *There is a strategy $\sigma(\varepsilon)$ for all $\varepsilon > 0$ if and only if $C_\ell^*$ is the set of all columns.*

*Proof.* We will first argue that if $C_\ell^*$ is not all columns $C$, then the strategy $\tau$ that plays uniformly over $C' = (C \setminus C_\ell^*)$ shows that no strategy $\sigma(\varepsilon)$ exists for small enough $\varepsilon > 0$. This is because any row $r$ such that $F^{r,c}(x, S \setminus S') > 0$ for some $c \in C'$ is also such that $F^{r,c'}(x, V \setminus S) > 0$ for some column $c' \in C'$. This is because otherwise $r$ would be in $R^i$ for some $i$ and then $c$ would be in $C_\ell^*$. Hence, the probability $F^{r,c'}(x, V \setminus S)$ cannot be more than a constant factor smaller than $F^{r,c}(x, S \setminus S')$.

Otherwise, if $C_\ell^* = C$, then let $\sigma(\varepsilon)$ be the strategy that picks an $i$ from the distribution $\mathcal{D}$ and then plays an action in $R^i$ uniformly at random. The distribution $\mathcal{D}$ is such that for all $j \in \{1, \dots, \ell-1\}$ we have $\Pr_{\mathcal{D}}[i=j] \varepsilon \delta_{\min}/m = \Pr_{\mathcal{D}}[i>j]$.

To argue that $\sigma = \sigma(\varepsilon)$ satisfies the subset property for $x, S, S'$ consider each column $c$. We have that $c \in C^j$ for some $j$. Let $p$ be the pr. with which a row in $R^j$ is played by $\sigma$ and thus, $F^{\sigma,c}(x, S \setminus S') \ge p \delta_{\min} > 0$. Any row $r$ such that $F^{r,c}(x, V \setminus S) > 0$ must be outside $R_j^*$ by construction (and if such a row exists $j < \ell$). We play such rows with pr. $\le \Pr_{\mathcal{D}}[i>j]$ and thus $\Pr_{\mathcal{D}}[i>j] \ge F^{\sigma,c}(x, V \setminus S)$. We have that $pm > \Pr_{\mathcal{D}}[i=j]$ (strict because $j < \ell$) and thus,

$$F^{\sigma,c}(x, S \setminus S') \varepsilon \ge p \delta_{\min} \varepsilon > \delta_{\min} \varepsilon / m \Pr_{\mathcal{D}}[i=j] \ge \Pr_{\mathcal{D}}[i>j] \ge F^{\sigma,c}(x, V \setminus S).$$

This completes the proof of the lemma. $\square$

<figure><img src="image_63.png" /></figure>

Our algorithm for checking if a vertex $x$ satisfies the subset property for sets $S, S'$ is as follows: We will construct the sequence of sets $(R_1, C_1), (R_2, C_2), \dots, (R_\ell, C_\ell)$. To do
<figure><img src="image_64.png" /><figcaption>Figure 7.6: Purgatory 4. For clarity, the colors are omitted, except that 0* corresponds to an edge to an absorbing vertex different from Win and 1* corresponds to an edge to Win</figcaption></figure>

so we will use a data structure. The data structure has the following properties: Initially, for each column c, we will make a list $L_c$ of the rows r such that $F^{r,c}(x, V \setminus S) > 0$. We will also have a counter for each row r that initially contains how many such columns there are. Finally for each row r, there is a list $L_r$ of columns such that $F^{r,c}(x, S \setminus S') > 0$.

The algorithm then uses the data structure as follows: Let $i \leftarrow 1$. Add all the rows with the counter at 0 to $R^i$. If $R^i$ is the empty set, return whether $C_{i-1}^*$ is all columns. For each row r in $R^i$ go through $c \in L_r$ and subtract 1 from the counter of each row in $L_c$. If a counter reach 0, add it to $R^{i+1}$. Increment $i$. Go to line 3.

The total running time the algorithm is $O(\sum_{r,c} |\text{supp}(\Delta(x, r, c))|)$.

**Lemma 111.** *We can check whether a vertex x satisfies the subset property for sets S and S' in time*

$$O(\sum_{r,c} |\text{supp}(\Delta(x, r, c))|).$$

We therefore get that

**Lemma 112.** *We can compute the set of vertices of value 1 in time*

$$O\left(n \sum_x |S_x| \sum_{r,c} |\text{supp}(\Delta(x, r, c))|\right).$$

Next, we will give a lower bound for patience: we prove that in some games, the patience for every $\epsilon$-optimal stationary strategy must be high. For a number $k$, let purgatory $k$ be the following game: There are $2+k$ vertices, Win (which is vertex 0), one vertex $\perp$ which is absorbing and each other vertex $i \in \{1, \dots, k\}$ has a $2 \times 2$ matrix, such that $\Delta(x, r, c)$ is a Dirac distribution over $(1) i-1$ for $r=c$, $(2) k$ for $r < c$ and $(3) \perp$ for $r > c$. There is an illustration of Purgatory 4 in Figure 7.6.

It is easy to see that all vertices but $\perp$ are in $S_1$ using the value 1 property.
**Lemma 113 (Properties of the purgatory game).** For any $0 < \varepsilon < 1/2$ and any $k \ge 1$, there is a unique strategy for Eve with least patience which is $\varepsilon$-optimal in purgatory $k$. That strategy has patience $\varepsilon^{-2^{k-1}}$

*Proof.* We will find the best strategy with patience $1/p$ for any number $0 < p < 1/2$. It is clear that the best strategy with patience $1/p$ is to play the strategy that maximizes the pr. of eventually reaching $i$ from vertex $j$ for all $j > i$ while having patience $1/p$. Let $x_k = 1-p$ and let $x_i = 1 - \sqrt{1-x_{i+1}}$. We will argue that $x_i$ is the probability of eventually reaching vertex $i-1$ from vertex $k$ for all $i \in \{1, \dots, k\}$ and that there is a unique best strategy with patience $1/p$.

The unique best strategy in vertex $k$ is to play the top action with pr. $1-p$ and the bottom action with pr. $p$. This ensures that the pr. $x_k$ of reaching $k-1$ from $k$ is $1-p$ if Adam plays the left column.

Consider now vertex $i \in \{1, \dots, k-1\}$. For the purpose of finding good strategies in $i$, we can view vertex $i$, when Eve plays her best strategy in $j > i$ and Adam plays a best response, as a smaller reachability game with 3 vertices, i.e. $i-1$ (as Win), $\perp$ and $i$, where $\Delta(i, r, c)$ is (1) a Dirac distribution over $i-1$ for $r=c$, (2) a Dirac distribution over $\perp$ for $r > c$ and (3) a distribution that goes to $\perp$ with pr. $1-x_{i-1}$ and to $i$ with the remaining pr. for $r < c$. See Figure 7.6.

Let $p_i$ be the probability with which a strategy $\sigma$ plays the top row in vertex $i$. We can then consider the game as a MDP, since we have fixed a stationary strategy for one of the players. It is clear that the pr. to reach $i-1$ from $i$ if Adam plays the right column is strictly increasing in $p_i$ and the pr. to reach $i-1$ from $i$ if Adam plays the left column is strictly decreasing in $p_i$. We will consider the strategy such that the pr. of reaching $i-1$ is equal no matter which column Adam plays (by the previous statement, this strategy must then be optimal). Observe that the pr. of reaching $i-1$ if Adam always plays the left column is $p_i$ (which is then also the pr. to reach $i-1$ from $i$) and if he always plays the right column it is $p_i x_i p_i + (1-p_i)$ (using that the pr. of reaching $i-1$ from $i$ is $p_i$). Thus, we have that

$$p_i = p_i x_i p_i + (1-p_i) \Rightarrow 0 = p_i^2/2x_i - p_i + 1/2 \Rightarrow p_i = \frac{1 \pm \sqrt{1-x_i}}{x_i}.$$

We see that $\frac{1+\sqrt{1-x_i}}{x_i} > 1$ and thus the solution is $p_i = \frac{1-\sqrt{1-x_i}}{x_i}$ or that $(x_{i-1}) = x_i p_i = 1 - \sqrt{1-x_i}$.

Consider now that the strategy is exactly $\varepsilon$-optimal, implying that $x_1 = 1 - \varepsilon$. We will argue that $p = \varepsilon^{2^{k-1}}$. We will do so by arguing using induction in $i$ that $x_i = 1 - \varepsilon^{2^{k-1}}$, since $x_k = 1-p$ (this also shows that the strategy is indeed using patience $1/p$ since the probabilities in the other vertices, which are $p_i = \frac{x_{i-1}}{x_i}$, are strictly above $1/p$). We have already noted that $x_1 = 1 - \varepsilon = 1 - \varepsilon^{2^0}$. We will next argue that $x_i = 1 - \varepsilon^{2^{k-1}}$, for $i \ge 2$ using that $x_{i-1} = 1 - \varepsilon^{2^{k-2}}$. We have that

$$1 - \varepsilon^{2^{k-2}} = x_{i-1} = 1 - \sqrt{1 - x_i} \Rightarrow \sqrt{1 - x_i} = \varepsilon^{2^{k-2}} \Rightarrow 1 - \varepsilon^{2^{k-1}} = x_i.$$

This completes the proof of the lemma. $\square$
<figure><img src="image_65.png" /><figcaption>Figure 7.7: Purgatory duel 2. For clarity, the colors are omitted, except that 0* corresponds to an edge to an absorbing vertex different from Win and 1* corresponds to an edge to Win</figcaption></figure>

Concurrent reachability games are not symmetric in the players. E.g. Adam always have an optimal strategy but Eve might not. We will next argue that Adam still requires double exponential patience to play well.

Consider the following game called purgatory duel $k$ which can be viewed as a symmetric version of purgatory $k$. There are $3+2k$ vertices, Win (which is vertex 0), one vertex $⊥$ which is absorbing (and is also vertex 0'), and the start vertex $s$ and each other vertex $\{1, \dots, k, 1', \dots, k'\}$ has a $2 \times 2$ matrix. Each vertex $x \in \{1, \dots, k\}$ is such that $\Delta(x, r, c)$ is a Dirac distribution over (1) $x-1$ for $r=c$, (2) $s$ for $r < c$ and (3) $⊥$ for $r > c$. Each vertex $x' \in \{1', \dots, k'\}$ is such that $\Delta(x', r, c)$ is a Dirac distribution over (1) $x-1'$ for $r=c$, (2) $s$ for $r < c$ and (3) Win for $r > c$. The start vertex is $1 \times 1$ matrix and is such that $\Delta(s, r, c)$ is a uniform distribution over $k$ and $k'$. There is a illustration of Purgatory Duel 2 in Figure 7.7.

We will say that a strategy $\sigma$ for Eve mirrors a strategy $\tau$ for Adam, if $\sigma(i) = \tau(i')$ and $\sigma(i') = \tau(i)$ for all $i$. Similarly, $\tau$ mirrors $\sigma$.

**Lemma 114.** The value of vertex $s$ is $1/2$. Also, for any $\varepsilon > 0$, any $(1/2 - \varepsilon)$-optimal strategy $\tau$ for Adam does not follow a Dirac distribution in $i'$ for any $i' \in \{1', \dots, k'\}$. Finally, every $\varepsilon$-optimal strategy is a mirror of an $\varepsilon$-optimal strategy

*Proof.* First, the value of vertex $s$ is at most $1/2$. This is because Adam can mirror any strategy $\sigma$ for Eve. This ensures that any play reaching Win is mirrored by an equally likely play reaching $⊥$. Thus, then the players follows these strategies, the pr. to reach
Win is equal to the pr. to reach $\perp$ (there might also be some positive pr. to not reach neither, but Adam also wins those plays).

Fix $\varepsilon > 0$ and consider a strategy $\tau$ for Eve that plays a Dirac distribution in $i' \in \{1', \dots, k'\}$. Then $\tau$ is not $(1/2 - \varepsilon)$-optimal. We can see that as follows: Let $\sigma$ be the strategy for Eve that plays $r = 1$ when in $j' \in \{(i+1)', \dots, k'\}$ and the action which is not equal to $\tau(i')$ when in $i'$. This ensures that the play will always reach either Win or $s$ from $k'$. But then Eve can play an $(\varepsilon/2)$-optimal strategy for purgatory $k$ in $\{1, \dots, k\}$, ensuring that Win is reached with pr. at least $1 - \varepsilon/2$. But then $\tau$ is not $(1/2 - \varepsilon)$-optimal.

Consider that Adam is following a strategy $\tau$ that is not playing a Dirac distribution in $i' \in \{1', \dots, k'\}$ and Eve is playing an arbitrary strategy $\sigma$. Then, eventually play reaches Win or $\perp$ with pr. 1, because in every $k+1$ steps, either $s$ is visited or either Win or $\perp$ is reached, and after $s$ has been visited, $k'$ is next half the time and from $k' \perp$ is reached with positive pr.

Consider an $\varepsilon$-optimal strategy $\tau$ for Adam, for $\varepsilon < 1/2$. Then, let Eve's mirror strategy to $\tau$ be $\sigma_\tau$. Now, either Win or $\perp$ is reached and because the strategies mirrors each other, the pr. to reach Win is equal to that of reaching $\perp$. Thus, we see that the value is at most $1/2$, implying that it is exactly $1/2$.

It also follows that the strategies that are $\varepsilon$-optimal mirrors each other. $\square$

We will now argue that Eve's (and thus Adam's) $\frac{1}{4}$-optimal strategies requires high patience.

To do so we will use the following lemma, showing that you can sometimes modify a concurrent game (or any of its special cases) and get a game with less value. While the proof is explicitly for concurrent reachability games, the proof is basically identical for concurrent discounted and mean payoff games. In a game $G$, for a vertex $v$ and a duration $T$, let $v_G^T$ be the value of the time-limited game with duration $T$.

**Lemma 115.** Consider a concurrent reachability game $G$ and a pair of vertices $u, v$, such that for all $T$, we have that $u_G^T \ge v_G^T$. Consider a vertex $w$ such that for a pair of actions, $(r, c)$ we have that $v \in \text{supp}(\Delta(w, r, c))$. Consider an alternate game $G'$ equal to $G$, except that some of the probability mass is moved from $v$ to $u$ when playing $(r, c)$ in $w$, i.e. $0 < \Delta(G, w, r, c)(v) - \Delta(G', w, r, c)(v) = \Delta(G', w, r, c)(u) - \Delta(G, w, r, c)(u)$. Then for all vertices $z$ we have that $z_G^T \le z_{G'}^T$

*Proof.* The proof is by induction in $T$. The proof is trivial for $T = 0$, because $z_G^T = 0 = z_{G'}^T$ for all non-goal vertices (and the goal vertex Win has value 1). For $T \ge 1$, we have that $z_G^{T-1} \le z_{G'}^{T-1}$. But, matrix games are monotone in their entries, so it follows directly that for $z \ne w$ we have that $z_G^T \le z_{G'}^T$. Consider the matrix for $w_G^T$ compared to $w_{G'}^T$. All entries but the one for $(r, c)$ are smaller directly by induction. We also have that $v_G^T \le u_G^T \le u_{G'}^T$, the first inequality by definition and the second by induction. We thus see that all entries in $w_G^T$ are smaller than in $w_{G'}^T$. The lemma follows. $\square$

We are now ready to find the patience in concurrent reachability games.

**Lemma 116.** Any $(1/4)$-optimal strategy, for either player, in purgatory duel $k$ has patience at least $(3/4)^{-2^{k-1}}$ for each $k$
*Proof.* We will show that the lemma is true for Eve's strategies and that it is true for Adam's follows from Lemma 115. Consider an (1/4)-optimal strategy $\sigma$ for Eve. Fixing this strategy for Eve, we get a MDP for Adam. Clearly, in this MDP $G'$, we have that $0 = \perp_{G'}^T \le s_{G'}^T$ for all $T$. We can thus apply Lemma 115 to changing $\Delta(1', 1, 1)$ from $\perp$ to $s$. In the resulting game $G''$, we still have that $0 = \perp_{G''}^T \le s_{G''}^T$ and thus, we can change $\Delta(1', 2, 2)$ from $\perp$ to $s$. Let the next game be $G^*$. Thus, for any $i' \in \{1', \dots, k'\}$, the plays from $i'$ to $\perp$ in $G^*$ all goes through $s$. Note that Adam can ensure that the play reaches $s$ from $i'$ and thus, when he plays optimally, do so. Thus, whenever $s$ is entered and Adam plays optimally, $k$ is enter eventually with pr. 1. For the purpose of the value, we can thus disregard $s$ and vertices in $\{1', \dots, k'\}$ and just view each edge going to $s$ as going to $k$ instead. But the resulting game is purgatory $k$ (in which Eve has fixed his strategy) and Eve is playing a strategy that gives value at least 1/4, which requires at least $(3/4)^{-2^{k-1}}$ patience, by Lemma 113. $\square$

## 7.5 Concurrent mean payoff games

In this section we consider concurrent mean payoff games. We will show that in general, any $\varepsilon$-optimal strategy in some concurrent mean payoff games are quite complex. We will first, however, show that finding the value of a concurrent mean payoff game can be done in polynomial space.

**Lemma 117 (Properties of concurrent mean payoff games).** *Concurrent mean payoff games are determined and the value is the limit of the value of the corresponding time-limited game as well as the limit of the corresponding discounted game, for the discount factor going to 0 from above. There is an polynomial time algorithm similar to Lemma 112, for finding the set of vertices where a finite memory strategy suffice to ensure $1 - \varepsilon$ (recall that all rewards are in $\{0,1\}$). For any fixed number $n$, there is a polynomial time algorithm for approximating the value in a concurrent mean payoff game with $n$ vertices (i.e. the running time is polynomial in the number of actions)*

We will not show this lemma, but simply note that the $\varepsilon$-optimal strategies known for general concurrent mean payoff games can be viewed as playing the corresponding discounted game with a variable discount factor that depends on how 'nice' the rewards has been up to now. Basically, in each round you play the optimal strategy in the corresponding discounted game with a discount factor $\gamma$. Whenever your rewards are close to or better than the value, you decrease $\gamma$ towards 0 and in each round your rewards are much worse than the value you let $\gamma$ increase, except not bigger than the initial $\gamma$ in the first round. Much of this section will argue that many natural candidates for simpler types of strategies does not work.

We will show that approximating the value, however, can, as mentioned, be done in polynomial space. The proof relies on Proposition 22 from [HKL$^+$11], stating the following:

**Proposition 1.** Let $\varepsilon = 2^{-j}$, where $j$ is some positive integer, and the probabilities be rational numbers where the numerator and denominator have bitsize at most $\tau$. Also, let $\lambda = \varepsilon^{\tau m^{O(n^2)}}$. Consider some state $s$ and let the value of that state in the $\lambda$ discounted game be $v_\lambda$ and the value in mean payoff game be $v$, then $|v - v_\lambda| < \varepsilon$.
We will use that to again reduce to the existential theory over the reals. For a fixed discount factor $\gamma$, we can easily express the value of the corresponding discounted game, like we expressed the value of a concurrent reachability game. We have that the value $v$ is then $v = \lim_{\gamma \to 0^+} f(\gamma)$, where $f$ is the found expression. I.e. for any $\varepsilon$, there is a $\gamma'$ such that for all $\gamma < \gamma'$, we have that $|f(\gamma) - v| \le \varepsilon$. Also, that $v > c$ means that there is $\varepsilon$, such that $v - \varepsilon > c$.

The problem is thus to come up with a polynomial sized formula to express that $\lambda$ is $\varepsilon \tau m^{O(n^2)} = 2^{-j \tau m^{O(n^2)}}$.

That can be done as follows, using $\ell = O(n^2) \cdot \log(m) + \log(j\tau)$ many variables, $v_0, v_1, \dots, v_{\ell-1}$:

$$v_0 = 1/2$$

and for all $0 < i < \ell$, we have that

$$v_i = v_{i-1} \cdot v_{i-1}.$$

Using induction, we see that $v_i = 2^{-2^i}$, i.e., $v_1 = 1/2 = 2^{-2^0}$ and

$$v_i = v_{i-1} \cdot v_{i-1} = 2^{-2^{i-1}} \cdot 2^{-2^{i-1}} = 2^{-2^{i-1}-2^{i-1}} = 2^{-2^i}$$

In particular,

$$v_{\ell-1} = 2^{-2^\ell} = 2^{-2O(n^2)\log(m)+\log(j\tau)} = 2^{-j\tau m^{O(n^2)}}$$

is the value we wanted for $\lambda$. Thus, for a given number $v$, we can test if the value of a concurrent $\lambda$-discounted game is above $v + \varepsilon$, which, using the proposition above, implies that $v$ is below the value of the corresponding concurrent mean payoff game. On the other hand, the proposition also implies that if the value of the concurrent $\lambda$-discounted game is below $v - \varepsilon$, then the value of the concurrent mean payoff game is below $v$. Being able to answer these questions lets you easily approximate the value of a concurrent mean payoff using binary search.

We get the following lemma.

**Lemma 118.** *Approximating the value of a concurrent mean payoff game can be in done in polynomial space*

We will now consider a specific, well-studied example of a concurrent mean payoff game, since it shows that many natural kinds of strategies do not suffice in general. The game is called the big match and is defined as follows: There are 3 vertices, $\{0, s, 1\}$, where the vertices in $\{0, 1\}$ are absorbing, and with value equal to their name. The last vertex $s$ has a $2 \times 2$-matrix and for all $i, j$ for $i \neq j$, we have that $c(s, 1, 1) = 1$, and for $i \neq 1 \neq j$ we have that $c(s, 1, 1) = 0$. Also, $\Delta(s, 1, i) = s$ for each $i$, $\Delta(s, 2, 1) = 0$ and $\Delta(s, 2, 2) = 1$. There is an illustration in Figure 7.8. The value of the Big Match is $1/2$.

Consider a finite-memory strategy $\sigma$ for Eve. We will argue that $\sigma$ cannot guarantee $\varepsilon$ (any strategy can guarantee $-1$, since the colors are between 0 and 1) for any $0 < \varepsilon$. Let $\tau$ be the stationary strategy for Adam that plays 1 with pr. $\varepsilon/2$. Then playing $\sigma$ against $\tau$, we get an Markov chain, where the vertex space is pairs of memory states and game vertices. In Markov chains, eventually, with pr. 1, a set of vertices $S$ is
<figure><img src="image_66.png" /><figcaption>Figure 7.8: The Big Match</figcaption></figure>

reached such that the set of vertices visited infinitely often is $S$. Such a set is called ergodic. The set $S$ can clearly only contain 1 game vertex, since whenever $s$ is left, it is never entered again. Hence, if $S$ contains $s$, the pr. that play will ever reach $\{0,1\}$ is 0. In the MC we get from the players playing $\sigma$ and $\tau$, let $T_{\varepsilon/2}$ be such that with pr. $\varepsilon/2$ some ergodic set has been reached. Let $\tau'$ be the strategy that plays $\tau$ for $T_{\varepsilon/2}$ and afterwards plays 2.

When $\sigma$ is played against $\tau'$, either we reach $\{0,1\}$ and Adam plays 1 only finitely many times, while in $s$ (the latter because there are only finitely many numbers below $T_{\varepsilon/2}$). Thus, for Eve to win a play, the play needs to reach vertex 1. There are two ways to do so, either Eve stops before $T_{\varepsilon/2}$ or after. In the former case, the pr. to reach 1 is only $\varepsilon/2$ (because Adam needs to play 2 at the time, which is only done with pr. $\varepsilon/2$). The latter only happens with pr. $\varepsilon/2$ by definition of $T_{\varepsilon/2}$ (because, Adam could play 2 for an arbitrary number of steps while following $\tau$ but $s$ would not be left anyway).

We get the following lemma.

**Lemma 119 (Properties of the Big Match).** *No finite memory strategy can guarantee more than 0 in the Big Match.*

The principle of sunken cost states that, when acting rationally, one should disregard cost already paid. We will next argue that this does not apply (naively) to the Big Match. A strategy following the principle of sunken cost would not depend on past cost paid and thus, in each step $T$, there is a pr. $p_T$ of stopping for Eve. Such strategies are called Markov strategies in the Big Match. Fix some Markov strategy $\sigma$ for Eve. We will argue, like before, that $\sigma$ cannot guarantee more than $\varepsilon$ for any $\varepsilon > 0$. Note that Eve does not depend on the choices of Adam and thus, either she stops with pr. 1 or she does not. In the former case, Adam just plays 1 forever. When Eve stops, the vertex reached is thus $-1$. Alternately, if Eve does not stop with pr. 1, there must be a time $T$, such that she only stops with pr. $\varepsilon$ after $T$ (this is actually also the case even if she stops with pr. 1). Adam's strategy is then to play 1 for $T$ steps and 2 thereafter. Observe that the pr. to reach 1 is thus at most $\varepsilon$, in that it must be that Eve stops after $T$. If she does not stop (or stops in 0), there will be only finitely many 1s.

We see the following:

**Lemma 120 (Properties of the Big Match).** *No Markov strategy can guarantee more than 0 in the Big Match.*
Bibliographic references

We will now give the references for this chapter, split into a few paragraphs, each corresponding to a section in the chapter.

John von Neumann’s work on matrix games [vNM44] (also called normal form games), showing that they have a value and there exists optimal stationary strategies, is typically considered the founding work in game theory. Besides that paper, Dantzig [Dan65] showed the equivalence to linear programming, and thus that they can be solved in polynomial time using e.g. Khachiyan’s [Kha79] work on the ellipsoid method. There are also some results on how complex the strategies for matrix games are: For any $\varepsilon > 0$, there exists an $\varepsilon$-optimal strategy that plays uniformly over a multi-set of actions of size $\lceil(\ln n)/\varepsilon^2\rceil$ as shown by Lipton and Young [LY94] (this is a stronger requirement than patience). Also, as shown by Feder, Nazerzadeh and Saberi [FNS07] there exists games such that any $\varepsilon$-optimal strategy has support at least $\Omega(\frac{\log n}{\varepsilon^2})$ (note that if, for some $x$, the support is $\Omega(x)$ then patience is also $\Omega(x)$). Finally, as shown by Hansen, Ibsen-Jensen, Podolskii and Tsigaridas [HIJPT13], there is an optimal strategy in any matrix game with patience less than $(n+2)^{\frac{n+2}{2}/2^{n+1}}$ and for each $k$ there exists games with $n=m=2^k$ such that any optimal strategy has patience at least $n^{n/2}/2^{n(1+o(1))}$ (there are also results for $m$ and $n$ not equal to $2^k$ for some $k$, but not quite as tight to the upper bound).

Shapley [Sha53] first considered concurrent games and focused on the class of concurrent discounted payoff games. For these, he showed that they have a value and that there are optimal stationary strategies, using in essence the proof we used for the first 3 items of Lemma 96. The proof of the fourth item, i.e. that the value can be approximated in PPAD, comes from the work of Etessami and Yannakakis [EY10]. The proof of the fifth item, an upper bound on the patience of $\varepsilon$-optimal strategies appears in [IJ12].

Everett [Eve57] was the first to consider concurrent reachability games (formally, he considered a slight generalization). In that paper, he showed that the games have a value and $\varepsilon$-optimal stationary strategies (i.e. the first part of Lemma 100 and Lemma 102). He also used the snowball game to show that Eve does not always have an optimal strategy (i.e. Lemma 101). Finally, he introduced the notion of patience for strategies. It was shown by Himmelberg, Parthasarathy, Raghavan and Vleck [Par73, HPRV76] that Adam has an optimal strategy. Frederiksen and Miltersen [FM13] showed that for each vertex $x$ and action $a$ (except for one action for each vertex), there is a number $c_{x,a}$ and an integer $d_{x,a}$, such that for any $\varepsilon > 0$, the strategy that plays each action $a'$ in vertex $x'$ with pr. $c_{x',a'}\varepsilon^{d_{x',a'}}$ is $\varepsilon$-optimal (the last action in each vertex is played with the remaining pr.). They used that to show that approximating the value (since the value can be irrational, it seems reasonable to approximate) can be done in TFNP[NP], slightly inside PSPACE. Finding the set of vertices of value 0, i.e. Lemma 105, is folklore. Finding the set of vertices of value 1, on the other hand, i.e. Lemma 112, is by de Alfaro, Henzinger and Kupferman [dAHK98] (their proof is different). Hansen, Koucký and Miltersen [HKM09] showed that purgatory $k$ requires patience $\varepsilon^{2^{k-1}}$ for any $1 > \varepsilon > 0$ for Eve. Later, Chatterjee, Hansen and Ibsen-Jensen [CHIJ17] showed that purgatory duel $k$ requires patience $(3/4)^{2^{k-1}}$
for any $0 \le \varepsilon < 1/4$ for either player.

Gillette [Gil57] was the first to consider concurrent mean payoff games and introduced the Big Match game we use as an example. He showed that the Big Match does not have stationary strategies ensuring more than 0. Later, Blackwell and Ferguson [BF68] showed that the Big Match have a value and that value is 1/2 by showing that some strategies that depends on the full history is ε-optimal. They also showed that no optimal Markov strategy (i.e. Lemma 120) can ensure more than 0 in that game. Next, Kohlberg [Koh74] extended this to show that all repeated games with absorbing states have a value. Finally, Mertens and Neyman [MN81] showed that all concurrent mean payoff games have a value (i.e the first part of Lemma 117). The strategies employed in all these papers kept track on the sum of over the rounds of the values of the vertex in that round minus the color in that round (the strategy by Mertens and Neyman set the memory to 0 if it should have been negative though). Finding the set of vertices where for every $\varepsilon > 0$, a finite memory strategy can ensure value $1 - \varepsilon$ was done by Chatterjee and Ibsen-Jensen [CIJ15] (the middle part of Lemma 117). Furthermore, finding the values in a game with a fixed number of vertices in polynomial time was done by Hansen, Koucký, Lauritzen, Miltersen and Tsigaridas [HKL$^{+}$11], informally speaking by doing binary search for the values. That finite-memory strategies cannot ensure more than 0 in the Big Match, i.e. Lemma 119 seems to be folklore. Hansen, Ibsen-Jensen and Koucký [HIJK16] considered extending Markov strategies with a finite amount of space and showed that if the memory is a deterministic function of the history, then no such strategy can ensure more than $-1$ in the Big Match. They also showed, for any fixed $\varepsilon > 0$, that in round $T$ one only needs $O(\log \log T)$ bits of memory to play $\varepsilon$-optimal in any absorbing game. Finally, Hansen, Ibsen-Jensen and Neyman [HIJN18] showed that Markov strategies extended with a single bit of space suffice to play the Big Match $\varepsilon$-optimally, for any $\varepsilon > 0$ (naturally, the strategy used randomisation to update the memory state).
GAMES WITH SIGNALS

<figure><img src="image_67.png" /></figure>
Chapter 8

# Games with Signals

HUGO GIMBERT

**Imperfect information.** This chapter presents a few results about zero-sum games with imperfect information. Those games are a generalization of concurrent games in order to take into account the possibility that players might be imperfectly informed about the current state of the game and the actions taken by their opponent, or even their own action. We will also discuss situations where players may forget what they used to know.

Before providing formal definitions of games with imperfect information, we give several examples.

**Simple poker.** Our first example is a finite duration game which is a simplified version of poker, inspired by Borel and von Neumann simplified poker [FF03]. This game is played with 4 cards {♠, ♡, ♣, ♦}.

• The goal of Eve and Adam is to win the content of a pot in which, initially, they both put 1 euro.

• Eve receives a private random card, unknown by Adam.

• Eve decides whether to check or raise. If she checks then she wins the pot iff her card is ♠.

• If Eve raises then Adam has two options: fold or call. If Adam folds then Eve receives the pot. If Adam raises then both player add two euros in the pot and Eve wins the pot iff her card is ♠.

A natural strategy for Eve is to raise when she has a spade and otherwise check. Playing so, she reveals her card to Adam, and we will see that the optimal behaviour for her consists in bluffing from time to time, i.e. raise although her card is not a spade.
**The distracted logician.** Our second example is another finite duration game. A logician is driving home. For that he should go through two crossings, and turn left at the first one and right at the second one. This logician is very much absorbed in his thoughts, trying to prove that $P \neq NP$, and is thus pretty distracted: upon taking a decision, he cannot tell whether he already saw a crossing or not.

This simple example is useful to discuss the observability of actions and make a distinction between mixed strategies and behavioral strategy.

**Network controller.** The following example is inspired from collision regulation in Ethernet protocols: the controller of a network card has to share an Ethernet layer with another network card, controller by another controller, possibly malicious.

When sending a data packet, the controller selects a delay in microseconds between 1 and 512 and transmits this delay to the network card. The other controller does the same. The network cards try to send their data packet at the chosen dates. Choosing the same date results in a data collision, and the process is repeated until there is no collision, at that time the data can be sent.

The chosen delay has to be kept hidden from the opponent. This way, it can be chosen randomly, which ensures that the data will eventually be sent with probability 1, whatever does the opponent.

**Guess my set.** Our fourth example is an infinite duration game, parametrized by some integer $n$. The play is divided into three phases.

• In the first phase, Eve secretly chooses a subset $X \subset \{1, \dots, 2n\}$ of size $n$ among the $\binom{2n}{n}$ possibilities.

• In the second phase, Eve discloses to Adam $\frac{1}{2}\binom{2n}{n}$ pairwise distinct sets of size $n$ which are all different from $X$.

• In the third phase, Adam aims at guessing $X$ by trying up to $\frac{1}{2}\binom{2n}{n}$ sets of size $n$. If Adam succeeds in guessing $X$, the game restarts from the beginning. Otherwise, Eve wins.

Clearly Adam has a strategy to prevent forever Eve to win: try up one by one all those sets that were not disclosed by Eve. This strategy uses a lot of memory: Adam has to remember the whole sequence of $\frac{1}{2}\binom{2n}{n}$ sets disclosed by Eve. We will see that a variant of this game can be represented in a compact way, using a number of states polynomial in $n$. As a consequence, playing optimally a game with imperfect-information and infinite duration might require a memory of size doubly-exponential in the size of the game.

## 8.1 Notations

We consider stochastic games with signals, that are a standard tool in game theory to model imperfect information in stochastic games [RSV06, Ren09]. When playing a stochastic game with signals, players cannot observe the actual state of the game,
nor the actions played by themselves or their opponent: the only source of information of a player are private signals they receive throughout the play. Stochastic games with signals subsume standard stochastic games [Sha53], repeated games with incomplete information [Aum64], games with imperfect monitoring [RSV06], concurrent games [dAH00] and deterministic games with imperfect information on one side [Rei84, CDHR07].

Like in previous chapters, V, C and A denote respectively the sets of vertices, colors and actions.

**Definition 24.** An imperfect information arena $\mathcal{A}$ is a tuple $(S, \Delta)$ where

* $S$ is the set of signals

* $\Delta: V \times A \times A \to \mathcal{D}(V \times S \times S \times C)$ maps the current vertex and a pair of actions to a probability distribution over vertices, pairs of signals and colors.

Initially, the game is in a state $v_0 \in V$ chosen according to a probability distribution $\delta_0 \in \mathcal{D}(V)$ known by both players; the initial state is $v_0$ with probability $\delta_0(v_0)$. At each step $n \in \mathbb{N}$, both players simultaneously choose some actions $a, b \in A$ They respectively receive signals $s, t \in S$, and the game moves to a new state $v_{n+1}$. This happens with probability $\Delta(v_n, a, b)(v_{n+1}, c, d)$. This fixed probability is known by both players, as well as the whole description of the game.

A *play* is a sequence $(v_0, a_0, b_0, s_0, t_0, c_0), (v_1, a_1, b_1, s_1, t_1, c_1), (v_2, \dots)$ such that for every $n$, the probability $\Delta(v_n, a_n, b_n)(v_{n+1}, s_n, t_n, c_n)$ is positive.

A sequence of signals for a player is *realisable* for Eve if it appears in a play, we denote $R_E \subseteq S^*$ the set of these sequence. Similarly for Adam.

**An example.** The simplified poker can be modelled as a stochastic game with signals. Actions of players are *public signals* sent to both players. Also their the payoff of Eve is publicly announced, when non-zero. Upon choosing whether to call or fold, Adam cannot distinguish between states $\diamond$Raised and $\blacksquare$Raised, in both cases he received the sequence of signals $\circ$, *raise*. A graphical representation is provided on Figure 8.1.

The game is played with 4 cards $\{\spades, \hearts, \clubs, \diamond\}$. We exploit the symmetry of payoffs with respect to $\{\spades, \clubs, \diamond\}$ and identify these three colours as a single one, denoted $\blacksquare$, received initially by Eve with probability $\frac{3}{4}$. The set of vertices is an initial vertex Start, a terminal vertex End plus the four states

$$ \{\spades, \blacksquare\} \times \{\text{Play, Raised}\} . $$

The set of colors are possible payoffs $C = \{0, -1, +1, -3, +3\}$.

The set of actions $A$ is the union of actions of Eve $A_E = \{\circ, \text{check}, \text{raise}\}$ and actions of Adam $A_A = \{\circ, \text{call}, \text{fold}\}$.

The set of signals is $\{\circ, \spades, \blacksquare\}$ plus $\{\text{check}, \text{raise}, \text{call}, \text{fold}\} \times \{0, -1, +1, -3, +3\}$.

The rules of the game, are defined by the set of *legal* transitions. Let $c \in \{\spades, \blacksquare\}$.
<figure><img src="image_68.png" /><figcaption>Figure 8.1: The simplified poker game.</figcaption></figure>

The following transitions are legal.

$$ \Delta(\text{Start}, \cdot, \cdot)((c, \text{Play}), c, \circ, 0) = \begin{cases} \frac{1}{4} & \text{if } c = \spadesuit \\ \frac{3}{4} & \text{if } c = \blacksuit. \end{cases} $$

$$ \Delta((c, \text{Play}), \text{check}, \cdot)(\text{End}, \text{check}_x, \text{check}_x, x) = 1 \text{ where } x = \begin{cases} +1 & \text{if } c = \spadesuit \\ -1 & \text{if } c = \blacksuit. \end{cases} $$

$$ \Delta((c, \text{Play}), \text{raise}, \cdot)((c, \text{Raised}), \text{raise}_0, \text{raise}_0, 0) = 1 $$

$$ \Delta((c, \text{Raised}), \cdot, \text{call})(\text{End}, \text{call}_x, \text{call}_x, x) = 1 \text{ where } x = \begin{cases} +3 & \text{if } c = \spadesuit \\ -3 & \text{if } c = \blacksuit. \end{cases} $$

$$ \Delta((c, \text{Raised}), \cdot, \text{fold})(\text{End}, \text{fold}_1, \text{fold}_1, +1) = 1 $$

state End is absorbing with payoff 0.

To simplify the notations, we assumed in the general case that players share the same set of actions and signals. As a consequence, other transitions than the legal ones are possible. One can use a threat to guarantee that Eve plays check and raise after receiving her card, by setting a heavy loss of -10 if she plays another action instead. Same thing to enforce that Adam plays call or fold after receiving the signal raise. When targeting applications, legal moves should be explicitly specified, typically using an automaton to compute the set of legal actions depending on the sequence of signals.

**Strategies: behavioral, mixed and general.** Intuitively, players make their decisions based upon the sequence of signals they receive, which is formalised with strate-
gies. There are several natural classes of strategies to play games with signals, as discussed in [CDH10b] and Section 4 in [BGG17].

A behavioural strategy of Eve associates with every realisable sequence of signals a probability distribution over actions:

$$ \sigma : R_E \to \mathcal{D}(A) . $$

When Eve plays $\sigma$, after having received a sequence of signals $s_0, \dots, s_n$ she chooses action $a$ with probability $\sigma(s_0, \dots, s_n)(a)$. Strategies of Adam are the same, except they are defined on $R_A$.

Remark that in general a player may not observe which actions he actually played, for example $S$ might be a singleton in which case the players only knows the number of steps so far.

A game has observable actions if there exists a mapping $Act : S \to A$ such that

$$ \Delta(v, a, b)(w, s, t) > 0 \implies (a = \text{Act}(s) \land b = \text{Act}(t)) . $$

In [BGG17, Lemma 4.6 and 4.7] it was shown that without loss of generality, one can consider games where actions are observable and players play behavioural strategies. The discussion is technical and beyond the scope of this book.

## 8.2 Finite duration

We start with some results on the very interesting class of game with finite duration.

A game has finite duration if there is a set of absorbing vertices $L$, called leaves, such that every play eventually reaches $L$. In other words, the directed graph $(V, E)$ induced by all pairs $(v, w)$ such that $\exists a, b \in A, s, t \in S, \Delta(v, a, b)(w, s, t) > 0$ is acyclic, except for self loops on leaves.

Moreover, $C$ is the set of real numbers, colours are called *payoffs*. At the moment the play $\pi$ reaches a leaf $\ell \in L$ for the first time, the game is essentially over: Eve receives the sum of payoffs seen to far, denoted $\text{pay}(\pi)$ and all future payoffs are 0. Such plays are called *terminal plays*.

Once a terminal play occurs, the game is over. For this reason, in this section we restrict realisable sequences of signals to the ones occurring in terminal plays and their prefixes. This guarantees finiteness of $R_E$ and $R_A$ since

$$ R_E \cup R_A \subseteq S^{\le n} . $$

An initial distribution $\delta_0$ and two strategies $\sigma$ and $\tau$ of Eve and Adam naturally induce a probability distribution $P_{\delta_0}^{\sigma, \tau}$ on the set of terminal plays starting in one of the vertices $v_0, \delta_0(v_0) > 0$. Players have opposite interests: Eve seeks to maximize her expected payoff

$$ \mathbb{E}_{\delta_0}^{\sigma, \tau} = \sum_{\text{terminal plays } \pi} P_{\delta_0}^{\sigma, \tau}(\pi) \cdot \text{pay}(\pi) , $$

while Adam wants to minimize it.
### 8.2.1 Existence and computability of the value

Next theorem gathers several folklore results.

**Theorem 93 (Finite duration games).** A game with finite duration and imperfect information has a value: for every initial distribution $\delta_0$,

$$ \sup_{\sigma} \inf_{\tau} \mathbb{E}_{\delta_0}^{\sigma, \tau} = \inf_{\tau} \sup_{\sigma} \mathbb{E}_{\delta_0}^{\sigma, \tau}. $$

This value is denoted $\text{val}(\delta_0)$ and is computable $^1$. Both players have optimal strategies.

**Reduction to normal form.** The main ingredient for proving this theorem is a transformation of the game into a matrix game called its normal form.

The intuition is that a player, instead of choosing progressively her actions as she receives new signals, may choose once for all at the beginning of the game how to react to every possible sequence of signals she might receive in the future.

Fix an initial distribution $\delta_0$. In the normal form version the game, Eve picks a deterministic strategy $\sigma: R_E \to A$ while simultaneously Adam picks $\tau: R_A \to A$. Then the game is over and Eve receives payoff $\mathbb{E}_{\delta_0}^{\sigma, \tau}$. There are finitely many such deterministic strategies, thus the normal form game is a matrix game. See Section 7.2 for more details about matrix games.

**An example.** In the simplified poker example, the reduction is as follows.

We rely on the formal description of the game at the end of Section 8.1 and perform two simplifications. First, we only consider strategies playing moves according to the rules, other strategies are strategically useless.

Deterministic strategies of Eve are mappings $\sigma: \{\spades, \clubs\} \to \{\text{check}, \text{raise}\}$. Adam has only two deterministic strategies: after the sequence ◦Raised, he should choose between actions call and fold.

The normal form is

<table><thead><tr><th></th><th>call</th><th>fold</th></tr></thead><tbody><tr><td>♠ → check, ♦ → check</td><td>-0.5</td><td>-0.5</td></tr><tr><td>♠ → raise, ♦ → check</td><td>0</td><td>-0.5</td></tr><tr><td>♠ → raise, ♦ → raise</td><td>-1.5</td><td>+1</td></tr><tr><td>♠ → check, ♦ → raise</td><td>-2</td><td>+1</td></tr></tbody></table>

The first line corresponds to Eve never raising, thus her odds are +1 euro at 25% and -1 at 75% thus an expected payoff of -0.5. The third line corresponds to Eve always raising. If Adam calls then her odds are +3 at 25% and -3 at 75%, on average -1.5. If Adam folds, she gets payoff +1.

Remark that the rows where Eve checks with ♠ are dominated by the corresponding row where Eve does not. Thus checking with ♠ (slow playing) has no strategic interest,

<footnote n="1">¹provided payoffs are presented in a way compatible with linear solvers, typically rational values.</footnote>
and by elimination of weakly dominated strategies, the normal form game is equivalent to:

<table><thead><tr><th></th><th></th><th>call</th><th>fold</th></tr></thead><tbody><tr><td>♠ → raise, ■ → check</td><td></td><td>0</td><td>-0.5</td></tr><tr><td>♠ → raise, ■ → raise</td><td></td><td>-1.5</td><td>1</td></tr></tbody></table>

The value of this game is $-\frac{1}{4}$. Eve has a unique optimal strategy which consists in playing the top row with probability $\frac{5}{6}$. In other words, she should bluff with probability $\frac{1}{6}$ when she receives ■. Adam has a unique optimal strategy which consists in calling or folding with equal probability $\frac{1}{2}$.

**Proof of Theorem 93.** The example illustrates the correspondence between behavioural strategies in the finite-duration game on one side and mixed strategies in the normal form game on the other. In the general case, the correspondence can be stated as follows.

**Lemma 121.** Denote Strat the set of behavioural strategies, Strat<sub>d</sub> the subset of deterministic strategies and $\mathcal{D}(Strat_d)$ the set of strategies in the normal form game.

1. There is a mapping $\Phi: \text{Strat} \to \mathcal{D}(\text{Strat}_d)$ which preserves payoffs:

$$ \forall \sigma, \tau \in \text{Strat}, \mathbb{E}_{\delta_0}^{\sigma, \tau} = \sum_{\sigma', \tau' \in \text{Strat}_d} \Phi(\sigma)(\sigma') \cdot \Phi(\tau)(\tau') \cdot \mathbb{E}_{\delta_0}^{\sigma', \tau'} $$

2. Since actions are observable, there is a mapping $\Phi' : \mathcal{D}(\text{Strat}_d) \to \text{Strat}$ which preserves payoffs:

$$ \forall \Sigma, T \in \mathcal{D}(\text{Strat}), \sum_{\sigma', \tau' \in \text{Strat}_d} \Sigma(\sigma')T(\tau')\mathbb{E}_{\delta_0}^{\sigma', \tau'} = \mathbb{E}_{\delta_0}^{\Phi'(\sigma), \Phi'(\tau)} $$

3. $\Phi' \circ \Phi$ is the identity.

We assumed earlier that each player can observe its own actions. This hypothesis is necessary for ii) and iii) to hold in general.

*Proof.* We start with i). Intuitively, all random choices of actions performed by a behavioural strategy $\sigma$ of Eve can be done at the beginning of the play. Playing $\sigma$ is equivalent to playing each deterministic strategy $\sigma'$ with probability

$$ \Phi(\sigma)(\sigma') = \prod_{u \in R_E} \sigma(u)(\sigma'(u)) $$

We prove ii). Let $\Sigma \in \mathcal{D}(\text{Strat})$. The definition of the behavioural strategy $\sigma = \Phi'(\Sigma)$ is as follows. Let $s_0...s_k$ be a finite sequence of signals. Since actions are observable, this defines unambiguously the sequence of corresponding actions $a_0...a_k$ where $a_i = \text{Act}(s_i)$. We set $\sigma(s_0...s_k)(a)$ to be the probability that a deterministic strategy chosen with $\Sigma$ chooses action $a$ after signals $s_0...s_k$, conditioned on the fact that it has already chosen action $a_0...a_k$:

$$ \sigma(s_0...s_k)(a) = \sum (\sigma'(s_0...s_k) = a | \forall 0 \le i \le k, \sigma'(s_0...s_{i-1}) = \text{Act}(s_i)) $$

where the vertical pipe denotes a conditional probability. $\square$
We proceed with the proof of Theorem 93. According to Theorem 92, the normal form has a value and optimal strategies for each player. Denote $val_N$ the value and $\Sigma^\sharp$ and $T^\sharp$ the optimal strategies. Let $\sigma^\sharp = \Phi'(\Sigma^\sharp)$. Then $\sigma^\sharp$ ensures a payoff of at least $val_N$ in the imperfect information game, because for every strategy $\tau$,

$$ \mathbb{E}_{\delta_0}^{\sigma^\sharp, \tau} = \mathbb{E}_{\delta_0}^{\Phi'(\Sigma^\sharp), \Phi'(\Phi(\tau))} = \sum_{\sigma', \tau' \in \mathrm{Strat}_d} \Sigma^\sharp(\sigma')\Phi(\tau)(\tau')\mathbb{E}_{\delta_0}^{\sigma', \tau'} \geq \mathrm{val}_N, $$

where the first equalities are applications of Lemma 121 and the inequality is by optimality of $\Sigma^\sharp$. Symmetrically, $\tau^\sharp = \Phi'(T^\sharp)$ guarantees $\forall \sigma, \mathbb{E}_{\delta_0}^{\sigma, \tau^\sharp} \leq val_N$. Thus the value of the game with finite duration is $val_N$ and $\sigma^\sharp$ and $\tau^\sharp$ are optimal. $\square$

### 8.2.2 The Koller-Meggido-von Stengel reduction to linear programming

The reduction of a finite-duration game with imperfect information to its normal form proves that the value exists and is computable. However the corresponding algorithm is computationally very expensive, it requires solving a linear program of size roughly doubly-exponential in the size of the original game, since the normal form is a matrix index by $A^{R_E} \times A^{R_A}$ and the set of signal sequences might contain all sequences of $S$ of length $\leq n$.

Koller, Meggido and von Stengel did provide a more efficient direct reduction to linear programming. Strategies of Eve in the normal form game live in $R^{A^{R_E}}$ while her strategies in the game with imperfect information live in a space with exponentially fewer dimensions, namely $R^{R_E \times A}$. The direct reduction avoids this dimensional blowup.

**Theorem 94.** The value of a game with imperfect information can be computed by a linear program with $|R_E| + |R_A|$ variables.

As a consequence, in the particular case where the game graph is a tree then $|R_E| \leq n$ and $|R_A| \leq n$ and the value can be computed in polynomial time, like stated in [KMvS94].

*Proof.* The construction of the linear program relies on three key ideas.

First, representing a behavioral strategy $\sigma: R_E \to \mathcal{D}(A)$ of Eve as a plan $\pi: R_E \to [0, 1]$ recursively defined by $\pi(\varepsilon) = 1$ and for every $s_0 \cdots s_n \in R_E, s \in S$,

$$ \pi(s_0 \cdots s_n \cdot s) = \pi(s_0 \cdots s_n) \cdot \sigma(s_0 \cdots s_n)(\mathrm{Act}(s)) . $$

Remind that actions are observable and $\mathrm{Act}(s)$ denotes the action that Eve has just played before receiving signal $s$. In the linear program, plans are represented by variables $(p_r)_{r \in R_E}$. Valuations corresponding to plans can be characterized by the following equalities. First, $p_E = 1$. Second, for every $s_0 \cdots s_{n-1}s, s_0 \cdots s_{n-1}s' \in R_E$,

$$ (\mathrm{Act}(s) = \mathrm{Act}(s')) \implies (p_{s_0 \cdots s_{n-1}s} = p_{s_0 \cdots s_{n-1}s'}) . $$
We denote $p_{s_0...s_{n-1}a}$ the common value of all $p_{s_0...s_{n-1}s}$ with $a = \text{Act}(s)$. The third equality is $p_{s_0...s_{n-1}} = \sum_{a \in A} p_{s_0...s_{n-1}a}$.

The second key idea is to introduce variables evaluating the contribution of a (real- isable) sequence of signals of Adam to the total expected payoff Eve. These contribu- tions are represented by variables $(v_r)_{r \in R_A}$.

The third key idea is to aggregate the product of transition probabilities along a play. For every play $(v_0, a_0, b_0, s_0, t_0, c_0), \dots, (v_k, a_k, b_k, s_k, t_k, c_k)$ we denote $\mathbb{E}(\pi)$ the product of all transition probabilities of $\pi$ and $r_E(\pi)$ the sequence of signals of Eve in this play:

$$ \mathbb{E}(\pi) = \delta_0(v_0) \cdot \Delta(v_0, a_0, b_0, s_0, t_0, c_0) \cdots \Delta(v_k, a_k, b_k, s_k, t_k, c_k) \\ r_E(\pi) = s_0, s_1, \dots, s_k . $$

We show that the following linear program with variables $(p_r)_{r \in R_E}, (v_r)_{r \in R_A}$ has an optimal solution which equals to $\text{val}(\delta_0)$. For every sequences of signals $r \in R_A$ we denote $T_A(r)$ the (possibly empty) set of terminal plays whose sequence of signals for Adam is $r$.

Maximise $v_E$ subject to

$(p_r)_{r \in R_E}$ is a plan of Eve

$\forall r \in R_A, \forall a \in A,$

$$ v_r \le \sum_{\substack{rs \in R_A \\ s \in S, \text{Act}(s)=a}} v_{rs} + \sum_{\pi \in T(r)} \mathbb{E}(\pi) \cdot \text{pay}(\pi) \cdot p_{r_E(\pi)} \quad (8.1) $$

For our purpose, it is enough to establish that the optimal solution of the LP is

$$ \text{val}(\delta_0) = \sup_{\sigma} \min_{\tau \text{ deterministic}} \mathbb{E}_{\delta_0}^{\sigma, \tau} . $$

The reason is that in a matrix game, for every fixed strategy of Eve, Adam can mini- mize the payoff by playing a single action with probability 1. Thus, according to the reduction to normal form seen in the previous chapter, for every strategy $\sigma$ of Eve, there is a deterministic strategy $\tau$ of Adam which minimizes $\mathbb{E}_{\delta_0}^{\sigma, \tau}$.

We show first that for every feasible solution $(p_r)_{r \in R_E}, (v_r)_{r \in R_A}$ of the linear pro- gram, the strategy $\sigma$ corresponding to the plan $(p_r)_{r \in R_E}$ guarantees that for every de- terministic strategy $\tau$, $\mathbb{E}_{\delta_0}^{\sigma, \tau} \ge v_E$. Since $\tau$ is deterministic then $\mathbb{E}_{\delta_0}^{\sigma, \tau}$ is the sum of all $\mathbb{E}(\pi) \cdot \text{pay}(\pi) \cdot p_{r_E(\pi)}$ over plays $\pi$ played according to $\tau$ thus a trivial induction shows $\mathbb{E}_{\delta_0}^{\sigma, \tau} \ge v_E$.

We show now that to every strategy $\sigma$ of Eve, and to every deterministic optimal answer $\tau$ of Adam, corresponds a feasible solution of the program such that $v_E = \mathbb{E}_{\delta_0}^{\sigma, \tau}$. Let $(p_r)_{r \in R_E}$ the plan corresponding to $\sigma$. For every $r \in R_A$ define $v_r$ be the expected payoff of Eve in an auxiliary game where she plays $\sigma$ and Adam plays $\tau$ and the payoff
of Eve is turned to 0 whenever Adam signals sequence does not start with $r$. We show that the linear constraint Equation (8.1) holds for every $r \in R_A$ and action $a$. Since $\tau$ is deterministic then Equation (8.1) is an equality whenever $a = \tau(r)$. And since $\tau$ is an optimal answer to $\sigma$, it is locally optimal in the sense where playing an action different from $\tau(r)$ after $r$ cannot be profitable to Adam, hence Equation (8.1) holds. Finally, $(p_r)_{r \in R_E}$, $(v_r)_{r \in R_A}$ is a feasible solution. $\square$

**An example.** The following linear program computes the value of the simplified poker example.

Maximise $v_E$ subject to

$$
\begin{align*}
& \forall r \in R_E, 0 \le p_r \le 1 \\
& p_{\spadesuit, \text{check}} + p_{\spadesuit, \text{raise}} = 1 \\
& p_{\blacksuit, \text{check}} + p_{\blacksuit, \text{raise}} = 1 \\
& v_E \le v_o \le v_{o, \text{check}} + v_{o, \text{raise}} \\
& v_{o, \text{check}} \le \frac{1}{4} \cdot p_{\spadesuit, \text{check}} \cdot (+1) + \frac{3}{4} \cdot p_{\blacksuit, \text{check}} \cdot (-1) \\
& v_{o, \text{raise}} \le \frac{1}{4} \cdot p_{\spadesuit, \text{raise}} \cdot (+1) + \frac{3}{4} \cdot p_{\blacksuit, \text{raise}} \cdot (+1) \\
& v_{o, \text{raise}} \le \frac{1}{4} \cdot p_{\spadesuit, \text{raise}} \cdot (+3) + \frac{3}{4} \cdot p_{\blacksuit, \text{raise}} \cdot (-3)
\end{align*}
$$

Setting $x = p_{\spadesuit, \text{check}}$ and $y = p_{\blacksuit, \text{check}}$, the solution is

$$
\begin{align*}
& \frac{1}{4} \max_{(x,y) \in [0,1]^2} (x - 3y + \min((1-x) + 3(1-y), 3(1-x) - 9(1-y))) \\
& = \frac{1}{4} \max_{(x,y) \in [0,1]^2} \min(4 - 6y, -6 - 2x + 6y) = \frac{1}{4} \max_{y \in [0,1]} \min(4 - 6y, -6 + 6y),
\end{align*}
$$

which is maximal when $y = \frac{5}{6}$ and the solution is $-\frac{1}{4}$.

**Nose scratch variant.** Assume now that Eve does not have the perfect poker face: whenever she has $\spadesuit$ she scratches her nose with probability $\frac{1}{2}$ whereas in general it happens only with probability $\frac{1}{6}$. Only Adam is aware of this sign, which he receives as a private signal $s$ (scratch) or $n$ (no scratch).

Compared to the perfect poker face situation, the situation is slightly better for Adam: the value drops from $-\frac{1}{4}$ to $(-\frac{1}{4} - \frac{1}{10})$. The optimal bluff frequency of Eve decreases from $\frac{1}{6}$ to $\frac{1}{10}$. Computation details follow.

Maximise $v_E$ subject to
$$
\begin{align*}
\forall u \in R_E, 0 \le p_u \le 1 & \\
p_{\diamond,c} + p_{\diamond,r} = 1 \quad p_{\blacksquare,c} + p_{\blacksquare,r} = 1 & \\
v_{\varepsilon} \le v_s + v_n \quad v_s \le v_{sc} + v_{sr} \quad v_n \le v_{nc} + v_{nr} & \\
v_{sc} \le \frac{1}{4} \cdot \frac{1}{2} \cdot p_{\diamond,c} \cdot (+1) + \frac{3}{4} \cdot \frac{1}{6} \cdot p_{\blacksquare,c} \cdot (-1) & \\
v_{nc} \le \frac{1}{4} \cdot \frac{1}{2} \cdot p_{\diamond,c} \cdot (+1) + \frac{3}{4} \cdot \frac{5}{6} \cdot p_{\blacksquare,c} \cdot (-1) & \\
v_{sr} \le \frac{1}{4} \cdot \frac{1}{2} \cdot p_{\diamond,r} \cdot (+1) + \frac{3}{4} \cdot \frac{1}{6} \cdot p_{\blacksquare,r} \cdot (+1) & \\
v_{sr} \le \frac{1}{4} \cdot \frac{1}{2} \cdot p_{\diamond,r} \cdot (+3) + \frac{3}{4} \cdot \frac{1}{6} \cdot p_{\blacksquare,r} \cdot (-3) & \\
v_{nr} \le \frac{1}{4} \cdot \frac{1}{2} \cdot p_{\diamond,r} \cdot (+1) + \frac{3}{4} \cdot \frac{5}{6} \cdot p_{\blacksquare,r} \cdot (+1) & \\
v_{nr} \le \frac{1}{4} \cdot \frac{1}{2} \cdot p_{\diamond,r} \cdot (+3) + \frac{3}{4} \cdot \frac{5}{6} \cdot p_{\blacksquare,r} \cdot (-3) &
\end{align*}
$$

Set $y = p_{\blacksquare,c}$. Some elementary simplifications lead to the equivalent program:

$$
\max_{0 \le y \le 1} \frac{1}{8} \left( \min \left( 8 - 12y, -10 + 8y, 6 - 8y, -12 + 12y \right) \right)
$$

The optimum is reached when $8y - 10 = 8 - 12y$ i.e. when $p_{\blacksquare,c} = \frac{9}{10}$ and is equal to
$$ -\frac{7}{20} = -\frac{1}{4} - \frac{1}{10}. $$

**8.3 Infinite duration**

Games with infinite duration and imperfect information are a natural model for appli-
cations such as synthesis of controllers of embedded systems. This is illustrated by the
example of the network controller. Whereas in the previous section games of finite-
duration were equipped with real-valued payoffs, here we focus on Büchi conditions.

**8.3.1 Playing games with infinite duration and imperfect informa-**
**tion**

Notations used for games of finite duration are kept. On top of that we need to define
how probabilities are measured and the winning conditions.

**Measuring probabilities.** The choice of an initial distribution $\delta_0 \in \mathcal{D}(V)$ and two strategies $\sigma: R_E \to \mathcal{D}(A)$ and $\tau: R_A \to \mathcal{D}(A)$ for Eve and Adam defines a Markov chain on the set of all finite plays. This in turn defines a probability measure $\mathbb{P}_{\delta_0}^{\sigma, \tau}$ on the Borel-measurable subsets of $\Delta^\omega$. The random variables $V_n, A_n, B_n, S_n$ and $T_n$ denote respectively the $n$-th state, action of Eve, action of Adam, signal received by Eve and Adam, and we denote $\pi_n$ the finite play $\pi_n = V_0, A_0, B_0, S_0, T_0, V_1, \dots, S_n, T_n, V_{n+1}$.
The probability measure $\mathbb{P}_{\delta_0}^{\sigma, \tau}$ is the only probability measure over $\Delta^\omega$ such that for every $v \in V$, $\mathbb{P}_{\delta_0}^{\sigma, \tau}(V_0 = v) = \delta_0(v)$ and for every $n \in \mathbb{N}$,

$$ \mathbb{P}_{\delta_0}^{\sigma, \tau}(V_{n+1}, S_n, T_n | \pi_n) = \sigma(S_0 \cdots S_{n-1})(A_n) \cdot \tau(T_0 \cdots T_{n-1})(B_n) \cdot \Delta(V_n, A_n, B_n)(V_{n+1}, S_n, T_n), $$

where we use standard notations for conditional probability measures.

**Winning conditions.** The set of colours is $C = \{0, 1\}$. The reachability, safety, Büchi and coBüchi condition are defined as follows:

$$ \text{Reach} = \{ \exists n \in \mathbb{N}, C_n = 1 \} $$

$$ \text{Safety} = \{ \forall n \in \mathbb{N}, C_n = 0 \} $$

$$ \text{Buchi} = \{ \forall m \in \mathbb{N}, \exists n \ge m, C_n = 1 \} $$

$$ \text{CoBuchi} = \{ \exists m \in \mathbb{N}, \forall n \ge m, C_n = 0 \}. $$

When the winning condition is Win, Eve and Adam use strategies $\sigma$ and $\tau$ and the initial distribution is $\delta_0$, then Eve wins the game with probability:

$$ \mathbb{P}_{\delta_0}^{\sigma, \tau}(\text{Win}). $$

Eve wants to maximise this probability, while Adam wants to minimise it.

### 8.3.2 The value problem.

The value problem is computationally intractable for games with infinite duration and imperfect information. This holds even for the very simple case of blind one-player games with reachability conditions. Those are games where the set of signals is a singleton and actions of Adam have no influence on the transition probabilities. These games can be seen as probabilistic automata, hence the undecidability result of Paz applies.

**Theorem 95** (Undecidability for blind one-player games). *Whether Eve has a strategy to win with probability $\ge \frac{1}{2}$ is undecidable, even in blind one-player games.*

Actually, the value might not even exist.

**Proposition 2** (The value may not be defined). *There is a game with infinite duration imperfect information and Büchi condition in which*

$$ \sup_{\sigma} \inf_{\tau} \mathbb{P}_{\delta_0}^{\sigma, \tau}(\text{Buchi}) = \frac{1}{2} < 1 = \inf_{\tau} \sup_{\sigma} \mathbb{P}_{\delta_0}^{\sigma, \tau}(\text{Buchi}). $$

The value however exists for games with reachability condition. Although the value problem is not decidable, there are some other interesting decision problems to consider.
### 8.3.3 Winning with probability 1 or > 0

**Winning almost-surely or positively.** A strategy $\sigma$ for Eve is almost-surely winning from an initial distribution $\delta_0$ if

$$ \forall \tau, \mathbb{P}_{\delta_0}^{\sigma, \tau}(\text{Win}) = 1 . $$

When such an almost-surely strategy $\sigma$ exists, the initial distribution $\delta_0$ is said to be almost-surely winning (for Eve).

A less enjoyable situation for Eve is when she only has a positively winning strategy. A strategy $\sigma$ for Eve is positively winning from an initial distribution $\delta_0$ if

$$ \forall \tau, \mathbb{P}_{\delta_0}^{\sigma, \tau}(\text{Win}) > 0 . $$

When such a strategy $\sigma$ exists, the initial distribution $\delta$ is said to be positively winning (for Eve). Symmetrically, a strategy $\tau$ for Adam is positively winning if it guarantees $\forall \sigma, \mathbb{P}_{\delta_0}^{\sigma, \tau}(\text{Win}) < 1$.

The worst situation for Eve is when her opponent has an almost-surely winning strategy $\tau$, which thus ensures $\mathbb{P}_{\delta_0}^{\sigma, \tau}(\text{Win}) = 0$ whatever strategy $\sigma$ is chosen by Eve.

**Qualitative determinacy.**

**Theorem 96 (Qualitative determinacy).** Stochastic games with signals and reachability, safety and Büchi winning conditions are qualitatively determined: either Eve wins almost-surely winning or Adam wins positively. Formally, in those games,

$$ (\forall \tau, \exists \sigma, \mathbb{P}_{\delta_0}^{\sigma, \tau}(\text{Win}) = 1) \implies (\exists \sigma, \forall \tau, \mathbb{P}_{\delta_0}^{\sigma, \tau}(\text{Win}) = 1) . $$

The proof of this result is given in the next section.

Since reachability and safety games are dual, a consequence of Theorem 96, is that in a reachability game, every initial distribution is either almost-surely winning for Eve, almost-surely winning for Adam, or positively winning for both players. When a safety condition is satisfied almost-surely for a fixed profile of strategies, it trivially implies that the safety condition is satisfied by all consistent plays, thus for safety games winning surely is the same than winning almost-surely.

By contrast, co-Büchi games are not qualitatively determined:

**Lemma 122.** There is a co-Büchi game in which neither Eve has an almost-surely winning strategy nor Adam has a positively winning strategy.

*Proof.* In this game, Eve observes everything, Adam is blind (he only observes his own actions), and Eve's objective is to visit only finitely many times the ⊙-state. The initial state is ⊙. The set of actions is $\{a, b, c, d\}$. All transitions are deterministic.

On one hand, no strategy $\Sigma$ is almost-surely winning for Eve for her co-Büchi objective. Since both players can observe their actions, it is enough to prove that no behavioral strategy $\sigma \in C^* \to \Delta(I)$ of Eve is almost-surely winning. Fix strategy $\sigma$ and assume towards contradiction that $\sigma$ is almost-surely winning. We define
a strategy $\tau$ such that $\mathbb{P}_{\oplus}^{\sigma, \tau}(\text{Buchi}) > 0$. Strategy $\tau$ starts by playing only $c$. The probability to be in state $\oplus$ at step $n$ is $x_n^0 = \mathbb{P}_{\oplus}^{\sigma, c^\omega}(V_n = \oplus)$ and since $\sigma$ is almost-surely winning then $x_n^0 \to_n 0$ thus there exists $n_0$ such that $x_{n_0}^0 \le \frac{1}{2}$. Then $\tau$ plays $d$ at step $n_0$. Assuming the state was 2 when $d$ was played, the probability to be in state $\oplus$ at step $n \ge n_0$ is $x_n^1 = \mathbb{P}_{\oplus}^{\sigma, c^{n_0}d^\omega}(V_n = \oplus | V_{n_0} = \oplus)$ and since $\sigma$ is almost-surely winning there exists $n_1$ such that $x_{n_1}^1 \le \frac{1}{4}$. Then $\tau$ plays $d$ at step $n_1$. By induction we keep defining $\tau$ this way so that $\tau = c^{n_0-1}dc^{n_1-n_0-1}dc^{n_2-n_1-1}d\dots$ and for every $k \in \mathbb{N}$, $\mathbb{P}_{\oplus}^{\sigma, \tau}(V_{n_{k+1}} = \oplus$ and $V_{n_{k+1}-1} = 2 | V_{n_k} = \oplus) \ge 1 - \frac{1}{2^{k+1}}$. Thus finally $\mathbb{P}_{\oplus}^{\sigma, \tau}(\text{Buchi}) \ge \Pi_k(1 - \frac{1}{2^{k+1}}) > 0$ which contradicts the hypothesis.

On the other hand, Adam does not have a positively winning strategy either. Intuitively, Adam cannot win positively because as time passes, either the play reaches state 1 or the chances that Adam plays action $d$ drop to 0. When these chances are small, Eve can play action $c$ and she bets no more $d$ will be played and the play will stay safe in state 2. If Eve loses her bet then again she waits until the chances to see another $d$ are small and then plays action $c$. Eve may lose a couple of bets but almost-surely she eventually is right and the CoBuchi condition is almost-surely fulfilled.

Finally neither Eve wins almost-surely nor Adam wins positively. □

### Decidability

**Theorem 97.** Deciding whether the initial distribution of a Büchi games, is almost-surely winning for Eve is 2EXP-complete. For safety games, the same problem is EXP-complete.

Concerning winning positively a safety or co-Büchi game, one can use Theorem 96 and the determinacy property: Adam has a positively winning strategy in the above game if and only if Eve has no almost-surely winning strategy. Therefore, deciding when Adam has a positively winning strategy can also be done, with the same complexity.

**Theorem 98.** For reachability and Büchi games where either Eve is perfectly informed about the state or Adam is better informed than Eve, deciding whether the initial distribution is almost-surely winning for Eve is EXP-complete. In safety games Eve is perfectly informed about the state, the decision problem is in P.

### 8.3.4 Qualitative determinacy: proof of Theorem 96

**Beliefs.** The belief of a player is the set of possible states of the game, according to the signals received by the player.

**Definition 25 (Belief).** Let $\mathcal{A}$ be an arena with observable actions. From an initial set of states $L \subseteq V$, the belief of Eve after having received signal $s$ is:

$$ \mathcal{B}_{Eve}(L,s) = \{v \in V \mid \exists l \in L, t \in S \text{ such that } \Delta(l,s,t)(v, \text{Act}(s), \text{Act}(t)) > 0\}. $$

Remark that in this definition we use the fact that actions of Eve are observable, thus when he receives a signal $s \in C$ Eve can deduce he played action $a_1(c) \in I$. The
belief of Eve after having received a sequence of signals $s_1, \dots, s_n$ is defined inductively by:

$$ \mathcal{B}_{Eve}(L, s_1, s_2, \dots, s_n) = \mathcal{B}_{Eve}(\mathcal{B}_{Eve}(L, s_1, \dots, s_{n-1}), s_n). $$

Beliefs of Adam are defined similarly. Given an initial distribution $\delta$, we denote $\mathcal{B}_{Eve}^n$ the random variable defined by

$$ \mathcal{B}_{Eve}^0 = \text{supp}(\delta) $$

$$ \mathcal{B}_{Eve}^{n+1} = \mathcal{B}_{Eve}(\text{supp}(\delta), C_1, \dots, C_{n+1}) = \mathcal{B}_{Eve}(\mathcal{B}_{Eve}^n, C_{n+1}) . $$

We will also rely on the notion of belief of belief, called here 2-belief, which, roughly speaking, represents for one player the set of possible beliefs for his (or her) adversary, as well as the possible current state.

**Definition 26 (2-Belief).** Let $\mathcal{A}$ be an arena with observable actions. From an initial set $\mathcal{L} \subseteq V \times \mathcal{P}(V)$ of pairs composed of a state and a belief for Adam, the 2-belief of Eve after having received signal $c$ is the subset of $V \times \mathcal{P}(V)$ defined by:

$$ \mathcal{B}_{Eve}^{(2)}(\mathcal{L}, s) = \{(v, \mathcal{B}_{Adam}(L, t)) \mid \exists (l, L) \in \mathcal{L}, t \in S, \Delta(v, s, t)(l, \text{Act}(s), \text{Act}(t)) > 0\} . $$

From an initial set $\mathcal{L} \subseteq V \times \mathcal{P}(V)$ of pairs composed of a state and a belief for Adam, the 2-belief of Eve after having received a sequence of signals $s_1, \dots, s_n$ is defined inductively by:

$$ \mathcal{B}_{Eve}^{(2)}(\mathcal{L}, s_1, s_2, \dots, s_n) = \mathcal{B}_{Eve}^{(2)}(\mathcal{B}_{Eve}^{(2)}(\mathcal{L}, s_1, \dots, s_{n-1}), s_n) . $$

There are natural definitions of 3-beliefs (beliefs on beliefs on beliefs) and even $k$-beliefs however for our purpose, 2-beliefs are enough, in the following sense: in Büchi games the positively winning sets of Adam can be characterised by fixed point equations on sets of 2-beliefs, and some positively winning strategies of Adam with finite-memory can be implemented using 2-beliefs.

**Supports positively winning supports.** Note that whether an initial distribution $\delta_0$ is almost-surely or positively winning depends only on its support, because $\mathbb{P}_{\delta_0}^{\sigma, \tau}(\text{Win}) = \sum_{v \in V} \delta_0(v) \cdot \mathbb{P}_{\delta_0}^{\sigma, \tau}(\text{Win} | V_0 = v)$. As a consequence, we will say that a support $L \subseteq V$ is almost-surely or positively winning for a player if there exists a distribution with support $L$ which has the same property.

In the sequel, we will denote $\mathcal{L}_{Eve,=1}$ the set of supports almost-surely winning for Eve and $\mathcal{L}_{Adam,>0}$ those positively winning for Adam.

Then the qualitative determinacy theorem is a corollary of the following lemma.

**Lemma 123.** In every Büchi game, every non-empty support which does not belong to $\mathcal{L}_{Adam,>0}$ belongs to $\mathcal{L}_{Eve,=1}$.

The proof of this lemma relies on the definition of a strategy called the maximal strategy. We prove that this strategy is almost-surely winning from any initial distribution which is not positively winning for Adam.
**Definition 27 (Maximal strategy).** For every non-empty support $L \subseteq V$ we define the set of L-safe actions for Eve as

$$ \mathrm{ISafe}(L) = \{a \in A \mid \forall s \in S, (\mathrm{Act}(s) = a) \implies (\mathcal{B}_{\mathrm{Eve}}(L, s) \notin \mathcal{L}_{\mathrm{Adam}, >0})\}, $$

in other words these are the actions which Eve can play without taking the risk that her belief is positively winning for Adam.

The maximal strategy is the strategy of Eve which plays the uniform distribution on $\mathrm{ISafe}(\mathcal{B}_{\mathrm{Eve}})$ when it is not empty and plays the uniform distribution on A otherwise. It is denoted $\sigma_{\max}$.

To play her maximal strategy at step $n$, Eve only needs to keep track of her belief $\mathcal{B}_{\mathrm{Eve}}$, thus $\sigma_{\max}$ can be implemented by Eve using a finite-memory device which keeps track of the current belief. Such a strategy is said to be belief-based. We will use several times the following technical lemma about belief-based strategies.

**Lemma 124.** Fix a Büchi game. Let $\mathcal{L} \subseteq \mathcal{P}(V)$ and $\sigma$ a strategy for player 1. Assume that $\sigma$ is a belief strategy, $\mathcal{L}$ is downward-closed (i.e. $L \in \mathcal{L} \wedge L' \subseteq L \implies L' \in \mathcal{L}$) and for every $L \in \mathcal{L} \setminus \{0\}$ and every strategy $\tau$,

$$ \mathbb{P}_{\delta_L}^{\sigma, \tau}(\mathrm{Reach}) > 0, \qquad (8.2) $$

$$ \mathbb{P}_{\delta_L}^{\sigma, \tau}(\forall n \in \mathbb{N}, \mathcal{B}_{\mathrm{Eve}}^n \in \mathcal{L}) = 1. \qquad (8.3) $$

Then $\sigma$ is almost-surely winning for the Büchi game from any support $L \in \mathcal{L} \setminus \{0\}$.

*Proof.* Since $\mathcal{L}$ is downward-closed then $\forall L \in \mathcal{L}, \forall l \in L, \{l\} \in \mathcal{L}$ thus Section 8.3.3 implies

$$ \forall L \in \mathcal{L}, \forall l \in L, \mathbb{P}_{\delta_L}^{\sigma, \tau}(\mathrm{Reach} | V_0 = l) > 0. \qquad (8.4) $$

Once $\sigma$ is fixed then the game is a one-player game with state space $V \times 2^V$ and imperfect information and Equation (8.4) implies that in this one-player game,

$$ \forall L \in \mathcal{L}, \forall l \in L, \forall \tau, \mathbb{P}_{\delta_L}^{\tau}(\mathrm{Reach} | V_0 = l) > \varepsilon, \qquad (8.5) $$

where $N = |K| \cdot 2^{|K|}$ and $\varepsilon = p_{\min}^{|K| \cdot 2^{|K|}}$ and $p_{\min}$ is the minimal non-zero transition probability. Moreover Equation (8.3) implies that in this one-player game the second component of the state space is always in $\mathcal{L}$, whatever strategy $\tau$ is played by player 2. Remind the definition

$$ \mathrm{Reach} = \{\exists n \in \mathbb{N}, C_n = 1\}. $$

As a consequence, in this one-player game for every $m \in \mathbb{N}$, and every behavioral strategy $\tau$ and every $l \in V$,

$$ \mathbb{P}_{\delta_L}^{\tau}(\exists m \le n \le m + N, C_n = 1 | K_m = l) \ge \varepsilon, \qquad (8.6) $$

whenever $\mathbb{P}_{\delta_L}^{\tau}(V_m = l) > 0$.
We use the Borel-Cantelli Lemma to conclude the proof. According to Equation (8.6), for every $\tau$, $L \in \mathcal{L}$, $m \in \mathbb{N}$,

$$ \mathbb{P}_{\delta_L}^{\tau} (\exists n, mN \le n < (m+1)N, C_n = 1 | V_{mN}) \ge \varepsilon, \qquad (8.7) $$

which implies for every behavioral strategy $\tau$ and $k, m \in \mathbb{N}$,

$$ \mathbb{P}_{\delta_L}^{\tau} (\forall n, ((m \cdot N) \le n < ((m+k) \cdot N) \implies C_n \ne 1)) \le (1 - \varepsilon)^k . $$

Since $\sum_k (1 - \varepsilon)^k$ is finite, we can apply Borel-Cantelli Lemma for the events $(\{\forall n, m \cdot N \le n < (m+k) \cdot N \implies C_n \ne 1\})_k$ and we get $\mathbb{P}_{\delta_L}^{\tau} (\forall n, m \cdot N \le n \implies C_n \ne 1) = 0$ thus

$$ \mathbb{P}_{\delta_L}^{\tau} (\text{Buchi}) = 1 . \qquad (8.8) $$

As a consequence $\sigma$ is almost-surely winning for the Büchi game. $\square$

An important feature of the maximal strategy is the following.

**Lemma 125.** In a Büchi game with observable actions, let $\delta \in \Delta(K)$ be an initial distribution which is not positively winning for Adam, i.e. $\text{supp}(\delta) \notin \mathcal{L}_{Adam,>0}$. Then for every strategy $\tau$ of Adam

$$ \mathbb{P}_{\delta}^{\sigma_{\max}, \tau} (\forall n \in \mathbb{N}, \mathcal{B}_{Eve}^{n} \notin \mathcal{L}_{Adam,>0}) = 1 . \qquad (8.9) $$

*Proof.* We only provide a sketch of proof. The proof is an induction based on the fact that for every non-empty subset $L \subseteq V$,

$$ (L \notin \mathcal{L}_{Adam,>0}) \implies (\text{ISafe}(L) \ne \emptyset) . $$

Assume a contrario that $\text{ISafe}(L) = \emptyset$ for some $L \notin \mathcal{L}_{Adam,>0}$. Then for every action $a \in A$ there exists a signal $s_a \in S$ such that $\mathcal{B}_{Eve}(L, s_a) \ne \emptyset$ and $\mathcal{B}_{Eve}(L, s_a) \in \mathcal{L}_{Adam,>0}$. Since $\mathcal{B}_{Eve}(L, s_a) \ne \emptyset$, the definition of the belief operator implies:

$$ \exists v_a \in L, w_a \in V, t_a \in T, \text{ such that } \Delta(w_a, s_a, t_a)(v_a, \text{Act}(s), \text{Act}(t_a)) > 0 . $$

But then Adam can win positively from $L$ with the following strategy. At the first round, Adam plays randomly any action in $A$. At the next round, Adam picks up randomly a belief in $\mathcal{L}_{Adam,>0}$ and plays forever the corresponding positively winning strategy. Remark that this strategy of Adam is not described as a behavioural strategy but rather as a finite-memory strategy. Since actions are observable, such a finite-memory strategy can be turned into a behavioural one, see [BGG17, Lemma 4.6 and 4.7].

Why is Adam strategy positively winning from $L$? Whatever action $a \in A$ is played by Eve, with positive probability she will receive signal $s_a$, because Adam might play the action $\text{Act}(t_a)$. Since $\mathcal{B}_{Eve}(L, s_a) \in \mathcal{L}_{Adam,>0}$ then there Adam might with positive probability play a strategy positively winning when the initial belief of Eve is $\mathcal{B}_{Eve}(L, s_a)$. Thus whatever action Eve chooses, she might lose with positive probability.

$\square$
The notion of maximal strategy being defined, we can complete the proof of Theorem 96. For that, we show that $\sigma_{\max}$ is almost-surely winning from every support not in $\mathcal{L}_{Adam,>0}$.

Reachability and safety conditions can be easily encoded as Büchi conditions, thus it is enough to consider Büchi games.

The first step is to prove that for every $L \in \mathcal{L}_{Eve,=1}$, for every strategy $\tau$ of Adam,

$$ \mathbb{P}_{\delta_L}^{\sigma_{\max}, \tau}(\text{Safety}) < 1. \qquad (8.10) $$

We prove Equation (8.10) by contradiction. Assume Equation (8.10) does not hold for some $L \in \mathcal{L}_{Eve,=1}$ and strategy $\tau$:

$$ \mathbb{P}_{\delta_L}^{\sigma_{\max}, \tau}(\text{Safety}) = 1. \qquad (8.11) $$

Under this assumption we use $\tau$ to build a strategy positively winning from $L$, which will contradict the hypothesis $L \in \mathcal{L}_{Adam,>0}$. Although $\tau$ is surely winning from $L$ against the particular strategy $\sigma_{\max}$, there is no reason for $\tau$ to be positively winning from $L$ against all other strategies of player 1.

However we can rely on $\tau$ in order to define another strategy $\tau'$ for Adam positively winning from $L$. The strategy $\tau'$ is a strategy which gives positive probability to play $\tau$ all along the play, as well as any strategy in the family of strategies $(\tau_{n,B})_{n \in \mathbb{N}, B \in \mathcal{L}_{Adam,>0}}$ defined as follows. For every $B \in \mathcal{L}_{Adam,>0}$ we choose a strategy $\tau_B$ positively winning from $B$. Then $\tau_{n,B}$ is the strategy which plays the uniform distribution on $A$ for the first $n$ steps then forgets past signals and switches definitively to $\tau_B$.

A possible way to implement the strategy $\tau'$ is as follows. At the beginning of the play player 2 tosses a fair coin. If the result is head then he plays $\tau$. Otherwise he keeps tossing coins and as long as the coin toss is head, player 2 plays randomly an action in $J$. The day the coin toss is tail, he picks up randomly some $B \in \mathcal{L}_{Adam,>0}$ and starts playing $\tau_B$.

Remark that this strategy of Adam is not described as a behavioural strategy but, since actions are observable, such a finite-memory strategy can be turned into a behavioural one, see [BGG17, Lemma 4.6 and 4.7].

Now that $\tau'$ is defined, we prove it is positively winning from $L$. Let $E$ be the event 'player 1 plays only actions that are safe with respect to her belief', i.e.

$$ E = \{ \forall n \in \mathbb{N}, A_n \in \text{ISafe}_{\mathcal{L}}(\mathcal{B}_{Eve}^n) \}. $$

Then for every behavioral strategy $\sigma$:

* Either $\mathbb{P}_{\delta_L}^{\sigma, \tau'}(E) = 1$. In this case

$$ \mathbb{P}_{\delta_L}^{\sigma, \tau'}(\text{Safety}) > 0, $$

because for every finite play $\pi = v_0a_0b_0s_1t_1v_1 \cdots v_n$,

$$ (\mathbb{P}_{\delta_L}^{\sigma, \tau'}(\pi) > 0) \implies (\mathbb{P}_{\delta_L}^{\sigma_{\max}, \tau'}(\pi) > 0) \implies \text{Safety}, $$