[BT91] Dimitri P. Bertsekas and John N. Tsitsiklis. An analysis of stochastic shortest path problems. *Math. Oper. Res.*, 16(3):580–595, 1991. doi:10.1287/MOOR.16.3.580.

[Bus19] Damien Busatto-Gaston. *Symbolic controller synthesis for timed systems: robustness and optimality*. PhD thesis, Aix-Marseille Université, 2019. URL: https://tel.archives-ouvertes.fr/tel-02436831.

[CdAH04] Krishnendu Chatterjee, Luca de Alfaro, and Thomas A. Henzinger. Trading memory for randomness. In *1st International Conference on Quantitative Evaluation of Systems (QEST 2004), 27-30 September 2004, Enschede, The Netherlands*, QEST '04, pages 206–217. IEEE Computer Society, 2004. doi:10.1109/QEST.2004.1348035.

[CHJ05] Krishnendu Chatterjee, Thomas A. Henzinger, and Marcin Jurdziński. Mean-payoff parity games. In *20th IEEE Symposium on Logic in Computer Science (LICS 2005), 26-29 June 2005, Chicago, IL, USA, Proceedings*, pages 178–187. IEEE Computer Society, 2005. doi:10.1109/LICS.2005.26.

[CHP08] Krishnendu Chatterjee, Thomas A. Henzinger, and Vinayak S. Prabhu. Trading infinite memory for uniform randomness in timed games. In Magnus Egerstedt and Bud Mishra, editors, *Hybrid Systems: Computation and Control, 11th International Workshop, HSCC 2008, St. Louis, MO, USA, April 22-24, 2008. Proceedings*, volume 4981 of Lecture Notes in Computer Science, pages 87–100. Springer, 2008. doi:10.1007/978-3-540-78929-1\_7.

[CRR14] Krishnendu Chatterjee, Mickael Randour, and Jean-François Raskin. Strategy synthesis for multi-dimensional quantitative objectives. *Acta Informatica*, 51(3-4):129–163, 2014. doi:10.1007/s00236-013-0182-6.

[GTW02] Erich Grädel, Wolfgang Thomas, and Thomas Wilke, editors. *Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001]*, volume 2500 of Lecture Notes in Computer Science. Springer, 2002. doi:10.1007/3-540-36387-4.

[GZ05] Hugo Gimbert and Wiesław Zielonka. Games where you can play optimally without any memory. In Martín Abadi and Luca de Alfaro, editors, *CONCUR 2005 - Concurrency Theory, 16th International Conference, CONCUR 2005, San Francisco, CA, USA, August 23-26, 2005, Proceedings*, volume 3653 of Lecture Notes in Computer Science, pages 428–442. Springer, 2005. doi:10.1007/11539452\_33.

[JT07] Marcin Jurdzinski and Ashutosh Trivedi. Reachability-time games on timed automata. In Lars Arge, Christian Cachin, Tomasz Jurdzinski, and Andrzej Tarlecki, editors, *Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings*, volume 4596 of Lecture Notes in Computer Science, pages 838–849. Springer, 2007. doi:10.1007/978-3-540-73420-8\_72.

[KBB+08] Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled M. Elbassioni, Vladimir Gurvich, Gábor Rudolf, and Jihui Zhao. On short paths interdiction problems: Total and node-wise limited interdiction. *Theory Comput. Syst.*, 43(2):204–233, 2008. doi:10.1007/S00224-007-9025-6.

[KRN65] Kazimierz Kuratowski and Czesław Ryll-Nardzewski. A general theorem on selectors. *Bull. Acad. Pol. Sci., Sér. Sci. Math. Astron. Phys.*, 13:397–403, 1965.

[KSK76] John G. Kemeny, J. Laurie Snell, and Anthony W. Knapp. *Denumerable Markov Chains*. Graduate Texts in Mathematics. Springer-Verlag, 1976. URL: https://books.google.fr/books?id=porsRg4NDM8C.

[MPR20] Benjamin Monmege, Julie Parreaux, and Pierre-Alain Reynier. Reaching your goal optimally by playing at random with no memory. In Igor Konnov and Laura Kovács, editors, *31st International Conference on Concurrency Theory, CONCUR 2020, September 1-4, 2020, Vienna, Austria (Virtual Conference)*, volume 171 of LIPIcs, pages 26:1–26:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPICS.CONCUR.2020.26.

[MPR21] Benjamin Monmege, Julie Parreaux, and Pierre-Alain Reynier. Playing stochastically in weighted timed games to emulate memory. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, *48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference)*, volume 198 of LIPIcs, pages 137:1–137:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPICS.ICALP.2021.137.

[Nas50] John F. Nash. Equilibrium points in n-person games. *Proceedings of the National Academy of Sciences of the United States of America*, 36(1):48–49, 1950.
## APPENDIX A. CONSTRUCTION OF THE PROBABILITY MEASURE

**Proposition 3.6.** If $\eta$ and $\theta$ are smooth strategies, then, for all finite plays $\rho_0$, there exists a probability measure $\mathbb{P}_{\rho_0}^{\eta,\theta}$ over $(\text{Plays}_{\rho_0}^{\eta,\theta}, \Sigma_{\rho_0})$.

