Estrategia ganadora en el juego de trillizos

8

El juego de trillizos se define por un conjunto finito de elementos X y una T multisistema finita que contiene tripletes de elementos. Dos jugadores se turnan para elegir elementos de X hasta que se toman todos los elementos. Luego, la puntuación de cada jugador es el número de trillizos de T en los que tiene al menos 2 elementos.

Un argumento estándar de robo de estrategia muestra que el primer jugador siempre puede anotar al menos |T|/2 . Supongamos por contradicción que es falso. Entonces el segundo jugador puede anotar más de |T|/2 . Pero entonces el primer jugador, copiando la estrategia ganadora del segundo jugador, puede anotar más de |T|/2 también. Esto es una contradicción ya que la suma de los puntajes es |T|.

PREGUNTA: ¿cuál es una estrategia explícita para que el primer jugador obtenga una puntuación de al menos |T|/2 ?

EDITAR: Aquí hay una estrategia explícita para que el primer jugador obtenga al menos 3|T|/8 . A cada triplete en T , asigne un potencial P(a,b) basado en el número de sus elementos tomados por el (primer, segundo) jugador:

ab012303/800013/41/2021131
Inicialmente, cada triplete tiene un potencial de 3/8 , por lo que el potencial de suma es 3|T|/8 .

La estrategia del jugador 1 es: elegir un elemento que maximice la suma potencial. Suponga que ese elemento es x el elemento elegido a continuación por el jugador 2 es y . Afirmo que la suma potencial después de estos dos movimientos aumenta débilmente:

  • El potencial de un triplete que no contiene ni x ni y no cambia.
  • El potencial de un triplete que contiene tanto x y y cambios de P(a,b) a P(a+1,b+1) , que es siempre al menos tan grande.
  • El potencial de un triplete que contiene x y no y aumenta en P(a+1,b)P(a,b) ;
  • El potencial de un triplete que contiene y y no x disminuye en P(a,b)P(a,b+1) ; es fácil verificar en la tabla que P(a,b)P(a,b+1)P(a+1,b)P(a,b) (la disminución al ir hacia la derecha es como máximo el aumento al bajar).

Con todo, la suma potencial aumenta en la suma de P(a+1,b)P(a,b) sobre todos los tripletes que contienen x , y disminuye en (como máximo) la suma de P(a+1,b)P(a,b) sobre todos los tripletes que contienen y . Al elegir x , la primera suma es débilmente mayor. Entonces, la suma potencial aumenta débilmente.

Entonces la suma potencial final es al menos 3|T|/8 . Al final, un triplete tiene potencial 1 ( 0 ) si es ganado por el jugador 1 (2), por lo que la suma potencial final es igual al puntaje del jugador 1.

Erel Segal-Halevi
fuente
1
Es poco probable que haya una estrategia simple, como es el caso de la mayoría de los juegos donde el robo de estrategias demuestra que el primer jugador siempre puede ganar.
domotorp
Estoy de acuerdo con domtorp. Sospecho que "tomar el elemento con el mayor número de ocurrencias" es la heurística básica correcta, aunque el número de ocurrencias no es exactamente lo correcto para contar. Los argumentos de robo de estrategia generalmente significan que si sigues una cierta heurística, siempre puedes jugar a la defensiva cuando te desafían y terminas ganando. El problema es descubrir cómo y cuándo jugar a la defensiva.
Stella Biderman
Para agregar a los comentaristas anteriores, sería muy interesante si un juego de este tipo (con el robo de estrategias en un marco natural que no sea "Corto tú elijas") se demostró que PSPACE estaba completo (con, por ejemplo, → un ganador primero mover siendo PSPACE completo). T
Dmytro Taranovsky

Respuestas:

3

Esta no es una prueba completa, pero aquí hay una justificación de por qué las conjeturas conocidas implican que el juego puede ser computacionalmente difícil de resolver. A saber, voy a argumentar que encontrar el primer movimiento correcto ya es probablemente complicado.


Como primer paso, sostenemos que el juego de los trillizos es más difícil (en el sentido apropiado) que el juego Denser Induced Subgraph definido de la siguiente manera.

Dos jugadores, A y B, alternan vértices de selección en un gráfico común G. Los vértices solo se pueden seleccionar una vez. Cuando no quedan más vértices por elegir, se comparan las subgrafías inducidas por las elecciones de cada jugador. El jugador con el mayor número de aristas inducidas se declara ganador.

Esquema de prueba:

Denser Induced SubgraphG=(V,E)TripletsGV(E×{0,1})eEuv(u,v,(e,0))(u,v,(e,1))vV(v,v,v)

TripletsVEE×{0,1}11V4

|V|V

VAVB(v,v,v)4|V|/2+2|E[VA]|+(|E||E[VA]||E[VB]|)E[S]S


Con esto en mente, podemos recurrir a algunos de los trabajos en la literatura de detección de subgrafías densas. Hay un montón de trabajo relevante sobre esto al que se puede recurrir, pero por simplicidad de análisis recurriré a una conjetura particular sobre la dificultad de encontrar gráficos aleatorios densos en gráficos aleatorios dispersos (creo que esta dependencia se puede eliminar con solo un poco más de reflexión, pero esto no pretende ser una prueba formal).

G=(V,E)G(n,1/n)1/2GVVnu,vV(u,v)En1/4G

51%

Suponga que el gráfico fue aumentado y que hay un componente inusualmente denso. Dado que ningún algoritmo de poli-tiempo puede detectar de manera confiable la presencia de este subgrafo denso, tampoco puede muestrear confiablemente un vértice de este componente denso (por ejemplo, debido a la auto-reducibilidad). Por lo tanto, dado que (desde la perspectiva del Jugador A) está seleccionando un vértice aleatorio de un gráfico puro de Erdos-Renyi, no importa mucho qué vértice A elija (hasta un pequeño cambio en su puntaje que terminará sin importar 1rr1r

rrΩ(n1/4)

O(1)


Por lo tanto, a pesar de que el juego se resuelve muy débilmente para el jugador A, es poco probable que A sea computacionalmente factible que A juegue incluso el primer movimiento de la estrategia ganadora.

Aquí tampoco debería ser difícil lograr un enfoque basado en la dureza del problema de subgrafo más denso "normal", y componer la reducción con un resultado de dureza de aproximación probablemente se pueda usar para obtener algún tipo de dureza basada en conjeturas más convencionales ( por ejemplo, ETH). No estoy seguro de cuál puede ser la dificultad de subir a la dureza NP (o más allá).

Yonatan N
fuente
La reducción es muy buena. ¿Puedes dar una referencia a esta conjetura de "El subgráfico denso plantado"?
Erel Segal-Halevi
La conjetura ha aparecido varias veces bajo sabores ligeramente diferentes, incluyendo cc.gatech.edu/~klai9/FinalThesis.pdf (Conjetura 2), users.cs.duke.edu/~rongge/derivatives_ics.pdf (Suposición de subgrafo denso) , proceedings.mlr.press/v40/Hajek15.pdf (PC hipótesis), math.ias.edu/files/ABW10_STOC.pdf (DUE Asunción), core.ac.uk/download/pdf/62922882.pdf (plantada Dense subgrafo Conjetura), entre otros. Los resultados finales son lo suficientemente similares como para que la construcción anterior no necesite casi ninguna modificación para adaptarse al sabor elegido.
Yonatan N
3|T|/83|T|/8|T|/2
No está fuera de mi alcance, pero veré si puedo pensarlo un poco más durante el fin de semana. Buen argumento de 3/8!
Yonatan N