k-Markov strategies in selection games

Steven Clontz | University of South Alabama | http://clontz.org

Spring Topology and Dynamics Conference 2017

at New Jersey City University

k-Markov strategies in selection games

Steven Clontz | University of South Alabama | http://clontz.org

Spring Topology and Dynamics Conference 2017

at New Jersey City University

ω-length Games

Used to characterize properties in topology and infinite combinatorics

Two players (I and II) alternate choosing moves A_{n} and B_{n} during round n.

A winner is declared based on <A_{0},B_{0},A_{1},B_{1},...>.

I | II |

A | B |

A | B |

A | B |

... | ... |

Strategies for ω-length Games

Perfect-Information

A function that decides a player’s move based on all previous opponent moves.

σ: M^{<ω}→M

σ(<A_{0},...,A_{n}>)

k-Tactical

A function that decides a player’s move based on last k-many of previous opponent moves.

σ: M^{≤k}→M

σ(<A_{0},...,A_{k-1}>)

k-Markov

A function that decides a player’s move based on last k-many of prev. opp. moves and round #.

σ: M^{≤k}⨉ω→M

σ(<A_{0},...,A_{k-1}>,n)

Coding

A function that decides a player’s move based on player & opponent’s last move

σ: M^{≤2}→M

σ(<B,A>)

Why study such things?

Banach-Mazur Game BM(X) (1935)

Players E,N choose decreasing open neighborhoods. E wins if intersection is empty.

X is Baire iff E has no winning strategy.

N’s Markov strategies can be improved to tactical strategies.

N’s perfect-info strategies can be improved to coding strategies.

Question (Telgarsky): Can k be improved for k-tactical strategies? (False for k=2.)

Countable-Finite Games (1990s)

Player C chooses countable C_{n}; player F chooses finite F_{n}. F wins if ⋃F_{n} contains ⋃C_{n}.

Scheepers studied k-tactics for player F assuming that C must choose strict supersets. Any (k+3)-tactic may be improved to a 3-tactic.

Clontz studied several variations, in particular when F need only contain ⋂C_{n}. Any (k+2)-mark may be improved to a 2-mark.

Selection Games G_{fin}(A,B) (1990s)

Player A chooses A_{n} from A; player B chooses finite subset B_{n}. B wins if ⋃B_{n} belongs to B. Two common cases:

A=B=O the collection of open covers of X (Menger game). When X=L(κ), this is equivalent to Clontz variation of countable-finite game.

A=B=D the collection of dense subsets of X (selectively separable game).

Improving Selection Game Strategies

Theorem

Any (k+2)-Markov strategy for a selection game may be improved to a 2-Markov strategy.

Idea of Proof

We define a 2-Markov strategy τ by asking the known winning (k+2)-Markov strategy σ what to do if the opponent repeated each move k+1 times:

τ(<A,A’>,n)=⋃σ(<A,...,A,A’,...,A’>,kn+i)

Since σ knows how to defeat the attack <A_{0},...,A_{0},A_{1},...,A_{1},...>, τ also successfully defeats the arbitrary attack <A_{0},A_{1},...>. ◻

Observation: Knowing how your opponent changes moves between rounds is powerful.

Theorem

Assume ⋃A is countable and B is closed under supersets.

Any perfect information strategy for such a selection game may be improved to a Markov strategy.

Idea of Proof (1/2)

Our improved Markov strategy τ will not be able to recover perfect information. However, due to the countability of ⋃A, there are only countably many “interesting” moves (moves that produce distinct responses by the perfect information strategy σ) that player A can utilize during the game.

Our Markov strategy will deal with all of these. Suppose we have defined A_{t} for all Ø<t≤s<ω^{<ω}. Then there are only countably many members of the set

{σ(<A_{s|1},A_{s|2},...,A_{s},A>):A∈A}⊆⋃A. Define A_{s^<n>} for n<ω such that

{σ(<A_{s|1},A_{s|2},...,A_{s},A>):A∈A}={σ(<A_{s|1},A_{s|2},...,A_{s},A_{s^<n>}>):n<ω}.

Idea of Proof (2/2)

Let b:ω→ω^{<ω} be a bijection. Our improved Markov strategy is defined by:

τ(<A>,n)=σ(<A_{b(n)|1},A_{b(n)|2},...,A_{b(n)},A>)

Importantly, note that τ(<A>,n)=σ(<A_{b(n)|1},A_{b(n)|2},...,A_{b(n)},A_{b(n)^<m>}>) for some m<ω, and thus τ(<A>,n)=σ(<A_{b(k)|1},A_{b(k)|2},...,A_{b(k)}>) for some k<ω.

To prove that τ is winning whenever σ is, from every attack <A’_{0},A’_{1},A’_{2},...> made by the opponent, one may extract a (possibly rearranged) subsequence equal to <A_{f|1},A_{f|2},A_{f|3},...> for some f:ω→ω.

Since σ defeats this attack, τ defeats <A’_{0},A’_{1},A’_{2},...>. ◻

Corollaries

Corollaries

Barman and Dow (2012): G_{fin}(D,D)

Every countable strategically SS space is Markov SS.

Question (Gruenhage): Are all strategically SS (or even 2-Markov selectively separable) spaces actually Markov SS?

Clontz (2015): G_{fin}(O,O)

Every second-countable strategically Menger space is Markov Menger.

Fact: L(ω_{1}) is a 2-Markov Menger space that is not Markov Menger.

Further fact: C_{p}(L(ω_{1})) is a 2-Markov CDFT space that is not Markov CDFT. Its separable subspaces are 2-Markov SS. (Are they Markov SS?)

References

(Available at clontz.org)

- A. V. Arkhangel′ ski˘ı. Hurewicz spaces, analytic sets and fan tightness of function spaces. Dokl. Akad. Nauk SSSR, 287(3):525–528, 1986.
- Doyel Barman and Alan Dow. Selective separability and SS+. Topology Proc., 37:181–204, 2011.
- Doyel Barman and Alan Dow. Proper forcing axiom and selective separability. Topology Appl., 159(3):806–813, 2012.
- Steven Clontz. Applications of limited information strategies in Menger’s game (to appear).
- Steven Clontz. Relating games of Menger, countable fan tightness, and selective separability (preprint).
- Winfried Just, Arnold W. Miller, Marion Scheepers, and Paul J. Szeptycki. The combinatorics of open covers. II. Topology Appl., 73(3):241–266, 1996.
- Robert A. McCoy and Ibula Ntantu. Topological properties of spaces of continuous functions, volume 1315 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1988.
- Fritz Rothberger. Eine verschrfung der eigenschaft c. Fundamenta Mathematicae, 30(1):50–55, 1938.
- Masami Sakai. Property C′ ′ and function spaces. Proc. Amer. Math. Soc., 104(3):917–919, 1988.
- Marion Scheepers. Combinatorics of open covers. I. Ramsey theory. Topology Appl., 69(1):31– 62, 1996.

k-Markov strategies in selection games

Thanks! Questions?

Steven Clontz | University of South Alabama | http://clontz.org

Spring Topology and Dynamics Conference 2017

at New Jersey City University