We follow a similar proof schema as in [BBB$^+$14, Appendix A]. We start by proving that $\mathbb{P}_{\rho_0}^{\eta,\theta}$ is a probability measure over the algebra $(\text{Plays}_{\rho_0}^{\eta,\theta}, \mathcal{A}_{\rho_0})$ generated by cylinders defined from paths (then closed by finite union and complement). Then, we use Carathéodory's extension theorem (Theorem A.3) to conclude that $\mathbb{P}_{\rho_0}^{\eta,\theta}$ is a probability measure over the $\sigma$-algebra generated by all maximal paths.

To define the probability $\mathbb{P}_{\rho_0}^{\eta,\theta}$ over elements of the algebra $\mathcal{A}_{\rho_0}$, we consider an inductive definition of $\mathcal{A}_{\rho_0}$. We remark that $\mathcal{A}_{\rho_0} = \bigcup_n \mathcal{A}_{\rho_0}^n$ where $\mathcal{A}_{\rho_0}^n$ is the algebra generated by all cylinders defined with a path of length at most $5^n$ from $\rho_0$. More precisely, we let $\text{FPaths}_{\rho_0}^n$ be the set of paths from $\rho_0$ that are either non-maximal and length $n$ or maximal and length at most $n$. Then, $\mathcal{A}_{\rho_0}^n$ is generated by all cylinders of the form $\text{Cyl}_{\rho_0}(\pi, C)$ with $\pi \in \text{FPaths}_{\rho_0}^n$ and $C$ a Lebesgue-measurable set of $\mathbb{R}^{\lfloor \pi \rfloor}$. Elements of $\mathcal{A}_{\rho_0}^n$ are finite unions of such disjoint cylinders and we let their probability be the sum of the probability of each cylinder.

**Lemma A.1.** Let $n \in \mathbb{N}$ and $\rho_0$ be a finite play, then $\mathbb{P}_{\rho_0}^{\eta,\theta}$ is a measure$^6$ over the algebra $(\text{Plays}_{\rho_0}^{\eta,\theta}, \mathcal{A}_{\rho_0}^n)$.

*Proof.* By definition and Lemma 3.5.(2), $\mathbb{P}_{\rho_0}^{\eta,\theta}$ is additive, non-negative and finite over $(\text{Plays}_{\rho_0}^{\eta,\theta}, \mathcal{A}_{\rho_0}^n)$. In particular, by [KSK76], $\mathbb{P}_{\rho_0}^{\eta,\theta}$ is $\sigma$-additive, if and only if for all sequences $(A_i)_i$ of elements of $\mathcal{A}_{\rho_0}^n$ such that $A_0 \subseteq A_1 \subseteq \dots$ and $A = \bigcup_i A_i \in \mathcal{A}_{\rho_0}^n$, we have $\mathbb{P}_{\rho_0}^{\eta,\theta}(A) = \lim_i \mathbb{P}_{\rho_0}^{\eta,\theta}(A_i)$. So, let $(A_i)_i$ be such a sequence. Without loss of generality, we can suppose that each $A_i$ is generated by the same path $\pi = \delta_1 \cdots \delta_k$ with $k \le n$ (since $\pi$ may be a maximal path of a length less than $n$), otherwise it suffices to intersect each $A_i$ with $\text{Cyl}_{\rho_0}(\pi)$. In particular, letting $(C_i^j)_j$ be the sequence of disjoint sets of constraints that appear in cylinders of $A_i$, we have $A_i = \bigcup_{j=0}^{m_i} \text{Cyl}_{\rho_0}(\pi, C_i^j)$ where $m_i$ is the number of cylinders in $A_i$. Now, by definition of probabilities (and its additivity on cylinders), we have

$$ \mathbb{P}_{\rho_0}^{\eta,\theta}(A_i) = \sum_{j=0}^{m_i} \mathbb{P}_{\rho_0}^{\eta,\theta}(\pi, C_i^j). $$

In particular, $\mathbb{P}_{\rho_0}^{\eta,\theta}(A_i)$ is equal to

$$ \sum_{j=0}^{m_i} \int_{I(\rho_0, \delta_1)} \dots \int_{I(\rho_0[\delta_1, t_1] \dots [\delta_{k-1}, t_{k-1}], \delta_k)} \xi_{\Delta}(\rho_0)(\delta_1) \dots \xi_{\Delta}(\rho_0[\delta_1, t_1] \dots [\delta_{k-1}, t_{k-1}]) (\delta_k) \times \mathbb{P}_{\rho_0[\delta_1, t_1] \dots [\delta_k, t_k]}^{\eta, \theta}(\pi, C_i^j) \mathrm{d}\xi_{\mathbb{R}^+}(\rho_0[\delta_1, t_1] \dots [\delta_{k-1}, t_{k-1}], \delta_k)(t_k) \dots \mathrm{d}\xi_{\mathbb{R}^+}(\rho_0, \delta_1)(t_1). $$

<footnote>$^5$In [BBB$^+$14] authors defined this set by cylinders with a length equal to $n$. Here, we need to relax this hypothesis since maximal paths may be finite of length smaller than $n$, and if we do not keep these shorter paths, we will lose some mass of probability.</footnote>

<footnote>$^6$More precisely, we can prove that $\mathbb{P}_{\rho_0}^{\eta,\theta}$ is a probability measure over $(\text{Plays}_{\rho_0}^{\eta,\theta}, \mathcal{A}_{\rho_0}^n)$. However, since this property is not useful in the following, we do not prove that $\mathbb{P}_{\rho_0}^{\eta,\theta}(\text{Plays}_{\rho_0}^{\eta,\theta}) = 1$ at this step of the proof.</footnote>
Moreover, by letting $\chi_Y$ be the characteristic function of the set $Y$, we remark that $\mathbb{P}_{\rho_0[\delta_1, t_1]\cdots[\delta_k, t_k]}^{\eta, \theta}(\pi, C_i^j) = \chi_{Cyl}(\pi, C_i^j) (\rho_0[\delta_1, t_1]\cdots[\delta_k, t_k])$ (by definition of the probability) and $\mathbb{P}_{\rho_0}^{\eta, \theta}(A_i)$ is equal to

