View source for Banach-Mazur game

A game that appeared in the famous Scottish Book [[#References|[a11]]], [[#References|[a6]]], where its initial version was formulated as Problem 43 by the Polish mathematician S. Mazur: Given the space of real numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b1300401.png" /> and a non-empty subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b1300402.png" /> of it, two players <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b1300403.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b1300404.png" /> play a game in the following way: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b1300405.png" /> starts by choosing a non-empty interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b1300406.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b1300407.png" /> and then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b1300408.png" /> responds by choosing a non-empty subinterval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b1300409.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004010.png" />. Then player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004011.png" /> in turn selects a non-empty interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004012.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004013.png" /> continues by taking a non-empty subinterval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004014.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004015.png" />. This procedure is iterated infinitely many times. The resulting infinite sequence of nested intervals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004016.png" /> is called a play. By definition, the player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004017.png" /> wins this play if the intersection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004018.png" /> has a common point with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004019.png" />. Otherwise <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004020.png" /> wins. Mazur had observed two facts:

a) if the complement of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004021.png" /> in some interval of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004022.png" /> is of the first Baire category in this interval (equivalently, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004023.png" /> is residual in some interval of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004024.png" />, cf. also [[Category of a set|Category of a set]]; [[Baire classes|Baire classes]]), then player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004025.png" /> has a winning strategy (see below for the definition); and

b) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004026.png" /> itself is of the first Baire category in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004027.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004028.png" /> 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 [[#References|[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|topological space]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004029.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004030.png" /> and the two players <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004031.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004032.png" /> were choosing alternatively sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004033.png" /> from an a priori prescribed family of sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004034.png" /> which has the property that every element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004035.png" /> contains a non-empty open subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004036.png" /> and every non-empty open subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004037.png" /> contains an element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004038.png" />. As above, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004039.png" /> wins if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004040.png" />, otherwise <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004041.png" /> wins. Oxtoby's theorem says that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004042.png" /> has a winning strategy if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004043.png" /> is of the first Baire category in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004044.png" />; also, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004045.png" /> is a [[Complete metric space|complete metric space]], then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004046.png" /> has a winning strategy exactly when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004047.png" /> is residual in some non-empty open subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004048.png" />.

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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004049.png" />, two players (usually called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004050.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004051.png" />) alternatively choose non-empty open sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004052.png" /> (in this sequence the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004053.png" /> are the choices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004054.png" /> and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004055.png" /> are the choices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004056.png" />; thus, it is player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004057.png" /> who starts this game). Player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004058.png" /> wins the play <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004059.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004060.png" />, otherwise <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004061.png" /> wins. To be completely consistent with the general scheme described above, one may think that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004062.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004063.png" /> starts by always choosing the whole space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004064.png" />. This game is often denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004065.png" />.

