3.4.1. On the choice of the set $S_1 = \{ V_0 > \phi \} \cup \{ \phi = \psi \}$ .

In the above algorithm, we may have $S_\infty \neq \{ V = \phi \}$ , but it is always true that $D_\infty \cup \{ \phi = \psi\} = \{ V = \psi \}$ . If we want to recover the set $\{ V = \phi \}$ , the set $S_1$ in (3.4) should be replaced by the set $\widetilde S_1 \,:\!=\, \{ V_0 \geq \phi \}$ and then we follow the steps in the previous section to obtain a new decreasing sequence $(\widetilde V_k)_{k\geq 1}$ . The proofs of previous results remain unchanged. Observe that $S_1 \subset \widetilde S_1$ and in fact $\widetilde S_1 \setminus S_1 = \{ V_0 = \phi \} \cap \{ \phi > \psi \}$ . In particular, if $\{ V_0 =\phi \} = \emptyset$ then $S_1 = \widetilde S_1$ , and the procedure yields the same sequence $(V_k)_{k \geq 1}$ . More precisely, we have the following result.

Proof. Items (i) and (ii) are straightforward from construction and from the proofs in the previous subsection, so we only prove the last three by induction. Consider the function $\widetilde V_1$ , and we know that $\widetilde V_1\leq V_0 \wedge \phi$ . Now $\widetilde V_1 = \phi$ on $\widetilde S_1$ and $\widetilde V_1 \leq V_0 < \phi$ outside $\widetilde S_1$ , and thus (iii) is true for $k = 1$ . Suppose this is true for some $k \geq 1$ ; we prove it is also true for $k+1$ . Indeed, set

\begin{align*}\Delta \,:\!=\, \inf\{t \geq 0\,:\, X_t \notin \widetilde S_{k} \setminus \widetilde S_{k+1} \}, \end{align*}

and observe that for all $x \in \widetilde S_{k} \setminus \widetilde S_{k+1} $ ,

\begin{align*} \widetilde \tau_{k+1} \wedge \widetilde \gamma_{k+1} = h(\widetilde D_{k+1} \cup \widetilde S_{k+1} ) \geq h( (\widetilde S_k)^c \cup \widetilde S_{k+1}) = \Delta >0 \quad \text{$\mathbb P_x$-a.s.} \end{align*}

because $\widetilde D_{k+1} \subset \widetilde D_k \subset (\widetilde S_k)^c$ (recall that $\widetilde D_k$ and $\widetilde S_k$ are disjoint). Using Lemma 2.1 and the fact that $\widetilde V_{k+1} \leq \widetilde V_k$ , we have for all $x \in \widetilde S_{k} \setminus \widetilde S_{k+1} $ ,

\begin{align*}\widetilde V_{k+1}(x) = R_x(\widetilde \tau_{k+1}, \widetilde \gamma_{k+1}) &= {\mathbb{E}}_x\bigl[\mathrm{e}^{-\beta (\widetilde \tau_{k+1} \wedge \widetilde \gamma_{k+1})}\widetilde V_{k+1}\bigl(X_{\widetilde \tau_{k+1} \wedge \widetilde \gamma_{k+1}}\bigr)\bigr] \\&= {\mathbb{E}}_x[\mathrm{e}^{-\beta \Delta }\widetilde V_{k+1}(X_{\Delta})] \\&\leq {\mathbb{E}}_x[\mathrm{e}^{-\beta \Delta }\widetilde V_k(X_{\Delta})] \\&= V_k(x) + {\mathbb{E}}_x \biggl[ \int^{\Delta} _{0} \mathrm{e}^{-\beta s}( \mathcal{Q}[V_k](X_s) - \beta V_k(X_s) ) \,{\mathrm{d}} s \biggr] \\&< V_k(x) \\&\leq \phi(x) \end{align*}

because $ \mathcal{Q}[V_k] - \beta V_k < 0$ on $ \widetilde S_{k} \setminus \widetilde S_{k+1}$ . But $ \widetilde V_{k+1} \leq \widetilde V_k < \phi$ outside $\widetilde S_k$ and thus $\widetilde V_{k+1} < \phi$ outside $\widetilde S_{k+1}$ . Passing this to the limit, we get $\widetilde V_\infty < \phi$ outside $\widetilde S_\infty$ . Now (iv) follows from (iii) and an analogue of Theorem 3.4(ii). Finally, for (v), since $\widetilde V_\infty > \psi $ outside $\widetilde D_\infty \cup \widetilde S_\infty$ , it is not hard to see that $\widetilde S_\infty = \{ V = \phi \}$ .

