Game

Games in which two players play forever.

Path

A path can be finite or infinite.

Let \(\rho = \langle \rho_{0}, \rho_{1}, \dots \rangle\) be an infinite path. We denote the prefix of \(\rho\) starting from the \(i\)-th vertex by \(\rho[i \dots]\). Define:

• \(visit(\rho) = \{ v \in V | \exists i, v = \rho_{i} \}\).
• \(inf(\rho) = \{ v \in V | \nexists i, v \notin visit(\rho[i \dots ]) \} = \{ v \in V | \forall i, v \in visit(\rho[i \dots ]) \}\), nodes visited infinitely many times.

Let \(T\) be a subset of vertices, here are some of the classical objectives:

We can check that:

• \(reach(T) = \overline{safe(V \setminus T)}\)
• \(Buchi(T) = \overline{coBuchi(V \setminus T)}\)

It is the most general objective we will study.

In this case, \(parity(p) = \{ \rho | \min \{ p(v) | v \in inf(\rho) \} = 0 \} = \{ \rho | \exists v \in inf(\rho), v \in T \} = Buchi(T)\).

To find a priority function for coBuchi, we want \(\{ \rho : inf(\rho) \nsubseteq T \} = \{ \rho | \min \{ p(v) | v \in inf(\rho) \} \text{is odd} \}\). This hints that we set \(p(v)\) to be a smaller odd number for \(v \notin T\).

The outcome is fixed given the initial vertex \(v\) and strategies of the two players \(\sigma_{1}, \sigma_{2}\). We denote it by \(Outcome(v, \sigma_{1}, \sigma_{2})\).

Finite memory

not can memorize only finite number of steps, but only finite bits of memory.

Suppose the objective for player 1 is \(reach(T)\). (Besides attractors and traps for this objective, I also include some related conclusions on winning strategies for player 2 and objective \(safe(V \setminus T)\).)

We will soon see that they are equal. Intuitively, \(A_{i}\) consists of all vertices that can reach \(T\) in at most \(i\) steps, so any valid attractor must be included in some \(A_{i}\).

Together, we have \(V \setminus A \subseteq Win_{2}(safe(V \setminus T))\), and \((V \setminus A) \cap Win_{1}(reach(T)) = \emptyset\). This implies that

Find \(A\) using a BFS:

\begin{algorithm}
\caption{Linear Algorithm for Finding Attractor}
\begin{algorithmic}
\STATE \(Q \gets T\)
\STATE \(A \gets \emptyset\)
\STATE \(SuccInA[v] \gets 0\) forall \(v \in V\)
\WHILE{$Q \neq \emptyset$}
\STATE Pop one vertex \(v\) from \(Q\)
\STATE \(A \gets A \cup \{ v \}\)
\FOR{$w \in Pred(v) \setminus A$}
\STATE \(SuccInA[w] \gets SuccInA[w] + 1\)
\IF{$w \in V_1$}
\STATE \COMMENT{corresponds to $\{ v \in V_1 | Succ(v) \cap A_i \neq \emptyset\}$}
\STATE \(Q \gets Q \cup \{ w \}\)
\ENDIF
\IF{$w \in V_2$ and $SuccInA[w] = outdeg(w)$}
\STATE \COMMENT{corresponds to $\{ v \in V_2 | Succ(v) \subseteq A_i \}$}
\STATE \(Q \gets Q \cup \{ w \}\)
\ENDIF
\ENDFOR
\ENDWHILE
\end{algorithmic}
\end{algorithm}

Running time:

• Visits all vertices: \(O(n)\).
• Visits all in-edges of \(A\): \(O(m)\).
• Overall: \(O(n + m) = O(m)\).

Consider the zero-sum Buchi game with \(O_1 = Buchi(T)\) and \(O_2 = coBuchi(V \setminus T)\). We want to solve \(Win_{1}(O_1)\) and \(Win_{2}(O_2)\).

The condition of having a successor is to ensure that the \(G_{W}\) satisfies the third requirement of arena, which is every vertex has at least one out-going edge.

We denote \(Attr_{i}(T) = Win_{i}(reach(T))\).

• \(A = Attr_{1}(T)\) may not have a subgame arena: For \(v \in A_i\)m \(i = 1, 2, \dots \), it must have an edge to \(A_{i-1}\). However, \(v \in A_0 = T\) may not satisfy the conditoin. \(Attr_{1}(T)\) has a subgame arena iff every vertex in \(A_0 = T\) has a successor in \(Attr_{1}(T)\).
• Any trap has a subgame arena: Check the definition. In particular, \(B = V \setminus Attr_{1}(T)\) has a subgame arena.
• \(C = Attr_{2}(V \setminus Attr_{1}(T))\) has a subgame graph: The base case is a trap \(V \setminus Attr_{1}(T)\), and hence satisfies the condition.
• Since \(V \setminus Attr_{2}(V \setminus Attr_{1}(T))\) is a trap for player 2, it also has a subgame arena.

Consider a zero-sum game with \(O_1 = parity(p)\) and \(O_2 = parity(p + 1)\), where \(p: V \to \{ 0, 1, \dots , d \}\).

W.l.o.g., we can assume that

• either 0 or 1 appears in the priorities: If not, can shift all priorities to the left by 2.
• priorities are contiguous: If not, we can shift any priority to the left by some multiple of 2 as long as it does not become less than the previous priority. More explicitly,
  • if the two adjacent priorities differ by some multiple of 2, then we can merge the larger one into the smaller one,
  • if the two adjacent priorities differ by some multiple of 2 plus 1, then we can shift the larger one to become the smaller one plus 1.
• When there are more than two priorities, w.l.o.g., priority 0 appears in the game, because we can solve \(O_2 = parity(p-1)\).

Running time:

• \(T(n, m, d) \leq n (T(n, m, d-1) + O(m))\): There are \(O(n)\) iterations, each of which needs to solve a parity game with \(d-1\) priorities and finds attractors.
• Base case: \(T(n, m, 2) = O(n m)\) (Buchi).
• \(T(n, m, d) = O(n ^{d-1} m)\).