Banach–Mazur game

From Wikipedia, the free encyclopedia

In general topology, set theory and game theory, a Banach-Mazur 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 has been the first infinite positional game of perfect information to be studied.

[edit] Definition and properties

In what follows we will make use of the formalism defined in Topological game. A general Banach-Mazur game is defined as follows: we have a topological space Y, a fixed subset X \subset Y, and a family W of subsets of Y that satisfy the following properties.

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

We will call this game MB(X,Y,W). Two players, P1 and P2, choose alternatively elements W_0, W_1, \cdots of W such that W_0 \supset W_1 \supset \cdots. P1 wins if and only if X \cap (\cap_{n<\omega} W_n) \neq \emptyset.

The following properties hold.

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

[edit] A simple proof: winning strategies

It is natural to ask for what sets X does P2 have a winning strategy. Clearly, if X = Y, P2 has a winning strategy, therefore the question can be informally rephrased as how "big" (respectively, "small") does X (respectively, the complement of X in Y) have to be to ensure that P2 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 - P2 has a winning strategy if the complement of X in Y is countable, Y is T1, and Y has no isolated points.

Proof - Let the elements of the complement of X be x_1, x_2, \cdots. Suppose that W1 has been chosen by P1, and let U1 be the (non-empty) interior of W1. Then U_1 \setminus \{x_1\} is a non-empty open set in Y, so P2 can choose a member W2 of W contained in this set. Then P1 chooses a subset W3 of W2 and, in a similar fashion, P2 can choose a member W_4 \subset W_3 that excludes x2. Continuing in this way, each point xn will be excluded by the set W2n, so that the intersection of all the Wn will be contained in X. Q.E.D


Note that the assumptions on Y are key to the proof: for instance, if Y = {a,b,c} is equipped with the discrete topology and W consists of all non-empty subsets of Y, then P2 has no winning strategy for the co-finite set {a,b} (as a matter of fact, her opponent has a winning strategy). Similar effects happen if Y is equipped with indiscrete topology and W = {Y}. A stronger result relates the complement of 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. P2 has a winning strategy if and only if the complement of X in Y is meagre.


Note that this does not imply that P1 has a winning strategy if the complement of X in Y is not meagre. In fact, P1 has a winning strategy if and only if there is some W_i \in W \; | \; X \cap W_i is a comeager subset of Yi. It may be the case that neither player has a winning strategy: when Y is [0,1] and W consists of the closed intervals [a,b], 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).

[edit] References

[1957] Oxtoby, J.C. The Banach-Mazur game and Banach category theorem, Contribution to the Theory of Games, Volume III, Annals of Mathematical Studies 39 (1957), Princeton, 159-163

[1987] Telgársky, R. J. Topological Games: On the 50th Anniversary of the Banach-Mazur Game, Rocky Mountain J. Math. 17 (1987), pp. 227-276.[1] (3.19 MB)