Banach–Mazur game

(Redirected from Banach-Mazur game)

In general topology, set theory and game theory, a BanachMazur 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 Stanisław Mazur as problem 43 in the Scottish book, and Mazur's questions about it were answered by Banach.

Definition

edit

Let   be a non-empty topological space,   a fixed subset of   and   a family of subsets of   that have the following properties:

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

Players,   and   alternately choose elements from   to form a sequence  

  wins if and only if

 

Otherwise,   wins. This is called a general Banach–Mazur game and denoted by  

Properties

edit
  •   has a winning strategy if and only if   is of the first category in   (a set is of the first category or meagre if it is the countable union of nowhere-dense sets).
  • If   is a complete metric space,   has a winning strategy if and only if   is comeager in some non-empty open subset of  
  • If   has the Baire property in  , then   is determined.
  • The siftable and strongly-siftable spaces introduced by Choquet can be defined in terms of stationary strategies in suitable modifications of the game. Let   denote a modification of   where   is the family of all non-empty open sets in   and   wins a play   if and only if
 
Then   is siftable if and only if   has a stationary winning strategy in  
  • A Markov winning strategy for   in   can be reduced to a stationary winning strategy. Furthermore, if   has a winning strategy in  , then   has a winning strategy depending only on two preceding moves. It is still an unsettled question whether a winning strategy for   can be reduced to a winning strategy that depends only on the last two moves of  .
  •   is called weakly  -favorable if   has a winning strategy in  . Then,   is a Baire space if and only if   has no winning strategy in  . It follows that each weakly  -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   and   consist of all closed intervals in the unit interval. Then   wins if and only if   and   wins if and only if  . This game is denoted by  

A simple proof: winning strategies

edit

It is natural to ask for what sets   does   have a winning strategy in  . Clearly, if   is empty,   has a winning strategy, therefore the question can be informally rephrased as how "small" (respectively, "big") does   (respectively, the complement of   in  ) have to be to ensure that   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.   has a winning strategy in   if   is countable,   is T1, and   has no isolated points.
Proof. Index the elements of X as a sequence:   Suppose   has chosen   if   is the non-empty interior of   then   is a non-empty open set in   so   can choose   Then   chooses   and, in a similar fashion,   can choose   that excludes  . Continuing in this way, each point   will be excluded by the set   so that the intersection of all   will not intersect  .

The assumptions on   are key to the proof: for instance, if   is equipped with the discrete topology and   consists of all non-empty subsets of  , then   has no winning strategy if   (as a matter of fact, her opponent has a winning strategy). Similar effects happen if   is equipped with indiscrete topology and  

A stronger result relates   to first-order sets.

Proposition.   has a winning strategy in   if and only if   is meagre.

This does not imply that   has a winning strategy if   is not meagre. In fact, if   is a complete metric space, then   has a winning strategy if and only if there is some   such that   is a comeagre subset of   It may be the case that neither player has a winning strategy: let   be the unit interval and   be the family of closed intervals in the unit interval. 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 the unit interval for which the Banach–Mazur game is not determined.

See also

edit

References

edit
edit
  • "Banach–Mazur game", Encyclopedia of Mathematics, EMS Press, 2001 [1994]