$$ \sum_{j=0}^{m_i} \int_{I(\rho_0, \delta_1)} \cdots \int_{I(\rho_0[\delta_1, t_1]\cdots[\delta_{k-1}, t_{k-1}], \delta_k)} \xi_{\Delta}(\rho_0)(\delta_1) \cdots \xi_{\Delta}(\rho_0[\delta_1, t_1]\cdots[\delta_{k-1}, t_{k-1}]) (\delta_k) \times \chi_{Cyl}(\pi, C_i^j) (\rho_0[\delta_1, t_1]\cdots[\delta_k, t_k]) \\ d\xi_{\mathbb{R}^+}(\rho_0[\delta_1, t_1]\cdots[\delta_{k-1}, t_{k-1}], \delta_k)(t_k) \cdots d\xi_{\mathbb{R}^+}(\rho_0, \delta_1)(t_1). $$

In particular by linearity of the integral, we obtain that $\mathbb{P}_{\rho_0}^{\eta, \theta}(A_i)$ is equal to

$$ \int_{I(\rho_0, \delta_1)} \cdots \int_{I(\rho_0[\delta_1, t_1]\cdots[\delta_{k-1}, t_{k-1}], \delta_k)} \xi_{\Delta}(\rho_0)(\delta_1) \cdots \xi_{\Delta}(\rho_0[\delta_1, t_1]\cdots[\delta_{k-1}, t_{k-1}]) (\delta_k) \times \chi_{A_i}(\rho_0[\delta_1, t_1]\cdots[\delta_k, t_k]) \\ d\xi_{\mathbb{R}^+}(\rho_0[\delta_1, t_1]\cdots[\delta_{k-1}, t_{k-1}], \delta_k)(t_k) \cdots d\xi_{\mathbb{R}^+}(\rho_0, \delta_1)(t_1). $$

since $\sum_{j=0}^{m_i} \chi_{Cyl}(\pi, C_i^j) = \chi_{A_i}$ (as $C_i^j$ are disjoint sets). Moreover, since, for all $i$, $\chi_{A_i}$ is bounded by 1, by dominated convergence, we deduce that $\lim_i \mathbb{P}_{\rho_0}^{\eta, \theta}(A_i)$ is equal to

$$ \int_{I(\rho_0, \delta_1)} \cdots \int_{I(\rho_0[\delta_1, t_1]\cdots[\delta_{k-1}, t_{k-1}], \delta_k)} \xi_{\Delta}(\rho_0)(\delta_1) \cdots \xi_{\Delta}(\rho_0[\delta_1, t_1]\cdots[\delta_{k-1}, t_{k-1}]) (\delta_k) \times \left( \lim_{i} \chi_{A_i}(\rho_0[\delta_1, t_1]\cdots[\delta_k, t_k]) \right) \\ d\xi_{\mathbb{R}^+}(\rho_0[\delta_1, t_1]\cdots[\delta_{k-1}, t_{k-1}], \delta_k)(t_k) \cdots d\xi_{\mathbb{R}^+}(\rho_0, \delta_1)(t_1). $$

Moreover, since $A = \bigcup_i A_i$, then $\lim_i \chi_{A_i} = \chi_A$. Thus, we deduce that $\lim_i \mathbb{P}_{\rho_0}^{\eta, \theta}(A_i)$ is equal to

$$ \int_{I(\rho_0, \delta_1)} \cdots \int_{I(\rho_0[\delta_1, t_1]\cdots[\delta_{k-1}, t_{k-1}], \delta_k)} \xi_{\Delta}(\rho_0)(\delta_1) \cdots \xi_{\Delta}(\rho_0[\delta_1, t_1]\cdots[\delta_{k-1}, t_{k-1}]) (\delta_k) \times \chi_A(\rho_0[\delta_1, t_1]\cdots[\delta_k, t_k]) \\ d\xi_{\mathbb{R}^+}(\rho_0[\delta_1, t_1]\cdots[\delta_{k-1}, t_{k-1}], \delta_k)(t_k) \cdots d\xi_{\mathbb{R}^+}(\rho_0, \delta_1)(t_1). $$

Thus, we conclude that $\lim_i \mathbb{P}_{\rho_0}^{\eta, \theta}(A_i) = \mathbb{P}_{\rho_0}^{\eta, \theta}(A)$ by the same way than for $\mathbb{P}_{\rho_0}^{\eta, \theta}(A_i)$, since $A$ is a finite union of cylinders (as $A \in \mathcal{A}_{\rho_0}^n$). $\square$

