Sinks and Ladders: ARRIVAL and SSG with Two Vertices per Level

For a binary graph $G=(V,E)$, a partition $(E_0,E_1)$ of the edge set $E$ is balanced, if every vertex $v\in V\setminus \{\mathrm{𝟎},\mathrm{𝟏}\}$ has exactly one outgoing edge in $E_0$ and one outgoing edge in $E_1$. We call these edges the even edge and the odd edge of $v$ and denote them by $(v,s_0(v))$ and $(v,s_1(v))$, respectively. Then an instance of ARRIVAL is defined formally as a tuple of a binary graph $G=(V,E)$, a designated source vertex $𝐨\in V$, and a balanced partition of $E$ into $E_0$ and $E_1$.

Given such an instance of ARRIVAL, consider moving a token along the edges of the graph according to the following rules: Whenever the token reaches a vertex $v$, it follows the even edge of $v$ if it has been at $v$ an even number of times already. Otherwise, it follows the odd edge of $v$. This results in the token effectively switching between the two outgoing edges at every vertex. The process finishes once the token reaches one of the two sinks. The problem is to decide which of the two sinks the token will end up at.

Following roughly the definition given by Condon [5], a (binary) Simple Stochastic Game (SSG) is played on a binary graph $G=(V,E)$ with $V=V_{\text{max}}\bigsqcup V_{\text{min}}\bigsqcup V_{\text{avg}}\bigsqcup \{\mathrm{𝟎},\mathrm{𝟏}\}$. Moreover, one of the vertices $𝐨\in V\setminus \{\mathrm{𝟎},\mathrm{𝟏}\}$ is considered the designated source.

The game works as follows: For every vertex $v\in V_{\text{max}}$, the so-called max-player chooses one of the outgoing edges of $v$. Next, the min-player chooses one outgoing edge for every $v\in V_{\text{min}}$. A token is then placed on $𝐨$ and starts moving along the directed edges of the graph. Whenever the token reaches a vertex $v\in V_{\text{max}}$, the token follows the outgoing edge that was chosen by the max-player for this vertex. Analogously, the edges chosen by the min-player determine where the token moves to from vertices in $V_{\text{min}}$. When the token reaches an average vertex $v\in V_{\text{avg}}$, an outgoing edge of $v$ is chosen uniformly at random and the token continues along this edge. The game ends when the token reaches either of the sinks $\mathrm{𝟎}$ or $\mathrm{𝟏}$. The max-player wins if the token eventually reaches $\mathrm{𝟏}$. If the token never reaches $\mathrm{𝟏}$, the min-player wins. This can happen if the token reaches $\mathrm{𝟎}$ instead or if it continues traversing the graph indefinitely without ever reaching any of the sinks.

A (positional) strategy $\sigma$ for the max-player is a function $\sigma :V_{\text{max}}\to E$ that assigns each vertex $v\in V_{\text{max}}$ one of its outgoing edges. If the max-player plays according to the strategy $\sigma$, this means that whenever the token reaches a vertex $v\in V_{\text{max}}$, it will continue along the outgoing edge $\sigma (v)$. Analogously, a strategy $\tau$ for the min-player is a function $\tau :V_{\text{min}}\to E$ that assigns to each vertex in $V_{\text{min}}$ one of its outgoing edges.

We denote by $G_{\sigma ,\tau }$ the graph that we obtain if we delete outgoing edges from vertices in $V_{\text{max}}\cup V_{\text{min}}$ that are not used by $\sigma$ and $\tau$. In other words, $G_{\sigma ,\tau }$ is the graph restricted to the strategies $\sigma ,\tau$. This can be thought of as a Markov chain: Vertices in $V_{\text{max}}\cup V_{\text{min}}$ have exactly one outgoing edge that is taken with probability $1$, vertices in $V_{\text{avg}}$ have two outgoing edges each with a transition probability of $\frac{1}{2}$. Given strategies $\sigma ,\tau$ and a vertex $v\in V$, the value (or hitting probability) $h_{\sigma ,\tau }(v)$ is the probability that a token starting at vertex $v$ will eventually hit $\mathrm{𝟏}$ in the Markov chain $G_{\sigma ,\tau }$. In other words, this is the probability of the max-player winning the game if the players play according to $\sigma$ and $\tau$ and the token starts at $v$. The optimal value $h(v)$ of a vertex $v\in V$ is defined as $h(v)≔{\max }_{\sigma }{\min }_{\tau }{h}_{\sigma ,\tau }(v)$.