Although it is rare in practice to encounter the case $\{ V_0 \geq \phi \} \neq \{ V_0 > \phi \}$ , the inclusion $S_1 \subset \widetilde S_1$ guarantees that $S_k \subset \widetilde S_k$ for all $k \in \mathbb N$ (see Proposition 3.3 below). As a result, initializing the algorithm with $S_1$ is expected to lead to faster convergence compared to initialization with $\widetilde S_1$ . For example, consider the case where $\phi > \psi$ and $|S_1| = 1$ while $|\widetilde S_1 |$ is 100 or more. In this case, initializing with $S_1$ would require only one iteration (as $S_2$ would be either empty or equal to $S_1$ ), making it evidently more efficient. Moreover, the two approaches may lead to different sets $S_\infty$ and $\widetilde S_\infty$ when $S_1 \neq \widetilde S_1$ , potentially resulting in multiple NE. Examples illustrating both $S_\infty = \widetilde S_\infty$ and $S_\infty \neq \widetilde S_\infty$ are given in Section 4.3. If our primary goal is to compute the value function V, initializing with $S_1$ consistently yields a faster and more efficient algorithm. If our goal is to recover the critical sets $\{ V =\psi \}$ and $\{ V = \phi \}$ , then initializing with $\widetilde S_1$ is recommended. Alternatively, we can initialize with $S_1$ , compute V, and then check which $x \in E$ such that $V(x) = \phi(x)$ .

The proof of Proposition 3.3 is a consequence of the following lemmas.

Proof. For $n=1$ , recall that $\widetilde \tau^{(1)}_1 = h\bigl(\widetilde D^{(1)}_1\bigr) $ , $\tau^{(1)}_1 = h\bigl(D^{(1)}_1\bigr) $ , $\gamma_1 = h(S_1)$ , and $\widetilde \gamma_1 = h(\widetilde S_1)$ , where

\[ \widetilde D^{(1)}_1 = \{\mathcal{Q}[\psi] -\beta \psi \leq 0 \} \setminus \widetilde S_1 \subset \{\mathcal{Q}[\psi] -\beta \psi \leq 0 \} \setminus S_1 = D^{(1)}_1,\]

and that

\[V^{(1)}_1(x) = R_x \bigl(\tau^{(1)}_1, \gamma_1\bigr), \quad \widetilde V^{(1)}_1(x) = R_x \bigl(\widetilde \tau^{(1)}_1, \widetilde \gamma_1\bigr)\quad {\text{{for all}}\ } x \in E.\]

We are going to prove that $\widetilde V^{(1)}_1 \geq V^{(1)}_1$ . Indeed, for $y \in \widetilde S_1$ , we have $\widetilde V^{(1)}_1(y) = \phi(y) \geq V^{(1)}_1(y)$ , while for $ x \in \widetilde D^{(1)}_1$ , we have $V^{(1)}_1(x) = \psi(x) = \widetilde V^{(1)}_1(x)$ . It remains to prove $\widetilde V^{(1)}_1 \geq V^{(1)}_1$ outside the set $\widetilde D^{(1)}_1 \cup \widetilde S_1 = D^{(1)}_1 \cup \widetilde S_1$ (and so $ \widetilde \tau^{(1)}_1 \wedge \widetilde \gamma_1 = \tau^{(1)}_1 \wedge \widetilde \gamma_1 $ ). Consider one $x \notin D^{(1)}_1 \cup \widetilde S_1$ . Then applying Lemma 2.1 yields

\begin{align*}\widetilde V^{(1)}_1(x) &= {\mathbb{E}}_x\bigl[ \mathrm{e}^{-\beta ( \widetilde \tau^{(1)}_1 \wedge \widetilde \gamma_1) } \widetilde V^{(1)}_1\bigl(X_{\widetilde \tau^{(1)}_1 \wedge \widetilde \gamma_1}\bigr) \bigr] \\&= {\mathbb{E}}_x\bigl[ \mathrm{e}^{-\beta ( \tau^{(1)}_1 \wedge \widetilde \gamma_1) } \widetilde V^{(1)}_1\bigl(X_{ \tau^{(1)}_1 \wedge \widetilde \gamma_1}\bigr) \bigr] \\&\geq {\mathbb{E}}_x\bigl[ \mathrm{e}^{-\beta ( \tau^{(1)}_1 \wedge \widetilde \gamma_1) } V^{(1)}_1\bigl(X_{\tau^{(1)}_1 \wedge \widetilde \gamma_1}\bigr) \bigr] \quad \text{(since $ \widetilde V^{(1)}_1 \geq V^{(1)}_1$ on $ D^{(1)}_1 \cup \widetilde S_1 $)}\\&= V^{(1)}_1(x) + {\mathbb{E}}_x \biggl[ \int^{\tau^{(1)}_1 \wedge \widetilde \gamma_1}_0 \mathrm{e}^{-\beta u} \bigl( \mathcal{Q}\bigl[V^{(1)}_1\bigr](X_u) - \beta V^{(1)}_1 (X_u)\bigr) \,{\mathrm{d}} u \biggr]\\&= V^{(1)}_1(x)\end{align*}

because $ \mathcal{Q}\bigl[V^{(1)}_1\bigr] - \beta V^{(1)}_1 = 0$ outside $ D^{(1)}_1 \cup S_1 \subset D^{(1)}_1 \cup \widetilde S_1 $ . This ends the proof that $\widetilde V^{(1)}_1 \geq V^{(1)}_1$ .

