Topological game

Last updated December 29, 2023

In mathematics, a topological game is an infinite 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 spaces, 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. There are also close links with selection principles.

The term topological game was first introduced by Claude Berge,^[1]^[2]^[3] 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,^[4] and later "spaces defined by topological games";^[5] this approach is based on analogies with matrix games, differential games 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^[6] 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 ^[7] in the study of antagonistic pursuit–evasion 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.

Basic setup for a topological game

Many frameworks can be defined for infinite positional games 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 nth 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₀, J₀, I₁, J₁,...

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 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 other than ω.

Definitions and notation

A play of the game is a sequence of legal moves

I₀, J₀, I₁, J₁,...

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₀, J₁, ..., 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 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 Markov 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 _{n\in \omega }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 or meagre if it is the countable union of nowhere-dense sets).
If Y is a complete metric space, then I has a winning strategy if and only if X is comeagre in some nonempty open subset of Y.
If X has the property of Baire in Y, then the game is determined.

Other topological games

Some other notable topological games are:

the binary game introduced by Ulam — 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 and player II chooses open neighborhoods of them;
selection games — each round player I chooses a (topological) collection and II chooses a member or finite subset of that collection. See Selection principle § Topological games.

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; computable functions. Topological games have also been related to ideas in mathematical logic, model theory, infinitely-long formulas, infinite strings of alternating quantifiers, ultrafilters, partially ordered sets, and the chromatic number of infinite graphs.

For a longer list and a more detailed account see the 1987 survey paper of Telgársky.^[6]

Related Research Articles

In mathematics, more specifically in functional analysis, a Banach space is a complete normed vector space. Thus, a Banach space is a vector space with a metric that allows the computation of vector length and distance between vectors and is complete in the sense that a Cauchy sequence of vectors always converges to a well-defined limit that is within the space.

<span class="mw-page-title-main">Compact space</span> Type of mathematical space

In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space. The idea is that a compact space has no "punctures" or "missing endpoints", i.e., it includes all limiting values of points. For example, the open interval (0,1) would not be compact because it excludes the limiting values of 0 and 1, whereas the closed interval [0,1] would be compact. Similarly, the space of rational numbers $is not compact, because it has infinitely many "punctures" corresponding to the irrational numbers, and the space of real numbers is not compact either, because it excludes the two limiting values and . However, the extended real number line would be compact, since it contains both infinities. There are many ways to make this heuristic notion precise. These ways usually agree in a metric space, but may not be equivalent in other topological spaces.$

The Hahn–Banach theorem is a central tool in functional analysis. It allows the extension of bounded linear functionals defined on a vector subspace of some vector space to the whole space, and it also shows that there are "enough" continuous linear functionals defined on every normed vector space to make the study of the dual space "interesting". Another version of the Hahn–Banach theorem is known as the Hahn–Banach separation theorem or the hyperplane separation theorem, and has numerous uses in convex geometry.

In mathematics, a topological space is called separable if it contains a countable, dense subset; that is, there exists a sequence $of elements of the space such that every nonempty open subset of the space contains at least one element of the sequence.$

In mathematics, a topological vector space is one of the basic structures investigated in functional analysis. A topological vector space is a vector space that is also a topological space with the property that the vector space operations are also continuous functions. Such a topology is called a vector topology and every topological vector space has a uniform topological structure, allowing a notion of uniform convergence and completeness. Some authors also require that the space is a Hausdorff space. One of the most widely studied categories of TVSs are locally convex topological vector spaces. This article focuses on TVSs that are not necessarily locally convex. Banach spaces, Hilbert spaces and Sobolev spaces are other well-known examples of TVSs.

The Baire category theorem (BCT) is an important result in general topology and functional analysis. The theorem has two forms, each of which gives sufficient conditions for a topological space to be a Baire space. It is used in the proof of results in many areas of analysis and geometry, including some of the fundamental theorems of functional analysis.

In the area of mathematics known as functional analysis, a reflexive space is a locally convex topological vector space (TVS) for which the canonical evaluation map from $into its bidual is an isomorphism of TVSs. Since a normable TVS is reflexive if and only if it is semi-reflexive, every normed space is reflexive if and only if the canonical evaluation map from into its bidual is surjective; in this case the normed space is necessarily also a Banach space. In 1951, R. C. James discovered a Banach space, now known as James' space, that is not reflexive but is nevertheless isometrically isomorphic to its bidual.$

In the mathematical field of general topology, a meagre set 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 nonmeagre, or of the second category. See below for definitions of other related terms.

In functional analysis and related areas of mathematics, Fréchet spaces, named after Maurice Fréchet, are special topological vector spaces. They are generalizations of Banach spaces. All Banach and Hilbert spaces are Fréchet spaces. Spaces of infinitely differentiable functions are typical examples of Fréchet spaces, many of which are typically not Banach spaces.

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

In mathematics, the axiom of determinacy is a possible axiom for set theory introduced by Jan Mycielski and Hugo Steinhaus in 1962. It refers to certain two-person topological games of length ω. AD states that every game of a certain type is determined; that is, one of the two players has a winning strategy.