To prove that $\mathbb{P}_{\rho_0}^{\eta, \theta}$ is a probability measure on the algebra $(\text{Plays}_{\rho_0}^{\eta, \theta}, \mathcal{A}_{\rho_0})$, we use another property over $\mathcal{A}_{\rho_0}^n$: for all $n \in \mathbb{N}$, $\mathcal{A}_{\rho_0}^n \subseteq \mathcal{A}_{\rho_0}^{n+1}$. Let $A$ be an element of $\mathcal{A}_{\rho_0}^n$: either $A$ is a union of cylinders generated by maximal paths (of length at most $n$) and $A \in \mathcal{A}_{\rho_0}^{n+1}$, or there exists a cylinder of $A$ generated by a non maximal path $\pi$ of length $n$. Since $\pi$ is non-maximal, it can be extended by a transition $\delta$. In particular, for all constraints $C \subseteq \mathbb{R}^n_{\ge 0}$, $Cyl_{\rho_0}(\pi, C) = \bigcup_{\delta} Cyl_{\rho_0}(\pi\delta, C \times \mathbb{R}_{\ge 0})$. Thus, we conclude that $A \in \mathcal{A}_{\rho_0}^{n+1}$ by definition of $\mathcal{A}_{\rho_0}^{n+1}$.

**Lemma A.2.** Let $\rho_0$ be a finite play, then $\mathbb{P}_{\rho_0}^{\eta, \theta}$ is a probability measure over $(\text{Plays}_{\rho_0}^{\eta, \theta}, \mathcal{A}_{\rho_0})$.

*Proof.* We start by proving that $\mathbb{P}_{\rho_0}^{\eta, \theta}$ is a measure on $\mathcal{A}_{\rho_0}$. Since $\mathbb{P}_{\rho_0}^{\eta, \theta}$ is additive (as $\mathcal{A}_{\rho_0}^n \subseteq \mathcal{A}_{\rho_0}^{n+1}$), non-negative and finite over $\mathcal{A}_{\rho_0}^n$ (by Lemma 3.5.(2)), the $\sigma$-additivity can be
obtained by showing that $\lim_n \mathbb{P}_{\rho_0}^{\eta, \theta}(B_n) = 0$ for all sequences $(B_n)_n$ of elements of $\mathcal{A}_{\rho_0}$ such that $B_0 \supseteq B_1 \supseteq \dots$ and $\bigcap_n B_n = \emptyset$ (by [KSK76]). Let $(B_n)_n$ be such a sequence. Without loss of generality, we suppose that for every $n$, $B_n \in \mathcal{A}_{\rho_0}^n$ (otherwise, all $B_n$ are in a fixed $\mathcal{A}_{\rho_0}^{n_0}$ and Lemma A.1 allows us to conclude).

To easily write the limit of probabilities of $B_n$, we begin by proving that all $B_n$ are generated by an unique cylinder where paths follow the same prefix. By [KSK76, Lemma 3.3], we know that if $\lim_n \mathbb{P}_{\rho_0}^{\eta, \theta}(B_n) > 0$, then there exists a sequence of cylinders $(\text{Cyl}_n)_n$ such that for all $n$, $\text{Cyl}_n \subseteq B_n$ and $\text{Cyl}_{n+1} \subseteq \text{Cyl}_n$. In other words, we can suppose, without loss of generality, that there exists a maximal path $\pi$ such that $B_n = \bigsqcup_{j=0}^{m_n} \text{Cyl}_{\rho_0}(\pi_n, C_n^j)$ where $\pi_n = \delta_1 \cdots \delta_n$ is the prefix of $\pi$ of length $n$, $(C_n^j)_j$ is a sequence of constraints for $\pi_n$ and $m_n$ the finite number of cylinders of $B_n$ (since $B_n \in \mathcal{A}_{\rho_0}^n$). Otherwise when $\mathbb{P}_{\rho_0}^{\eta, \theta}$ is not a measure on $\mathcal{A}_{\rho_0}$, such a sequence suffices to prove it. In particular, $B_n = \text{Cyl}_{\rho_0}(\pi_n, C_n)$ where $C_n = \bigsqcup_{j=0}^{m_n} C_n^j$ (which is a Lebesgue-measurable set of $\mathbb{R}^n$ since each $C_n^j$ is). Moreover, with the same reasoning than in previous lemma and by letting $\chi_Y$ the characteristic function of the set $Y$, $\mathbb{P}_{\rho_0}^{\eta, \theta}(B_n)$ is equal to

$$ \int_{I(\rho_0, \delta_1)} \xi_{\Delta}(\rho_0)(\delta_1) \times \int_{I(\rho_0[\delta_1, t_1], \delta_2)} \xi_{\Delta}(\rho_0[\delta_1, t_1])(\delta_2) \cdots \\ \int_{I(\rho_0[\delta_1, t_1] \cdots [\delta_{n-1}, t_{n-1}], \delta_n)} \xi_{\Delta}(\rho_0[\delta_1, t_1] \cdots [\delta_{n-1}, t_{n-1}])(\delta_n) \times \chi_{B_n}(\rho_0[\delta_1, t_1] \cdots [\delta_n, t_n]) \\ d\xi_{\mathbb{R}^+}(\rho_0[\delta_1, t_1] \cdots [\delta_{n-1}, t_{n-1}], \delta_n)(t_n) \cdots d\xi_{\mathbb{R}^+}(\rho_0[\delta_1, t_1], \delta_2)(t_2) d\xi_{\mathbb{R}^+}(\rho_0, \delta_1)(t_1). $$

