Topological game

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.

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 In of X, and player II responds with a subset Jn. There is a round for every natural number n, and after all rounds are played, player I wins if the sequence

I0, J0, I1, J1,...

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 .

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 where and . Alternatively, the sequence of moves might have length some ordinal number other than ω1.

Definitions and notation

I0, J0, I1, J1,...
The result of a play is either a win or a loss for each player.
is according to strategy s. (Here λ denotes the empty sequence of moves.)

The Banach–Mazur game

Main article: 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 , and player II responds with a nonempty open subset . 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

The game-theoretic and topological connections demonstrated by the game include:

Other topological games

Some other notable topological games are:

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, ultrafilters, 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.[6]

References

  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.
  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.
This article is issued from Wikipedia - version of the 9/29/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.