# Banach-Mazur game

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

A game that appeared in the famous Scottish Book [a11], [a6], where its initial version was formulated as Problem 43 by the Polish mathematician S. Mazur: Given the space of real numbers $\mathbf{R}$ and a non-empty subset $E$ of it, two players $A$ and $B$ play a game in the following way: $A$ starts by choosing a non-empty interval $I_{0}$ of $\mathbf{R}$ and then $B$ responds by choosing a non-empty subinterval $I _ { 1 }$ of $I_{0}$. Then player $A$ in turn selects a non-empty interval $I _ { 2 } \subset I _ { 1 }$ and $B$ continues by taking a non-empty subinterval $I_3$ of $I_2$. This procedure is iterated infinitely many times. The resulting infinite sequence of nested intervals $\{ I _ { n } \} _ { n = 0 } ^ { \infty }$ is called a play. By definition, the player $A$ wins this play if the intersection $\cap _ { n = 0 } ^ { \infty } I _ {n}$ has a common point with $E$. Otherwise $B$ wins. Mazur had observed two facts:

a) if the complement of $E$ in some interval of $\mathbf{R}$ is of the first Baire category in this interval (equivalently, if $E$ is residual in some interval of $\mathbf{R}$, cf. also Category of a set; Baire classes), then player $A$ has a winning strategy (see below for the definition); and

b) if $E$ itself is of the first Baire category in $\mathbf{R}$, then $B$ has a winning strategy. The question originally posed by Mazur in Problem 43 of the Scottish Book (with as prize a bottle of wine!) was whether the inverse implications in the above two assertions hold. On August 4, 1935, S. Banach wrote in the same book that "Mazur's conjecture is true" . The proof of this statement of Banach however has never been published. The game subsequently became known as the Banach–Mazur game.

More than 20 years later, in 1957, J. Oxtoby [a8] published a proof for the validity of Mazur's conjecture. Oxtoby considered a much more general setting. The game was played in a general topological space $X$ with $\emptyset \neq E \subset X$ and the two players $A$ and $B$ were choosing alternatively sets $W _ { 0 } \supset W _ { 1 } \supset \ldots$ from an a priori prescribed family of sets $\mathcal{W}$ which has the property that every element of $\mathcal{W}$ contains a non-empty open subset of $X$ and every non-empty open subset of $X$ contains an element of $\mathcal{W}$. As above, $A$ wins if $( \cap _ { n = 0 } ^ { \infty } W _ { n } ) \cap E \neq \emptyset$, otherwise $B$ wins. Oxtoby's theorem says that $B$ has a winning strategy if and only if $E$ is of the first Baire category in $X$; also, if $X$ is a complete metric space, then $A$ has a winning strategy exactly when $E$ is residual in some non-empty open subset of $X$.

Later, the game was subjected to different generalizations and modifications.

## Generalizations.

Only the most popular modification of this game will be considered. It has turned out to be useful not only in set-theoretic topology, but also in the geometry of Banach spaces, non-linear analysis, number theory, descriptive set theory, well-posedness in optimization, etc. This modification is the following: Given a topological space $X$, two players (usually called $\alpha$ and $\beta$) alternatively choose non-empty open sets $U _ { 1 } \supset V _ { 1 } \supset U _ { 2 } \supset V _ { 2 } \supset \ldots$ (in this sequence the $U _ { n }$ are the choices of $\beta$ and the $V _ { n }$ are the choices of $\alpha$; thus, it is player $\beta$ who starts this game). Player $\alpha$ wins the play $\{ U _ { n } , V _ { n } \} _ { n = 1 } ^ { \infty }$ if $\cap _ { n = 1 } ^ { \infty } U _ { n } = \cap _ { n = 1 } ^ { \infty } V _ { n } \neq \emptyset$, otherwise $\beta$ wins. To be completely consistent with the general scheme described above, one may think that $E = X$ and $\alpha$ starts by always choosing the whole space $X$. This game is often denoted by $\operatorname{BM} ( X )$.

A strategy $s$ for the player $\alpha$ is a mapping which assigns to every finite sequence $( U _ { 1 } \supset V _ { 1 } \supset \ldots \supset U _ { n } )$ of legal moves in $\operatorname{BM} ( X )$ a non-empty open subset $V _ { n }$ of $X$ included in the last move of $\beta$ (i.e. $V _ { n } \subset U _ { n }$). A stationary strategy (called also a tactics) for $\alpha$ is a strategy for this player which depends only on the last move of the opponent. A winning strategy (a stationary winning strategy) $s$ for $\alpha$ is a strategy such that $\alpha$ wins every play in which his/her moves are obtained by $s$. Similarly one defines the (winning) strategies for $\beta$.