Suppose that the claim of the lemma is true for n; we prove it is true for $n+1$ . First, recall

\[\widetilde D^{(n+1)}_1 = \bigl\{ \mathcal{Q}\bigl[\widetilde V^{(n)}_1\bigr] - \beta \widetilde V^{(n)}_1 \leq 0 \bigr\} \cap \widetilde D^{(n)}_1, \quad D^{(n+1)}_1 = \bigl\{ \mathcal{Q}\bigl[V^{(n)}_1\bigr] - \beta V^{(n)}_1 \leq 0 \bigr\} \cap D^{(n)}_1.\]

Let $x \in \widetilde D^{(n+1)}_1$ . Then $x \in \widetilde D^{(n)}_1 \subset D^{(n)}_1 $ and consequently $\widetilde V^{(n)}_1(x) = \psi(x) = V^{(n)}_1(x)$ . We also have

\begin{align*}0& \geq \mathcal{Q}\bigl[ \widetilde V^{(n)}_1\bigr](x) -\beta \widetilde V^{(n)}_1(x) \\&= \sum_{y \neq x} Q(x,y)\widetilde V^{(n)}_1(y) + (Q(x,x) -\beta) \widetilde V^{(n)}_1(x) \\&= \sum_{y \neq x} Q(x,y)\widetilde V^{(n)}_1(y) + (Q(x,x) -\beta) \psi(x) \\&\geq \sum_{y \neq x} Q(x,y)V^{(n)}_1(y) + (Q(x,x) -\beta) V^{(n)}_1(x) \\&= \mathcal{Q}\bigl[ V^{(n)}_1\bigr](x) -\beta V^{(n)}_1(x),\end{align*}

which shows

\[x \in \bigl\{ \mathcal{Q}\bigl[V^{(n)}_1\bigr] - \beta V^{(n)}_1 \leq 0 \bigr\},\]

and hence $\widetilde D^{(n+1)}_1 \subset D^{(n+1)}_1 $ . The proof of the inequality $\widetilde V_1^{(n+1)} \geq V_1^{(n+1)}$ follows similarly to the case $n=1$ . First consider $x \in D^{(n+1)}_1$ ; then

\[\widetilde V_1^{(n+1)} (x) \geq \psi(x) = V_1^{(n+1)}(x)\]

( $\widetilde V_1^{(n)} \geq \psi$ follows similarly in Lemma 3.2 and Proposition 3.2). If $x \in \widetilde S_1$ , then $ \widetilde V_1^{(n+1)} (x) = \phi(x) \geq V_1^{(n+1)} (x)$ . It remains to show that $\widetilde V_1^{(n+1)} \geq V_1^{(n+1)}$ outside $D^{(n+1)}_1 \cup \widetilde S_1$ . If $x \notin D^{(n+1)}_1 \cup \widetilde S_1$ , then we have

\[ \widetilde \tau^{(n+1)}_1 \wedge \widetilde \gamma_1 \geq \tau^{(n+1)}_1 \wedge \widetilde \gamma_1 \quad \text{$\mathbb P_x$-a.s.}\]

Applying Lemma 2.1 yields

\begin{align*}\widetilde V^{(n+1)}_1(x) &= {\mathbb{E}}_x\bigl[ \mathrm{e}^{-\beta ( \widetilde \tau^{(n+1)}_1 \wedge \widetilde \gamma_1) } \widetilde V^{(n+1)}_1\bigl(X_{\widetilde \tau^{(n+1)}_1 \wedge \widetilde \gamma_1}\bigr) \bigr] \\&= {\mathbb{E}}_x\bigl[ \mathrm{e}^{-\beta ( \tau^{(n+1)}_1 \wedge \widetilde \gamma_1) } \widetilde V^{(n+1)}_1\bigl(X_{ \tau^{(n+1)}_1 \wedge \widetilde \gamma_1}\bigr) \bigr] \\&\geq {\mathbb{E}}_x\bigl[ \mathrm{e}^{-\beta ( \tau^{(n+1)}_1 \wedge \widetilde \gamma_1) } V^{(n+1)}_1\bigl(X_{\tau^{(n+1)}_1 \wedge \widetilde \gamma_1}\bigr) \bigr] \quad \text{(since $ \widetilde V^{(n+1)}_1 \geq V^{(n+1)}_1$ on $ D^{(n+1)}_1 \cup \widetilde S_1 $)}\\&= V^{(n+1)}_1(x) + {\mathbb{E}}_x \biggl[ \int^{\tau^{(n+1)}_1 \wedge \widetilde \gamma_1}_0 \mathrm{e}^{-\beta u} \bigl( \mathcal{Q}\bigl[V^{(n+1)}_1\bigr](X_u) - \beta V^{(n+1)}_1 (X_u)\bigr) \,{\mathrm{d}} u \biggr]\\&= V^{(n+1)}_1(x)\end{align*}

because $ \mathcal{Q}\bigl[V^{(n+1)}_1\bigr] - \beta V^{(n+1)}_1 = 0$ outside $ D^{(n+1)}_1 \cup S_1 \subset D^{(n+1)}_1 \cup \widetilde S_1 $ . This establishes that $\widetilde V_1^{(n+1)} \geq V_1^{(n+1)}$ , thereby completing the induction step.