Now, to prove that the limit of probabilities is equal to 0, we will prove that there exists $i \in \mathbb{N}$ such that $B_i = \emptyset$ (more precisely, $C_i = \emptyset$) from the hypothesis of $\bigcap_n B_n = \emptyset$. For all $i > 0$, we let $p_i: \mathbb{R}_{\ge 0}^{i+1} \to \mathbb{R}_{\ge 0}^i$ be the continuous (for product topologies) projection over the $i$ first components of a constraint in $\mathbb{R}_{\ge 0}^{i+1}$. For all $i < n$, we can define the constraint for the $i$ first steps by induction along $C_n$ such that $C_n^i = p_i(C_n^{i+1})$. Moreover, since $B_{n+1} \subseteq B_n$ and all sets follows the same prefix, we have for all $i \le n$ that $C_{n+1}^i \subseteq C_n^i$. In particular, for some fixed $i$, the sequence $(C_n^i)_n$ decreases, thus it converges to $C^i \subseteq \mathbb{R}_{\ge 0}^i$. Now, we want to prove that there exists $i > 0$ such that $C^i = \emptyset$. To do so, we reason by contradiction and we suppose that for all $i$, $C^i \ne \emptyset$, and we want to define a play where its delays are in $\cap_i C^i$. To define this play, we define, by induction on $i$, a sequence of delays that satisfies $C^i$: for all $i$ if we have a sequence of delays $(t_i)_i$ that satisfies $C^i$ (for all $i$), then since $C^i = p_i(C^{i+1})$ (by continuity of $p_i$), there exists $t_{i+1}$ such that $(t_1, \dots, t_i, t_{i+1})$ satisfies $C^{i+1}$ (with $(t_1, \dots, t_i)$ satisfying $C^i$). This sequence of delays define a play $\rho \in \cap_i \text{Cyl}_{\rho_0}(\pi_i, C^i) = \cap_i B_i$. However, by hypothesis on $(B_n)_n$, $\cap_i B_i = \emptyset$, thus, we obtain a contradiction and there exists $i$ such that $C^i = 0$, i.e. $B_i = \emptyset$.

To conclude about the $\sigma$-additivity, we prove that $\lim_n \mathbb{P}_{\rho_0}^{\eta, \theta}(B_n) = 0$. We let $B_i$ be the subset such that $B_i = \emptyset$, and for all $n \ge i$, by letting $\chi_Y$ the characteristic function of the
set Y, $\mathbb{P}_{\rho_0}^{\eta, \theta}(B_n)$ is equal to

$$ 
\begin{aligned}
& \int_{I(\rho_0, \delta_1)} \xi_{\Delta}(\rho_0)(\delta_1) \times \int_{I(\rho_0[\delta_1, t_1], \delta_2)} \xi_{\Delta}(\rho_0[\delta_1, t_1])(\delta_2) \cdots \\
& \qquad \int_{I(\rho_0[\delta_1, t_1] \cdots [\delta_{n-1}, t_{n-1}], \delta_n)} \xi_{\Delta}(\rho_0[\delta_1, t_1] \cdots [\delta_{n-1}, t_{n-1}])(\delta_n) \times \chi_{B_n}(\rho_0[\delta_1, t_1] \cdots [\delta_n, t_n]) \\
& \qquad d\xi_{\mathbb{R}^+}(\rho_0[\delta_1, t_1] \cdots [\delta_{n-1}, t_{n-1}], \delta_n)(t_n) \cdots d\xi_{\mathbb{R}^+}(\rho_0[\delta_1, t_1], \delta_2)(t_2) d\xi_{\mathbb{R}^+}(\rho_0, \delta_1)(t_1).
\end{aligned}
$$

In particular, since $i \le n$, by restricting the probability to the $i$ first components, $\mathbb{P}_{\rho_0}^{\eta, \theta}(B_n)$ is bound by

$$ 
\begin{aligned}
& \int_{I(\rho_0, \delta_1)} \xi_{\Delta}(\rho_0)(\delta_1) \times \int_{I(\rho_0[\delta_1, t_1], \delta_2)} \xi_{\Delta}(\rho_0[\delta_1, t_1])(\delta_2) \cdots \\
& \qquad \int_{I(\rho_0[\delta_1, t_1] \cdots [\delta_{i-1}, t_{i-1}], \delta_i)} \xi_{\Delta}(\rho_0[\delta_1, t_1] \cdots [\delta_{i-1}, t_{i-1}])(\delta_i) \times \chi_{B_i}(\rho_0[\delta_1, t_1] \cdots [\delta_i, t_i]) \\
& \qquad d\xi_{\mathbb{R}^+}(\rho_0[\delta_1, t_1] \cdots [\delta_{i-1}, t_{i-1}], \delta_i)(t_i) \cdots d\xi_{\mathbb{R}^+}(\rho_0[\delta_1, t_1], \delta_2)(t_2) d\xi_{\mathbb{R}^+}(\rho_0, \delta_1)(t_1).
\end{aligned}
$$

By dominated convergence (since $\chi_{B_i} \le 1$), we obtain that $\lim_n \mathbb{P}_{\rho_0}^{\eta, \theta}(B_n)$ is bound by

$$ 
\begin{aligned}
& \int_{I(\rho_0, \delta_1)} \xi_{\Delta}(\rho_0)(\delta_1) \times \int_{I(\rho_0[\delta_1, t_1], \delta_2)} \xi_{\Delta}(\rho_0[\delta_1, t_1])(\delta_2) \cdots \\
& \qquad \int_{I(\rho_0[\delta_1, t_1] \cdots [\delta_{i-1}, t_{i-1}], \delta_n)} \xi_{\Delta}(\rho_0[\delta_1, t_1] \cdots [\delta_{i-1}, t_{i-1}])(\delta_i) \times \lim_{n} \chi_{B_n}(\rho_0[\delta_1, t_1] \cdots [\delta_i, t_i]) \\
& \qquad d\xi_{\mathbb{R}^+}(\rho_0[\delta_1, t_1] \cdots [\delta_{i-1}, t_{i-1}], \delta_i)(t_i) \cdots d\xi_{\mathbb{R}^+}(\rho_0[\delta_1, t_1], \delta_2)(t_2) d\xi_{\mathbb{R}^+}(\rho_0, \delta_1)(t_1).
\end{aligned}
$$

