Juegos que nunca empiezan

Question

Los juegos que nunca terminan desempeñan un papel fundamental en la teoría descriptiva de conjuntos. Véase, por ejemplo, GTM de Kechris.

Preguntas: ¿Existe literatura sobre los juegos que nunca empiezan?

Tengo en mente a dos jugadores, Alice y Bob, haciendo selecciones alternas de ${\Bbb N}$ sus movimientos indexados por enteros no positivos crecientes, el juego termina cuando Bob juega su movimiento 0.

En cuanto a los conjuntos de resultados y estrategias, defínelos como para los juegos que nunca terminan, mutatis mutandis.

Una diferencia importante: un par de estrategias, una para Alice y otra para Bob, ya no determinan una única tirada del juego, sino un conjunto de tiradas, posiblemente vacías. Aun así, se puede decir que la estrategia de Alice gana a la de Bob si cada compatible de una estrategia contra la otra pertenece al conjunto de resultados.

Otra diferencia importante tiene que ver con el tamaño teórico de las estrategias. Ahora Alice y Bob juegan cada movimiento a la luz de una historia infinita. ¿Así que las consideraciones de tamaño significan que ciertos argumentos familiares, por ejemplo los juegos no determinados del axioma de elección, no funcionan de ninguna manera obvia?

Pregunta: ¿Qué conjuntos de pago dan determinados juegos que nunca comienzan?

Editado: A la fría luz de la mañana, veo que abusé de las palabras "mutatis mutandis". A la Kechris, la estrategia de Alice vence a Bob si la única carrera del juego cae en el conjunto de resultados. Lo que tenía en mente aquí era que la estrategia de Alice gana a la de Bob si el conjunto de ejecuciones (consistente con ambas estrategias) es un subconjunto del conjunto de ganancias. La inteligente respuesta de Joel David Hamkins sigue siendo mordaz, sólo que ahora con la importación de que Alice siempre gana jugando una estrategia con conjuntos de ejecuciones vacíos independientemente de la estrategia de Bob.

La Alice de Joel necesita una memoria infinita, pero si su estrategia en cada movimiento consiste en aumentar en 1 su movimiento anterior, eso también produce necesariamente un conjunto de ejecuciones vacío independientemente de la elección de Bob.

Posible solución 1 Alice debe jugar un comprometido estrategia, una estrategia que produce un conjunto de ejecuciones no vacío contra al menos una estrategia de Bob.

Posible solución 2 El juego residual en cualquier turno sólo tiene un futuro finito, por lo que un jugador tiene una estrategia ganadora a partir de ese momento. Llamamos estrategia racional si requiere que el jugador realice una jugada ganadora en la partida residual siempre que exista una. Llamamos estrategia fuertemente racional si requiere que el jugador juegue la menor jugada ganadora posible siempre que exista una. Para evitar estrategias fáciles que ni siquiera hacen referencia al conjunto de resultados, insista en estrategias racionales, o incluso fuertemente racionales.

Posible solución 3 Combina las correcciones anteriores.

Answer 1

Es una pregunta muy bonita.

Observación 1. Algunas estrategias no tienen juego que concuerde con ellas. En consecuencia, tal estrategia para Alicia es ganadora en cualquier juego, ya que toda jugada conforme con ella es (vacuamente) en su conjunto de resultados. (Estrategias similares existen para Bob).

Pruebas: Aquí, considero que una estrategia es una función que asigna una posición de juego al número a jugar. Una posición de juego es una secuencia casi infinita, con sólo los últimos dígitos finitos sin especificar. Consideremos la estrategia de Alicia: ante una posición de juego posición de juego de la jugada anterior, inspecciona sus propias jugadas anteriores; si infinitamente muchas de ellas fueron $0$ juega $1$ y en caso contrario juega $0$ . No puede haber ninguna jugada que concuerde con esta estrategia, ya que si la jugada muestra que Alicia ha jugado infinitamente muchas $0$ s, entonces debería haber estado jugando $1$ en cualquiera de y, a la inversa, si sólo hubiera jugado a un número finito de $0$ s, entonces debería haber empezado a jugar $0$ mucho antes que ella lo hizo.

