HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, a topological game is an infinite game of
perfect information Perfect information is a concept in game theory and economics that describes a situation where all players in a game or all participants in a market have knowledge of all relevant information in the system. This is different than complete informat ...
played between two players on a
topological space In mathematics, a topological space is, roughly speaking, a Geometry, geometrical space in which Closeness (mathematics), closeness is defined but cannot necessarily be measured by a numeric Distance (mathematics), distance. More specifically, a to ...
. Players choose objects with topological properties such as points,
open sets In mathematics, an open set is a generalization of an open interval in the real line. In a metric space (a set with a distance defined between every two points), an open set is a set that, with every point in it, contains all points of the metr ...
,
closed sets In geometry, topology, and related branches of mathematics, a closed set is a set whose complement is an open set. In a topological space, a closed set can be defined as a set which contains all its limit points. In a complete metric space, a ...
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 In topology, the closure of a subset of points in a topological space consists of all points in together with all limit points of . The closure of may equivalently be defined as the union of and its boundary, and also as the intersection ...
and
convergence Convergence may refer to: Arts and media Literature *''Convergence'' (book series), edited by Ruth Nanda Anshen *Convergence (comics), "Convergence" (comics), two separate story lines published by DC Comics: **A four-part crossover storyline that ...
. It turns out that some fundamental topological constructions have a natural counterpart in topological games; examples of these are the Baire property,
Baire space In mathematics, a topological space X is said to be a Baire space if countable unions of closed sets with empty interior also have empty interior. According to the Baire category theorem, compact Hausdorff spaces and complete metric spaces are ...
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 Game theory is the study of mathematical models of strategic interactions. It has applications in many fields of social science, and is used extensively in economics, logic, systems science and computer science. Initially, game theory addressed ...
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. There are also close links with
selection principle In mathematics, a selection principle is a rule asserting the possibility of obtaining mathematically significant objects by selecting elements from given sequences of Set (mathematics), sets. The theory of selection principles studies these pri ...
s. The term ''topological game'' was first introduced by
Claude Berge Claude Jacques Berge (5 June 1926 – 30 June 2002) was a French mathematician, recognized as one of the modern founders of combinatorics and graph theory. Biography and professional history Claude Berge's parents were André Berge and Genevièv ...
, who defined the basic ideas and formalism in analogy with
topological group In mathematics, topological groups are the combination of groups and topological spaces, i.e. they are groups and topological spaces at the same time, such that the continuity condition for the group operations connects these two structures ...
s. 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 In game theory, differential games are dynamic games that unfold in continuous time, meaning players’ actions and outcomes evolve smoothly rather than in discrete steps, and for which the rate of change of each state variable—like position, spe ...
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 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 spa ...
. 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–evasion Pursuit–evasion (variants of which are referred to as cops and robbers and graph searching) 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 ...
games. The trajectories in these topological games are continuous in time. * The games of Nash (the Hex games), the
Milnor John Willard Milnor (born February 20, 1931) is an American mathematician known for his work in differential topology, algebraic K-theory and low-dimensional holomorphic dynamical systems. Milnor is a distinguished professor at Stony Brook Univ ...
games (Y games), the
Shapley Shapley is a surname that might refer to one of the following: * Lieutenant General Alan Shapley (1903–1973), of the U.S. Marine Corps, was a survivor the sinking of the USS Arizona in the attack on Pearl Harbor * Harlow Shapley (1885–1972), Am ...
games (projective plane games), and Gale's games (
Bridg-It The Shannon switching game is a connection game for two players, invented by American mathematician and electrical engineer Claude Shannon, the "father of information theory", some time before 1951. Two players take turns coloring the edges of a ...
games) were called ''topological games'' by
David Gale David Gale (December 13, 1921 – March 7, 2008) was an American mathematician and economist. He was a professor emeritus at the University of California, Berkeley, affiliated with the departments of mathematics, economics, and industrial ...
in his invited address 979/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.


Basic setup for a topological game

