Todo jogo finito tem um ponto de equilíbrio.

— John Nash, Non-Cooperative Games, tese de doutorado (1950)

Alguns jogos não têm equilíbrio nenhum se cada jogador escolher uma jogada fixa. O mais simples é o par ou ímpar. Ana escolhe “par”, Bruno escolhe “ímpar”, e cada um mostra um ou dois dedos. Se a soma for par, Ana ganha um ponto; se for ímpar, ganha Bruno. Reduzindo cada escolha a “um” ou “dois” dedos, os ganhos são:

Ana / Bruno 1 dedo 2 dedos
1 dedo (1, −1) (−1, 1)
2 dedos (−1, 1) (1, −1)

Teste as quatro combinações: em cada uma, quem perdeu ganharia trocando a sua jogada. Não há equilíbrio em jogadas fixas. Faz sentido: quem joga sempre a mesma coisa é derrotado assim que o outro percebe.

Sortear é a melhor estratégia

A saída é misturar: escolher ao acaso, com certas probabilidades. Uma estratégia mista é uma distribuição de probabilidades sobre as jogadas. Suponha que Ana mostre 1 dedo com probabilidade $p$ e Bruno com probabilidade $q$, sorteados de forma independente.

Se Ana mostrar 1 dedo, o seu ganho esperado é $q\cdot1+(1-q)\cdot(-1)=2q-1$. Se mostrar 2 dedos, é $q\cdot(-1)+(1-q)\cdot1=1-2q$. Ana só aceita misturar as duas jogadas se elas lhe derem o mesmo ganho, ou seja, se Bruno a deixar indiferente:

$$2q-1=1-2q\quad\Longrightarrow\quad q=\frac12.$$

Pelo mesmo raciocínio, Bruno só mistura se $p=\frac12$. O único equilíbrio é cada um jogar 1 ou 2 dedos com chance de 50%. Contra essa mistura, nenhuma estratégia, pura ou mista, dá ao outro um ganho esperado maior que zero.

O teorema de Nash

Esse é o grande resultado da tese de 1950: todo jogo com um número finito de jogadores e de jogadas tem pelo menos um equilíbrio de Nash, se forem permitidas estratégias mistas.

A prova usa um teorema de ponto fixo. Para cada combinação de estratégias mistas, construa outra, em que cada jogador desloca um pouco a sua mistura na direção das jogadas que lhe dariam mais ganho. Isso define uma função contínua do conjunto das combinações nele mesmo. Esse conjunto é como uma bola sem buracos, e o teorema de Brouwer garante que toda função contínua de uma bola nela mesma tem um ponto fixo: uma combinação que a função não move. Um ponto que não se move é exatamente uma combinação em que ninguém quer mudar: um equilíbrio.

O teorema garante que o equilíbrio existe, mas não diz que ele é único, nem que é fácil de calcular. Hoje se sabe que, em jogos grandes, encontrar um equilíbrio de Nash pode ser um problema computacional dificílimo.

O pênalti

O exemplo mais famoso de estratégia mista acontece nos estádios. Num pênalti, o batedor escolhe o canto, e o goleiro precisa pular antes de ver a bola. Para um batedor destro, o canto natural é o seu lado esquerdo, que é o lado direito do goleiro. Suponha que as chances de gol sejam estas:

Batedor / Goleiro Goleiro pula no canto natural Goleiro pula no outro canto
Chuta no canto natural 60% 95%
Chuta no outro canto 90% 70%

Os números são arredondados, mas estão perto dos dados reais do futebol europeu: o batedor quase não erra quando o goleiro pula para o lado errado, e o canto natural é o mais confortável para chutar, mas também o que o goleiro defende melhor quando acerta o lado.

Se o batedor chuta no canto natural com probabilidade $p$, o goleiro fica indiferente quando os dois pulos dão a mesma chance de gol:

$$0{,}60p+0{,}90(1-p)=0{,}95p+0{,}70(1-p)\quad\Longrightarrow\quad0{,}20=0{,}55p\quad\Longrightarrow\quad p\approx0{,}36.$$

E se o goleiro pula para o canto natural com probabilidade $q$, o batedor fica indiferente quando

$$0{,}60q+0{,}95(1-q)=0{,}90q+0{,}70(1-q)\quad\Longrightarrow\quad0{,}25=0{,}55q\quad\Longrightarrow\quad q\approx0{,}45.$$

No equilíbrio, o batedor chuta no canto natural só 36% das vezes, e o goleiro pula para lá 45% das vezes. A chance de gol fica em cerca de 79%. A explicação: quando o goleiro acerta o lado, o canto natural é o mais fácil de defender, 60% de gol contra 70%, e o batedor compensa usando mais o outro canto. Mas não pode usá-lo sempre, senão o goleiro passaria a pular só para lá.

Exercício: no par ou ímpar, se Bruno mostra 1 dedo com probabilidade 0,8, qual é a melhor resposta de Ana?

Mostrando 1 dedo, Ana ganha em média $2(0{,}8)-1=0{,}6$. Mostrando 2, ganha $-0{,}6$. Ela deve mostrar sempre 1 dedo. Qualquer mistura diferente de 50% pode ser explorada.

Exercício: no pedra, papel e tesoura, qual é o equilíbrio de Nash?

Por simetria, cada jogador escolhe cada uma das três opções com probabilidade $\frac13$. Contra essa mistura, qualquer escolha ganha, empata e perde com a mesma chance, $\frac13$, e o ganho esperado é zero. Se um jogador jogasse pedra mais de $\frac13$ das vezes, o outro passaria a jogar mais papel.

Fontes: John F. Nash, “Non-cooperative games”, Annals of Mathematics 54 (1951) · Ignacio Palacios-Huerta, “Professionals play minimax”, The Review of Economic Studies 70 (2003) · Avinash Dixit e Barry Nalebuff, A Arte da Estratégia (Campus, 2010).

Todos os tópicos de John Nash · ← O equilíbrio de Nash: ninguém melhora sozinho · A solução de barganha de Nash →

Créditos das imagens.