# $\subset$-minimal set to determine an opponent's strategies up to an equivalence relation

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).

-
What is your motivation behind this question? – Michael Greinecker Feb 12 '13 at 14:10
@MichaelGreinecker: I've made some revisions and added a brief part on motivation, which I should have done 2 days ago. – Metta World Peace Feb 13 '13 at 1:32

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.