In topology and related branches of mathematics, total-boundedness is a generalization of compactness for circumstances in which a set is not necessarily closed. A totally bounded set can be covered by finitely many subsets of every fixed “size”.

In functional analysis and related areas of mathematics, a sequence space is a vector space whose elements are infinite sequences of real or complex numbers. Equivalently, it is a function space whose elements are functions from the natural numbers to the field K of real or complex numbers. The set of all such functions is naturally identified with the set of all possible infinite sequences with elements in K, and can be turned into a vector space under the operations of pointwise addition of functions and pointwise scalar multiplication. All sequence spaces are linear subspaces of this space. Sequence spaces are typically equipped with a norm, or at least the structure of a topological vector space.

Determinacy is a subfield of set theory, a branch of mathematics, that examines the conditions under which one or the other player of a game has a winning strategy, and the consequences of the existence of such strategies. Alternatively and similarly, "determinacy" is the property of a game whereby such a strategy exists. Determinacy was introduced by Gale and Stewart in 1950, under the name "determinateness".

In mathematical analysis, the Kakutani fixed-point theorem is a fixed-point theorem for set-valued functions. It provides sufficient conditions for a set-valued function defined on a convex, compact subset of a Euclidean space to have a fixed point, i.e. a point which is mapped to a set containing it. The Kakutani fixed point theorem is a generalization of the Brouwer fixed point theorem. The Brouwer fixed point theorem is a fundamental result in topology which proves the existence of fixed points for continuous functions defined on compact, convex subsets of Euclidean spaces. Kakutani's theorem extends this to set-valued functions.

In mathematics, nuclear spaces are topological vector spaces that can be viewed as a generalization of finite dimensional Euclidean spaces and share many of their desirable properties. Nuclear spaces are however quite different from Hilbert spaces, another generalization of finite dimensional Euclidean spaces. They were introduced by Alexander Grothendieck.

In mathematics, the binary game is a topological game introduced by Stanisław Ulam in 1935 in an addendum to problem 43 of the Scottish book as a variation of the Banach–Mazur game.

In mathematics, the Banach game is a topological game introduced by Stefan Banach in 1935 in the second addendum to problem 43 of the Scottish book as a variation of the Banach–Mazur game.

<span class="mw-page-title-main">Selection principle</span> Rule in mathematics

In mathematics, a selection principle is a rule asserting the possibility of obtaining mathematically significant objects by selecting elements from given sequences of sets. The theory of selection principles studies these principles and their relations to other mathematical properties. Selection principles mainly describe covering properties, measure- and category-theoretic properties, and local properties in topological spaces, especially function spaces. Often, the characterization of a mathematical property using a selection principle is a nontrivial task leading to new insights on the characterized property.

This is a glossary for the terminology in a mathematical field of functional analysis.

References

↑ C. Berge, Topological games with perfect information. Contributions to the theory of games, vol. 3, 165–178. Annals of Mathematics Studies, no. 39. Princeton University Press, Princeton, N. J., 1957.
↑ C. Berge, Théorie des jeux à n personnes, Mém. des Sc. Mat., Gauthier-Villars, Paris 1957.
↑ A. R. Pears, On topological games, Proc. Cambridge Philos. Soc. 61 (1965), 165–171.
↑ R. Telgársky, On topological properties defined by games, Topics in Topology (Proc. Colloq. Keszthely 1972), Colloq. Math. Soc. János Bolyai, Vol. 8, North-Holland, Amsterdam 1974, 617–624.
↑ R. Telgársky, Spaces defined by topological games, Fund. Math. 88 (1975), 193–223.
1 2 R. Telgársky, "Topological Games: On the 50th Anniversary of the Banach-Mazur Game", Rocky Mountain J. Math. 17 (1987), 227–276.
↑ L. A. Petrosjan, Topological games and their applications to pursuit problems. I. SIAM J. Control 10 (1972), 194–202.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] C. Berge, Topological games with perfect information. Contributions to the theory of games, vol. 3, 165–178. Annals of Mathematics Studies, no. 39. Princeton University Press, Princeton, N. J., 1957.

[2] C. Berge, Théorie des jeux à n personnes, Mém. des Sc. Mat., Gauthier-Villars, Paris 1957.

[3] A. R. Pears, On topological games, Proc. Cambridge Philos. Soc. 61 (1965), 165–171.

[4] R. Telgársky, On topological properties defined by games, Topics in Topology (Proc. Colloq. Keszthely 1972), Colloq. Math. Soc. János Bolyai, Vol. 8, North-Holland, Amsterdam 1974, 617–624.

[5] R. Telgársky, Spaces defined by topological games, Fund. Math. 88 (1975), 193–223.

[Telgarsky-1987-6] 1 2 R. Telgársky, "Topological Games: On the 50th Anniversary of the Banach-Mazur Game", Rocky Mountain J. Math. 17 (1987), 227–276.

[7] L. A. Petrosjan, Topological games and their applications to pursuit problems. I. SIAM J. Control 10 (1972), 194–202.

[1]

[2]

[3]

[4]

[5]

[6]

[7]