A strategy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004066.png" /> for the player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004067.png" /> is a mapping which assigns to every finite sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004068.png" /> of legal moves in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004069.png" /> a non-empty open subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004070.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004071.png" /> included in the last move of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004072.png" /> (i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004073.png" />). A stationary strategy (called also a tactics) for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004074.png" /> is a strategy for this player which depends only on the last move of the opponent. A winning strategy (a stationary winning strategy) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004075.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004076.png" /> is a strategy such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004077.png" /> wins every play in which his/her moves are obtained by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004078.png" />. Similarly one defines the (winning) strategies for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004079.png" />.

A topological space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004080.png" /> is called weakly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004082.png" />-favourable if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004083.png" /> has a winning strategy in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004084.png" />, while it is termed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004086.png" />-favourable if there is a stationary winning strategy for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004087.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004088.png" />. It can be derived from the work of Oxtoby [[#References|[a8]]] (see also [[#References|[a4]]], [[#References|[a7]]] and [[#References|[a9]]]) that the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004089.png" /> is a [[Baire space|Baire space]] exactly when player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004090.png" /> does not have a winning strategy in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004091.png" />. Hence, every weakly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004092.png" />-favourable space is a Baire space. In the class of metric spaces <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004093.png" />, a metric space is weakly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004094.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004095.png" /> that neither <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004096.png" /> nor <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004097.png" /> has a winning strategy. For instance, the Bernstein set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004098.png" /> in the real line (cf. also [[Non-measurable set|Non-measurable set]]) is a Baire space which does not contain a dense completely metrizable subspace (consequently <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004099.png" /> does not admit a winning strategy for either <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040100.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040101.png" />).

The above characterization of weak <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040102.png" />-favourability for metric spaces has been extended for some non-metrizable spaces in [[#References|[a10]]].

A characterization of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040103.png" />-favourability of a given [[Completely-regular space|completely-regular space]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040104.png" /> can be obtained by means of the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040105.png" /> of all continuous and bounded real-valued functions on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040106.png" /> equipped with the usual sup-norm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040107.png" />. The following statement holds [[#References|[a5]]]: The space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040108.png" /> is weakly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040109.png" />-favourable if and only if the set

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040110.png" /></td> </tr></table>

is residual in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040111.png" />. In other words, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040112.png" /> is weakly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040113.png" />-favourable if and only if almost-all (from the Baire category point of view) of the functions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040114.png" /> attain their maximum in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040115.png" />. The rich interplay between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040116.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040117.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040118.png" /> is excellently presented in [[#References|[a3]]].

The class of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040119.png" />-favourable spaces (spaces which admit <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040120.png" />-winning tactics) is strictly narrower than the class of weakly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040121.png" />-favourable spaces. G. Debs [[#References|[a2]]] has exhibited a completely-regular topological space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040122.png" /> which admits a winning strategy for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040123.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040124.png" />, but does not admit any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040125.png" />-winning tactics in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040126.png" />. Under the name  "espaces tamisables" , the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040127.png" />-favourable spaces were introduced and studied also by G. Choquet [[#References|[a1]]].

[[#References|[a10]]] is an excellent survey paper about topological games (including <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040128.png" />).

====References====
<table>
<TR><TD valign="top">[a1]</TD> <TD valign="top">  G. Choquet,   "Une classe régulières d'espaces de Baire"  ''C.R. Acad. Sci. Paris Sér. I'' , '''246'''  (1958)  pp. 218–220</TD></TR>
<TR><TD valign="top">[a2]</TD> <TD valign="top">  G. Debs,   "Strategies gagnantes dans certain jeux topologique"  ''Fundam. Math.'' , '''126'''  (1985)  pp. 93–105</TD></TR>
<TR><TD valign="top">[a3]</TD> <TD valign="top">  G. Debs,   J. Saint-Raymond,   "Topological games and optimization problems"  ''Mathematika'' , '''41'''  (1994)  pp. 117–132</TD></TR>
<TR><TD valign="top">[a4]</TD> <TD valign="top">  M.R. Krom,   "Infinite games and special Baire space extensions"  ''Pacific J. Math.'' , '''55''' :  2  (1974)  pp. 483–487</TD></TR>
<TR><TD valign="top">[a5]</TD> <TD valign="top">  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</TD>
</TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  "The Scottish Book: Mathematics from the Scottish Café"  R.D. Mauldin (ed.) , Birkhäuser  (1981)</TD></TR>
<TR><TD valign="top">[a7]</TD> <TD valign="top">  R.A. McCoy,   "A Baire space extension"  ''Proc. Amer. Math. Soc.'' , '''33'''  (1972)  pp. 199–202</TD></TR>
<TR><TD valign="top">[a8]</TD> <TD valign="top">  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</TD></TR>
<TR><TD valign="top">[a9]</TD> <TD valign="top">  J. Saint-Raymond,   "Jeux topologiques et espaces de Namioka"  ''Proc. Amer. Math. Soc.'' , '''87'''  (1983)  pp. 499–504  {{MR|}} {{ZBL|0511.54007}} </TD></TR>
<TR><TD valign="top">[a10]</TD> <TD valign="top">  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}}</TD></TR>
<TR><TD valign="top">[a11]</TD> <TD valign="top">  S.M. Ulam,   "The Scottish Book" , ''A LASL monograph'' , Los Alamos Sci. Lab.  (1977)  (Edition: Second)</TD></TR>
</table>