Therefore we have shown that $\widetilde V_1^{(n)} \geq V_1^{(n)}$ for all $n \in \mathbb N$ . Letting $n \rightarrow + \infty$ , we conclude that $\widetilde V_1 \geq V_1$ and $\widetilde D_1 \subset D_1$ .

Proof. We first recall that

\begin{align*}S_2 = \{\mathcal{Q}[V_1] -\beta V_1 \geq 0 \} \cap S_1, \quad \widetilde S_2 = \{\mathcal{Q}[\widetilde V_1] -\beta \widetilde V_1 \geq 0 \} \cap \widetilde S_1 .\end{align*}

Let $x \in S_2$ . Then $x \in S_1 \subset \widetilde S_1$ and hence $V_1(x) = \phi(x) = \widetilde V_1(x)$ . Also, we have

Therefore $x \in \{ \mathcal{Q}[\widetilde V_1] -\beta \widetilde V_1 \geq 0\}$ and the claim follows.

Proof of Proposition 3.3. The proof now follows by induction, using the same ideas and techniques as those employed in the preceding lemmas: first show that $\widetilde D_2 \subset D_2$ and $\widetilde V_2 \geq V_2$ , then proceed similarly for $k =3,4, \ldots$ .

3.4.2. A way to create examples that have many NE in the case $\{ V_0 > \phi \} \neq \emptyset$ .

In Theorem 3.6, we proved that $\widetilde V_\infty = V_\infty = V$ , so that

\begin{align*} R_x(\tau_\infty \wedge \tau_{\phi,\psi}, \gamma_\infty) = V_\infty (x) = \widetilde V_\infty(x) = R_x(\tau_\infty \wedge \tau_{\phi,\psi}, \widetilde \gamma_\infty)\quad {\text{{for all}}\ } x \in E, \end{align*}

and that the two pairs $ (\tau_\infty \wedge \tau_{\psi,\phi}, \gamma_\infty)$ and $(\tau_\infty \wedge \tau_{\psi,\phi}, \widetilde \gamma_\infty)$ are all NE. Note that $\widetilde \gamma_\infty \leq \gamma_\infty$ because $S_\infty \subset \widetilde S_\infty$ and the two stopping times are different when the inclusion is strict. Although we have examples where the inclusion $S_\infty \subset \widetilde S_\infty$ is strict, thus yielding multiple NE, one may still wonder whether there is a systematic way to construct other stopping times $\gamma$ that preserve the property that $(\tau_\infty \wedge \tau_{\psi,\phi}, \gamma)$ is an NE. In this subsection we aim to address this question. First, we provide an intuitive justification for the possibility of multiple NE, without invoking Theorem 3.6. Next we offer a constructive approach for demonstrating examples where more than one NE arises.

Let us begin with the first objective. For notational convenience, we set $D \,:\!=\, D_\infty$ and $S \,:\!=\, S_\infty \cap \{ \phi > \psi \}$ , and note that $D \cap S = \emptyset$ . We get

\begin{align*} V_\infty(x) = R_x(\tau_\infty \wedge \tau_{\phi,\psi}, \gamma_\infty) = R_x(h(D \cup \{ \phi = \psi\}), h(S \cup \{ \phi = \psi\}) )\quad {\text{{for all}}\ } x \in E.\end{align*}

From Theorem 3.5 we know $V_\infty \leq \phi$ , with $V_\infty = \phi$ on $S_\infty = S \cup \{ \phi = \psi \}$ and $V = \psi < \phi$ on D. However, outside the set $D \cup S \cup \{ \phi = \psi\}$ , no further information is available to determine whether the inequality $V_\infty \leq \phi$ is strict. Thus, perhaps there exists a non-empty set O, disjoint from $ D \cup S \cup \{ \phi = \psi\} $ , such that $V_\infty = \phi$ on O. If this is the case, we claim that the function

\begin{align*} V_O(x) \,:\!=\, R_x(h(D \cup \{ \phi = \psi\}), h(O \cup S \cup \{ \phi = \psi\}) )\quad {\text{{for all}}\ } x \in E\end{align*}

coincides with $V_\infty$ . Indeed, let $\Delta_1 \,:\!=\, h(D \cup \{ \phi = \psi\})$ and $ \Delta_2 \,:\!=\, h(O \cup S \cup \{ \phi = \psi\})$ ; then, ${\text{{for all}}\ } x \in E$ ,

