History-based strategy versus position-based strategy

infinite-gamesset-theory

SUMMARY: suppose a game is played that is a walk on an infinite directed graph without blind points, where the two players each make one step alternatingly.
Suppose that the pay-off of a play is determined by any confinal subset of the play.
In this case, can a winning history-based strategy always be replaced by a winning position-based strategy?
In the comments, Bof answered no. Gabriel Debs in Paris had a counterexample.

Game theorists probably know the answer to this question. Thank you for your interest.

Let $M$ be a move set and $A \subset {^\omega}M$ a pay-off set. Let $\rho: M\cup\{0\} \rightarrow \mathcal{P}M\setminus\{\emptyset\}$ be a rule.
A play is a sequence $x\in{^\omega}M$, where the even moves were made by player I and the odd moves were made by player II.
The first move (made by I) should be in $\rho(0)$.
After one player plays a move $m$, the other player is required to play a move in $\rho(m)$.
If any player makes an illegal move in this sense, the first player to do so loses the game.
If, on the other hand, in a play $x$ all moves were legal, then player I is the winner iff $x\in A$.
A history-based strategy is a mapping $\sigma:{^{<\omega}}M\rightarrow M$. If a player plays $\sigma$, this means that if $s\in{^{<\omega}}M$ is the history of all moves that have been made up to a certain point, then the player plays $\sigma(s)$.
A position-based strategy is a mapping $\tau:M\sqcup\{0\}\rightarrow M$. If a player plays $\tau$, this means that if $s\in{^{<\omega}}M$ is the history of all moves up to a given point, then the player plays
$$
\begin{cases}
\tau(0)\quad&\text{if $s=\emptyset$,}\\
\tau\big(s(len(s)-1)\big)\quad&\text{otherwise.}
\end{cases}
$$

PROBLEM. Suppose that for any legal plays (obeying $\rho$) $x,y \in {^\omega}M$ and $c_1<c_2<\dots<\omega,d_1<d_2<\dots<\omega$ such that $\forall i:x(c_i)=y(d_i)$, we have that $x \in A$ iff $y \in A$.
Also assume that player I has a winning history-based strategy. Can we conclude that I has a winning position-based strategy?

AFFIRMATION IF $|M|<\omega$.
Observe that $A$ is determined by the moves that occur cofinally often in some element of $A$.
Let $G=\big\{m\in M:\exists x\in A,C\in[\omega]^\omega:x(C)=\{m\}\big\}$.
Let $\sigma$ be a winning history-based strategy for I.
This means that for every play $x$ following $\sigma$ we have $|x^{-1}G|=\omega$.
Let
$$
U=\big\{u\in{^\omega}M:\forall i:u(2i)=\sigma\big(u|(2i)\big)\big\}
$$

be the set of won plays according to $\sigma$.
Let
$$
N=\bigcup_{u\in U}u[2\mathbb{N}+1]\subseteq M
$$

be the set of won positions where it is I to move.
Consider $u\in U$ and $i\in\omega$ odd.
There is an $n(u,i)>0$ such that for all $y\in U$ with $y|(i+1)=u|(i+1)$ we have
$$
y[i,n(u,i)]:=\{y(i+1),y(i+2),\dots,y(i+2n(u,i))\}\cap G\neq\emptyset.
$$

(If this were not true, the set
$$
\big\{y|n:y\in U\land y|i=u|i\land n\in\omega\land y[i,n]\cap G\neq\emptyset\big\}
$$

would be an infinite tree of finite width.
It contains an infinite branch by König's lemma, contradicting the fact that $\sigma$ is winning.)
Assume that $n(u,i)$ was chosen minimal with its property.
For $m\in N$, let
$$
n(m)=\min_{u\in U,u(i)=m}n(u,i)
$$

and $u^m,i^m$ the corresponding arguments. Thus $u^m(i^m)=m$ and $n(m)=n(u^m,i^m)$.
Let
$$
\tau(m)=\sigma\big(u^m|(i^m+1)\big).
$$

(Of course, $\tau(0)=\sigma(\emptyset)$.)
Then $\tau$ is a winning position-based strategy for I: let $x$ be a play according to $\tau$ and $i\in\omega$ odd.
Then $m:=x(i)\in N$. For all $y\in U$ with $y|i^m=u^m|i^m$ it holds that $y[i^m,n(m)]\cap G\neq\emptyset$.
We need to find $j>i$ such that $x(j)\in G$. Pick $v\in U$ such that $v|(i^m+1)=u^m|(i^m+1)$, $v(i^m+1)=\tau(m)=x(i+1)$ and $v(i^m+2)=x(i+2)$.
Assume w.l.o.g. that $x(i+1),x(i+2)\notin G$.
We have $\{x(i+1),x(i+2)\}\cup y[i^m+2,n(m)-1]=y[i^m,n(m)]$ for all $y\in U$ with $y|(i^m+3)=v|(i^m+3)$.
This implies that $n(v,i^m+2)\leq n(m)-1$. So $n(x(i+2))\leq n(m)-1$.
We see that $n(x(i))>n(x(i+2))>\dots$ so eventually we find a $j>i$ such that $x(j)\in G$.

Q.E.D.

(Our game is in addition determined in the case $|M|<\omega$, which I saw when applying König's lemma.)

I have a slight feeling that the answer to the problem will be no in general.
If the answer is yes anyways, we naturally extend the question to game lengths larger than $\omega$.

Best Answer

The Banach–Mazur (or Banach–Mazur–Oxtoby) game $BM(X)$ on a topological space $X$ is played as follows. A play of the game is an infinite nested sequence $B_1\supseteq W_1\supseteq B_2\supseteq W_2\supseteq\cdots$ of nonempty open sets, where $B_n$ is chosen by Black and $W_n$ by White; Black wins if the intersection of the chosen sets is empty, White wins if it's nonempty. This is a game of the kind you're asking about; $M$ is the set of all nonempty open subsets of $X$. (If you want a smaller set $M$, you could require the moves to be chosen from a given $\pi$-base without, I think, affecting anything important.)

It is known that Black has a winning (historical or perfect-information) strategy if and only if $X$ is not a Baire space, and in this case Black even has a winning positional strategy, also called a stationary strategy or a tactic. On the other hand, Gabriel Debs, Stratégies gagnantes dans certains jeux topologiques, Fund. Math. 126 (1985), 93–105 (pdf), has constructed an example of a topological space $X$ (a refinement of the usual topology on the real line) such that White has a winning historical strategy in $BM(X)$ but has no winning positional strategy.

Related Question