Now, since the sequence $(B_n)_n$ decreases, we know that for all $n \ge i$, $B_n = \emptyset$. Thus, $\lim_n \chi_{B_n}(\rho_0[\delta_1, t_1] \cdots [\delta_i, t_i]) = 0$, and we deduce that $\lim_n \mathbb{P}_{\rho_0}^{\eta, \theta}(B_n) = 0$.

Finally, we conclude the proof by proving that $\mathbb{P}_{\rho_0}^{\eta, \theta}(\text{Plays}_{\rho_0}^{\eta, \theta}) = 1$. To do that, we remark that $\mathcal{A}_{\rho_0}^0 = (\text{Plays}_{\rho_0}^{\eta, \theta}, \text{Cyl}_{\rho_0}(\pi_0))$, i.e. $\text{Plays}_{\rho_0}^{\eta, \theta} = \text{Cyl}_{\rho_0}(\pi_0)$ where $\rho_0$ follows $\pi_0$. Thus, since $\rho_0$ follows $\pi_0$, $\text{Cyl}_{\rho_0}(\pi_0) \ne \emptyset$, and by definitions, we obtain that

$$ \mathbb{P}_{\rho_0}^{\eta, \theta}(\text{Plays}_{\rho_0}^{\eta, \theta}) = \mathbb{P}_{\rho_0}^{\eta, \theta}(\pi_0) = 1. \quad \square $$

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

Finally, we conclude the proof of Proposition 3.6 by using the following theorem.

**Theorem A.3 (Carathéodory's extension theorem).** Let $S$ be a set, and $\nu$ be a $\sigma$-finite measure defined on an algebra $A \subseteq 2^S$. Then, $\nu$ can be extended in a unique manner to the $\sigma$-algebra generated by $A$.

**Proof of Proposition 3.6.** We apply Theorem A.3 to the set $S = \text{Plays}_{\rho_0}^{\eta, \theta}$, $A = \mathcal{A}_{\rho_0}$, and $\nu = \mathbb{P}_{\rho_0}^{\eta, \theta}$ which is a $\sigma$-finite measure on $\mathcal{A}_{\rho_0}$ (by Lemma A.2). Hence, there is a unique extension of $\mathbb{P}_{\rho_0}^{\eta, \theta}$ on the $\sigma$-algebra generated by the cylinders which is a probability measure over maximal plays. $\square$

<figure><img src="image_20.png" /></figure>
<figure><img src="image_21.png" /><figcaption>Figure 12: A WTG where Min has a non-proper (smooth) deterministic strategy that reaches the target with probability 1 against all (stochastic) strategies for Max.</figcaption></figure>

## APPENDIX B. A (NON-PROPER) SMOOTH DETERMINISTIC STRATEGY OF Min WITH AN INFINITE EXPECTED PAYOFF

We consider the WTG depicted in Figure 12, with $(\ell_0, 0)$ as initial configuration. We define a smooth deterministic strategy $\sigma$ that always chooses $(\delta_0, 0)$ from $\ell_0$, and chooses $i$ times $(\delta_2, 0)$ before $(\delta_3, 0)$ when $\ell_2$ is reached with a valuation $\nu \in [1 - \frac{1}{i}, 1 - \frac{1}{i+1})$. First, this strategy guarantees that all plays conforming to it reach a target location, even if the number of steps to do it depends on the first configuration reached in $\ell_2$.

Now, we consider $\theta \in \text{Strat}_{\text{Max}}$ defined such that, for all configurations $(\ell_1, \nu)$,

$$ \theta_{\Delta}(\ell_1, \nu) = \text{Dirac}_{\delta_1} \quad \text{and} \quad \theta_{\mathbb{R}^+}((\ell, \nu), \delta_1) = \mathcal{U}(\nu, 1) $$

where $\mathcal{U}(\nu, 1)$ is the uniform distribution over the open interval $(\nu, 1)$, and we compute $\mathbb{E}_{\ell_0, 0}^{\sigma, \theta}$. By Lemma 3.14, we have

$$ \begin{aligned} \mathbb{E}_{\ell_0, 0}^{\sigma, \theta} &= \sum_{\pi \in \text{TPaths}_{\ell_0, 0}} \mathbb{E}_{\ell_0, 0}^{\sigma, \theta}(\pi) = \sum_n \sum_{\pi \in \text{TPaths}_{\ell_0, 0}^{n+2}} \mathbb{E}_{\ell_0, 0}^{\sigma, \theta}(\pi) \\ &= \sum_n \sum_{\pi \in \text{TPaths}_{\ell_0, 0}^{n+2}} \mathbb{E}_{(\ell_0, 0)][\delta_0, 0]}^{\sigma, \theta}(\pi) \quad (\text{by definition of } \sigma) \\ &= \sum_n \sum_{\pi \in \text{TPaths}_{\ell_0, 0}^{n+2}} \int_0^1 \mathbb{E}_{(\ell_0, 0)[\delta_0, 0][\delta_1, t]}^{\sigma, \theta}(\pi) d\eta_{\mathbb{R}^+}((\ell_1, 0), \delta_1)(t) \quad (\text{by definition of } \theta). \end{aligned} $$

