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

The term "topological game" was first introduced by Berge [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.] , 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 [R. Telgársky, On topological properties defined by games, Topics in Topology (Proc. Colloq. Keszthely 1972), Colloq. Math. Soc. Janos Bolyai, Vol. 8, North-Holland, Amsterdam 1974, 617-624.] , and later "spaces defined by topological games" [R. Telgársky, Spaces defined by topological games, Fund. Math. 88 (1975), 193-223.] ; 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árskyR. Telgársky, Topological Games: On the 50th Anniversary of the Banach-Mazur Game, Rocky Mountain J. Math. 17 (1987), 227-276. [http://www.telgarsky.com/1987-RMJM-Telgarsky-Topological-Games.pdf] (3.2MB PDF)] 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 [L. A. Petrosjan, Topological games and their applications to pursuit problems. I. SIAM J. Control 10 (1972), 194-202.] 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.

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 P_1 and P_2 is defined as a pair G(X,Phi) where X is a topological space with cardinality |X| and Phi: X mapsto mathcal{P}(X) is an upper (and/or lower) semicontinuous multivalued map assigning to each position x in X a set Phi(x) in mathcal{P} = {Y ; | ; Y subset X} of legal positions having the Vietoris topology. We assume that P_1 makes the first move, and we say that x is a "terminal position" if Phi(x) = emptyset.

* We set [X] ^{kappa} = {Y subset X ; | ; |Y|=kappa}, [X] ^{, and [X] ^{>kappa} = {Y subset X ; | ; |Y|>kappa}, where kappa is a cardinal number. Furthermore, we denote with ar E the closure of a subset E of a topological space X, and we use mathcal{F}(X) to denote the collection of all closed subsets of X.

* A "play" of the game is a sequence of type omega, where omega = {0, 1, 2, cdots}. In many analyses the following quantities are useful: 2^{omega} = {0,1} imes {0,1} imes cdots (homeomorphic to the Cantor Discontinuum), and omega^{omega} = omega imes omega imes cdots (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 P_i is a function defined over every legal finite sequence of moves of player P_{-i}. We denote with P_i uparrow G the fact that player P_i has a winning strategy for G, and we say that G is "determined" if either P_1 uparrow G or P_2 uparrow G.

* Two games G_1 and G_2 are said to be "equivalent" if (P_1 uparrow G_1 Leftrightarrow P_1 uparrow G_2) land (P_2 uparrow G_1 Leftrightarrow P_2 uparrow G_2).

* A strategy for P_i is "stationary" if it depends only on the last move of P_{-i}; a strategy is "Markov" if it depends both on the last move of P_{-i} "and" on the ordinal number of the move.

* Many analyses focus on the set of real numbers, and denote with R the real line, and with J 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 mathfrak{E} be a family of subsets of a space Y such that the following properties hold.

* (E subset mathfrak{E}) land (E subset E' subset Y) Rightarrow (E' subset mathfrak{E});

* (cup_{n.

Furthermore, let's associate with each decreasing sequence (A_n ; | ; n of subsets of Y, a family H(A_n) of subsets of Y such that:

* (A in H(A_n)) land (A subset A' subset Y) Rightarrow (A' in H(A_n));

* (B_0, B_1, cdots in H(A_n)) Rightarrow (cap_{n.

Now, given a subset X of Y, consider the following game S(X, Y, mathfrak{E}, H): each player chooses alternatively elements E_0, E_1, cdots in mathfrak{E}, enforcing that X supset E_0 supset E_1 subset cdots. Player P_2 wins when X in H(E_n ; | ; n. If P_2 uparrow S(X, Y, mathfrak{E}, H), then X is called a "smooth set".

The "Sierpiński game" S(X,Y) is a particular instance of this setup, in which Y is Euclidean, mathfrak{E}= [X] ^{>omega}, and H(A_n) = {A subset X ; | ; A supset (cap_{n. It turns out that this game has interesting correlations with many topological concepts.

* If P_1 uparrow S(X,J), then J setminus X contains a copy of the Cantor Discontinuum; if P_2 uparrow S(X,J), then X contains a copy of the Cantor Discontinuum.

* If X is "analytic" in J, then P_2 uparrow S(X,J); the converse has not been proven yet.

* If J setminus X contains an analytic set that is not Borel-separated from X, then P_1 uparrow S(X,J). This implies that, if X is a coanalitic non-Borel subset of J, then P_1 uparrow S(X,J).

* The family {X subset J ; | ; P_2 uparrow S(X,J)} 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 Choquet game -- related to siftable spaces;

* the point-open game -- in which P_1 chooses points and P_2 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; 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.

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • 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 spaces.… …   Wikipedia

  • Combinatorial game theory — This article is about the theory of combinatorial games. For the theory that includes games of chance and games of imperfect knowledge, see Game theory. Mathematicians playing Konane at a Combinatorial game theory workshop (for technical content …   Wikipedia

  • Mazur game — noun A topological game invented by the Polish mathematician Mazur in order to illustrate the difference between sets of the first category and second category …   Wiktionary

  • number game — Introduction       any of various puzzles and games that involve aspects of mathematics.       Mathematical recreations comprise puzzles and games that vary from naive amusements to sophisticated problems, some of which have never been solved.… …   Universalium

  • Asteroids (video game) — Infobox VG title=Asteroids caption= developer=Atari Inc. publisher=Atari Inc. distributor= designer=Lyle Rains and Ed Logg released=start date|1979 genre=Multi directional shooter modes=Up to 2 players, alternating turns platforms=Arcade… …   Wikipedia

  • Timelike topological feature — No closed timelike curve (CTC) on a Lorentzian manifold can be continuously deformed as a CTC to a point, because Lorentzian manifolds are locally causally well behaved. Every CTC must pass through some topological feature which prevents it from… …   Wikipedia

  • List of mathematics articles (T) — NOTOC T T duality T group T group (mathematics) T integration T norm T norm fuzzy logics T schema T square (fractal) T symmetry T table T theory T.C. Mits T1 space Table of bases Table of Clebsch Gordan coefficients Table of divisors Table of Lie …   Wikipedia

  • List of topology topics — This is a list of topology topics, by Wikipedia page. See also: topology glossary List of general topology topics List of geometric topology topics List of algebraic topology topics List of topological invariants (topological properties)… …   Wikipedia

  • Discrete mathematics — For the mathematics journal, see Discrete Mathematics (journal). Graphs like this are among the objects studied by discrete mathematics, for their interesting mathematical properties, their usefulness as models of real world problems, and their… …   Wikipedia

  • Wadge hierarchy — In descriptive set theory, Wadge degrees are levels of complexity for sets of reals and more comprehensively, subsets of any given topological space. Sets are compared by continuous reductions. The Wadge hierarchy is the structure of Wadge… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”