Otro ejemplo es la estrategia de añadir siempre uno que mencionó en respuesta a esto, y me parece que es bastante elegante. Si Alice juega para siempre añadir uno a su movimiento anterior, entonces es evidente que no puede tener hecho esto para siempre. Esta estrategia tiene sentido en juegos con número natural, pero en realidad se puede utilizar la misma idea para juegos binarios binarios, en los que los jugadores juegan $0$ o $1$ haciendo que Alicia juegue una secuencia (estrictamente más larga) de $n$ consecutivos $1$ s en su próximo $n$ movimientos (a menos que se acabe el tiempo de juego).

Una respuesta anterior mía (ver historial de edición) contiene otro argumento, utilizando diagonalización y el axioma de elección. QED

Por lo tanto, parece que Alice gana todos los juegos, de acuerdo con la definición que usted ha proporcionado. Pero yo prefiero decir que ambos jugadores tienen estrategias ganadoras, porque ambos tienen estrategias tal que cualquier juego que se ajusta a ellos es en sus respectivos respectivas.

Observación 2. Si se modifica la definición de estrategia para que los movimientos de uno dependan sólo de los movimientos del oponente en una posición, entonces no todos los pares de estrategias de Alice y Bob tienen una jugada conforme.

Prueba: Consideremos la estrategia para Bob que simplemente copia el movimiento anterior de Alice jugada anterior de Alice, y la estrategia de Alice que juega $1$ si y sólo si todos los movimientos anteriores de Bob fueron $0$ . No puede haber juego conforme para este par de estrategias, ya que si Bob estaba previamente jugando todos ceros hasta un punto, entonces Alice debería haber jugado $1$ mucho antes, y si no, entonces Alice debe haber jugado $1$ sin causa. QED

Observación 3. Hay un juego para el que ambos jugadores tienen estrategias ganadoras racionales comprometidas.

Prueba: Consideremos el juego en el que Alicia gana todas las jugadas teniendo sólo finitamente muchas $1$ s. El siempre-jugador $3$ estrategia es un racional, estrategia ganadora comprometida para Bob, ya que tiene jugadas conformes, cada jugada conforme es una victoria para Bob, y desde cualquier posición, hace una jugada ganadora en el juego finito restante. Mientras tanto, Alice también tiene una estrategia ganadora: jugar $0$ si casi todos movimientos anteriores fueron $0$ y si no, añade uno a su anterior. Esta estrategia está comprometida, ya que Bob podría haber jugado $0$ s, y es fuertemente racional para Alice, ya que está jugando $0$ s siempre que esté en una posición ganadora; y es ganadora para Alice, ya que las únicas jugadas conformes son casi todas $0$ y por lo tanto gana Alice. QED

Teorema. (AC) Hay un juego en el que ninguno de los jugadores tiene estrategia racional comprometida ganadora.

Prueba: Este teorema funcionará independientemente de si uno permite que las estrategias dependan de la posición completa o sólo de la posición del movimientos previos del adversario. Digamos que dos secuencias son casi igual si sólo difieren en un número finito de valores. Utilizando el axioma de elección, podemos seleccionar un representante de cada clase de casi-igualdad. Sea $A$ sea el juego en el que Alicia gana un jugada, si ésta se desvía del representante de su clase por primera vez en su turno, y Bob gana si la jugada se desvía por primera vez en su turno, o no gana. Lo que hay que tener en cuenta es que si $s$ es una jugada del juego, entonces tanto Alice como Bob tenían incentivo para haber jugado de forma diferente antes, ya que al hacer un movimiento diferente mucho antes, habrían causado una desviación desviación en la jugada, haciendo que hubieran ganado antes. En efecto, era irracional por su parte no haber hecho la jugada anterior, ya que su adversario podría haber ganado en la siguiente jugada. Por lo tanto, no puede haber estrategia racional para ninguno de los dos jugadores. Por tanto, ninguno de los jugadores tiene una estrategia racional comprometida. QED

Definimos que un conjunto es un juego de cola si es invariante bajo finita. Estos son precisamente los conjuntos que están saturados con respecto a la relación de casi igualdad.

Observación 4. En cada juego cuyo conjunto de pagos es una cola todas las estrategias son racionales.

Prueba: El punto es que cuando usted está jugando un juego cuyo payoff es un conjunto de colas, entonces el juego ya está ganado o perdido cuando cualquier movimiento en particular, ya que la clase de equivalencia de la cola ya está determinada. ya está determinada. Así que en un juego de este tipo, ningún movimiento individual afecta al resultado del juego. QED