Now, since $\sigma$ is a deterministic strategy, for all $n$, there exists only one path $\pi_n \in \text{TPaths}_{\ell_0, 0}^{n+2}$. In particular, we obtain that

$$ \mathbb{E}_{\ell_0, 0}^{\sigma, \theta} = \sum_n \int_0^1 \mathbb{E}_{(\ell_0, 0)[\delta_0, 0][\delta_1, t]}^{\sigma, \theta}(\pi_n) d\eta_{\mathbb{R}^+}((\ell_1, 0), \delta_1)(t). $$

By definition of $\sigma$, we know that $\pi_n$ is conforming to $\sigma$ only when $t \in [1 - \frac{1}{n}, 1 - \frac{1}{n+1})$, i.e.

$$ \mathbb{E}_{(\ell_0, 0)[\delta_0, 0][\delta_1, t]}^{\sigma, \theta}(\pi_n) = n \times \chi_{[1 - \frac{1}{n}, 1 - \frac{1}{n+1})}(t). $$

Since $\eta_{\mathbb{R}^+}((\ell_1, 0), \delta_1)$ follows a uniform distribution over $(0, 1)$, we deduce that

$$ \mathbb{E}_{\ell_0, 0}^{\sigma, \theta} = \sum_n n \int_{\frac{n-1}{n}}^{\frac{n}{n+1}} dt = \sum_n \frac{n}{n(n+1)} = +\infty. $$
APPENDIX C. PROBABILITIES UNDER A PROPER STRATEGY FOR Min

**Lemma 3.10.** Let $\eta \in \text{Strat}_{\text{Min}}^{\mathbb{P}}$ be a strategy of Min satisfying the second condition of Hypothesis 3.9 for the bounds $\alpha$ and $m$. Let $\theta \in \text{Strat}_{\text{Max}}$ be a strategy of Max and $\rho_0 \in \text{FPlays}$ be a finite play following a finite path $\pi_0$. For all $n$, we have

$$ \sum_{\pi \in \text{TPaths}_{\rho_0}^{n}} \mathbb{P}_{\rho_0}^{\eta, \theta}(\pi_0 \pi) \le (1 - \alpha)^{\lfloor n/m \rfloor}. $$

We proceed by induction, showing first that for all $n \in \mathbb{N}$ and all finite plays $\rho_0$ following $\pi_0$,

$$ \sum_{\pi \in \text{TPaths}_{\rho_0}^{nm}} \mathbb{P}_{\rho_0}^{\eta, \theta}(\pi_0 \pi) \le (1 - \alpha)^n. $$

For $n = 0$, the property holds since $(1 - \alpha)^0 = 1$. Otherwise, suppose that the property holds for $n$, and we prove it for $n + 1$ by decomposing the sum as

$$ \sum_{\pi \in \text{TPaths}_{\rho_0}^{(n+1)m}} \mathbb{P}_{\rho_0}^{\eta, \theta}(\pi_0 \pi) = \sum_{\delta_0} \sum_{\delta_1} \cdots \sum_{\delta_{m-1}} \sum_{\pi \in \text{TPaths}_{\rho_0}^{nm}} \mathbb{P}_{\rho_0}^{\eta, \theta}(\pi_0 \delta_0 \delta_1 \cdots \delta_{m-1} \pi). \quad (C.1) $$

