Intuition behind equivalence of infinite games

129 Views Asked by At

In my lecture notes we denote with $S_I^T$ and $S_{II}^T$ the sets of all strategies for player I and II for a game in (a tree) $T$. Then follows a definition:

Say that the game $G(T; A)$ dominates the game $G(T'; A')$ iff there are functions $S_I^T \to S_I^{T'}$ and $S_{II}^T \to S_{II}^{T'}$ mapping winning strategies to winning strategies.

The games $G(T; A)$ and $G(T'; A')$ are equivalent if they dominate each other.

Here $T$ is a tree and $A$ is the payoff set.

I don't understand the intuition behind this definition. Isn't this the same as saying that two games are equivalent iff either the same player has a winning strategy in both games, or in both games no player has a winning strategy?

Somehow this doesn't jive with me as the "correct" notion of equivalence between two games. Maybe because the functions $S_I^T \to S_I^{T'}$ and $S_{II}^T \to S_{II}^{T'}$ can be arbitrary. I would expect that two games are equivalent if strategies can be translated between them "by a rule", or something like that. This definition doesn't seem to really take the nature of the games into account (which makes me doubt whether I understood the above definition correctly in the first place).

1

There are 1 best solutions below

4
On

[I heavily edited the initial answer in response to comments.]


I believe the definition is incomplete as stated. Otherwise, it is indeed equivalent to what you mention: a player has a winning strategy in one game if and only if it does in the other. (If a player has winning strategies in both games, pick one in the target set, say $\sigma$, and define the domination map for that player as the constant map with value $\sigma$.)

I imagine the most natural additional requirement would be surjectivity (i.e., any winning strategy for either player for the game on $T'$ is the image of a winning strategy for the same player for the game on $T$).

It is also common in the area to consider domination maps (in the incomplete sense of Andretta's definition) that are continuous, meaning that they should not just send winning strategies to winning strategies (for the same player), but they should essentially do it bit by bit, that is, the map actually takes a partial strategy playing on $T$ to a partial strategy (for the same player) playing on $T'$ in such a way that if the domain of one such partial strategy extends that of another, then their images also satisfy this containment, and if a branch through the tree of such partial strategies on $T$ results in a winning strategy, then the corresponding path in the image is also winning.

Although the definition of a dominating map is simpler than that of a covering, even with the continuity requirement I suggest, the notions seem related. Coverings lead to the key idea of unraveling games, which in turn is behind Martin's inductive proof of determinacy. If sets in a pointclass can be unraveled, then they are determined, but establishing the existence of an unraveling is much more involved than mere determinacy and, accordingly, knowing that sets in a pointclass can be unraveled gives us more information (determinacy of larger pointclasses, for example).


I should probably add that injectivity (rather than surjectivity) does not seem to be the right requirement missing from the definition. This is because we may want to have domination maps from strategies on a very large tree $T$ to strategies in a smaller tree $T'$, and injectivity would make this impossible. This is common in practice. The proof that analytic games are determined under large cardinals considers an open game, where in addition to the integer moves, an ordinal parameter is also played. How to choose the ordinal to respond is determined by a measure on a measurable cardinal, and the domination map simply forgets this additional information.