The computational problem SSG is to decide whether $h(𝐨)>\frac{1}{2}$ or not, where $h(𝐨)$ is the optimal value of the designated source.

An SSG is called stopping if and only if a sink is reachable from every vertex in the graph $G_{\sigma ,\tau }$ for all strategies $\sigma$ and $\tau$ of the players. In other words, in a stopping game, the probability of the token looping indefinitely in the graph without ever reaching a sink is zero, regardless of the played strategies. There is a well-known trick that reduces SSGs to stopping SSGs [5]. However, using it for SSGs on ladders would destroy the ladder structure of the underlying graph. Hence, in this article, we only consider stopping SSGs on ladders.

The first ingredient for our algorithm is to find out which of the two vertices in each levelset has larger optimal value. For this, consider the following definition.

In particular, we have ${\mathrm{\ell }}_0=\mathrm{𝟎}$ and $u_0=\mathrm{𝟏}$. The following observation will be crucial.

In Section 4.1 we proved that we can find ${\mathrm{\ell }}_i$ and $u_i$ in polynomial time for all $i\in \{0,1,\mathrm{\dots },k\}$. From Lemma 4, we know that this gives us a total order

on the optimal values of all vertices in the graph. From this total order, we can directly derive optimal strategies $\sigma ,\tau$ for both players. More precisely, for each vertex in $V_{\max }$, we keep the outgoing edges to the out-neighbor with the higher value, while for each vertex in $V_{\min }$, we keep the edge to the one with the lower value. Finally, we can solve the Markov chain $G_{\sigma ,\tau }$ to obtain the optimal value $h(𝐨)$ and decide the game in polynomial time.

Consider the Markov chain on the ladder $G$, where the transition probability of every edge is $\frac{1}{2}$. That is, from every vertex in $V\setminus \{\mathrm{𝟏},\mathrm{𝟎}\}$, there is an equal probability to visit one of its two out-neighbors next. Let ${\tilde{h}}_G(v)$ be the hitting probability at vertex $v$ in this Markov chain. In other words, ${\tilde{h}}_G(v)$ is exactly the optimal $h(v)$ of the SSG on $G$ where $V_{\max }=V_{\min }=\mathrm{\varnothing }$. For this reason, we call this the zero-player hitting probability. We drop the subscript $G$ from ${\tilde{h}}_G$ when the graph $G$ is clear from context.

As explained in Section 4, in polynomial time, we can label the two vertices in each levelset $L_i$ for $i\in \{0,\mathrm{\dots },k\}$ as ${\mathrm{\ell }}_i$ and $u_i$ such that ${\mathrm{\ell }}_0=\mathrm{𝟎}$, $u_0=\mathrm{𝟏}$, and

Next, we can assume without loss of generality that $({\mathrm{\ell }}_k,{\mathrm{\ell }}_{k-1},\mathrm{\dots },{\mathrm{\ell }}_0)$ and $(u_k,u_{k-1},\mathrm{\dots },u_0)$ are two directed paths in $G$. Indeed, suppose for some $i\in \{1,\mathrm{\dots },k\}$, there is no edge from ${\mathrm{\ell }}_i$ to ${\mathrm{\ell }}_{i-1}$. (The case of the missing edge $(u_i,u_{i-1})$ can be argued analogously.) Then ${\mathrm{\ell }}_i$ must have an edge to $u_{i-1}$. By Lemma 8, $\tilde{h}(u_i)\le \tilde{h}({\mathrm{\ell }}_i)$. Combined with (1), this implies that $\tilde{h}(u_i)=\tilde{h}({\mathrm{\ell }}_i)$. If $u_i$ has an edge to ${\mathrm{\ell }}_{i-1}$, we can exchange the labels of $u_i$ and ${\mathrm{\ell }}_i$, and after this relabeling, we have the edges $({\mathrm{\ell }}_i,{\mathrm{\ell }}_{i-1})$ and $(u_i,u_{i-1})$. Otherwise, the target of all forward edge(s) of $u_i$ is $u_{i-1}$. This means that all vertices of $L_i$ have their forward edges to $u_{i-1}$. Then by using the same argument as in Section 3, we can contract all vertices in ${\bigcup }_{j\ge i}{L}_j$ to $u_{i-1}$.

Finally, for each vertex $v\in V\setminus \{\mathrm{𝟎},\mathrm{𝟏}\}$, we define the gap $g_G(v):={\tilde{h}}_G(v)-{\tilde{h}}_G(s_0(v))=-\left({\tilde{h}}_G(v)-{\tilde{h}}_G(s_1(v))\right).$ We also drop the subscript $G$ from $g_G$ when the graph $G$ is clear. The following lemma shows a crucial structural property of ladders that allows us to design an efficient algorithm later.

Switching flows were first introduced in [7]. We define them here more generally.

We distinguish between different types of switching flows.

The following result goes back to Dohrau, Gärtner, Kohler, Matoušek, and Welzl [7] and implicitly proves that ARRIVAL is in $\mathrm{𝖭𝖯}\cap \mathrm{𝖢𝗈𝖭𝖯}$.

In other words, in order to solve ARRIVAL, it suffices to find an integral switching flow.

As we have seen in the previous subsection, one way to try to solve ARRIVAL is to solve its integer linear program (ILP) formulation implicitly given in Definition 12 together with the constraints that all variables are integral. Unfortunately, we do not know how to solve this ILP fast. However, we can easily obtain a (not necessarily integral) switching flow by solving the linear system in Definition 12 in polynomial time. In fact, for each of the two sinks, we can efficiently check if there exists a switching flow to that sink. The non-existence of a switching flow to one sink suffices to decide ARRIVAL. Thus, the interesting case is when there are two switching flows from $𝐨$, one to $\mathrm{𝟏}$ and one to $\mathrm{𝟎}$.

The general idea to solve this case is as follows. We start with the two switching flows above. At every iteration, we attempt to make more values in the two switching flows to be integral, while maintaining that one switching flow is from $𝐨$ to $\mathrm{𝟏}$ and the other to $\mathrm{𝟎}$. More specifically, at iteration $i$, we require the flow on the edges starting from a vertex in ${\bigcup }_{j\le i}{L}_j$ to be integral. We show that for each switching flow, there is at most one choice of integral values for these edges, and we can compute it in polynomial time. Hence, either we can decide the instance immediately (because no integral values are possible for one switching flow) or we can progressively fix more integral values in both switching flows.

This subsection is dedicated to Lemma 16 below, which is the key lemma to our algorithm and discusses the relationship between any two switching flows with respect to the same tuple $(V,E_0,E_1,\phi )$. In particular, it shows that the inflows to $\mathrm{𝟏}$ in any two switching flows cannot differ by more than one. This is trivial when the switching flows are from an origin $𝐨$, since the inflows to $\mathrm{𝟏}$ can then be at most one. However, it is not obvious for an arbitrary function $\phi$, where the inflow to $\mathrm{𝟏}$ can potentially take any value between 0 and ${\sum }_{v\in V\setminus \{\mathrm{𝟎},\mathrm{𝟏}\}}\phi (v)$. Further, Lemma 16 also states that when the difference between the inflows to $\mathrm{𝟏}$ in the two switching flows is exactly one, we know exactly the difference between the flows of the even and odd edges from each vertex $v$ such that $g(v)\ne 0$, in both switching flows.

For convenience, we first define a few notations. For $i\in \{0,\mathrm{\dots },k\}$, define $L_{\le i}:={\bigcup }_{j=0}^i{L}_j$ and $L_{\ge i}:={\bigcup }_{j=i}^k{L}_j$. Moreover, we say a switching flow $x$ is $i$-integral if for every edge $e$ from a vertex in $L_{\le i}$, $x(e)\in \mathbb{N}$. $(x,y)$ is an $i$-pair, if $x$ and $y$ are $i$-integral switching flows from $𝐨$ to $\mathrm{𝟏}$ and $\mathrm{𝟎}$, respectively. In this subsection, we package the idea of the algorithm in Section 5.3 in the following lemma.