Topological game
Encyclopedia
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 lengths, and extensions to continuum time have been put forth. The conditions for a player to win can involve notions like topological closure and convergence.
It turns out that some fundamental topological constructions have a natural counterpart in topological games; examples of these are the Baire property, Baire space
s, completeness and convergence properties, separation properties, covering and base properties, continuous images, Suslin sets, and singular spaces. At the same time, some topological properties that arise naturally in topological games can be generalized beyond a game-theoretic context: by virtue of this duality, topological games have been widely used to describe new properties of topological spaces, and to put known properties under a different light.
The term topological game was first introduced by Berge,
who defined the basic ideas and formalism in analogy with topological groups. A different meaning for topological game, the concept of “topological properties defined by games”, was introduced in the paper of Rastislav Telgársky,
and later "spaces defined by topological games";
this approach is based on analogies with matrix games, differential game
s and statistical games, and defines and studies topological games within topology. After more than 35 years, the term “topological game” became widespread, and appeared in several hundreds of publications. The survey paper of Telgársky
emphasizes the origin of topological games from the Banach-Mazur game.
There are two other meanings of topological games, but these are used less frequently.
be a family of subsets of a space 
such that the following properties hold.
Furthermore, let's associate with each decreasing sequence
of subsets of 
, a family 
of subsets of 
such that:
Now, given a subset
of 
, consider the following game 
: each player chooses alternatively elements 
, enforcing that 
. Player 
wins when 
. If 
, then 
is called a smooth set.
The Sierpiński game
is a particular instance of this setup, in which 
is Euclidean, 
, and 
. It turns out that this game has interesting correlations with many topological concepts.
Many more games have been introduced over the years, to study, among others: the Kuratowski coreduction principle; separation and reduction properties of sets in close projective classes; Luzin sieves; invariant descriptive set theory; Suslin sets; the closed graph theorem
; webbed spaces; MP-spaces; the axiom of choice; recursive functions. Topological games have also been related to ideas in mathematical logic, model theory, infinitely-long formulas, infinite strings of alternating quantifiers, ultrafilter
s, partially ordered sets, and the coloring number of infinite graphs.
For a longer list and a more detailed account see the 1987 survey paper of Telgársky.
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....
played between two players on 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...
. 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 lengths, and extensions to continuum time have been put forth. The conditions for a player to win can involve notions like topological closure and convergence.
It turns out that some fundamental topological constructions have a natural counterpart in topological games; examples of these are the Baire property, 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, completeness and convergence properties, separation properties, covering and base properties, continuous images, Suslin sets, and singular spaces. At the same time, some topological properties that arise naturally in topological games can be generalized beyond a game-theoretic context: by virtue of this duality, topological games have been widely used to describe new properties of topological spaces, and to put known properties under a different light.
The term topological game was first introduced by Berge,
who defined the basic ideas and formalism in analogy with topological groups. A different meaning for topological game, the concept of “topological properties defined by games”, was introduced in the paper of Rastislav Telgársky,
and later "spaces defined by topological games";
this approach is based on analogies with matrix games, differential game
Differential game
In game theory, differential games are a group of problems related to the modeling and analysis of conflict in the context of a dynamical system. The problem usually consists of two actors, a pursuer and an evader, with conflicting goals...
s and statistical games, and defines and studies topological games within topology. After more than 35 years, the term “topological game” became widespread, and appeared in several hundreds of publications. The survey paper of Telgársky
emphasizes the origin of topological games from the Banach-Mazur game.
There are two other meanings of topological games, but these are used less frequently.
- The term topological game introduced by Leon Petrosjan in the study of antagonistic pursuit-evasionPursuit-evasionPursuit-evasion is a family of problems in mathematics and computer science in which one group attempts to track down members of another group in an environment. Early work on problems of this type modeled the environment geometrically...
games. The trajectories in these topological games are continuous in time. - The games of Nash (the Hex games), the Milnor games (Y games), the Shapley games (projective plane games), and Gale's games (Bridg-It games) were called topological games by David Gale in his invited address [1979/80]. The number of moves in these games is always finite. The discovery or rediscovery of these topological games goes back to years 1948-49.
Definitions and notation
Many frameworks can be defined for infinite positional games of perfect information. Here we use the following.- An infinite positional game between two players
and 
is defined as a pair 
where 
is a topological space with cardinality 
and 
is an upper (and/or lower) semicontinuous multivalued map assigning to each position 
a set 
of legal positions having the Vietoris topology. We assume that 
makes the first move, and we say that 
is a terminal position if 
.
- We set
, 
, and 
, where 
is a cardinal number. Furthermore, we denote with 
the closure of a subset 
of a topological space 
, and we use 
to denote the collection of all closed subsets of 
.
- A play of the game is a sequence of type
, where 
. In many analyses the following quantities are useful: 
(homeomorphic to the Cantor Discontinuum), and 
(homeomorphic to the set of irrational numbers). The result of a play is either a win or a loss for each player.
- A strategy for player
is a function defined over every legal finite sequence of moves of player 
. We denote with 
the fact that player 
has a winning strategy for 
, and we say that 
is determined if either 
or 
.
- Two games
and 
are said to be equivalent if 
.
- A strategy for
is stationary if it depends only on the last move of 
; a strategy is Markov if it depends both on the last move of 
and on the ordinal number of the move.
- Many analyses focus on the set of real numbers, and denote with
the real line, and with 
the closed unit interval.
The Sierpiński game
An illuminating example of the connections between game-theoretic notions and topological properties is the Sierpiński game. Let be a family of subsets of a space such that the following properties hold.-
;
-
.
Furthermore, let's associate with each decreasing sequence
of subsets of , a family of subsets of such that:-
;
-
.
Now, given a subset
of , consider the following game : each player chooses alternatively elements , enforcing that . Player wins when . If , then is called a smooth set.The Sierpiński game
is a particular instance of this setup, in which is Euclidean, , and . It turns out that this game has interesting correlations with many topological concepts.- If
, then 
contains a copy of the Cantor Discontinuum; if 
, then 
contains a copy of the Cantor Discontinuum.
- If
is analytic in 
, then 
; the converse has not been proven yet.
- If
contains an analytic set that is not Borel-separated from 
, then 
. This implies that, if 
is a coanalitic non-Borel subset of 
, then 
.
- The family
is closed under the Suslin operation.
Other topological games
Some other notable topological games are:- the Banach-Mazur game — the first infinite positional game of perfect information to have been studied;
- the Ulam game — a modification of the Banach-Mazur game;
- the Banach game — played on a subset of the real line;
- the ChoquetGustave ChoquetGustave Choquet was a French mathematician.Choquet was born in Solesmes, Nord. His contributions include work in functional analysis, potential theory, topology and measure theory...
game — related to siftable spaces; - the point-open game — in which
chooses points and 
chooses open neighborhoods of them.
Many more games have been introduced over the years, to study, among others: the Kuratowski coreduction principle; separation and reduction properties of sets in close projective classes; Luzin sieves; invariant descriptive set theory; Suslin sets; the closed graph theorem
Closed graph theorem
In mathematics, the closed graph theorem is a basic result in functional analysis which characterizes continuous linear operators between Banach spaces in terms of the operator graph.- The closed graph theorem :...
; webbed spaces; MP-spaces; the axiom of choice; recursive functions. Topological games have also been related to ideas in mathematical logic, model theory, infinitely-long formulas, infinite strings of alternating quantifiers, ultrafilter
Ultrafilter
In the mathematical field of set theory, an ultrafilter on a set X is a collection of subsets of X that is a filter, that cannot be enlarged . An ultrafilter may be considered as a finitely additive measure. Then every subset of X is either considered "almost everything" or "almost nothing"...
s, partially ordered sets, and the coloring number of infinite graphs.
For a longer list and a more detailed account see the 1987 survey paper of Telgársky.