Euler's Eyes
2026-10-26
O teorema minimax: como jogar sem ser adivinhado
No par ou ímpar, não existe jogada boa. Se você sempre põe um dedo, o adversário aprende e passa a ganhar sempre. A única defesa é não ser previsível: jogar ao acaso, metade das vezes um, metade das vezes dois. Assim, faça o adversário o que fizer, você ganha metade das partidas.
Em 1928, num artigo chamado Sobre a teoria dos jogos de salão, von Neumann mostrou que essa ideia vale para todo jogo de soma zero entre duas pessoas, em que o que um ganha o outro perde. E que ela leva sempre a um número exato, o valor do jogo.
Um jogo pequeno
Linha escolhe A ou B; Coluna escolhe C ou D, ao mesmo tempo. A tabela diz quanto Linha recebe (e Coluna paga):
| C | D | |
|---|---|---|
| A | $3$ | $-1$ |
| B | $-2$ | $1$ |
Não há escolha óbvia. Se Linha joga sempre A, Coluna responde com D e Linha perde $1$. Se joga sempre B, Coluna responde com C e Linha perde $2$. Suponha então que Linha sorteie: joga A com probabilidade $p$ e B com probabilidade $1 - p$. O ganho esperado de Linha é
$$\text{contra C: } 3p - 2(1-p) = 5p - 2, \qquad \text{contra D: } -p + (1-p) = 1 - 2p.$$Coluna escolherá a resposta que der menos a Linha. Então Linha pode contar apenas com o menor dos dois valores, e quer escolher $p$ para que esse mínimo seja o maior possível. Isso acontece onde as retas se cruzam:
$$5p - 2 = 1 - 2p \;\Longrightarrow\; p = \frac{3}{7}, \qquad \text{ganho garantido} = 5 \cdot \frac{3}{7} - 2 = \frac{1}{7}.$$O valor do jogo
Agora o raciocínio de Coluna: jogando C com probabilidade $q$, ela paga a Linha $4q - 1$ se Linha jogar A e $1 - 3q$ se jogar B. O melhor para Coluna é igualar os dois: $q = \frac{2}{7}$, e então paga no máximo $\frac17$.
Os dois números coincidem. Linha consegue garantir pelo menos $\frac17$; Coluna consegue garantir pagar no máximo $\frac17$. Esse é o teorema minimax:
$$\max_{p}\,\min_{q}\; G(p, q) \;=\; \min_{q}\,\max_{p}\; G(p, q),$$em que $G$ é o ganho esperado de Linha. O lado esquerdo é o melhor que Linha consegue garantir sozinha; o direito, o melhor que Coluna consegue garantir sozinha. Von Neumann provou que eles são sempre iguais, para qualquer tabela finita, desde que os jogadores possam sortear.
Não, não, o xadrez não é um jogo. O xadrez é uma forma bem definida de cálculo. […] Os jogos de verdade não são nada assim. A vida real é feita de blefe, de pequenas táticas de engano, de perguntar a si mesmo o que o outro vai pensar que eu pretendo fazer. É disso que tratam os jogos na minha teoria.
— John von Neumann, numa conversa de táxi em Londres relatada por Jacob Bronowski em The Ascent of Man (1973)
Do salão à economia
Em 1944, von Neumann e o economista austríaco Oskar Morgenstern publicaram a Teoria dos jogos e do comportamento econômico, um livro de mais de seiscentas páginas que levou o minimax para mercados, leilões e negociações, e definiu a utilidade esperada de um jeito que os economistas usam até hoje. Seis anos depois, um jovem de Princeton chamado John Nash mostrou como estender a ideia aos jogos em que não há soma zero, com o equilíbrio que leva o seu nome.
Exercício: o par ou ímpar
No par ou ímpar, quem acerta a paridade da soma ganha $1$ e o outro perde $1$. Mostre que jogar 1 ou 2 dedos com probabilidade $\frac12$ cada garante ganho esperado $0$, faça o adversário o que fizer.
Se eu jogo 1 com probabilidade $\frac12$ e o adversário joga 1, a soma é par ou ímpar com probabilidade $\frac12$ cada: ganho esperado $\frac12 \cdot 1 + \frac12 \cdot (-1) = 0$. O mesmo vale se ele jogar 2. O valor do jogo é $0$: nenhum dos dois tem vantagem, mas só quem sorteia está protegido.
Exercício: a estratégia de Coluna
Confira que, com $q = \frac{2}{7}$, Coluna paga exatamente $\frac17$ tanto contra A quanto contra B.
Contra A: $3 \cdot \frac27 + (-1) \cdot \frac57 = \frac{6 - 5}{7} = \frac17$. Contra B: $-2 \cdot \frac27 + 1 \cdot \frac57 = \frac{-4 + 5}{7} = \frac17$. Como paga o mesmo nos dois casos, Linha não tem como explorar a escolha de Coluna.
Fontes: John von Neumann, “Zur Theorie der Gesellschaftsspiele”, Mathematische Annalen (1928) · John von Neumann e Oskar Morgenstern, Theory of Games and Economic Behavior (1944) · Jacob Bronowski, The Ascent of Man (1973).
Todos os tópicos de John von Neumann · ← Os ordinais: números feitos de conjuntos vazios · A mecânica quântica num espaço de Hilbert →