For a fixed $\delta_0 \cdots \delta_{m-1} \pi \in \text{TPaths}_{\rho_0}^{(n+1)m}$, letting $\pi' = \pi_0 \delta_0 \delta_1 \cdots \delta_{m-1} \pi$, we can unravel the $m$ first steps of the definition of $\mathbb{P}_{\rho_0}^{\eta, \theta}(\pi')$. Letting $\xi_i$ denote the strategy $\eta$ or $\theta$ depending if the source location of the transition $\delta_i$ belongs to Min or Max, we can write $\mathbb{P}_{\rho_0}^{\eta, \theta}(\pi')$ under the form:

$$ \int_{I(\rho_0, \delta_0)} \cdots \int_{I(\rho_0[\delta_0, t_0] \cdots [\delta_{m-1}, t_{m-1}])} \xi_{\Delta}^{0}(\rho_0)(\delta_0) \cdots \xi_{\Delta}^{m-2}(\rho_0[\delta_0, t_0] \cdots [\delta_{m-1}, t_{m-2}]) (\delta_{m-1}) \mathbb{P}_{\rho_0[\delta_0, t_0] \cdots [\delta_{m-1}, t_{m-1}]}^{\eta, \theta}(\pi') \\ d\xi_{\mathbb{R}^+}^{m-1}(\rho_0[\delta_0, t_0] \cdots [\delta_{m-2}, t_{m-2}], \delta_{m-1}) (t_{m-1}) \cdots d\xi_{\mathbb{R}^+}^{0}(\rho_0, \delta_0)(t_0). $$

Thus, (C.1) can be rewritten as

$$ \sum_{\delta_0} \sum_{\delta_1} \cdots \sum_{\delta_{m-1}} \int_{I(\rho_0, \delta_0)} \int_{I(\rho_0[\delta_0, t_0])} \cdots \int_{I(\rho_0[\delta_0, t_0] \cdots [\delta_{m-1}, t_{m-1}])} \xi_{\Delta}^{0}(\rho_0)(\delta_0) \cdots \xi_{\Delta}^{m-1}(\rho_0[\delta_0, t_0] \cdots [\delta_{m-2}, t_{m-2}]) (\delta_{m-1}) \\ \sum_{\pi \in \text{TPaths}_{\rho_0}^{nm}} \mathbb{P}_{\rho_0[\delta_0, t_0] \cdots [\delta_{m-1}, t_{m-1}]}^{\eta, \theta}(\pi_0 \delta_0 \delta_1 \cdots \delta_{m-1} \pi) \\ d\xi_{\mathbb{R}^+}^{m-1}(\rho_0[\delta_0, t_0] \cdots [\delta_{m-2}, t_{m-2}], \delta_{m-1}) (t_{m-1}) \cdots d\xi_{\mathbb{R}^+}(\rho_0, \delta_0)(t_0). $$

By induction hypothesis,

$$ \sum_{\pi \in \text{TPaths}_{\rho_0}^{nm}} \mathbb{P}_{\rho_0[\delta_0, t_0] \cdots [\delta_{m-1}, t_{m-1}]}^{\eta, \theta}(\pi_0 \delta_0 \delta_1 \cdots \delta_{m-1} \pi) \le (1 - \alpha)^n $$
so that $\sum_{\pi \in \mathcal{TPaths}_{\rho_0}^{(n+1)m}} \mathbb{P}_{\rho_0}^{\eta, \theta}(\pi_0 \delta_0 \delta_1 \cdots \delta_{m-1} \pi)$ can be bounded by

$$ (1 - \alpha)^n \sum_{\delta_0} \sum_{\delta_1} \cdots \sum_{\delta_{m-1}} \int_{I(\rho_0, \delta_0)} \cdots \int_{I(\rho_0[\delta_0, t_0] \cdots [\delta_{m-1}, t_{m-1}])} \\ \xi_{\Delta}^0(\rho_0)(\delta_0) \cdots \xi_{\Delta}^{m-1}(\rho_0[\delta_0, t_0] \cdots [\delta_{m-2}, t_{m-2}]) (\delta_{m-1}) \\ d\xi_{\mathbb{R}^+}^{m-1}(\rho_0[\delta_0, t_0] \cdots [\delta_{m-2}, t_{m-2}], \delta_{m-1}) (t_{m-1}) \cdots d\xi_{\mathbb{R}^+}^0(\rho_0, \delta_0)(t_0) $$

that is $(1 - \alpha)^n$ multiplied by the probability of all paths that can continue after $\rho$ for at least $m$ steps without having reached the target set $L_T$, i.e. by the second item of Hypothesis 3.9

$$ (1 - \alpha)^n \mathbb{P}_{\rho_0}^{\eta, \theta} \left( \bigcup_{n \ge m} \mathcal{TPlays}_{\rho_0}^n \right) \le (1 - \alpha)^n (1 - \alpha). $$

This concludes the induction proof. To conclude, we simply need to consider paths of length that is not a multiple of $m$: we thus unravel similarly the first $k \in (0, m)$ transitions, bounding all their probabilities by 1.

## APPENDIX D. CYLINDERS DECOMPOSITION FOR THE SET OF PLAYS CONFORMING TO $\eta^p$

We want to justify why the set of delays that appears in a path $\pi$ of $S_{\rho_0}^k$, $C_\pi$ is a constraint, i.e. is a finite union and intersection of the constraints in $\eta_{\mathbb{R}^+}^p$ and $\theta_{\mathbb{R}^+}$.

Let consider a finite path $\pi = \rho_0 \delta_0 \cdots \delta_k$ that appears in $S_{\rho_0}^k$, i.e. that contains a transition chosen by $\eta^p$ with probability $p$. A play following $\pi$ and conforming to $\eta^p$ and $\theta$ must satisfy certain constraints over each transition. If $\delta_k$ belongs to Min, then the set of delays such that $\rho_0[\delta_0, t_0] \cdots [\delta_{k-1}, t_{k-1}]$ satisfies a (Lebesgue-measurable) constraint $C_{\delta_k}$ given by Hypothesis 3.3 over $\eta^p$ (as the inverse image of the strategy applying on $\rho_0[\delta_0, t_0] \cdots [\delta_{k-1}, t_{k-1}$]). The case where $\delta_k$ belongs to Max is analogous. Now, let $\delta_i$ with $0 \le i \le k$ belongs to Min with the constraint $C_{\delta_{i+1} \cdots \delta_k}$. The constraint $C_{\delta_i \cdots \delta_k}$ is given by the inverse image of $\eta^p$ on $\rho_0[\delta_0, t_0] \cdots [\delta_{i-i}, t_{i-1}]$ (that gives a measurable set of delay) and the intersection with $C_{\delta_{i+1} \cdots \delta_k}$ (we consider only delays that satisfying the next constraints). Thus, by induction, we can define the constraint $C_\pi$ by a finite (since $\pi$ is finite) intersection of the constraints in $\eta_{\mathbb{R}^+}^p$ and $\theta_{\mathbb{R}^+}$ (that are measurable by Hypothesis 3.3).

To conclude, we remark that in $\pi$, we need to choose the position of the transition $p$ (when $\sigma_1$ and $\sigma_2$ choose the same transition). In particular, there exists at most $k$ available possible positions, and $C_{\delta_k}$ is given by the finite union over all possible positions.