Namespaces
Variants
Actions

Banach-Mazur game

From Encyclopedia of Mathematics
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