history-based strategy versus position-based strategy

118 Views Asked by At

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

1

There are 1 best solutions below

3
On 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.