9
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Well, the "without replacement" can of course be modelled by saying that a player loses if he plays a move that has already been made. I was thinking about the finite case though. $\endgroup$ Dec 26, 2013 at 10:50
  • 1
    $\begingroup$ As an aside, if something in $\verb!\mathcal!$ is a collection of subsets, then usually things on the level of the original set wouldn't be in $\verb!\mathcal!$. That's why some people used $F$ instead of $\mathcal F$ in their answers. Compare with the Wikipedia page for positional game, which uses $\mathcal F$ for a family of subsets of $X$. $\endgroup$
    – Mark S.
    Dec 29, 2013 at 6:42

1 Answer 1

6
+150
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ This looks good to me; well done! How did you go about finding this? $\endgroup$
    – Mark S.
    Dec 28, 2013 at 23:22
  • $\begingroup$ Nagyon szep! B.U.E.K.! $\endgroup$
    – bof
    Dec 29, 2013 at 3:05
  • 3
    $\begingroup$ Nice. I think you mean that Bob finishes by picking 3 $b_{i+1}$'s. $\endgroup$ Dec 29, 2013 at 13:21
  • $\begingroup$ Indeed, corrected, thx. $\endgroup$
    – domotorp
    Dec 29, 2013 at 15:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .