Estratégia vencedora para um determinado jogo em gráficos

Question

O jogo é o seguinte.Dois jogadores estão jogando um jogo, jogador 1 e jogador 2, em que o primeiro jogador começa nomeando um herói $h_1$, então o jogador 2 responde com um vilão $v_1$ que já atuou em um filme com $h_1$.Então o jogador 1 responde com outro herói $h_2$ que atuou em um filme junto com $v_1$, e assim por diante.Cada herói e vilão pode ser usado no máximo uma vez.O primeiro jogador que não conseguir nomear nenhum personagem (os heróis/vilões disponíveis não possuem um filme comum com a última escolha do outro jogador), perde o jogo.O jogador 1 sempre inicia o jogo.

A entrada é um conjunto de heróis $H$, um conjunto de vilões $V$ ($ | H | = | V | geq 1 $) e uma família de filmes $M$, onde cada filme é um conjunto de heróis e vilões que apareceram naquele filme.

A questão é:Você pode, com base em $H$, $V$ e $M$, decidir qual jogador ganha o jogo, assumindo que ambos os jogadores estão jogando de maneira ideal?

---

Exemplo:

Dados os seguintes dados:os heróis são Homem de Ferro, Capitão América, Thor e homem Aranha.Os vilões são Chicote, Ultron, Thanos e Abutre.Os filmes são Vingadores:Guerra Infinita (estrelado por Homem de Ferro, Capitão América, Thor, Thanos e Homem-Aranha) e Homem Aranha:Regresso a casa (estrela Homem de Ferro, Abutre e Homem-Aranha).Você consegue decidir qual jogador tem a estratégia vencedora?

---

Minha abordagem é usar a correspondência bipartida máxima para descobrir qual jogador tem a estratégia vencedora, porque podemos dividir os dados em dois conjuntos, ou seja, $H$ e $V$ e tem relações entre esses dois conjuntos.O algoritmo Hopcroft-Karp pode pegar dois desses conjuntos e descobrir a cardinalidade máxima.Por favor me corrija se eu estiver errado:nos casos em que há um emparelhamento perfeito, o jogador 2 vence e, caso contrário, o jogador 1 vence.Sempre que há uma combinação perfeita, significa que o jogador 2 sempre teve uma resposta para o herói que o jogador 1 nomeou.

Como você resolveria isso?Existe uma solução melhor e mais eficiente do que alguma correspondência bipartida máxima.

Answer 1

A resposta curta é: o jogador dois vence se e somente se o gráfico correspondente admitir uma correspondência que "cobre" o conjunto $H$.

---

Aqui está um pouco de explicação.

Sua ideia está quase certa.No entanto, a prova não é intuitiva e você pode perder alguns detalhes necessários se for uma questão teórica ou se precisar projetar a estratégia vencedora exata e não apenas produzir o jogador vencedor.

Então, vamos começar com a parte que falta na sua resposta.Suponha que uma determinada instância corresponda a um grafo que admite um emparelhamento perfeito.De acordo com a sua estratégia, o Jogador 2 vence neste caso, o que é certo.Agora suponhamos que o mesmo exemplo seja dado com mais um vilão, ou mais dez vilões ou mil deles.Claramente, o jogador dois ainda vence, já que adicionar vilões, independentemente de como os atribuímos, só ajuda o segundo jogador.Portanto, sua reivindicação nem sempre é válida.Porém, sua resposta está muito próxima da minha afirmação e tem a mesma intuição.Só falta um pouco de formalidade.

Alegar. Supondo que ambos os jogadores estejam jogando de forma otimizada, o Jogador 1 vence se e somente se, dada uma instância $EU$, o gráfico correspondente não admite um emparelhamento que sature o conjunto $H$.

Então, o que isso significa?Uma correspondência satura um conjunto de vértices $S$, se cada vértice em $S$ é incidente a um vértice na correspondência.Agora provamos a afirmação.Mostramos duas estratégias vencedoras, uma para o jogador dois quando o gráfico admite uma correspondência que satura o conjunto $H$ e um para o Jogador dois quando o grafo não admite tal emparelhamento.

Prova. Agora suponha que o gráfico admita tal emparelhamento.Deixe esta correspondência ser $M$.A estratégia é a seguinte.Contanto que o Jogador um não perca, para cada escolha $h \em H$ para o jogador um, escolha $v\em V$ o vértice corresponde a $h$ em $M$.

A correção decorre diretamente do fato de que cada vértice do Jogador dois é único e adjacente à escolha do Jogador um (devido às propriedades de uma correspondência).Intuitivamente, o jogador um ficará sem movimentos em algum momento (possivelmente depois de escolher todos os heróis do conjunto $H$).

Agora, assumindo que o gráfico não admite uma saturação correspondente $H$, de acordo com o teorema de Hall, existe um subconjunto $A \subseteq H$, de tal modo que $ | N (a) | <A $.Escolha um conjunto que seja mínimo em termos de inclusão.Afirmamos que há uma correspondência $M'$ que satura $N(A)$.Supondo o contrário, novamente devido a Hall, existe um subconjunto $S \subseteq N(A)$ de tal modo que $ | N (s) | <S $, mas depois removendo $N(S)\cap A$ de $A$ e $S$ de $N(A)$ produz um subconjunto de $A$ isso também contradiz a condição de Hall, que contradiz a escolha de $A$ ser mínimo.Portanto, há uma correspondência $M'$ que satura $N(A)$.

Agora a estratégia é a seguinte.Escolha um vértice em $A$ que não é incidente em nenhuma borda $M$.Tal vértice existe desde $ | N (a) | <| A | $.Escolha este vértice primeiro e para cada escolha $v\em V$ do jogador dois, escolha o vértice $h \em H$ correspondente a $v$ em $M'$.

Novamente, é fácil ver que o Jogador dois ficará sem movimentos em algum momento (possivelmente depois de escolher todos os vértices em $N(A)$) e, portanto, o jogador um vence.