Banach–Mazur game

From HandWiki

In general topology, set theory and game theory like [tiny fishing unblocked], 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 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

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

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

Players, P1 and P2 alternately choose elements from 𝒲 to form a sequence W0W1.

P1 wins if and only if

X(n<ωWn).

Otherwise, P2 wins. This is called a general Banach–Mazur game and denoted by MB(X,Y,𝒲).

Properties

  • P2 has a winning strategy 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).
  • If Y is a complete metric space, P1 has a winning strategy if and only if X is comeager in some non-empty open subset of Y.
  • If X has the Baire property in Y, then MB(X,Y,𝒲) 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 BM(X) denote a modification of MB(X,Y,𝒲) where X=Y,𝒲 is the family of all non-empty open sets in X and P2 wins a play (W0,W1,) if and only if
n<ωWn.
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 P2 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 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 arises when Y=J=[0,1] and 𝒲 consist of all closed intervals in the unit interval. Then P1 wins if and only if X(n<ωJn) and P2 wins if and only if X(n<ωJn)=. This game is denoted by MB(X,J).

A simple proof: winning strategies

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

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

A stronger result relates X to first-order sets.

Proposition. P2 has a winning strategy in MB(X,Y,𝒲) if and only if X is meagre.

This does not imply that P1 has a winning strategy if X is not meagre. In fact, if Y is a complete metric space, then P1 has a winning strategy if and only if there is some Wi𝒲 such that XWi is a comeagre subset of Wi. It may be the case that neither player has a winning strategy: let Y 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

References