\begin{align*} V_O(x) &= {\mathbb{E}}_x \bigl[\mathrm{e}^{-\beta \Delta_1} \psi(X_{\Delta_1}) \mathbf{1}_{\{\Delta_1 \leq \Delta_2\}} + \mathrm{e}^{-\beta \Delta_2} \phi(X_{\Delta_2}) \mathbf{1}_{\{\Delta_1 > \Delta_2\}} \bigr] \\&= {\mathbb{E}}_x \bigl[\mathrm{e}^{-\beta \Delta_1} V_\infty (X_{\Delta_1}) \mathbf{1}_{\{\Delta_1 \leq \Delta_2\}} + \mathrm{e}^{-\beta \Delta_2} V_\infty(X_{\Delta_2}) \mathbf{1}_{\{\Delta_1 > \Delta_2\}} \bigr] \\&= {\mathbb{E}}_x \bigl[\mathrm{e}^{-\beta (\Delta_1 \wedge \Delta_2)} V_\infty(X_{\Delta_1 \wedge \Delta_2}) \bigr] \\&= V_\infty(x) + {\mathbb{E}}_x\biggl[ \int^{\Delta_1 \wedge \Delta_2}_0 \mathrm{e}^{-\beta s} ( \mathcal{Q}[V_\infty](X_s) - \beta V_\infty(X_s)) \,{\mathrm{d}} s \biggr], \\&= V_\infty(x)\end{align*}

because $ \mathcal{Q}[V_\infty] - \beta V_\infty = 0$ outside $D \cup S \cup O \cup \{ \phi = \psi \}$ . Next we claim that any set O disjoint from $D \cup S \cup \{ \phi = \psi \}$ and satisfying $V_\infty(x) = \phi(x)$ for all $x \in O$ gives rise to an NE pair

\[(h(D \cup \{ \phi = \psi\}), h(O \cup S \cup \{ \phi = \psi\})).\]

At this point we emphasize that a pair of stopping times $(\tau,\gamma)$ may yield the correct value function, i.e. $V(x) = R_x(\tau,\gamma)$ , without necessarily forming an NE. To verify that the pair $(h(D \cup \{ \phi = \psi\}), h(O \cup S \cup \{ \phi = \psi\}) )$ does in fact constitute an NE, we observe

\begin{align*} R_x(h(D \cup \{ \phi = \psi\}), \gamma ) &\geq V_\infty(x) \\&= V_O(x) \\&= R_x(h(D \cup \{ \phi = \psi\}), h(O \cup S \cup \{ \phi = \psi\}) )\quad {\text{{for all}}\ } \gamma,\end{align*}

and from $\psi \leq V_\infty$ , $V_\infty = \phi$ on $O \cup S \cup \{ \phi = \psi \}$ , we use Dynkin’s formula to get

\begin{align*} R_x(\tau, O \cup S \cup \{ \phi = \psi\} ) &\leq V_\infty(x) + {\mathbb{E}}_x \biggl[\int^{\tau \wedge h(O\cup S \cup \{ \phi = \psi\})}_0 \mathrm{e}^{-\beta s}(\mathcal{Q}[V_\infty](X_s) - \beta V_\infty (X_s) ) \,{\mathrm{d}} s \biggr] \\ &\leq V_\infty(x) \\&= V_O(x)\quad {\text{{for all}}\ } \tau,\end{align*}

which shows the claim.

Now suppose that $ | \{ V =\phi \} \setminus S_\infty | \geq 1$ . (Note that $ \{ V =\phi \} = \widetilde S_\infty$ , but here we are intentionally disregarding the construction of $\widetilde S_\infty$ and Theorem 3.6.) If we take any non-empty subset $O \subset\{ V =\phi \} \setminus S_\infty$ , then, from the previous analysis, we get $V_O= V_\infty$ , and the pair

\[(h(D \cup \{ \phi = \psi\}), h(O \cup S \cup \{ \phi = \psi\}) ) \]

constitutes an NE. In particular, this demonstrates that there are multiple Nash equilibria in this case, thereby disproving the intuitive expectation that the NE might be unique.

Returning briefly to Theorem 3.6, suppose that

\[ | \{ V =\phi \} \setminus S_\infty | = |\widetilde S_\infty \setminus S_\infty | \geq 2.\]

Then we can, in fact, choose O such that $h(O \cup S \cup \{ \phi = \psi\}) $ differs from both $\gamma_\infty$ and $\widetilde \gamma_\infty$ . Indeed, if $ | \widetilde S_\infty \setminus S_\infty | \leq 1$ , then any subset $O \subset \widetilde S_\infty \setminus S_\infty$ is either empty or equal to $ \widetilde S_\infty \setminus S_\infty$ , in which case the resulting stopping time coincides with either $\gamma_\infty$ or $\widetilde \gamma_\infty$ , respectively.

The preceding discussion offers only an intuitive justification for the possibility of multiple NE without appealing to Theorem 3.6, as the existence of a set O satisfying the necessary conditions has remained a mystery until now. In general, it may happen that $S_\infty = \widetilde S_\infty$ even though $S_1 \neq \widetilde S_1$ . Consequently, no such O can exist. Therefore we need a more concrete method to construct examples with multiple NE without requiring knowledge of the set $\widetilde S_\infty \setminus S_\infty$ as discussed above. Such a construction is provided in the following proposition.

Proposition 3.4. Let V be the value function for the pair $(\psi,\phi)$ and let I be a subset of $ \{ \psi < V < \phi \}$ , where we assume that $ \{ \psi < V < \phi \} \neq \emptyset$ . We define the function $\phi_c$ by

