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?

  • $\begingroup$ Except the title of the book, is there an actual reason for this this to depend on the axiom of choice? (the question in the book mentions nothing.) $\endgroup$ – Asaf Karagila Nov 28 '12 at 1:12
  • $\begingroup$ If the action space is infinite, the existence of winning strategy is equivalenet to axiom of choice as shown on Page 139 Theorem 6.4. $\endgroup$ – Metta World Peace Nov 28 '12 at 1:16
  • $\begingroup$ Okay, good. Then the fact that I came up with a counterexample like the one below makes sense. $\endgroup$ – Asaf Karagila Nov 28 '12 at 1:26

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.

  • $\begingroup$ Hm. I'm actually not a 100% sure about this right now. It is possible that the the strategy "always pick the least $n$ that you haven't used yet" would count as a winning strategy, but it's almost 4am. I'll re-read this in the morning, please leave insightful comments if you have them. $\endgroup$ – Asaf Karagila Nov 28 '12 at 1:40
  • $\begingroup$ Right. Now I think the answer is correct. $\endgroup$ – Asaf Karagila Nov 28 '12 at 1:56
  • $\begingroup$ Tons of thanks. Could you please provide some motivations behind the assumption of existence of Russell set? Is it merely a bizarre product of ZF with the negation of AC? $\endgroup$ – Metta World Peace Nov 28 '12 at 2:33
  • $\begingroup$ Oh Russell sets are quite a strong anti-choice assumption. Their existence contradicts countable choice and the ultrafilter lemma. They make fantastic counterexamples though, and they are quite simple to use. I am sure that if one is so inclined then one could replace the Russell set by some other form of pathology. $\endgroup$ – Asaf Karagila Nov 28 '12 at 8:04
  • $\begingroup$ @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 :) $\endgroup$ – RGS Jan 25 '17 at 18:12

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.