4
$\begingroup$

On Page 141, Axiom of Choice, Herrlich(2006)

Show that if in a game of the form $G(1, X_1, Y_1, A)$, the first player has no winning strategy, then the second player can always win, even though he may not have a winning strategy.

In this question, $G(1, X_1, Y_1, A)$ denotes a sequential game with two players. The first player starts with a choice from her action space $X_1$, and the second player player follows with a choice in $Y_1$. $A$ is a sub set of $X_1 \times Y_1$, if the outcome belongs to $A$, then the second player wins, otherwise, the first player wins. A winning strategy for the first player is a choice $x$ from $X_1$, such that $\{x\} \times Y_1 \bigcap A = \emptyset$ ,while a winning strategy for the second player is a function $f:X_1 \to Y_1$, such that $X_1 \times f(X_1) \subseteq A$.

I'm confused with the scenario that the second player always win without a winning strategy. Why not they are tautological?

  • 0
    Okay, good. Then the fact that I came up with a counterexample like the one below makes sense.2012-11-28

1 Answers 1

3

Suppose that Player I has no winning strategy, this means that for every move I does, II can find a move which assures that the outcome is in $A$. To say that II has a strategy is to say that there is one particular function which assures II the victory, rather just denying I the win.

One could argue that a possible way to devise a strategy for the second player would be to take $f(S)$ (where $S$ is some state) to return a move which denies I the win from the current state.

However if the axiom of choice fails such choice may not exist. Regardless to that, by induction we can show that II can always deny the victory.


As Theorem 6.4 on p. 139 states this game is always determinate if and only if AC holds. So a counterexample would have to come from a situation where the axiom of choice fails.

Let $X=\omega$ and let $Y$ be a Russell set, which is a set that can be partitioned into a countable union of pairs whose product is empty. We define the following $A=\{(i,p)\mid p\in P_i\}$ where $P_n$ is the $n$-th pair in a fixed partition of $Y$ into pairs.

Clearly Player I has no winning strategy here, because $P_i\neq\varnothing$, so it cannot assure its winning. However II does not have a winning strategy either because that such winning $f$ would have to tell II which element to choose from $P_i$ for all $i\in\omega$.

If I won then at some stage II didn't choose $p\in P_i$, which is preposterous. So despite II not having a clear strategy to win -- he cannot lose.

  • 0
    @AsafKaragila this is the reason I like mathematics. One day I read some sentences that make no sense, talking about things I never heard of. Then some months go by and I can read the same non-sense gibberish and give it a meaning, understand it and even take part in the discussion. Right now I am on the "I understood nothing" state :)2017-01-25