AGV 11.6 -- A Remark on Undetermined Games

Previous chapter: Muller Games

This is a learning note of a course in CISPA, UdS. Taught by Bernd Finkbeiner

Since we have shown that reachability, Büchi, parity, and Muller games are all determined, it might seem as if all games were determined. The purpose of this last subsection is to remark that this is not the case. By definition, every play is either won by Player 0 or by Player 1; however, it is entirely possible that neither Player 0 nor Player 1 has a winning strategy.

We will construct a game with a winning condition that allows the players to steal strategies in the sense that if Player i has a winning strategy σ, then Player 1−$i$ has a strategy $\tau$ that mimicks $\sigma$ so that the play resulting from strategies σ and τ is won by Player 1-$i$: hence, strategy $\sigma$ is not winning after all!

We fix the alphabet $\mathbb{B}=\{0,1\}$. To define the winning condition, we introduce an infinite $\text{XOR}$ function $f$. An infinite $\text{XOR}$ function is a function $f:{\mathbb{B}}^{\omega }\to \mathbb{B}$ such that $f(\alpha )\ne f(\beta )$ for all α, β ∈ B ω that have the exact same letter in every position except for exactly one position where they have different letters.

To see that such a function exists, define an equivalence relation $\sim$ such that $\alpha \sim \beta$ iff there exists a position $n\in \mathbb{N}$ such that $\alpha (i)=\beta (i)$ for all $i\ge n$. Let $S\subseteq {\mathbb{B}}^{\omega }$ be a set that contains exactly one element from each $\sim$-equivalence class, and let $r(\alpha )$ be the unique $\beta \in S$ such that $\alpha \sim \beta$. For every $\alpha \in {\mathbb{B}}^{\omega }$, the two sequences $\alpha$ and $r(\alpha )$ differ only in a finite number of positions. We define $f(\alpha )=0$ if this number is even and $f(\alpha )=1$ if it is odd. Hence, $f$ is indeed an infinite $\text{XOR}$ function: if two sequences $\alpha ,\beta \in {\mathbb{B}}^{\omega }$ differ in exactly one position, then $f(\alpha )\ne f(\beta )$.

We now use the infinite $\text{XOR}$ function $f$ to define the game. We’ll describe the game somewhat informally in terms of rounds executed by the players; it is straightforward to translate this into an explicit arena and winning condition. Our game is played in rounds $n=0,1,2,\dots ,$ where in round $n$, first Player 0 picks a finite word $w_{2n}\in {\mathbb{B}}^{+}$, then Player 1 picks $w_{2n+1}\in {\mathbb{B}}^{+}$. The resulting play $\alpha =w_0,w_1,w_2,\dots$ is winning for Player $f(\alpha )$.

We now use the “strategy stealing” argument to show that no player has a winnig strategy in this game. A strategy for Player $i$ is a mapping $\sigma :{\cup }_{n\in \mathbb{N}}({\mathbb{B}}^{+}{)}^{2n+i}$, where we denote $({\mathbb{B}}^{+}{)}^0=\epsilon$.

As usual, $\sigma$ is a winning strategy for Player $i$ if Player $i$ wins every play that is consistent with ${\sigma }_i$ . Now fix an arbitrary strategy $\tau$ for Player 1. From $\tau$, we construct two different strategies $\sigma$ and ${\sigma }^{\prime }$ for Player 0.

For the first round:

• $\sigma (\epsilon )=0$

• ${\sigma }^{\prime }(\epsilon )=1w_1$ where $w_1=\tau (0)$

and for all subsequent rounds:

• $\sigma (0,w_1,w_2,\dots ,w_{2n+1})=\tau (1w_1,w_2,\dots ,w_{2n+1})$

• ${\sigma }^{\prime }(1w_1,w_2,\dots ,w_{2n+1})=\tau (0,w_1,w_2,\dots ,w_{2n+1})$

i.e., $\sigma$ continues to mimick $\tau$. Consider now the plays $\alpha$, resulting from playing strategies $\sigma$ and $\tau$, and ${\alpha }^{\prime }$ resulting from playing strategies ${\sigma }^{\prime }$ and $\tau$. By construction, $\alpha =0w_1{w}_2{w}_3\dots$ and ${\alpha }^{\prime }=1w_1{w}_2\dots$ are the same except for the first position, where $\alpha$ has a 0 and ${\alpha }^{\prime }$ has a 1. Hence, we have that $f(\alpha )\ne f({\alpha }^{\prime })$: one of the two plays is won by Player 0, the other by Player 1. Hence, $\tau$ cannot be a winning strategy for Player 1!

The construction of the stealing strategies $\tau$, ${\tau }^{\prime }$ for Player 1 from a given strategy σ of Player 0 is analogous.

For the first round:

• $\tau (w_0)=0$ for $W_0=\sigma (\epsilon )$

• ${\tau }^{\prime }(w_0)=1w_1$ for $w_1=\sigma (0,w_0)$

and for all subsequent rounds:

• $\tau (w_0,0,w_2,\dots ,w_{2n+1})=\sigma (w_0,1w_1,w_2,\dots ,w_{2n+1})$

• ${\tau }^{\prime }(w_0,1w_1,w_2,\dots ,w_{2n+1})=\sigma (w_0,0,w_1,w_2,\dots ,w_{2n+1})$

Again, the resulting plays only differ in exactly one position and are, hence, won by different players. Thus, strategy $\sigma$ cannot be winning for Player 0 either.

---

Next chapter: Tree Automata and Acceptance Game

Further Reading: