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?


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.
  • 1
    $\begingroup$ One more thing, the complete superset-closed-Muller condition for your example looks like this $$\{ \{1, 2\}, \{3, 4\}, \{1, 2, 3\}, \{1, 2, 4\}, \{1, 3, 4\}, \{2, 3, 4\}, \{1, 2, 3, 4\} \}$$ $\endgroup$
    – Sudeep
    Jun 25 '13 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.