Banach–Mazur game

Banach–Mazur game

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.

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, P_1 and P_2, choose alternatively elements W_0, W_1, cdots of W such that W_0 supset W_1 supset cdots. P_1 wins if and only if X cap (cap_{n.

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 P_2 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 P_2 wins a play (W_0, W_1, cdots) if and only if cup_{n. Then X is siftable if and only if P_2 has a stationary winning strategy in BM(X).

* A Markov winning strategy for P_2 in BM(X) can be reduced to a stationary winning strategy. Furthermore, if P_2 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 P_2 can be reduced to a winning strategy that depends only on the last two moves of P_1.

* X is called "weakly alpha-favorable" if P_2 has a winning strategy in BM(X). Then, X is a Baire space if and only if P_1 has no winning strategy in BM(X). It follows that each weakly alpha-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 P_1 wins if and only if X cap (cap_{n. P_2 wins if and only if cap_{n.

A simple proof: winning strategies

It is natural to ask for what sets X does P_2 have a winning strategy. Clearly, if X is empty, P_2 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 P_2 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: "P_2 has a winning strategy if X is countable, Y is T1, and Y has no isolated points."

Proof: Let the elements of X be x_1, x_2, cdots. Suppose that W_1 has been chosen by P_1, and let U_1 be the (non-empty) interior of W_1. Then U_1 setminus {x_1} is a non-empty open set in Y, so P_2 can choose a member W_2 of W contained in this set. Then P_1 chooses a subset W_3 of W_2 and, in a similar fashion, P_2 can choose a member W_4 subset W_3 that excludes x_2. Continuing in this way, each point x_n will be excluded by the set W_{2n}, so that the intersection of all the W_n will have empty intersection with X. Q.E.D

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 P_2 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 W={Y}.

A stronger result relates 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. P_2 has a winning strategy if and only if X is meagre.

This does not imply that P_1 has a winning strategy if X is not meagre. In fact, P_1 has a winning strategy if and only if there is some W_i in W such that X cap W_i is a comeagre subset of W_i. 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). Assuming the axiom of choice, there are subsets of [0,1] for which the Banach–Mazur game is not determined.

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. [http://www.telgarsky.com/papers/1987-RMJM-Telgarsky-Topological-Games.pdf] (3.19 MB)


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Topological game — A topological game is an infinite positional game of perfect information played between two players on a topological space. Players choose objects with topological properties such as points, open sets, closed sets and open coverings. Time is… …   Wikipedia

  • Stanisław Mazur — (born 1 January 1905, Lvov 5 November 1981, Warsaw) was a Polish mathematician and a member of the Polish Academy of Sciences. Mazur was a student of Stefan Banach at Lwów (now Lviv, Ukraine). His doctorate, under Banach s supervision, was… …   Wikipedia

  • Stefan Banach — Infobox Scientist name = Stefan Banach box width = image width = caption = birth date = Birth date|1892|3|30 birth place = death date = Death date|1945|8|31 death place = nationality = Polish citizenship = Austro Hungarian, Polish, Soviet Union [ …   Wikipedia

  • List of game topics — The list of game topics aims to list articles related to games.#8 bit era 16 bit era 32 bit and 64 bit era 128 bit eraAAbalone (board game) Abandonware Abstract strategy game Acquire Advanced Dungeons Dragons Advanced Squad Leader Adventure game… …   Wikipedia

  • Meagre set — In the mathematical fields of general topology and descriptive set theory, a meagre set (also called a meager set or a set of first category) is a set that, considered as a subset of a (usually larger) topological space, is in a precise sense… …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

  • Determinacy — Determined redirects here. For the 2005 heavy metal song, see Determined (song). For other uses, see Indeterminacy (disambiguation). In set theory, a branch of mathematics, determinacy is the study of under what circumstances one or the other… …   Wikipedia

  • Axiom of determinacy — The axiom of determinacy (abbreviated as AD) is a possible axiom for set theory introduced by Jan Mycielski and Hugo Steinhaus in 1962. It refers to certain two person games of length ω with perfect information. AD states that every such game in… …   Wikipedia

  • List of general topology topics — This is a list of general topology topics, by Wikipedia page. Contents 1 Basic concepts 2 Limits 3 Topological properties 3.1 Compactness and countability …   Wikipedia

  • Property of Baire — A subset A of a topological space X has the property of Baire (Baire property) if it differs from an open set by a meager set; that is, if there is an open: Usubseteq Xsuch that: ADelta Uis meager (here, Delta; denotes the symmetric… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”