In a two-player sequential game, each player's strategy is a function that maps history records to her own action space. Naturally, once two players' strategies are given, the outcome, a vector of each player's actions, shall be determined. Suppose player I's strategy is fixed, which player II is ignorant of ex ante. Each time player II choose a strategy from her strategy space and observe an outcome.What is the $\subset$-minimal set in as a subset of strategy space of player II can determine the strategy of player I by carrying them out one-by-one? (To accord with Consequentialism implicit in above statement, it's necessary to define an equivalence relation that sweep those strategies indistinguishable from outcomes and opponent's strategies under the rug.)

Formally, a two-player game $$G(n,(X_i)_{i \leq n},(Y_j)_{j \leq n})$$ where

  • $n$ is the number of the moves of each of the two players I and II.
  • $(X_i)_{i \leq n}$ (or $(Y_j)_{j \leq n} $) is an $n$-tuple of $X_i$(or $Y_j$), which is the action space of $n$th move of first (second) player.
  • The game is played in an alternating fashion.An outcome is an $2n$-tuple $\{a_i\}_{i \leq 2n} $ in the outcome space $A$:$$a_1 \in X_1, a_2\in Y_1, a_3 \in X_2…… a_{2n-1} \in X_{n},a_{2n} \in Y_n$$
  • A player moves at any stage contingent on history. So a strategy for player I take the form as a sequence of functions $\{\sigma_i\}_{i \leq n}$: $$\sigma_i : \prod_{j < i}{X_j \times Y_j} \to X_i$$ Player II's strategy's form $\{\tau_i\}_{i \leq n}$is defined similarly.
  • Player I and Player II's strategy spaces are denoted as $S_{\text I}$ and $S_{\text {II}}$ respectively. Denote the binary operation $\star$ as the function that sends $\sigma$ and $\tau$, a pair of strategies of player I and player II to the outcome $a$ they give rise to$$\sigma \star \tau \mapsto a$$
  • Strategy $\sigma$ and $\sigma'$ for player I are equivalent, if for any player II's strategy $\tau$, $$\sigma \star \tau = \sigma' \star \tau$$ The equivalence class $[\sigma]$ is denoted as$\{\sigma' \in S_{\text{I}}:\forall \tau \in S_{\text{II}}(\sigma \star \tau = \sigma' \star \tau)\}$, and the corresponding partition of $S_{\text{I}}$ as $S_{\text{I}}'$. We define the equivalence relation for Player II in the same way.
  • We characterize $\subset$-minimal set that determine player I's strategy $S_{\text{II}}^{min}$ as the minimal subset of $S_{\text {II}}'$, such that: For any $[\sigma_1]$, $[\sigma_2]$ in $S_{\text{I}}'$ and $[\sigma_1] \neq [\sigma_2]$, there exists $[\tau] \in S_{\text{II}}^{min}$, $\sigma_1 \star \tau \neq \sigma_2 \star \tau$

Added: This problem is directly related to another question, Classification of $ω$-games of different fixed action spaces. If we can pinpoint $\subset$-minimal set of $\omega$-game, then for any two games with the same cardinality of $\subset$-minimal sets, we can extend the bijection(between $\subset$-minimal sets) to the whole strategy spaces. My first guess are those strategies of constant functions at each stages. But a problem, as pointed by Trevor Wilson, is that it suggests that $\bf AD_2 \Leftrightarrow AD_{\mathbb{R}}$, which is wrong(See here).

  • $\begingroup$ What is your motivation behind this question? $\endgroup$ Feb 12, 2013 at 14:10
  • $\begingroup$ @MichaelGreinecker: I've made some revisions and added a brief part on motivation, which I should have done 2 days ago. $\endgroup$ Feb 13, 2013 at 1:32

1 Answer 1


Your question presumes that there is a minimal such set of strategies and furthermore that this set is unique. This is not obvious to me. The following discussion doesn't really answer your question but it hints (to me, anyway) that your premise might be incorrect. I'm going to switch the roles of players I and II to make things slightly simpler.

Let's just consider the set of constant strategies $\sigma_f$ of player I where $f \in X^\omega$. Notice that these suffice to distinguish any pair of inequivalent strategies for player II. Moreover if $D$ is any dense subset of $X^\omega$ (in the product of the discrete topologies on $X$) then the corresponding subset of strategies $\{\sigma_f : f \in D\}$ also suffices: for any pair of inequivalent strategies $\tau$ and $\tau'$ for player II, there must be some finite sequence $t \in X^{<\omega}$ to which they respond differently, so for any $f$ extending $t$ we have $\sigma_f \star \tau \ne \sigma_f \star \tau'$.

On the other hand, if $A \subset X^\omega$ is not dense, say it has no sequences extending $t \in X^{<\omega}$, then the corresponding subset of strategies $\{\sigma_f : f \in A\}$ does not suffice to distinguish all pairs of inequivalent strategies $\tau$ and $\tau'$ for player II. In particular, if we let $\tau$ be some constant strategy for player II, we let $t' \in X^{<\omega}$ be a proper extension of $t$, and we let $\tau'$ be some strategy that deviates from $\tau$ if and only if player I plays $t'$, then the set of strategies $\{\sigma_f : f \in A\}$ cannot distinguish between $\tau$ and $\tau'$.

There is no minimal dense subset of $X^\omega$, so the set of constant strategies has no minimal subset with the desired property. This doesn't prove that there is no minimal set of strategies with the desired property, but I don't see any reason to consider non-constant strategies in this context anyway, because you get the same notion of equivalence just by playing against constant strategies.

  • $\begingroup$ Incredible!I did take these things for granted unconsciously, but can not figure them out, until being informed. A question, do you mean "there is no minimal dense subset……" that we can't constuct such thing without axiom of choice? $\endgroup$ Feb 16, 2013 at 2:02
  • 1
    $\begingroup$ @Metta actually any reasonable topological space has no minimal dense subset, because if you remove any point from a dense set it is still dense. Zorn's lemma doesn't apply because the intersection of a chain of dense sets need not be dense. $\endgroup$ Feb 16, 2013 at 20:19
  • $\begingroup$ I see. Thank you for your illuminating explanation. $\endgroup$ Feb 17, 2013 at 2:19

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.