Many frameworks can be defined for infinite
positional game A positional game in game theory is a kind of a combinatorial game for two players. It is described by: *Xa finite set of elements. Often ''X'' is called the ''board'' and its elements are called ''positions''. *\mathcala family of subsets of ...
s of perfect information. The typical setup is a game between two players, I and II, who alternately pick subsets of a topological space ''X''. In the ''n''th round, player I plays a subset ''I''''n'' of ''X'', and player II responds with a subset ''J''''n''. There is a round for every natural number ''n'', and after all rounds are played, player I wins if the sequence : ''I''0, ''J''0, ''I''1, ''J''1,... satisfies some property, and otherwise player II wins. The game is defined by the target property and the allowed moves at each step. For example, in the
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 spa ...
''BM''(''X''), the allowed moves are nonempty open subsets of the previous move, and player I wins if \bigcap_n I_n \neq \emptyset. This typical setup can be modified in various ways. For example, instead of being a subset of ''X'', each move might consist of a pair (I, p) where I \subseteq X and p \in x. Alternatively, the sequence of moves might have length some
ordinal number In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets. A finite set can be enumerated by successively labeling each element with the leas ...
other than ω.


Definitions and notation

* A ''play'' of the game is a sequence of legal moves :: ''I''0, ''J''0, ''I''1, ''J''1,... : The ''result of a play'' is either a win or a loss for each player. * A ''strategy'' for player P is a function defined over every legal finite sequence of moves of P's opponent. For example, a strategy for player I is a function ''s'' from sequences (''J''0, ''J''1, ..., ''J''''n'') to subsets of ''X''. A game is said to be played ''according to strategy s'' if every player P move is the value of ''s'' on the sequence of their opponent's prior moves. So if ''s'' is a strategy for player I, the play :: s(\lambda), J_0, s(J_0), J_1, s(J_0, J_1), J_2, s(J_0, J_1, J_2), \ldots : is ''according to strategy s''. (Here λ denotes the empty sequence of moves.) * A strategy for player P is said to be ''winning'' if for every play according to strategy ''s'' results in a win for player P, for any sequence of legal moves by P's opponent. If player P has a winning strategy for game ''G'', this is denoted P \uparrow G. If either player has a winning strategy for ''G'', then ''G'' is said to be ''determined.'' It follows from the
axiom of choice In mathematics, the axiom of choice, abbreviated AC or AoC, is an axiom of set theory. Informally put, the axiom of choice says that given any collection of non-empty sets, it is possible to construct a new set by choosing one element from e ...
that there are non-determined topological games. * A strategy for P is ''stationary'' if it depends only on the last move by P's opponent; a strategy is ' if it depends both on the last move of the opponent ''and'' on the ordinal number of the move.


The Banach–Mazur game

The first topological game studied was the Banach–Mazur game, which is a motivating example of the connections between game-theoretic notions and topological properties. Let ''Y'' be a topological space, and let ''X'' be a subset of ''Y'', called the ''winning set''. Player I begins the game by picking a nonempty open subset I_0 \subseteq Y, and player II responds with a nonempty open subset J_0 \subseteq I_0. Play continues in this fashion, with players alternately picking a nonempty open subset of the previous play. After an infinite sequence of moves, one for each natural number, the game is finished, and I wins if and only if : X \cap \bigcap_ I_n \neq \emptyset. The game-theoretic and topological connections demonstrated by the game include: * II has a winning strategy in the game if and only if ''X'' is of the ''first category'' in ''Y'' (a set is of the
first category In the mathematical field of general topology, a meagre set (also called a meager set or a set of first category) is a subset of a topological space that is small or negligible in a precise sense detailed below. A set that is not meagre is called ...
or meagre if it is the countable union of
nowhere-dense set In mathematics, a subset of a topological space is called nowhere dense or rare if its closure has empty interior. In a very loose sense, it is a set whose elements are not tightly clustered (as defined by the topology on the space) anywhere. ...
s). * If ''Y'' is a
complete metric space In mathematical analysis, a metric space is called complete (or a Cauchy space) if every Cauchy sequence of points in has a limit that is also in . Intuitively, a space is complete if there are no "points missing" from it (inside or at the bou ...
, then I has a winning strategy if and only if ''X'' is
comeagre In the mathematical field of general topology, a meagre set (also called a meager set or a set of first category) is a subset of a topological space that is small or negligible in a precise sense detailed below. A set that is not meagre is called ...
in some nonempty open subset of ''Y''. * If ''X'' has the
property of Baire A subset A of a topological space X has the property of Baire (Baire property, named after René-Louis Baire), or is called an almost open set, if it differs from an open set by a meager set; that is, if there is an open set U\subseteq X such tha ...
in ''Y'', then the game is determined.


Other topological games

Some other notable topological games are: * the binary game introduced by
Ulam Ulam may refer to: * ULAM, the ICAO airport code for Naryan-Mar Airport, Russia * Ulam (surname) * Ulam (salad), a type of Malay salad * ''Ulam'', a Filipino term loosely translated to viand or side dish; see Tapa (Filipino cuisine) * Ulam, the ...
— a modification of the Banach–Mazur game; * the Banach game — played on a subset of the real line; * the Choquet game — related to siftable spaces; * the point-open game — in which player I chooses
points A point is a small dot or the sharp tip of something. Point or points may refer to: Mathematics * Point (geometry), an entity that has a location in space or on a plane, but has no extent; more generally, an element of some abstract topologica ...
and player II chooses
open neighborhood In topology and related areas of mathematics, a neighbourhood (or neighborhood) is one of the basic concepts in a topological space. It is closely related to the concepts of open set and interior. Intuitively speaking, a neighbourhood of a po ...
s of them; * selection games — each round player I chooses a (topological) collection and II chooses a member or finite subset of that collection. See . Many more games have been introduced over the years, to study, among others: the
Kuratowski Kazimierz Kuratowski (; 2 February 1896 – 18 June 1980) was a Polish mathematician and logician. He was one of the leading representatives of the Warsaw School of Mathematics. He worked as a professor at the University of Warsaw and at the Math ...
coreduction principle; separation and reduction properties of sets in close projective classes; Luzin sieves; invariant
descriptive set theory In mathematical logic, descriptive set theory (DST) is the study of certain classes of "well-behaved" set (mathematics), subsets of the real line and other Polish spaces. As well as being one of the primary areas of research in set theory, it has a ...
;
Suslin set In mathematics, a Suslin representation of a set of reals (more precisely, elements of Baire space) is a tree whose projection is that set of reals. More generally, a subset ''A'' of ''κ''ω is ''λ''-Suslin if there is a tree ''T'' on ''κ'' × ...
s; the
closed graph theorem In mathematics, the closed graph theorem may refer to one of several basic results characterizing continuous functions in terms of their graphs. Each gives conditions when functions with closed graphs are necessarily continuous. A blog post by ...
;
webbed space In mathematics, particularly in functional analysis, a webbed space is a topological vector space designed with the goal of allowing the results of the open mapping theorem and the closed graph theorem to hold for a wider class of linear maps whos ...
s; MP-spaces; the
axiom of choice In mathematics, the axiom of choice, abbreviated AC or AoC, is an axiom of set theory. Informally put, the axiom of choice says that given any collection of non-empty sets, it is possible to construct a new set by choosing one element from e ...
;
computable function Computable functions are the basic objects of study in computability theory. Informally, a function is ''computable'' if there is an algorithm that computes the value of the function for every value of its argument. Because of the lack of a precis ...
s. Topological games have also been related to ideas in
mathematical logic Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...
,
model theory In mathematical logic, model theory is the study of the relationship between theory (mathematical logic), formal theories (a collection of Sentence (mathematical logic), sentences in a formal language expressing statements about a Structure (mat ...
, infinitely-long formulas, infinite strings of alternating quantifiers,
ultrafilter In the Mathematics, mathematical field of order theory, an ultrafilter on a given partially ordered set (or "poset") P is a certain subset of P, namely a Maximal element, maximal Filter (mathematics), filter on P; that is, a proper filter on P th ...
s,
partially ordered sets In mathematics, especially order theory, a partial order on a set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements needs to be comparable; ...
, and the
chromatic number In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...
of infinite graphs. For a longer list and a more detailed account see the 1987 survey paper of Telgársky.


See also

* Topological puzzle


References

{{reflist General topology Game theory