Strategy-stealing argument in generalization of positional game?

391 Views Asked by At

Suppose we have a set $\mathcal{F}$ and a family, $\mathcal{W}$, of non-empty subsets of $\mathcal{F}$.

Alice and Bob are going to play a game using this data. Play proceeds with Alice and Bob alternating picking an element of $\mathcal{F}$ that has not been picked before until one of them wins or there are no more unclaimed elements. A player wins and the game ends if the set of elements (s)he has claimed is in $\mathcal{W}$. If the elements run out without either player achieving this condition, the game is a draw.

This is a generalization of what Wikipedia calls a positional game. To recover Wikipedia's definition you require tha that if $X\in \mathcal{W}$ and $X\subset Y$ then $Y \in \mathcal{W}$. In a positional game you can use the classic strategy stealing argument to show that Bob can not have a winning strategy.

The argument does not work for my class of games (since having made an extra move can hurt a player), yet intuitively I feel that Bob should not have a winning strategy. Can someone prove this?

Update: You may assume $\mathcal{F}$ is a finite set.

1

There are 1 best solutions below

4
On BEST ANSWER

Here is an example of a game where the second player (B) has a winning strategy. It is more comfortable to describe it using multisets, this should lead to no confusion. Our base set has $3\times a_i$ and $6\times b_i$ for $i=0,1,2$, thus a total of $27$ elements. The winning sets are (with indices mod $3$) the following.

($3\times a_i);\ (3\times a_i,\ a_{i-1});\ (2\times a_i,\ 3\times b_i);\ (2\times a_i,\ 3\times b_i,\ a_{i-1})\ $ for $i=0,1,2$.

If the first player (A) picks $a_i$ or $b_i$ in her first move, B replies by picking $a_{i+1}$. If later A picks another $a_i$, then B also picks an $a_i$. Otherwise, B first picks another $a_{i+1}$ forcing A to pick the last $a_{i+1}$, this way making sure that A cannot win. Now he can comfortably pick $3$ $b_{i+1}$'s and win.