Banach–Mazur game

In general topology, set theory and game theory, a Banach–Mazur game is a topological game played by two players, trying to pin down elements in a set (space). The concept of a Banach–Mazur game is closely related to the concept of Baire spaces. This game was the first infinite positional game of perfect information to be studied. It was introduced by Mazur as problem 43 in the Scottish book, and Mazur's questions about it were answered by Banach.

Definition

A general Banach–Mazur game is defined as follows: we are given a topological space $Y$, a fixed subset $X\subset Y$, and a family $W$ of subsets of $Y$ that have the following properties:

• Each member of $W$ has non-empty interior.
• Each non-empty open subset of $Y$ contains a member of $W$.

Two players, $P_{1}$ and $P_{2}$, choose alternatively elements from W: $W_{0},W_{1},\cdots$ such that $W_{0}\supset W_{1}\supset \cdots$. The player $P_{1}$ wins if and only if

$X\cap \left(\bigcap _{n<\omega }W_{n}\right)\neq \emptyset$.

We denote this game $MB(X,Y,W)$.

Properties

• $P_{2}$ has a winning strategy if and only if $X$ is of the first category in $Y$ (a set is of the first category or meagre if it is the countable union of nowhere-dense sets).

• If $Y$ is a complete metric space, $P_{1}$ has a winning strategy if and only if $X$ is comeager in some nonempty open subset of $Y$.

• If $X$ has the Baire property in $Y$, then $MB(X,Y,W)$ is determined.

• Any winning strategy of $P_{2}$ can be reduced to a stationary winning strategy.

• The siftable and strongly-siftable spaces introduced by Choquet can be defined in terms of stationary strategies in suitable modifications of the game. Let $BM(X)$ denote a modification of $MB(X,Y,W)$ where $X=Y$, and $W$ is the family of all nonempty open sets in $X$, and $P_{2}$ wins a play $(W_{0},W_{1},\cdots )$ if and only if

$\cap _{n<\omega }W_{n}\neq \emptyset .$

Then $X$ is siftable if and only if $P_{2}$ has a stationary winning strategy in $BM(X)$.

• A Markov winning strategy for $P_{2}$ in $BM(X)$ can be reduced to a stationary winning strategy. Furthermore, if $P_{2}$ has a winning strategy in $BM(X)$, then $P_{2}$ has a winning strategy depending only on two preceding moves. It is still an unsettled question whether a winning strategy for $P_{2}$ can be reduced to a winning strategy that depends only on the last two moves of $P_{1}$.

• $X$ is called weakly $\alpha$-favorable if $P_{2}$ has a winning strategy in $BM(X)$. Then, $X$ is a Baire space if and only if $P_{1}$ has no winning strategy in $BM(X)$. It follows that each weakly $\alpha$-favorable space is a Baire space.

Many other modifications and specializations of the basic game have been proposed: for a thorough account of these, refer to [1987].

The most common special case arises when $Y=J=[0,1]$ and $W$ consist of all closed intervals $[a,b]\subset [0,1]$. Then $P_{1}$ wins if and only if $X\cap (\cap _{n<\omega }J_{n})\neq \emptyset$ and $P_{2}$ wins if and only if $X\cap (\cap _{n<\omega }J_{n})=\emptyset$. This game is denoted by $MB(X,J)$.

A simple proof: winning strategies

It is natural to ask for what sets $X$ does $P_{2}$ have a winning strategy. Clearly, if $X$ is empty, $P_{2}$ has a winning strategy, therefore the question can be informally rephrased as how "small" (respectively, "big") does $X$ (respectively, the complement of $X$ in $Y$) have to be to ensure that $P_{2}$ has a winning strategy. The following result gives a flavor of how the proofs used to derive the properties in the previous section work:

Proposition. $P_{2}$ has a winning strategy if $X$ is countable, $Y$ is T₁, and $Y$ has no isolated points.

Proof. Index the elements of X as a sequence: $x_{1},x_{2},\cdots$. Suppose that $W_{1}$ has been chosen by $P_{1}$, and let $U_{1}$ be the non-empty interior of $W_{1}$. Then $U_{1}\setminus \{x_{1}\}$ is a non-empty open set in $Y$, so $P_{2}$ can choose $W_{2}$ in $W$ that is contained in this set. Then $P_{1}$ chooses a subset $W_{3}$ of $W_{2}$ and, in a similar fashion, $P_{2}$ can choose a member $W_{4}\subset W_{3}$ that excludes $x_{2}$. Continuing in this way, each point $x_{n}$ will be excluded by the set $W_{2n}$, so that the intersection of all $W_{n}$ will not intersect $X$.

The assumptions on $Y$ are key to the proof: for instance, if $Y=\{a,b,c\}$ is equipped with the discrete topology and $W$ consists of all non-empty subsets of $Y$, then $P_{2}$ has no winning strategy if $X=\{a\}$ (as a matter of fact, her opponent has a winning strategy). Similar effects happen if $Y$ is equipped with indiscrete topology and $W=\{Y\}$.

A stronger result relates $X$ to first-order sets.

Proposition. $P_{2}$ has a winning strategy if and only if $X$ is meagre.

This does not imply that $P_{1}$ has a winning strategy if $X$ is not meagre. In fact, $P_{1}$ has a winning strategy if and only if there is some $W_{i}\in W$ such that $X\cap W_{i}$ is a comeagre subset of $W_{i}$. It may be the case that neither player has a winning strategy: let $Y=[0,1]$ and $W$ be the family of closed intervals $[a,b]$, the game is determined if the target set has the property of Baire, i.e. if it differs from an open set by a meagre set (but the converse is not true). Assuming the axiom of choice, there are subsets of $[0,1]$ for which the Banach–Mazur game is not determined.

References

• [1957] Oxtoby, J.C. The Banach–Mazur game and Banach category theorem, Contribution to the Theory of Games, Volume III, Annals of Mathematical Studies 39 (1957), Princeton, 159–163
• [1987] Telgársky, R. J. Topological Games: On the 50th Anniversary of the Banach–Mazur Game, Rocky Mountain J. Math. 17 (1987), pp. 227–276.[1]
• [2003] Julian P. Revalski The Banach–Mazur game: History and recent developments, Seminar notes, Pointe-a-Pitre, Guadeloupe, France, 2003–2004 [2]