## 1 Introduction

^{1}to as many disturbances as possible, i.e., to tolerate as many disturbances as possible but still win? Put slightly differently, disturbances induce an order on the space of winning strategies (“a winning strategy is better if it is more resilient”), and the natural problem is to compute optimally resilient winning strategies, yielding optimally resilient controllers. Note that this is in contrast to the classical theory of infinite games, where the space of winning strategies is unstructured.

### 1.1 Our contributions

## 2 Preliminaries

### 2.1 Infinite games with disturbances

### 2.2 Positional and finite-state strategies

### 2.3 Infinite games without disturbances

### 2.4 Resilient strategies

## 3 Computing optimally resilient strategies

### 3.1 Characterizing vertices of finite resilience

- If \(j_v\) is odd, then \(r_j(v) = \frac{j_v+1}{2}\) for every \(j \ge j_v\).
- If \(j_v\) is even, then \(r_j(v) = \frac{j_v}{2}\) for every \(j \ge j_v\).

- If j is odd, then no v is updated in \(r_j\) to some \(k < \frac{j+1}{2}\).
- If j is even, then no v is updated in \(r_j\) to some \(k < \frac{j}{2}\).

### 3.2 Characterizing vertices of resilience \(\omega +1\)

- D: Player 1 uses a disturbance edge.
- \( \{ (v ,\overline{v}) \mid v \in V_0 \} \): Player 1 does not use a disturbance edge and yields control to Player 0.
- \(\{ (\overline{v},v') \mid (v,v') \in E \text { and } v\in V_0 \}\): Player 0 has control and picks a standard edge.
- \( \{ (v ,v') \mid (v,v') \in E \text { and } v\in V_1 \} \): Player 1 takes a standard edge.

- If \(b_{j+1} =1\), then \((v_j, v_{j+1}) \in D\), i.e., the play traverses the disturbance edge \((v_j,v_{j+1})\). This move is mimicked by defining$$\begin{aligned}t'((v_0, b_0) \cdots (v_j, b_j)(v_{j+1}, b_{j+1})) = t'((v_0, b_0) \cdots (v_j, b_j)) \cdot (v_{j+1},0).\end{aligned}$$
- If \(b_{j+1} =0\), i.e., \((v_j, v_{j+1}) \in E\), and \(v_{j} \in V_0\), then the play did not traverse a disturbance edge and instead allowed Player 0 to pick a standard edge \((v_j,v_{j+1})\) to traverse. This move is mimicked by defining$$\begin{aligned} t'((v_0, b_0) \cdots (v_j, b_j)(v_{j+1}, b_{j+1})) = t'((v_0, b_0) \cdots (v_j, b_j)) \cdot (\overline{v_j},0) \cdot (v_{j+1},0). \end{aligned}$$
- If \(b_{j+1} =0\), i.e., \((v_j, v_{j+1}) \in E\), and \(v_{j} \in V_1\), then the play traversed the standard edge \((v_j,v_{j+1})\). This move is mimicked by defining$$\begin{aligned}t'((v_0, b_0) \cdots (v_j, b_j)(v_{j+1}, b_{j+1})) = t'((v_0, b_0) \cdots (v_j, b_j)) \cdot (v_{j+1},0). \end{aligned}$$

- First, assume we have a prefix of the form \( (v_0,0) \cdots (v_j, 0) (v_{j+1},0) \) for some \(v_j \in V_0\), i.e., Player 1’s move simulates the disturbance edge \((v_j, v_{j+1}) \in D\). Then, we define$$\begin{aligned} \quad \quad t((v_0,0) \cdots (v_j, 0) (v_{j+1},0)) = t((v_0,0) \cdots (v_j,0) )\cdot (v_{j+1},1). \end{aligned}$$
- Next, assume we have a prefix of the form \( (v_0,0) \cdots (v_j,0) (v_{j+1},0) \) for some \(v_j \in V_1\), i.e., Player 1’s move simulates the standard edge \((v_j, v_{j+1}) \in E\). Then, we define$$\begin{aligned} \quad \quad t((v_0,0) \cdots (v_j,0) (v_{j+1},0)) = t((v_0,0) \cdots (v_j,0) )\cdot (v_{j+1},0). \end{aligned}$$
- Finally, the last case is a prefix of the form \( (v_0,0) \cdots (v_j,0) (\overline{v_j}, 0) (v_{j+1},0) \) for some \(v_j \in V_0\), i.e., Player 0’s move simulates the standard edge \((v_j, v_{j+1}) \in E\). Then, we define$$\begin{aligned} \quad \quad t((v_0,0) \cdots (v_j,0) (\overline{v_j},0) (v_{j+1},0)) = t((v_0,0) \cdots (v_j,0) )\cdot (v_{j+1},0). \end{aligned}$$

### 3.3 Computing optimally resilient strategies

- For every \(v \in V\) with \(r_\mathcal {G}(v) \in \omega {\setminus } \{ 0 \}\), the strategy \(\sigma _v\) is winning for Player 0 from v for the game \((\mathcal {A}, \mathrm {Win}\cap \mathrm {Safety}(\{ v' \in V \mid r_\mathcal {G}(v') < r_\mathcal {G}(v) \}))\). We have shown the existence of such a strategy in the proof of Item 1 of Lemma 5.
- For every \(v \in V\) with \(r_\mathcal {G}(v)=\omega \), the strategy \(\sigma _v\) is winning for Player 0 from v for the game \((\mathcal {A}, \mathrm {Win}\cap \mathrm {Safety}(\{ v' \in V \mid r_\mathcal {G}(v') \in \omega \}))\). We have shown the existence of such a strategy in the proof of Item 2 of Lemma 5.
- For every \(v \in V\) with \(r_\mathcal {G}(v) = \omega +1\), the strategy \(\sigma _v\) is \((\omega +1)\)-resilient from v. The existence of such a strategy follows from Item 1 of Corollary 3, as we assume Player 0 to win \(\mathcal {G}_\mathrm {rig}\) with positional strategies.
- For every \(v \in V\) with \(r_\mathcal {G}(v) = 0\), we fix an arbitrary positional strategy \(\sigma _v\) for Player 0.

- If \(r_\mathcal {G}(v) \in \omega \), then \(r_\mathcal {G}(v') \ge r_\mathcal {G}(v) -1\).
- If \(r_\mathcal {G}(v) = \omega \), then \(r_\mathcal {G}(v') = \omega \), and
- If \(r_\mathcal {G}(v) = \omega + 1\), then \(r_\mathcal {G}(v') = \omega + 1\) and \(m(v) \ge m(v')\) (here, the second property follows from the definition of \(R_v\) for v with \(r_\mathcal {G}(v) = \omega + 1\), which takes disturbance edges into account).