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$ – FanOfFourier Dec 26 '13 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 '13 at 6:42
7
+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 '13 at 23:22
  • $\begingroup$ Nagyon szep! B.U.E.K.! $\endgroup$ – bof Dec 29 '13 at 3:05
  • 3
    $\begingroup$ Nice. I think you mean that Bob finishes by picking 3 $b_{i+1}$'s. $\endgroup$ – FanOfFourier Dec 29 '13 at 13:21
  • $\begingroup$ Indeed, corrected, thx. $\endgroup$ – domotorp Dec 29 '13 at 15:30

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.