Equilibrio en un juego detenido

10

Considere el siguiente juego de 2 jugadores:

  • La naturaleza elige un programa al azar
  • Cada jugador juega un número en [0, infinito] inclusive en respuesta al movimiento de la naturaleza
  • Tome el mínimo de los números de los jugadores y ejecute el programa durante (hasta) tantos pasos (a menos que ambos jugadores elijan el infinito)
  • Si el programa se detiene, el jugador que jugó el número mínimo gana 1 punto. Si el programa no se detiene, ese jugador pierde 1 punto. Cualquier jugador que jugó un número no mínimo recibe 0 puntos, y ambos jugadores reciben 0 si ambos juegan al infinito.

(Los casos de esquina se pueden manejar de la manera que mejor conserve el espíritu del problema; por ejemplo, la semicontinuidad superior puede ser útil).

La pregunta: ¿este juego posee un equilibrio de Nash computable?

Sin el requisito de computabilidad, cada jugador solo juega el número exacto de pasos en los que el programa se detiene (o infinito, si no se detiene).

Si prueba el argumento de diagonalización habitual para el problema de detención, encontrará que existe un equilibrio en las estrategias mixtas, por lo que el enfoque obvio no funciona de inmediato. Tal vez hay alguna manera de modificarlo?

Por otro lado, la equivalencia de los campos cerrados reales significa que los juegos finitos con pagos computables tienen equilibrios computables . Este juego no es finito, pero el espacio de estrategia está cerrado y los pagos son computables, así que ¿tal vez podría aplicarse el mismo truco con el teorema de Glicksberg o algo por el estilo? El problema es que, sin el requisito de computabilidad, el equilibrio se encuentra en estrategias puras, por lo que cualquier intento de demostrar la existencia de un equilibrio computable utilizando la existencia de un equilibrio tal vez computable debe explicar por qué el equilibrio se degrada de puro a mixto.

Este parece ser el tipo de problema en el que las personas pueden no haber abordado esta pregunta exacta antes, pero podrían haber visto algo similar. No he podido aparecer mucho, pero si alguien sabe algo en espíritu, ¡hágamelo saber!

Motivación: existe una intuición común de que la autorreferencia es el bloque principal para la computabilidad, es decir, que cualquier problema no controlable de alguna manera incorpora la autorreferencia. Si un juego como este tiene un equilibrio de Nash computable, proporcionaría evidencia de esa intuición.

ACTUALIZACIÓN: Para aclarar, el equilibrio debe ser "computable" en el sentido de números reales computables: las probabilidades que describen la distribución de la estrategia mixta deben ser computables con precisión arbitraria. (Tenga en cuenta que solo muchas probabilidades estarán por encima de cualquier límite de precisión en particular). Esto también significa que podemos tomar muestras de una aproximación arbitrariamente cercana de la estrategia de equilibrio.

John Wentworth
fuente
¿Su actualización también considera las jugadas como números reales computables? (es decir, pueden jugar un número con probabilidad 1 sin saber si-o-no que el número es infinito?)
¿Se nos permite conocer la distribución del oponente?
Bjørn Kjos-Hanssen
Ricky: las jugadas podrían considerarse reales computables, pero truncar a un número entero debería dominar cualquier juego finito no entero, ya que un programa solo se ejecutará por un número entero de pasos (o infinito). Sin embargo, no estoy seguro de entender su ejemplo entre paréntesis, por lo que puedo estar malinterpretando su pregunta.
John Wentworth
Bjørn: sí. Suponga que la distribución de la naturaleza es conocida y asigna un peso distinto de cero a todos los programas válidos. También suponga que cada jugador conoce la estrategia del otro jugador (es decir, la distribución).
John Wentworth
@johnwentworth, use @ o no podrán ver su respuesta.
rus9384

Respuestas:

11

1/2iitjtjjt

Lance Fortnow
fuente
Me gusta esta construcción: establece que cualquier equilibrio de Nash debe jugar correctamente para todos los programas. Se necesita un paso adicional para establecer que resuelve el problema de detención, ya que las distribuciones solo necesitan converger para un rendimiento perfecto en el límite de alta precisión (y, por lo tanto, cálculo infinito). Como sabemos que la salida debe poner el peso unitario en un entero, creo que es suficiente calcular las probabilidades de la estrategia dentro de 1/4 y luego tomar el entero que tenga un peso mayor que 1/2.
John Wentworth