Teorema de Zermelo

"Teorema de Zermelo" é um conceito na teoria dos jogos.
 Nota: Para a teoria axiomática mais comum da teoria de conjuntos, veja Axiomas de Zermelo-Fraenkel.
Vitória!

O teorema de Zermelo apresentou pela primeira vez uma aplicação dos recursos matemáticos para um tipo restrito de interação entre agentes racionais egoístas que, não obstante o mérito da descoberta, raramente ocorria no cotidiano. O matemático e lógico alemão, Ernst Zermelo, demonstra a existência de uma estratégia para jogos como o xadrez que assegurava a vitória ou ao menos o empate para o jogador que a tomasse em primeiro lugar. Zermelo mostrou que seu teorema garantia que quem estivesse de posse de uma estratégia vitoriosa teria ao menos o empate em determinados tipos de interação, independente do que o outro adversário viesse fazer.

Na teoria dos jogos, o teorema de Zermelo , diz que em qualquer jogo finito de informação perfeita, entre duas pessoas, em que os jogadores movem alternadamente e onde o acaso não afeta o processo de decisão, se o jogo não pode terminar em um empate, então um dos dois jogadores devem ter uma estratégia de vitória. Mais formalmente, todos os jogos de forma extensiva-finita exibindo informações completas tem um equilíbrio de Nash que pode ser descoberto por indução retroativa. Se cada recompensa é única, para cada jogador, esta solução de indução retroativa é única.

Teorema de Zermelo

U*(q) ≠∅ é condição suficiente e necessária para que q seja posição vencedora.

Prova

[U*(q) ≠∅] Seja (q,q1,….,qn) um resultado em U*(q) com n > s [U*(q)= ∅] Existem Vw(q), conjuntos de sequências de movimentos, onde U não perde antes de s movimentos, e, todas as alternativas de movimentos para V estão

Observações

  1. Se w > w’ então V w(q) ⊆ Vw’(q)
  2. Existem infinitos w tais que Vw(q)≠∅ ou estes estão limitados a σ≤τ≤s, pois se V puder ganhar pode forçar a vitória em τ≤s passos.
  3. Fazendo V(q) = Vτ+1 (q), sabe-se que U pode forçar o empate se e somente se Vτ+1 (q) ≠∅

Ver também