Generlized Büchi Games and Closed under superset Muller Games

Question

For a unique infinite play $p$ in a 2-Player game $G=(V_0,V_1,E)$. Let

$$ \inf(p) \subseteq V_0 \cup V_1 $$

be the set of vertices which occur infinitly often in $p$.

Generlized Büchi (GB) Games are infinite games with a certain winning condition. Let $\mathcal{B} = \{B_1, \dots , B_k\}$ with $B_i \subset V$. Player $0$ wins the GB-game play $p$ iff for each $i$

$$ B_i \cap \inf(p) \neq \emptyset.$$

Which means that in each of the $B_i$ sets at least one vertex occurs infinitly often in the game.

Muller games are more general. The winning condition consists of a set $\mathcal{F_0} \subseteq \mathcal{P}(V)$ and Player $0$ wins a play $p$ iff

$$\inf(p) \in \mathcal{F}_0.$$

Muller games closed under superset are Muller games such that $\mathcal{F}_0$ is closed under supersets:

$$ X \in \mathcal{F}_0, X \subseteq Y \Rightarrow Y \in \mathcal{F}_0.$$

The taks now is to prove that GB-games and Muller games closed under superset are the same winning conditions.

One direction is easy. Just show that $\mathcal{F}_0 := \{X \subset V \mid \forall 1 \leq i \leq k, X \cap B_i \neq \emptyset\}$ is closed under supersets.

The other direction is a little bit more tricky:

Show that for each muller condition closed under supersets there is a GB condition with the same $\inf$-set for each game. E.g. :

$$ V=\{1,2,3,4\} ~~ \mathcal{F}_0=\{\{1,2\},\{3,4\},\{1,2,3,4\}\}$$

The muller condition is closed under supersets. Now the GB-Condition

$$\{\{1,3\},\{2,4\}, \dots$$

Here is where I'm stuck. How do I prevent $\inf(p)=\{1,4\}$ or $\inf(p)=\{2,3\}$? There is no construction for "forbidden combinations". Any ideas?

Answer 1

For the other direction, let $S$ be the set of all $\it{minimal}$ (without proper subset) set of sets in $\mathcal{F}_0$ in Muller condition, i.e, let $$ S = \{X \subset \mathcal{F}_0 \mid \forall Y \in \mathcal{F}_0, Y \not \subset X \} $$

In your example, $S = \{ \{1, 2\}, \{3, 4\}\}$.

Now consider the cross product of all elements of $S$. Claim is that this cross product forms the corresponding GB-condition. In your example,

$$ S_\times = \{1, 2\} \times \{3, 4\} = \{ \{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}\}$$

forms the accepting condition of the GB-game. There are two things to be proved:

1. Every winning play $p$ of GB-game is also winning in Muller game. This is true because every state in $inf(p)$ comes from at least one state in $S$ in Muller game. Thus, $inf(p) \subseteq \cup_{X \in S} X$. The proof follows from the fact that Muller game is closed under subset.
2. Every winning play $p$ of Muller game is also winning in GB-game. In this case, let $inf(p) = R \in \mathcal{F}_0$ be the winning set. Since Muller game is closed under superset, there exists a $\it{minimal}$ set $X$ such that $X \subseteq R$. Now at least one element of $X$ appears in any winning condition of the GB-game. Hence, $R \cap \beta \neq \emptyset$, proving the other direction as well.