Estrategia ganadora para un determinado juego en gráficos

Question

El juego va como sigue.Dos jugadores están jugando un juego, el jugador 1 y el jugador 2, en el que el primer jugador comienza por el nombramiento de un héroe $h_1$, entonces el jugador 2 responde con un villano $v_1$ que haya jugado en una película con $h_1$.Entonces el jugador 1 responde con otro héroe $h_2$ que ha jugado juntos en una película con $v_1$, y así sucesivamente.Cada héroe y villano puede ser utilizado en más de una vez.El primer jugador que no puede nombrar a cualquier carácter (disponible héroes/villanos no tienen un cine con la última elección del otro jugador), pierde el juego.El jugador 1 siempre se inicia el juego.

La entrada es un conjunto de héroes $H$, un conjunto de villanos $V$ ($|H| = |V| \geq 1$) y una familia de películas $M$, donde cada película es un conjunto de héroes y villanos que aparecieron en la película.

La pregunta es:Puede usted, basado en $H$, $V$ y $M$, decidir que jugador gana el juego si ambos jugadores están jugando de manera óptima?

---

Ejemplo:

Dados los siguientes datos:los héroes son Iron Man, Capitán América, Thor y Spider-Man.Los villanos son El latigazo cervical, Ultron, Thanos y Buitre.Las películas son Vengadores:Infinity War (estrellas de Iron Man, Capitán América, Thor, Thanos y Spider-Man) y Spider-Man:De regreso a casa (estrellas del Hombre de Hierro, el Buitre y Spider-Man).Puedes decidir qué jugador tiene la estrategia ganadora?

---

Mi enfoque es el uso de la máxima coincidente bipartita para averiguar qué jugador tiene la estrategia ganadora, porque podemos dividir los datos en dos conjuntos, a saber, $H$ y $V$ y tienen las relaciones entre los dos conjuntos.El Hopcroft-Karp algoritmo puede tomar dos de estos conjuntos y encontrar la máxima cardinalidad.Por favor me corrija si estoy equivocado:en los casos en los que hay una perfecta coincidencia, el jugador 2 gana y de lo contrario, el jugador 1 gana.Siempre que hay una perfecta coincidencia, significa que el jugador 2 ha tenido siempre una de las respuestas para el héroe que el jugador 1 nombre.

¿Cómo se podría solucionar esto?Hay un mejor y más eficiente solución de algunos máxima coincidente bipartita.

Answer 1

La respuesta corta es, el jugador dos gana si y solo si el gráfico correspondiente admite una coincidencia que "cubre" el conjunto $ H $ .

---

Aquí hay un poco de explicación.

Tu idea es casi correcta. Sin embargo, la prueba no es intuitiva y puede perderse algunos detalles que necesita si es una pregunta teórica o si necesita diseñar la estrategia exacta y no solo emitirá al jugador ganador.

así que comencemos con la parte que falta en su respuesta. Supongamos que un ejemplo dado corresponde a un gráfico que admite una coincidencia perfecta. Según su estrategia, el jugador 2 gana en este caso que tiene razón. Ahora asuma que se da la misma instancia con un villano más, o diez villanos más o mil de ellos. Claramente, el jugador dos aún gana desde que agrega villanos, independientemente de cómo los asignamos, solo ayuda al segundo jugador. Así que su reclamo no siempre lo sostiene. Sin embargo, su respuesta está muy cerca de mi reclamación y tiene la misma intuición. Solo falta un poco de formalidad.

afirmación. asumiendo que ambos jugadores estén jugando de manera óptima, el jugador 1 gana si y solo si, dada una instancia $ i $ , el correspondiente Gráfico no admite una coincidencia saturando el conjunto $ H $ .

Entonces, ¿qué significa eso? Una coincidencia sula un conjunto de vértices $ s $ , si cada vértice en $ s $ es incidente a un vértice en la coincidencia. Ahora probamos la reclamación. Mostramos dos estrategias ganadoras para el jugador dos cuando la gráfica admite una coincidencia del conjunto el conjunto $ h $ y uno para el jugador dos cuando el gráfico no admite tal coincidencia .

Prueba. ahora asume que el gráfico admite tal coincidencia. Deje que esta coincidencia sea $ m $ . La estrategia va como sigue. Mientras el jugador no haya perdido, para cada opción $ h \ in h $ para el jugador uno, elija $ v \ en v $ el vértice coincidido con $ h $ en $ m $ .

La corrección sigue directamente del hecho de que cada vértice del jugador dos es único y adyacente a la elección del jugador uno (debido a las propiedades de una coincidencia). Intuitivamente, el jugador se agotará de los movimientos en algún momento (posiblemente después de elegir a todos los héroes en el conjunto $ H $ ).

Ahora suponiendo que el gráfico no admite una saturación coincidente $ H $ , según el teorema de Hall, hay un subconjunto $ A \ Subesteq H $ , de tal manera que $ | n (a) | . Elija un conjunto de este tipo que sea mínimo inclusión. Afirmamos que hay un $ m '$ que saturamos $ n (a) $ . Suponiendo lo contrario, nuevamente debido a la sala, hay un subconjunto $ s \ subesteq n (a) $ tal que $ | n (S) | , pero luego eliminando $ N (S) \ Cap A $ de $ a $ y $ s $ de $ n (a) $ produce un subconjunto de $ A $ que también contradice la condición de la sala que forma una contradicción con la elección de $ a $ para ser mínimo. Por lo tanto, hay un $ m '$ que satura $ n (a) $ .

Ahora la estrategia va como sigue. Elija un vértice en $ A $ que no es incidente a ninguna ventaja en $ m $ . Tal vértice existe desde $ | n (a) | <| A | $ . Elija este vértice al principio y para cada opción $ v \ in v $ del jugador dos, elija el vértice $ h \ in H $ coincidido con $ v $ en $ m '$ .

de nuevo, es fácil ver que el jugador dos se quedará sin movimientos en algún momento (posiblemente después de elegir todos los vértices en $ n (a) $ ) y Por lo tanto, el jugador uno gana.