Banach–Mazur game

# Banach–Mazur game

Discussion

Encyclopedia
In general topology
General topology
In mathematics, general topology or point-set topology is the branch of topology which studies properties of topological spaces and structures defined on them...

, set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...

and game theory
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...

, a Banach
Stefan Banach
Stefan Banach was a Polish mathematician who worked in interwar Poland and in Soviet Ukraine. He is generally considered to have been one of the 20th century's most important and influential mathematicians....

Mazur
Stanislaw Mazur
Stanisław Mazur was a Polish mathematician and a member of the Polish Academy of Sciences....

game
is a topological game
Topological game
A topological game is an infinite positional game of perfect information played between two players on a topological space. Players choose objects with topological properties such as points, open sets, closed sets and open coverings. Time is generally discrete, but the plays may have transfinite...

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 space
Baire space
In mathematics, a Baire space is a topological space which, intuitively speaking, is very large and has "enough" points for certain limit processes. It is named in honor of René-Louis Baire who introduced the concept.- Motivation :...

s. This game was the first infinite positional game
Positional game
Positional games are a class of combinatorial games. Well-known games that fall into this class include tic-tac-toe, hex and Shannon switching game....

of perfect information
Perfect information
In game theory, perfect information describes the situation when a player has available the same information to determine all of the possible games as would be available at the end of the game....

to be studied.

## Definition and properties

In what follows we will make use of the formalism defined in Topological game
Topological game
A topological game is an infinite positional game of perfect information played between two players on a topological space. Players choose objects with topological properties such as points, open sets, closed sets and open coverings. Time is generally discrete, but the plays may have transfinite...

. A general Banach–Mazur game is defined as follows: we have a topological space
Topological space
Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...

$Y$, a fixed subset $X \subset Y$, and a family $W$ of subsets of $Y$ that satisfy the following properties. NEWLINE
NEWLINE
• Each member of $W$ has non-empty interior.
• NEWLINE
• Each non-empty open subset of $Y$ contains a member of $W$.
NEWLINE We will call this game $MB\left(X,Y,W\right)$. Two players, $P_1$ and $P_2$, choose alternatively elements $W_0$, $W_1$, $\cdots$ of $W$ such that $W_0 \supset W_1 \supset \cdots$. $P_1$ wins if and only if $X \cap \left(\cap_\left\{n<\omega\right\} W_n\right) \neq \emptyset$. The following properties hold. NEWLINE
NEWLINE
• $P_2 \uparrow MB\left(X,Y,W\right)$ if and only if $X$ is of the first category in $Y$ (a set is of the first category
Baire space
In mathematics, a Baire space is a topological space which, intuitively speaking, is very large and has "enough" points for certain limit processes. It is named in honor of René-Louis Baire who introduced the concept.- Motivation :...

or meagre
Meagre set
In the mathematical fields of general topology and descriptive set theory, a meagre set is a set that, considered as a subset of a topological space, is in a precise sense small or negligible...

if it is the countable union of nowhere-dense sets).
• NEWLINE
• Assuming that $Y$ is a complete metric space, $P_1 \uparrow MS\left(X,Y,W\right)$ if and only if $X$ is residual in some nonempty open subset of $Y$.
• NEWLINE
• If $X$ has the Baire property in $Y$, then $MB\left(X,Y,W\right)$ is determined.
• NEWLINE
• Any winning strategy of $P_2$ can be reduced to a stationary winning strategy.
• NEWLINE
• 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\left(X\right)$ denote a modification of $MB\left(X,Y,W\right)$ where $X=Y$, $W$ is the family of all nonempty open sets in $X$, and $P_2$ wins a play $\left(W_0, W_1, \cdots\right)$ if and only if $\cap_\left\{n<\omega\right\} W_n \neq \emptyset$. Then $X$ is siftable if and only if $P_2$ has a stationary winning strategy in $BM\left(X\right)$.
• NEWLINE
• A Markov winning strategy for $P_2$ in $BM\left(X\right)$ can be reduced to a stationary winning strategy. Furthermore, if $P_2$ has a winning strategy in $BM\left(X\right)$, then she 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$.
• NEWLINE
• $X$ is called weakly $\alpha$-favorable if $P_2$ has a winning strategy in $BM\left(X\right)$. Then, $X$ is a Baire space if and only if $P_1$ has no winning strategy in $BM\left(X\right)$. It follows that each weakly $\alpha$-favorable space is a Baire space.
NEWLINE 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, called $MB\left(X,J\right)$, consists in letting $Y = J$, i.e. the unit interval $\left[0,1\right]$, and in letting $W$ consist of all closed intervals $\left[a,b\right]$ contained in $\left[0,1\right]$. The players choose alternatively subintervals $J_0, J_1, \cdots$ of $J$ such that $J_0 \supset J_1 \supset \cdots$, and $P_1$ wins if and only if $X \cap \left(\cap_\left\{n<\omega\right\} J_n\right) \neq \emptyset$. $P_2$ wins if and only if $X\cap \left(\cap_\left\{n<\omega\right\} J_n\right) = \emptyset$.

## 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. To give a flavor of how the proofs used to derive the properties in the previous section work, let us show the following fact. Fact: $P_2$ has a winning strategy if $X$ is countable, $Y$ is T1
T1 space
In topology and related branches of mathematics, a T1 space is a topological space in which, for every pair of distinct points, each has an open neighborhood not containing the other. An R0 space is one in which this holds for every pair of topologically distinguishable points...

, and $Y$ has no isolated
Isolated point
In topology, a branch of mathematics, a point x of a set S is called an isolated point of S, if there exists a neighborhood of x not containing other points of S.In particular, in a Euclidean space ,...

points.
Proof: Let the elements of $X$ be $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 \\left\{x_1\\right\}$ is a non-empty open set in $Y$, so $P_2$ can choose a member $W_2$ of $W$ 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_\left\{2n\right\}$, so that the intersection of all the $W_n$ will have empty intersection with $X$. Q.E.D The assumptions on $Y$ are key to the proof: for instance, if $Y=\\left\{a,b,c\\right\}$ is equipped with the discrete topology
Discrete space
In topology, a discrete space is a particularly simple example of a topological space or similar structure, one in which the points are "isolated" from each other in a certain sense.- Definitions :Given a set X:...

and $W$ consists of all non-empty subsets of $Y$, then $P_2$ has no winning strategy if $X=\\left\{a\\right\}$ (as a matter of fact, her opponent has a winning strategy). Similar effects happen if $Y$ is equipped with indiscrete
Trivial topology
In topology, a topological space with the trivial topology is one where the only open sets are the empty set and the entire space. Such a space is sometimes called an indiscrete space, and its topology sometimes called an indiscrete topology...

topology and $W=\\left\{Y\\right\}$. A stronger result relates $X$ to first-order sets. Fact: Let $Y$ be a topological space, let $W$ be a family of subsets of $Y$ satisfying the two properties above, and let $X$ be any subset of $Y$. $P_2$ has a winning strategy if and only if $X$ is meagre
Meagre set
In the mathematical fields of general topology and descriptive set theory, a meagre set is a set that, considered as a subset of a topological space, is in a precise sense small or negligible...

. 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: when $Y$ is $\left[0,1\right]$ and $W$ consists of the closed intervals $\left[a,b\right]$, 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 $\left[0,1\right]$ for which the Banach–Mazur game is not determined.