Home Discussion Topics Dictionary Almanac

Signup Login

Banach–Mazur game

Discussion

Ask a question about 'Banach–Mazur game'

Start a new discussion about 'Banach–Mazur game'

Answer questions from other users

Full Discussion Forum

Encyclopedia

In general topology

General topology

In mathematics, general topology or point-set topology is the branch of topology which studies properties of topological spaces and structures defined on them...

, set theory

Set theory

Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...

and game theory

Game theory

Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...

, a Banach
Stefan Banach
Stefan Banach was a Polish mathematician who worked in interwar Poland and in Soviet Ukraine. He is generally considered to have been one of the 20th century's most important and influential mathematicians....

–Mazur
Stanislaw Mazur
Stanisław Mazur was a Polish mathematician and a member of the Polish Academy of Sciences....

game is a topological game

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 generally discrete, but the plays may have transfinite...

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 space

Baire space

In mathematics, a Baire space is a topological space which, intuitively speaking, is very large and has "enough" points for certain limit processes. It is named in honor of René-Louis Baire who introduced the concept.- Motivation :...

s. This game was the first infinite positional game

Positional game

Positional games are a class of combinatorial games. Well-known games that fall into this class include tic-tac-toe, hex and Shannon switching game....

of perfect information

Perfect information

In game theory, perfect information describes the situation when a player has available the same information to determine all of the possible games as would be available at the end of the game....

to be studied.

Definition and properties

In what follows we will make use of the formalism defined in Topological game

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 generally discrete, but the plays may have transfinite...

. A general Banach–Mazur game is defined as follows: we have a topological space

Topological space

Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...

Y

, a fixed subset

X \subset Y

, and a family

W

of subsets of

Y

that satisfy the following properties. NEWLINE

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

NEWLINE 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<\omega} W_n) \neq \emptyset

. The following properties hold. NEWLINE

$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
Baire space
In mathematics, a Baire space is a topological space which, intuitively speaking, is very large and has "enough" points for certain limit processes. It is named in honor of René-Louis Baire who introduced the concept.- Motivation :...

or meagre
Meagre set
In the mathematical fields of general topology and descriptive set theory, a meagre set is a set that, considered as a subset of a topological space, is in a precise sense small or negligible...

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 $\cap_{n<\omega} W_n \neq \emptyset$ . 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.

NEWLINE 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<\omega} J_n) \neq \emptyset

.

P_2

wins if and only if

X\cap (\cap_{n<\omega} J_n) = \emptyset

.

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 T₁
T1 space
In topology and related branches of mathematics, a T1 space is a topological space in which, for every pair of distinct points, each has an open neighborhood not containing the other. An R0 space is one in which this holds for every pair of topologically distinguishable points...

, and $Y$ has no isolated
Isolated point
In topology, a branch of mathematics, a point x of a set S is called an isolated point of S, if there exists a neighborhood of x not containing other points of S.In particular, in a Euclidean space ,...

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

Discrete space

In topology, a discrete space is a particularly simple example of a topological space or similar structure, one in which the points are "isolated" from each other in a certain sense.- Definitions :Given a set X:...

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

Trivial topology

In topology, a topological space with the trivial topology is one where the only open sets are the empty set and the entire space. Such a space is sometimes called an indiscrete space, and its topology sometimes called an indiscrete topology...

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

Meagre set

In the mathematical fields of general topology and descriptive set theory, a meagre set is a set that, considered as a subset of a topological space, is in a precise sense small or negligible...

. 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.