\begin{align*} \phi_c(x) \,:\!=\, V(x)\quad {{{for\ all}}}\ x \in I\quad {and} \quad \phi_c(x) \,:\!=\, \phi(x)\quad {{{for\ all}}}\ x \notin I, \end{align*}

and let $V_c$ be the value function for the corresponding pair $(\psi, \phi_c)$ under the new expected payoff $R^c_x(\cdot,\cdot)$ (with $\phi$ replaced by $\phi_c$ in (1.1)). Then it holds that $V_c = V$ .

Consider the case $\phi > \psi$ . Applying Theorem 2.1, we can easily verify that both pairs $h(\{V =\psi \}), h( \{V= \phi \}))$ and $h(\{V =\psi \}), h( \{V= \phi \} \cup I))$ are NE for the game with functions $(\psi,\phi_c)$ . Also note that $\{V= \phi \} \cup I = \{V= \phi_c \}$ .

3.4.3. Computational aspects.

We discuss the computational aspects of our algorithm. By closely examining each iteration involved in computing a function $V_k$ , we always start with the set $D^{(1)}_k = \{ \mathcal{Q}[\psi] - \beta \psi \leq 0 \} \setminus S_k$ and iteratively shrink this set until no further reduction is possible (potentially resulting in an empty set). The number of steps required to compute $V_k$ is thus bounded above by the cardinality of the set $\{\mathcal{Q}[\psi] - \beta \psi \leq 0\}$ . To clarify, by ‘iteration’, we refer to the index k in the sequence $(V_k)_{k\geq 0}$ , while ‘steps’ refer to each update in the sequence $V_{k}^{(n)}$ for each $n=1,2,\ldots$ .

Additionally, the sequence $(S_k)_{k \geq 1}$ decreases from $S_1 = \{ V_0 > \phi \} \cup \{ \phi = \psi \}$ . Notably, by definition, the set $\{ \phi = \psi \}$ is always included in each member of this sequence. Therefore we are ‘only’ shrinking the set $\{ V_0 > \phi \}$ , which is disjoint from $\{ \phi = \psi \}$ . If we used $\widetilde S_1 = \{ V_0 \geq \phi \}$ instead, the set we shrink would be $ \widetilde S_1\setminus \{ \phi = \psi \} = \{ V \geq \phi > \psi \}$ . In total, if $\{V_0 > \phi \} \neq \emptyset$ , the total number of steps, summed over all iterations required to compute V, is bounded above by

\begin{align*} |\{\mathcal{Q}[\psi] - \beta \psi \leq 0 \} | \times (| \{ V_0 > \phi \} | +1 ) \leq |E|^2,\end{align*}

where $|{\cdot}|$ denotes the cardinality and $| \{ V_0 > \phi \} | +1$ is an upper bound for the number of iterations. The additional plus 1 in the above inequality arises from the need for at least $|\{\mathcal{Q}[\psi] - \beta \psi \leq 0 \} |$ iterations to compute $V_0$ and then check if $\{V_0 > \phi \} \neq \emptyset$ . For example, consider the case where $\phi$ is strictly greater than $\psi$ , i.e. $\{ \phi = \psi \} = \emptyset$ and $\{ V_0 > \phi \} = \{ x_0 \}$ for some $x_0 \in E$ . Then the function $V_1$ satisfies $\psi \leq V_1 \leq \phi$ and

\begin{align*} \mathcal{Q}[V_1](x) - \beta V_1(x) \leq 0 \quad {\text{{for all}}\ } x \in D_1,\quad \mathcal{Q}[V_1](x) - \beta V_1(x) = 0 \quad {\text{{for all}}\ } x \notin D_1 \cup \{ x_0 \}. \end{align*}

We claim the $V_1$ is the value function, i.e. $V_1 = V$ . To see this, observe that $\mathcal{Q}[V_1](x_0) - \beta V_1(x_0) > 0$ must hold. If this were not the case, then $V_1$ would be $\beta$ -excessive and dominate $\psi$ , which would in turn imply that $V_0 \leq V_1 \leq V_0$ (recall that $V_0$ is the smallest $\beta$ -excessive function dominating $\psi$ ), leading to the conclusion $V_0 = V_1$ . This is impossible because $V_0(x_0) > \phi(x_0) = V_1(x_0)$ . By applying Theorem 2.1, we conclude that $V = V_1$ . Therefore, in this case, less than $2 \times | \{ \mathcal{Q}[\psi] - \beta \psi \leq 0 \} | \leq 2 |E|$ steps are required to compute $V_1 = V$ .

Finally, the following result demonstrates that if the players choose the NE $(h(\{V = \psi\}), h(\{V = \phi\}))$ as their strategies, then the game always stops after a finite period of time by the sup-player, if not by the inf-player.

4.1.1. Subexample 1.1.

We first consider the first subexample, where the two functions $\psi$ and $\phi$ are given by

\begin{align*} \psi(x) = 10 + x/4 + 3 \cos(x) + 2 \sin (x/2) \quad \text{and} \quad \phi = \psi +3 \quad {\text{{for all}}\ } x \in \{0,\ldots,N-1 \}.\end{align*}

For the choice of

\[N = 50, \quad \beta = 0.1, \quad \lambda = 40, \quad r = 28, \]

we have the following evolution of functions given in Figure 1, where the algorithm stops after calculating $V_3 = V$ . Note that all the functions $(V_k)_{k \geq 0}$ lie between $\psi$ and $\phi$ , except for $V_0$ .

Figure 1.

The evolution of $(V_k)_{k\geq 0}$ (here $V_3 = V$ ).

Figure 1 Long description

A line graph showing the evolution of different value functions over time. The horizontal axis represents time, ranging from 0 to 49. The vertical axis represents the value, ranging from 7.5 to 27.5. The graph includes multiple lines representing different value functions: psi, phi, V 0, V 1, V 2, and V equals V bar. Each line shows the trend of the respective value function over time. The psi line fluctuates significantly, showing peaks and troughs. The phi line also fluctuates but generally stays above the psi line. The V 0 line shows a more stable trend with smaller fluctuations. The V 1 line follows a similar pattern to V 0 but with slightly different values. The V 2 line shows a trend that is somewhat between the psi and phi lines. The V equals V bar line represents the common value function and shows a trend that is generally between the psi and phi lines but with less fluctuation.

The evolution of $(D_k)_{k = 1,2,3}$ and $(S_k)_{k = 1 ,2 ,3}$ is given by

\begin{align*} D_1 &= \{31, 38, 44, 49\},\\ D_2 &= \{6, 7, 13, 18, 19, 25, 26, 31, 32, 38, 44, 49\}, \\ D_3 &= \{0, 6, 7, 13, 18, 19, 25, 26, 31, 32, 38, 44, 49\}, \\ S_1 &= \{0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 20, 21,\\ & \hspace{3cm} 22, 23, 24, 27, 28, 29, 33, 34, 35, 36, 40, 41, 46, 47, 48\}, \\ S_2 &= \{2, 3, 4, 9, 10, 11, 15, 16, 21, 22, 23, 28, 34, 35, 41, 47\}, \\ S_3 &= \{3, 9, 10, 16, 22, 23, 28, 34, 35, 41, 47\}.\end{align*}

4.1.2. Subexample 1.2.

In this subexample we keep all $N, \beta, \lambda$ and r as above and modify the function $\phi$ a little bit so that $\{ \phi = \psi \} \neq \emptyset$ :

\begin{align*} \phi(x) = \psi(x) + 4(\sin(x/5)+0.7)_+ \quad {\text{{for all}}\ } x \in \{0,\ldots,49\}.\end{align*}

Then the evolution of the $(V_k)_{k\geq 0}$ is given in Figure 2. Note that the sequence $(V_k)_{k\geq 0}$ still lies in the ‘sandwich’ $\psi \leq \phi$ , except for $V_0$ . The evolutions of $(D_k)_{k = 1,2,3,4}$ and $(S_k)_{k = 1 ,2 ,3,4}$ are then given by

\begin{align*} D_1 &= \{20, 21, 22, 23, 24, 27, 31, 38, 44, 49\}, \\ D_2 &= \{13, 18, 19, 20, 21, 22, 23, 24, 27, 31, 32, 38, 44, 49\} , \\ D_3 &= D_4 = \{6, 13, 18, 19, 20, 21, 22, 23, 24, 27, 31, 32, 38, 44, 49\},\\ S_1 &= \{0, 1, 2, 3, 4, 5, 8, 9, 10, 11, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23,\\ & \hspace{3cm} 24, 25, 26, 27, 28, 29, 30, 33, 34, 35, 46, 47, 48\} \\ S_2 &= \{0, 2, 3, 4, 9, 10, 15, 16, 17, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 34, 35, 47, 48\}, \\ S_3 &= \{3, 9, 10, 16, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 34, 35, 47, 48\}, \\ S_4 &= \{9, 10, 16, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 34, 35, 47, 48\}.\end{align*}

Figure 2.

The evolution of $(V_k)_{k\geq 0}$ (here $V_4=V$ ).

4.1.3. Subexample 1.3.

In this subexample we choose $N = 50, \beta = 0.05, \lambda = 14, r = 12$ . The functions $\psi$ and $\phi$ are defined by

\begin{align*} \psi(x) = (\!-25+x)_+, \quad \phi(x) = \psi(x) +5 \quad {\text{{for all}}\ } x \in \{ 0,1,\ldots,N-1\}\end{align*}

Figure 3 depicts the evolution of the sequence $(V_k)_{k\geq 0}$ ; the algorithm stops after computing $V_6=V$ . The evolutions of $(D_k)_{k = 1,2,3,4,5,6}$ and $(S_k)_{k = 1 ,2 ,3,4,5,6}$ in this case are given by

\begin{align*} D_k &=\{ 49\}, \quad k= 1,2,3,4,5,6, \\ S_1 &= \{0,1,2,\ldots,39\}, \\ S_k &= \{ 25,26,\ldots, 40 - k\}, \quad k = 2,3,4,5,6.\end{align*}