A topological space $X$ is called weakly $\alpha$-favourable if $\alpha$ has a winning strategy in $\operatorname{BM} ( X )$, while it is termed $\alpha$-favourable if there is a stationary winning strategy for $\alpha$ in $\operatorname{BM} ( X )$. It can be derived from the work of Oxtoby [a8] (see also [a4], [a7] and [a9]) that the space $X$ is a Baire space exactly when player $\beta$ does not have a winning strategy in $\operatorname{BM} ( X )$. Hence, every weakly $\alpha$-favourable space is a Baire space. In the class of metric spaces $X$, a metric space is weakly $\alpha$-favourable if and only if it contains a dense and completely metrizable subspace. One can use these two results to see that the Banach–Mazur game is "not determined" . I.e. it could happen for some space $X$ that neither $\alpha$ nor $\beta$ has a winning strategy. For instance, the Bernstein set $X$ in the real line (cf. also Non-measurable set) is a Baire space which does not contain a dense completely metrizable subspace (consequently $X$ does not admit a winning strategy for either $\alpha$ or $\beta$).

The above characterization of weak $\alpha$-favourability for metric spaces has been extended for some non-metrizable spaces in [a10].

A characterization of $\alpha$-favourability of a given completely-regular space $X$ can be obtained by means of the space $C ( X )$ of all continuous and bounded real-valued functions on $X$ equipped with the usual sup-norm $\| f \| _ { \infty } : = \operatorname { sup } \{ | f ( x ) | : x \in X \}$. The following statement holds [a5]: The space $X$ is weakly $\alpha$-favourable if and only if the set

\begin{equation*} \{ f \in C ( X ) : f \ \text{attains its maximum in} \ X \} \end{equation*}

is residual in $C ( X )$. In other words, $X$ is weakly $\alpha$-favourable if and only if almost-all (from the Baire category point of view) of the functions in $C ( X )$ attain their maximum in $X$. The rich interplay between $X$, $C ( X )$ and $\operatorname{BM} ( X )$ is excellently presented in [a3].

The class of $\alpha$-favourable spaces (spaces which admit $\alpha$-winning tactics) is strictly narrower than the class of weakly $\alpha$-favourable spaces. G. Debs [a2] has exhibited a completely-regular topological space $X$ which admits a winning strategy for $\alpha$ in $\operatorname{BM} ( X )$, but does not admit any $\alpha$-winning tactics in $\operatorname{BM} ( X )$. Under the name "espaces tamisables" , the $\alpha$-favourable spaces were introduced and studied also by G. Choquet [a1].

[a10] is an excellent survey paper about topological games (including $\operatorname{BM} ( X )$).

#### References

 [a1] G. Choquet, "Une classe régulières d'espaces de Baire" C.R. Acad. Sci. Paris Sér. I , 246 (1958) pp. 218–220 [a2] G. Debs, "Strategies gagnantes dans certain jeux topologique" Fundam. Math. , 126 (1985) pp. 93–105 [a3] G. Debs, J. Saint-Raymond, "Topological games and optimization problems" Mathematika , 41 (1994) pp. 117–132 [a4] M.R. Krom, "Infinite games and special Baire space extensions" Pacific J. Math. , 55 : 2 (1974) pp. 483–487 [a5] P.S. Kenderov, J.P. Revalski, "The Banach–Mazur game and generic existence of solutions to optimization problems" Proc. Amer. Math. Soc. , 118 (1993) pp. 911–917 [a6] "The Scottish Book: Mathematics from the Scottish Café" R.D. Mauldin (ed.) , Birkhäuser (1981) [a7] R.A. McCoy, "A Baire space extension" Proc. Amer. Math. Soc. , 33 (1972) pp. 199–202 [a8] J. Oxtoby, "The Banach–Mazur game and the Banach category theorem" , Contributions to the Theory of Games III , Ann. of Math. Stud. , 39 , Princeton Univ. Press (1957) pp. 159–163 [a9] J. Saint-Raymond, "Jeux topologiques et espaces de Namioka" Proc. Amer. Math. Soc. , 87 (1983) pp. 499–504 Zbl 0511.54007 [a10] R. Telgárski, "Topological games: On the fiftieth anniversary of the Banach–Mazur game" Rocky Mount. J. Math. , 17 (1987) pp. 227–276 [[ZBL|0619.90110}} [a11] S.M. Ulam, "The Scottish Book" , A LASL monograph , Los Alamos Sci. Lab. (1977) (Edition: Second)
How to Cite This Entry:
Banach-Mazur game. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Banach-Mazur_game&oldid=50395
This article was adapted from an original article by P.S. Kenderov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article