Estratégia vencedora no jogo dos trigêmeos

8

O jogo de tripletos é definida por um conjunto finito de elementos X , e um filtro multi-conjunto finito T contendo tripletos de elementos. Dois jogadores se revezam escolhendo elementos de X até que todos os elementos sejam retirados. Então, a pontuação de cada jogador é o número de trigêmeos de T nos quais ele possui pelo menos 2 elementos.

Um argumento padrão de roubo de estratégia mostra que o primeiro jogador sempre pode marcar pelo menos |T|/2 . Suponha, por contradição, que isso é falso. Então o segundo jogador pode marcar mais do que |T|/2 . Mas então o primeiro jogador, copiando a estratégia vencedora do segundo jogador, pode marcar mais de |T|/2 também. Isso é uma contradição, pois a soma das pontuações é |T|.

PERGUNTA: qual é uma estratégia explícita para o primeiro jogador obter uma pontuação de pelo menos |T|/2 ?

EDIT: Aqui está uma estratégia explícita para o primeiro jogador obter pelo menos 3|T|/8 . Para cada trigêmeo em T , atribua um potencial P(a,b) base no número de seus elementos obtidos pelo (primeiro, segundo) jogador:

ab012303/800013/41/2021131
Inicialmente, cada trio tem potencial 3/8 , de modo que o potencial de soma é 3|T|/8 .

A estratégia do jogador 1 é: escolha um elemento que maximize a soma potencial. Suponha que o elemento seja x e o elemento escolhido a seguir pelo jogador 2 seja y . Afirmo que a soma potencial após esses dois movimentos aumenta fracamente:

  • O potencial de um trigêmeo que não contém x nem y não muda.
  • O potencial de um tripleto que contém ambos x e y alterações de P(a,b) a P(a+1,b+1) , o que é sempre pelo menos tão grande.
  • O potencial de um trigêmeo que contém x e não y aumenta em P(a+1,b)P(a,b) ;
  • O potencial de um trigêmeo que contém y e não x diminui em P(a,b)P(a,b+1) ; é fácil verificar na tabela que P(a,b)P(a,b+1)P(a+1,b)P(a,b) (a diminuição ao ir para a direita é, no máximo, o aumento ao descer).

Em suma, a soma potencial aumenta pela soma de P(a+1,b)P(a,b) sobre todos os trigêmeos que contêm x , e diminui (no máximo) a soma de P(a+1,b)P(a,b) sobre todos os trigêmeos que contêm y . Pela escolha de x , a primeira soma é um pouco maior. Portanto, a soma potencial aumenta fracamente.

Portanto, a soma potencial final é de pelo menos 3|T|/8 . No final, um trigêmeo tem potencial 1 ( 0 ) se for ganho pelo jogador 1 (2), portanto a soma do potencial final é igual à pontuação do jogador 1.

Erel Segal-Halevi
fonte
1
É bastante improvável que exista uma estratégia simples, como é o caso da maioria dos jogos em que o roubo de estratégias prova que o primeiro jogador sempre pode vencer.
Domotorp #
Eu concordo com domtorp. Suspeito que "pegar o elemento com o maior número de ocorrências" seja a heurística básica correta, embora o número de ocorrências não seja exatamente a coisa certa a ser contada. Argumentos de roubo de estratégia geralmente significam que, se você seguir uma certa heurística, poderá sempre jogar defensivamente quando desafiado e acabar vencendo. A questão é descobrir como e quando jogar na defensiva.
Stella Biderman 8/18
Para acrescentar aos comentadores anteriores, seria muito interessante se um jogo desse tipo (com roubo de estratégia em uma estrutura natural diferente de "eu cortei você escolher") fosse provado completo no PSPACE (com, por exemplo, → um vencedor primeiro mover sendo PSPACE completo). T
Dmytro Taranovsky

Respostas:

3

Esta não é uma prova completa, mas aqui estão algumas justificativas para o porquê de conjecturas conhecidas implicarem que o jogo pode ser computacionalmente difícil de resolver. Ou seja, vou argumentar que encontrar o primeiro passo correto já é provavelmente complicado.


Como primeiro passo, argumentamos que o jogo dos trigêmeos é mais difícil (no sentido apropriado) do que o jogo Denser Induced Subgraph definido da seguinte maneira.

Dois jogadores, A e B, alternam os vértices em um gráfico comum G. Os vértices podem ser escolhidos apenas uma vez. Quando não houver mais vértices a serem selecionados, os subgráficos induzidos pelas escolhas de cada jogador são comparados. O jogador com o maior número de arestas induzidas é declarado vencedor.

Esboço da prova:

Dada uma instância do jogo Denser Induced Subgraph com o gráfico G=(V,E) , construímos uma instância de Triplets seguinte forma. Sem perda de generalidade, assuma que G não possui vértices isolados. O conjunto de elementos em nossa instância será V(E×{0,1}) . Para cada aresta eE entre os vértices u e v , temos dois trigêmeos da forma (u,v,(e,0)) e(u,v,(e,1)) . Além disso, para cada vérticevV , lançamos quatro trigêmeos adicionais da forma(v,v,v) . Isso completa a redução.

Agora imagine os procedimentos do jogo Triplets . Enquanto alguns vértice do V não tiver sido escolhido, a escolha de tal vértice um domina estritamente que de qualquer elemento de E . De fato, escolher um elemento de E×{0,1} apenas gera um aumento potencial de pontuação de 1 (e também bloqueia o oponente de no máximo 1 ponto), enquanto escolher um elemento de V automaticamente aumenta automaticamente a pontuação de 4 , com potencial para mais.