Figure 3.

The evolution of $(V_k)_{k\geq 0}$ (here $V_6 = V$ ).

4.2.1. Subexample 2.1.

Define the functions $\psi$ and $\phi$ as follows:

\begin{align*}\psi(x) = (x - N^2/2 )_+, \quad \phi(x) = \psi(x) + \delta \quad {\text{{for all}}\ } x = 0,1,\ldots,N^2-1, \end{align*}

where $\delta > 0$ is a fixed constant. Note that the closer to the line $y = N-1$ the process is (corresponding to the values near $N^2-1$ ), the bigger $\psi$ and $\phi$ get.

In what follows, we choose $N = 13$ , $\beta = 0.05$ , $r = 5$ , and $\delta = 8$ . The algorithm gives the following evolution of the sets $(D_k)_{k\geq 1}$ (in $\bullet$ ) and $(S_k)_{k \geq 1}$ (in $\blacksquare$ ) and stops after calculating $V_4$ . The evolutions of these stopping regions are illustrated in Figure 4. In view of functions on $\{0,1,\ldots,N^2-1\}$ , we can draw $\psi, \phi$ (in connected lines), $V_0$ and the value function V in one dimension in Figure 5.

Figure 4.

The evolution of stopping regions $(D_k,S_k)_{k= 1,2,3,4}$ from left to right.

Figure 5.

The functions $\psi, \phi, V_0, V$ on $\{0,1,\ldots,168\}$ ( $N = 13$ ).

4.2.2. Subexample 2.2.

We now consider a second subexample in which the function $\phi$ is slightly modified so that the set $\{\phi = \psi\} \neq \emptyset.$ Specifically, we set $\phi = 1.5\,\psi$ and increase the rate parameter to $r = 500$ and $\beta = 1$ . The evolution of the sets $(D_k, S_k)_{k \geq 1}$ is illustrated in Figure 6. The set $\{\phi = \psi\}$ is denoted by black triangles $\blacktriangle$ . The elements of $S_k \setminus \{\phi = \psi\}$ are represented by black squares ${\small\blacksquare}$ , so that $S_k$ is the union of the triangles and squares. Finally, the sets $D_k$ are depicted by filled circles $\bullet$ .

Figure 6.

The evolution of $(D_k,S_k)_{k\geq 1}$ .

The algorithm terminates after computing $V_4$ , which corresponds to the final value function.

In one dimension, we can view the evolution of $(V_k)_{k \geq 0}$ as in Figure 7. The function $V_3$ is omitted from the figure because its graph overlaps significantly with other curves, making it difficult to distinguish visually.

Figure 7.

The functions $\psi, \phi, V_0, V_1, V_2, V_4 = V$ on $\{0,1,\ldots,168\}$ ( $N = 13$ ).

4.3.1. The case when $\widetilde S_\infty = S_\infty$ .

In this subsection, $\psi$ is chosen such that

\begin{align*}\psi(0) =10, \quad \psi(1) =4, \quad \psi(2) =2, \quad \psi(3) =1.\end{align*}

We then compute $V_0$ and choose $\phi$ as follows:

\begin{alignat*}{7}V_0(0) &= 10, \quad & V_0(1) & = 6.8106 , \quad & V_0(2) & = 4.9834, \quad & V_0(3) & = 4.1528, \\\phi(0) &=12, \quad & \phi(1) & =8, \quad &\phi(2) & = V_0(2), \quad & \phi(3) & =1.\end{alignat*}

In this case, $S_1 = \{ 3\}$ and $\widetilde S_1 = \{2,3\}$ and the limiting sets are equal $\widetilde S_\infty = S_\infty = \{ 3 \}$ . This is illustrated in Figure 8(a).

Figure 8.

Different initializations may lead to different NE: (a) the case when $\widetilde S_\infty = S_\infty$ ; (b) the case when $\widetilde S_\infty \neq S_\infty$ .

4.3.2. The case when $\widetilde S_\infty \neq S_\infty$ .

In this subsection, $\psi$ is chosen such that

\begin{align*}\psi(0) = 4, \quad \psi(1) = 7, \quad \psi(2) =0, \quad \psi(3) =5.\end{align*}

We then compute $V_0$ and choose $\phi$ as follows:

\begin{alignat*}{7}V_0(0) &= 35/6, \quad & V_0(1)& = 7 , \quad & V_0(2)& = 60/11, \quad & V_0(3)& = 5, \\\phi(0) &= 5, \quad & \phi(1)& = 10, \quad & \phi(2)& = V_0(2) = 60/11, \quad & \phi(3)& = V_0(3) = 5.\end{alignat*}

In this case, $S_1 = \{ 0, 3\}$ and $\widetilde S_1 = \{0, 2,3\}$ and the limiting sets are $S_\infty = \{ 0, 3 \}$ while $\widetilde S_\infty= \{ 0,2,3\}$ . This example is illustrated in Figure 8(b).