# Markov Strategies in Selection Games

## Seminar talk at Auburn University

Posted by Steven Clontz on February 5, 2017

Here is an outline of the talk I gave at the AU set-theoretic topology seminar on 2017 Feb 06.

• Definition of the Banach-Mazur Game:
• Introduced by Mazur as Problem 43 of the Scottish Book [pdf], a notebook kept by mathematicians frequenting the Scottish Cafe in Lwów, Poland in the 1930s and 1940s.
• Let $$S\subseteq\mathbb R$$. Two players alternate choosing decreasing intervals $$N_0\supseteq E_0\supseteq N_1\supseteq E_1\supseteq\dots$$. The first player wins if $$\bigcap_{n<\omega}N_n$$ contains a point of $$S$$; the first player wins otherwise.
• Banach (1935) showed that the second player has a winning strategy for this game if and only if $$S$$ is meager, a countable union of nowhere-dense sets. The prize was a bottle of wine, awarded by Mazur.
• Our variant of interest: two players choose
decreasing non-empty open subsets $$E_0\supseteq N_0\supseteq E_1\supseteq N_1\supseteq\dots$$ of a topological space $$X$$, and let the second player win if and only if $$\bigcap_{n<\omega}N_n\not=\emptyset$$. Call this game $$BM(X)$$.
• Limited information strategies
• Let $$M$$ be a set of possible moves for a game.
• A (perfect information) strategy is a function $$\sigma:M^{<\omega}\to M$$ that determines the next move for a player based upon all the previous moves of her opponent.
• A $$k$$-tactical strategy is a function $$\sigma:M^{\leq k}\to M$$ that determines the next move for a player based upon the most recent $$k$$ previous moves of her opponent.
• A $$k$$-Markov strategy is a function $$\sigma:M^{\leq k}\times\omega\to M$$ that determines the next move for a player based upon the most recent $$k$$ moves of her opponent and the current round number.
• A coding strategy is a function $$\sigma:M^{\leq 2}\to M$$ that determines the next move for a player based upon the most recent moves of both players.
• A strategy is winning if a player that follows the strategy is guaranteed to win the game regardless of the moves of the opponent.
• A winning (perfect information) strategy for the second player in $$BM(X)$$ may always be improved to a winning coding strategy. (Debs 1985; Galvin,Telgarsky 1986)
• A winning Markov (that is, $$1$$-Markov) strategy for the second player in $$BM(X)$$ may always be improved to a winning tactical (that is, $$1$$-tactical, also known as stationary) strategy. (Galvin,Telgarsky 1986)
• Debs (1985) found examples of spaces for which the second player in $$BM(X)$$ has winning ($$2$$-tactical; see Bartoszynski,Scheepers,Just 1993) strategies, but no winning tactical strategies.
• Telgarksy conjectures (1987) that there exist spaces $$X_k$$ for $$k<\omega$$ such that the second player in $$BM(X_k)$$ has a winning $$(k+1)$$-tactical strategy, but no winning $$k$$-tactical strategy.
• Countable/Finite Games
• Scheepers (1992) published the first of many papers under the title of Meager-Nowhere Dense Games: $$n$$-Tactics.
• Let $$MG(X)$$ be a game where the first player chooses meager subsets $$M_{n+1}\supseteq M_n$$ during round $$n+1$$, followed by the second player choosing a nowhere dense subset $$N_{n+1}$$. The second player wins if $$\bigcup_{n<\omega}N_n\supseteq\bigcup_{n<\omega}M_n$$.
• The special case where $$X=\kappa$$ has the co-finite topology (and therefore the first player chooses countable sets and the second player chooses finite sets) was studied by Scheepers in Concerning $$n$$-tactics in the countable-finite game. Call this game $$Sch^{\cup,\supsetneq}(\kappa)$$.
• Scheepers showed that any $$(k+3)$$-tactical strategy for the second player in $$Sch^{\cup,\supsetneq}(\kappa)$$ may be improved to a $$k$$-tactical strategy.
• Modification: $$Sch^{\cap}(\kappa)$$: the first player chooses any countable set $$C_n$$, and the second player chooses any finite set $$F_n$$. The second player wins if $$\bigcup_{n<\omega}F_n\supseteq\bigcap_{n<\omega}C_n$$.
• The axiom $$\mathcal A’(\kappa)$$ implies that the second player has a winning $$2$$-tactical strategy in $$Sch^{\cup,\supsetneq}(\kappa)$$ (Scheepers) and a winning $$2$$-Markov strategy in $$Sch^{\cap}(\kappa)$$ (Clontz).
• $$A’(\aleph_n)$$ holds in ZFC for $$n<\omega$$ (Clontz,Dow to appear); $$A’(\kappa)$$ may be forced to hold for arbitrarily large $$\kappa\leq\mathfrak c$$ (Scheepers).
• Selection Games
• Let $$G_{fin}(\mathcal A,\mathcal B)$$ be the game where the first player chooses $$A_n\in \mathcal A$$ and the second player chooses a finite subset $$B_n\in[A_n]^{<\omega}$$. The second player wins if $$\bigcup_{n<\omega}B_n\in\mathcal B$$.
• For each cardinal $$\kappa$$, let $$L(\kappa)=\kappa\cup\{\infty\}$$ be the space with $$\kappa$$ discrete and $$\infty$$ having co-countable neighborhoods.
• Let the Menger game be $$Men(X)=G_{fin}(\mathcal O,\mathcal O)$$ where $$\mathcal O$$ is the set of open covers of $$X$$.
• In regards to $$k$$-Markov strategies for the second player, $$Men(L(\kappa))$$ and $$Sch^{\cap}(\kappa)$$ are equivalent (Clontz).
• Markov strategies in Selection Games
• Any $$(k+2)$$-Markov strategy for the second player in $$G_{fin}(\mathcal A,\mathcal B)$$ may be improved to a $$2$$-Markov strategy.
• Assume $$|\bigcup\mathcal A|\leq\aleph_0$$ and $$\mathcal B$$ is closed under supersets. Then any winning (perfect-information) strategy for the second player in $$G_{fin}(\mathcal A,\mathcal B)$$ may be improved to a Markov strategy.
• Corollaries:
• Let $$\mathcal D$$ give the dense subsets of a space $$X$$. The second player having a winning strategy in $$G_{fin}(\mathcal D,\mathcal D)$$ characterizes strategic selective separability, $$SS^+$$. Thus all countable $$SS^+$$ spaces are Markov selectively separable, $$SS^{+mark}$$. (Barman,Dow 2012).
• The second player having a winning strategy in $$G_{fin}(\mathcal O,\mathcal O)$$ characterizes the strategic Menger property. All second-countable strategic Menger spaces are Markov Menger. Markov Menger spaces are exactly the $$\sigma$$-relatively-compact spaces (equivalent to $$\sigma$$-compact for regular spaces). (Clontz)
• Question (Gruenhage): Does there exist an $$SS^+$$ space that is not $$SS^{+mark}$$?