Variations on a game of Gale. II: Markov strategies (Q1329737)

[For Part I see J. Symb. Log. 58, 1035-1043 (1993; Zbl 0792.03038).] Let \(S\) be an infinite set and let \(f\) and \(g\) be sequences of positive integers. Players ONE and TWO play the following game: An inning is played for every positive integer. In the \(n\)-th inning, ONE selects a finite subset \(O_ n\) of \(S\); TWO responds with a finite subset \(T_ n\) of \(S\). ONE must obey the rules that \(1 \leq | O_ 1 | \leq f(1)\) and for each \(n\), \(1 \leq | O_{n + 1} \setminus O_ n | \leq f(n + 1)\). TWO must obey the rule that for each \(n\), \(| T_ n | \leq g(n)\). Thus the players construct a sequence \((O_ 1, T_ 1, \dots, O_ n, T_ n, \dots)\), which is said to be a play. TWO wins a play if \(\bigcup^ \infty_{n = 1} O_ n = \bigcap^ \infty_{n = 1} T_ n\). Otherwise, ONE wins. If \(S\) is linearly orderable and if TWO has a large enough memory, then TWO has a winning strategy in this game. Roughly, it is sufficient that TWO remembers \(O_ n\) for about \(f(1) + \dots + f(n) - n\) innings before finally forgetting it. If \(f\) is a fast growing function, this would require enormous memory capacity. The author investigates the problem: does TWO really need this much memory? In particular, it is asked whether it would be sufficient for TWO to remember only the most recent move of ONE (a strategy depending on only this information is said to be a tactic), or if it would be sufficient to remember the most recent move of ONE as well as the number of innings that have elapsed (a strategy depending on only this information is said to be a Markov strategy). If \(S\) is countable, then for any \(f\) TWO has a winning tactic, even if TWO chooses only one point per inning. In contrast to this, for uncountable well-orderable sets there is for every \(g\) an \(f\) such that TWO does not have a winning Markov strategy in the corresponding game. The \(f\) exhibited for a given \(g\) grows much faster than \(g\). This raises the issue of whether such growth rates are inherently necessary. For example, let \(m\) be a fixed positive integer and suppose that for each \(n\) we have \(f(n) = m\) and \(g(n) = m + 1\). It is shown that then, if \(S\) is linearly orderable, TWO has a winning tactic. The situation when for each \(n\) we have \(f(n) = g(n)\) is apparently more difficult. Here the author gives some consistency results which amount to the following: (1) Suppose \(S\) is the real line. If every subset of \(S\) has the property of Baire, then TWO does not even have a winning Markov strategy. (2) Suppose that \(S\) is \(\omega_ 1\), the first uncountable ordinal. If it is consistent that there is an \(\omega + \omega\)-Erdős cardinal, then it is consistent that whenever \(f = g\), TWO does not have a winning Markov strategy in this game on \(\omega_ 1\).