Portanto, em condições ideais, o primeiro |V|rodadas corresponderá a ambos os jogadores escolhem elementos de V . Após essas rodadas, os jogadores alternam a coleção de triplos de tamanho uniforme que ainda não foram reivindicados, que correspondem exatamente às arestas cujos pontos finais foram escolhidos uma vez por cada jogador. Qualquer estratégia razoável aqui, para qualquer jogador, acaba pegando exatamente metade desses trigêmeos disponíveis. O jogo termina com uma sequência de movimentos NOOP nos trigêmeos já coletados.

Deixe- VA ser os vértices escolhidos pelo jogador A, e VB aqueles escolhidos por B. A pontuação para o jogador A é a soma de (i) quatro pontos por vtice escolhido de entre os (v,v,v) tripletos (ii) dois pontos por aresta induzida criados a partir desses vértices e (iii) um ponto para cada aresta dividida. Portanto, a pontuação é 4|V|/2+2|E[VA]|+(|E||E[VA]||E[VB]|) , OndeE[S] é o conjunto de arestas induzidas porS . Como o primeiro e o último termo são finalmente iguais para ambos os jogadores, o jogador com o subgráfico induzido maior vence.


Com isso em mente, podemos apelar para alguns dos trabalhos na literatura de detecção de subgráficos densos. Há uma tonelada de trabalhos relevantes por aí sobre os quais se pode recorrer, mas, para simplificar a análise, recorreremos a uma conjectura específica sobre a dificuldade de encontrar gráficos aleatórios densos em gráficos aleatórios esparsos (acredito que essa dependência possa ser removida com apenas um pouco mais de reflexão, mas isso não pretende ser uma prova formal).

O Problema do Subgráfico Denso Plantado (informal). Seja G=(V,E) um gráfico aleatório amostrado da distribuição Erdos-Renyi G(n,1/n). Com probabilidade1/2, voltamosGcomo é. Caso contrário, deixamosVser um subconjunto uniformemente aleatório deVde tamanhon . Para cadau,vpar emV, adiciona-se um bordo(u,v)aE, independentemente, com probabilidaden1/4 . Só então é que vamos voltarG. O problema é que, dada apenas a saída acima, identifique corretamente se o gráfico Erdos-Renyi foi ou não aumentado.

A conjectura do subgráfico denso plantado (informal). Nenhum algoritmo de tempo polinomial pode resolver o problema do subgráfico denso plantado com probabilidade de pelo menos 51% .

Suponha que o gráfico tenha sido aumentado e que exista um componente invulgarmente denso. Como nenhum algoritmo poli-tempo pode detectar com segurança a presença desse subgráfico denso, ele também não pode amostrar com segurança um vértice desse componente denso (por exemplo, devido à auto-redutibilidade). Portanto, como (da perspectiva do jogador A) está selecionando um vértice aleatório de um gráfico Erdos-Renyi puro, não importa muito qual vértice A escolhe (até uma pequena alteração na pontuação que acabará não importando 1) No entanto, se o Jogador B for onisciente, ele poderá obter uma amostra confiável de um vértice do componente denso em seu primeiro disparo. Esse processo repete um número superconstante de vezes antes que as escolhas de B comecem a desvendar o componente denso para A (caso contrário, um algoritmo de tempo polinomial pode percorrer todos os caminhos nesta árvore de jogo a uma profundidade constante, a fim de resolver o problema do subgráfico denso plantado). Se o processo repetido r vezes antes pega um, então o primeiro r1 rodadas podem ser vistos como rodadas "brinde" para B, enquanto o r ª rodada é o começo de A e B de combate sobre o componente densa, com B recebendo a primeira jogada e (pelo argumento da sua estratégia de roubar) um subconjunto vencedor.

Uma vez esgotado o componente denso, os dois jogadores retomam a luta pelo resto do gráfico. Enquanto Um escolheu r mais vértices aqui que B tem, primeiro de B r vértices valem Ω(n1/4) vezes mais, e assim, em última análise, B é o vencedor.

1. Por algum tipo de concentração e argumento de pombo, a diferença entre fazer a primeira e a segunda escolha não deve ser maior que O(1) na pontuação final.


Portanto, apesar de o jogo ter sido muito pouco resolvido para o jogador A, é improvável que seja computacionalmente viável que A jogue até o primeiro passo da estratégia vencedora.

Uma abordagem baseada na dureza do problema "subgráfico" mais denso "normal" também não deve ser difícil de obter, e compor a redução com um resultado de dureza de aproximação provavelmente pode ser usado para obter algum tipo de dureza com base em conjecturas mais comuns ( por exemplo, ETH). Não sei ao certo qual pode ser a dificuldade de subir para a dureza NP (ou além).

Yonatan N
fonte
A redução é muito legal. Você pode fazer uma referência a esta conjectura "O subgráfico denso plantado"?
Erel Segal-Halevi
A conjectura apareceu várias vezes sob sabores levemente variados, incluindo cc.gatech.edu/~klai9/FinalThesis.pdf (Conjectura 2), users.cs.duke.edu/~rongge/derivatives_ics.pdf (Densest Subgraph Assunção) , proceedings.mlr.press/v40/Hajek15.pdf (PC Hipótese), math.ias.edu/files/ABW10_STOC.pdf (DUE Assunção), core.ac.uk/download/pdf/62922882.pdf (Plantada Dense subgráfico Conjectura), entre outros. Os resultados finais são semelhantes o suficiente para que a construção acima quase não precise de modificações para ser adaptada ao sabor escolhido.
Yonatan N
3|T|/83|T|/8|T|/2
Não estou de cabeça para baixo, mas vou ver se consigo pensar um pouco mais no fim de semana. Bom argumento de 3/8!
precisa