Por último, permítanme mencionar que su concepto de juego me recuerda al arqueológico modelo de computación en tiempo infinito, donde el computación infinita crece a partir de un pasado infinito en lugar de en lugar de extenderse hacia un futuro infinito. La idea es que, habiendo abierto una cámara bajo la pirámide, se encuentra una máquina de Turing, todavía en funcionamiento, con una cinta infinita toda llena y con todos los indicaciones de que ha estado funcionando desde un tiempo que se extiende infinitamente en el pasado. ¿Qué tipo de problemas son decidibles en principio por tales máquinas? Para una teoría interesante, supongamos que podemos encontrar pirámides correspondientes a cualquier programa dado.

Answer 2

Como complemento a la respuesta de Joel, tal vez quieras echar un vistazo a este bonito papel de Bollobas, Leader y Walters sobre juegos continuos. Como punto de partida discuten el clásico León y hombre juego presentado por Rado. En este juego hay un león que persigue a un hombre dentro del disco de la unidad. Ambos tienen velocidades máximas idénticas. El león gana si atrapa al hombre, y el hombre gana si nunca es atrapado por el león. Si el león elige correr siempre directamente hacia el hombre, entonces se acercará arbitrariamente al hombre, pero nunca lo atrapará. En cambio, si el león se mueve a toda velocidad, de modo que siempre se encuentre en el vector radial que va del centro al hombre, está "claro" que se trata de una estrategia ganadora. Prueba: sin pérdida de generalidad, el hombre permanece en el límite del disco. Sin embargo, en 1952, Besicovitch presentó una ingeniosa estrategia ganadora para el hombre. Por lo tanto, la permanencia en el límite es, con pérdida de generalidad, para el hombre. No obstante, cabe preguntarse si el león también tiene una estrategia ganadora. En este juego concreto, resulta que la respuesta es no. Pero cambiando el espacio métrico, Bollobas, Leader y Walters demuestran que hay juegos similares en los que tanto el león como el hombre tienen estrategias ganadoras.

Answer 3

Una respuesta un poco más tangencial, pero que espero que siga siendo útil: existe una conexión bien conocida entre los juegos infinitos y la lógica infintinta. En el contexto habitual de los juegos sin final, los principios de determinación pueden verse como versiones de la ley de De Morgan para ciertas sentencias infinitas: para $\Gamma$ una clase puntual, $\Gamma$ -Det es la afirmación de que cada una de las disyunciones $$ \forall x_0\exists x_1\forall x_2\exists x_3 . . . . ((x_0, x_1, x_2, x_3, . . . )\not\in X) \vee \exists x_0\forall x_1\exists x_2\forall x_3 . . . ((x_0, x_1, x_2, x_3, . . . ) \in X)$$ para $X\in\Gamma$ es cierto. Del mismo modo, los juegos sin principio deben conectarse a la semántica de las oraciones infinitas con infundado cadenas de cuantificadores. En el artículo "On languages with non-homogeneous strings of quantifiers" ( https://doi.org/10.1007/BF02771553 ), Saharon Shelah hizo algunos trabajos sobre el comportamiento de tales sentencias (su semántica para estas sentencias está en términos de funciones de Skolem; parece evitar la observación de Joel requiriendo que una estrategia para un jugador mire solamente los movimientos hechos por el otro jugador, pero no estoy seguro de esto - ¡corríjame por favor si me equivoco!). El resultado principal es que "toda cadena lineal de cuantificadores puede sustituirse por una secuencia bien ordenada de cuantificadores", lo que en cierto modo reduce el estudio de los juegos sin principio al estudio de los juegos sin fin.

Sin embargo, hay que tener en cuenta que también se han estudiado "cadenas" (¿posets?) no lineales de cuantificadores (cf. "Lógica de la dependencia"), y no tengo ni idea de qué ocurre si consideramos colecciones de cuantificadores ramificadas y mal fundadas, o si esto se ha estudiado en el pasado (aunque recuerdo vagamente un artículo de Hintikka o Vaananen sobre el tema, pero no lo encuentro, así que quizá no exista). Tampoco conozco una buena interpretación teórica de juegos de tales colecciones de cuantificadores, pero imagino que no sería muy difícil encontrar una.