Un juego topológico es un juego infinito de información perfecta jugado entre dos jugadores en un espacio topológico . Los jugadores eligen objetos con propiedades topológicas como puntos, conjuntos abiertos , conjuntos cerrados y cubiertas abiertas . El tiempo es generalmente discreto, pero las obras pueden tener una duración transfinita y se han propuesto extensiones al tiempo continuo. Las condiciones para que un jugador gane pueden involucrar nociones como el cierre topológico y la convergencia .
Resulta que algunas construcciones topológicas fundamentales tienen una contraparte natural en los juegos topológicos; ejemplos de estos son la propiedad Baire , espacios de Baire , propiedades de completitud y convergencia, propiedades de separación, propiedades de cobertura y base, imágenes continuas, conjuntos de Suslin y espacios singulares. Al mismo tiempo, algunas propiedades topológicas que surgen naturalmente en los juegos topológicos pueden generalizarse más allá de un contexto de teoría de juegos : en virtud de esta dualidad, los juegos topológicos se han utilizado ampliamente para describir nuevas propiedades de espacios topológicos y para poner propiedades conocidas bajo una luz diferente. También existen estrechos vínculos con los principios de selección .
El término juego topológico fue introducido por primera vez por Claude Berge , [1] [2] [3] quien definió las ideas básicas y el formalismo en analogía con los grupos topológicos. Un significado diferente para el juego topológico , el concepto de “propiedades topológicas definidas por juegos”, fue introducido en el trabajo de Rastislav Telgársky, [4] y más tarde “espacios definidos por juegos topológicos”; [5] este enfoque se basa en analogías con juegos matriciales, juegos diferenciales y juegos estadísticos, y define y estudia los juegos topológicos dentro de la topología. Después de más de 35 años, el término "juego topológico" se generalizó y apareció en varios cientos de publicaciones. El estudio de Telgársky [6] enfatiza el origen de los juegos topológicos del juego Banach-Mazur .
Hay otros dos significados de juegos topológicos, pero estos se usan con menos frecuencia.
- El término juego topológico introducido por Leon Petrosjan [7] en el estudio de los juegos antagónicos de persecución-evasión . Las trayectorias en estos juegos topológicos son continuas en el tiempo.
- Los juegos de Nash (los juegos Hex ), los juegos de Milnor (juegos de Y), los juegos de Shapley (juegos de planos proyectivos) y los juegos de Gale (juegos de Bridg-It ) fueron llamados juegos topológicos por David Gale en su discurso invitado [1979 / 80]. El número de movimientos en estos juegos siempre es finito. El descubrimiento o redescubrimiento de estos juegos topológicos se remonta a los años 1948-1949.
Configuración básica para un juego topológico
Se pueden definir muchos marcos para juegos posicionales infinitos de información perfecta.
La configuración típica es un juego entre dos jugadores, I y II , que alternativamente recogen subconjuntos de un espacio topológico X . En el n ª ronda, reproductor de I juega un subconjunto I n de X , y el jugador II responde con un subconjunto J n . Hay una ronda para cada número natural n , y después de que se juegan todas las rondas, el jugador I gana si la secuencia
- Yo 0 , J 0 , I 1 , J 1 , ...
satisface alguna propiedad y, de lo contrario, el jugador II gana.
El juego está definido por la propiedad objetivo y los movimientos permitidos en cada paso. Por ejemplo, en el juego Banach-Mazur BM ( X ), los movimientos permitidos son subconjuntos abiertos no vacíos del movimiento anterior, y el jugador I gana si.
Esta configuración típica se puede modificar de varias formas. Por ejemplo, en lugar de ser un subconjunto de X , cada movimiento puede consistir en un par dónde y . Alternativamente, la secuencia de movimientos puede tener una longitud de algún número ordinal distinto de ω 1 .
Definiciones y notación
- Una jugada del juego es una secuencia de movimientos legales.
- Yo 0 , J 0 , I 1 , J 1 , ...
- El resultado de una jugada es una victoria o una pérdida para cada jugador.
- Una estrategia para el jugador P es una función definida sobre cada secuencia finita legal de movimientos del oponente de P. Por ejemplo, una estrategia para el jugador I es una función s a partir de secuencias ( J 0 , J 1 , ..., J n ) para subconjuntos de X . Se dice que un juego se juega de acuerdo con la estrategia s si cada movimiento del jugador P es el valor de s en la secuencia de movimientos anteriores de su oponente. Entonces, si s es una estrategia para el jugador I , el juego
- es de acuerdo con la estrategia s . (Aquí λ denota la secuencia vacía de movimientos).
- Se dice que una estrategia para el jugador P es ganadora si por cada jugada de acuerdo con la estrategia s resulta en una victoria para el jugador P , por cualquier secuencia de movimientos legales del oponente de P. Si el jugador P tiene una estrategia ganadora para el juego G , esto se denota. Si alguno de los jugadores tiene una estrategia ganadora para G , entonces se dice que G está determinado. Se deduce del axioma de elección que hay juegos topológicos no determinados.
- Una estrategia para P es estacionaria si depende sólo del último movimiento del oponente de P ; una estrategia esMarkov si depende tanto del último movimiento del oponentecomodel número ordinal del movimiento.
El juego Banach-Mazur
El primer juego topológico estudiado fue el juego Banach-Mazur, que es un ejemplo motivador de las conexiones entre las nociones de la teoría de juegos y las propiedades topológicas.
Sea Y un espacio topológico y sea X un subconjunto de Y , llamado conjunto ganador . El jugador I comienza el juego eligiendo un subconjunto abierto no vacío, y el jugador II responde con un subconjunto abierto no vacío. El juego continúa de esta manera, y los jugadores eligen alternativamente un subconjunto abierto no vacío del juego anterior. Después de una secuencia infinita de movimientos, uno por cada número natural, el juego termina y yo gano si y solo si
Las conexiones topológicas y teóricas del juego demostradas por el juego incluyen:
- II tiene una estrategia ganadora en el juego si y solo si X es de la primera categoría en Y (un conjunto es de la primera categoría o escaso si es la unión contable de conjuntos densos en ninguna parte).
- Si Y es un espacio métrico completo, a continuación, que tiene una estrategia ganadora si y sólo si X es comeagre en algún subconjunto abierto no vacío de S .
- Si X tiene la propiedad de Baire en Y , entonces el juego está determinado.
Otros juegos topológicos
Algunos otros juegos topológicos notables son:
- el juego binario introducido por Ulam , una modificación del juego Banach-Mazur;
- el juego de Banach - jugado en un subconjunto de la línea real;
- el juego Choquet - relacionado con los espacios tamizables;
- el juego de puntos abiertos, en el que el jugador I elige puntos y el jugador II elige vecindarios abiertos de ellos.
Se han introducido muchos más juegos a lo largo de los años, para estudiar, entre otros: el principio de correducción de Kuratowski ; propiedades de separación y reducción de conjuntos en clases proyectivas cercanas; Tamices Luzin ; teoría de conjuntos descriptiva invariante ; Conjuntos de Suslin ; el teorema del grafo cerrado ; espacios palmeados ; MP-espacios; el axioma de la elección ; funciones recursivas. Los juegos topológicos también se han relacionado con ideas en lógica matemática, teoría de modelos, fórmulas infinitamente largas, cadenas infinitas de cuantificadores alternos, ultrafiltros , conjuntos parcialmente ordenados y el número de colores de gráficos infinitos.
Para una lista más larga y una descripción más detallada, consulte el documento de encuesta de Telgársky de 1987. [6]
Ver también
- Rompecabezas topológico
Referencias
- ^ C. Berge, Juegos topológicos con información perfecta. Contribuciones a la teoría de juegos, vol. 3, 165-178. Annals of Mathematics Studies, no. 39. Princeton University Press, Princeton, Nueva Jersey, 1957.
- ↑ C. Berge, Théorie des jeux à n personnes, Mém. des Sc. Mat., Gauthier-Villars, París 1957.
- ^ AR Pears, Sobre juegos topológicos, Proc. Cambridge Philos. Soc. 61 (1965), 165-171.
- ↑ R. Telgársky, Sobre propiedades topológicas definidas por juegos, Temas de topología (Proc. Colloq. Keszthely 1972), Colloq. Matemáticas. Soc. János Bolyai, vol. 8, Holanda Septentrional, Amsterdam 1974, 617–624.
- ^ R. Telgársky, Espacios definidos por juegos topológicos, Fondo. Matemáticas. 88 (1975), 193-223.
- ^ a b R. Telgársky, "Juegos topológicos: en el 50 aniversario del juego Banach-Mazur" , Rocky Mountain J. Math. 17 (1987), 227-276.
- ^ LA Petrosjan, Juegos topológicos y sus aplicaciones para perseguir problemas. I. SIAM J. Control 10 (1972), 194-202.