Curso

Problema da semanaTeoria dos jogos

O duelo dos números sorteados

Enunciado

Difícil

Ana e Beto jogam o seguinte jogo. Cada um recebe, em segredo, um número sorteado ao acaso entre 0 e 1, com todos os valores igualmente prováveis. Olhando só o próprio número, cada um decide se fica com ele ou se o descarta e sorteia outro, com o qual é obrigado a ficar. As decisões são tomadas ao mesmo tempo, sem que um saiba o que o outro fez. Ganha quem terminar com o número maior.

Se Beto nunca troca de número, qual a melhor estratégia para Ana, e com que probabilidade ela vence?

Se os dois jogam bem, qual estratégia nenhum dos dois tem motivo para abandonar?

Dica

Pense em estratégias do tipo trocar sempre que o número estiver abaixo de um limiar. Fixe a estratégia do adversário e compare, para o seu número, a chance de vencer ficando com ele e a chance de vencer trocando. No equilíbrio, quem tira exatamente o número do limiar fica indiferente entre as duas opções.

Solução completa

Contra quem nunca troca

Se Beto nunca troca, o número final dele é uniforme entre 0 e 1. Ana, com o número \( x \), vence ficando com ele com probabilidade \( x \), a chance de o número de Beto ser menor. Se trocar, o número novo dela também é uniforme, e ela vence com probabilidade de 0,5. Ana deve ficar quando \( x > 1/2 \) e trocar quando \( x < 1/2 \). A probabilidade de vitória é

$$ \int_0^{1/2} \tfrac12\,dx + \int_{1/2}^{1} x\,dx = \tfrac14 + \tfrac38 = \tfrac58 $$

Por que a resposta tem a forma de um limiar

Fixe a estratégia de Beto e chame de \( F(y) \) a probabilidade de o número final dele ser no máximo \( y \). Ana, com o número \( x \), vence ficando com probabilidade \( F(x) \), que cresce com \( x \). Trocando, vence com probabilidade \( \mathbb{E}[F(U)] \), em que \( U \) é o número novo, e isso não depende de \( x \). Então a melhor resposta é sempre ficar acima de um corte e trocar abaixo dele, qualquer que seja a estratégia de Beto.

O equilíbrio, pelo atalho da indiferença

Suponha que Beto troca abaixo do limiar \( t \). O número final dele fica abaixo de \( y \) de dois jeitos. Ele tirou menos que \( t \), trocou e o novo saiu abaixo de \( y \), com probabilidade \( t\,y \). Ou ele tirou um número entre \( t \) e \( y \) e ficou com ele, o que só existe quando \( y > t \). Então

$$ F(y) = \begin{cases} t\,y, & y < t,\\ t\,y + (y - t), & y \ge t. \end{cases} $$

Num equilíbrio simétrico, Ana usa o mesmo limiar, e quem tira exatamente \( t \) fica indiferente entre ficar e trocar. Ficar com \( t \) vence com probabilidade \( F(t) = t^2 \). Trocar vence com

$$ \mathbb{E}[F(U)] = \int_0^1 F(y)\,dy = \frac{t}{2} + \frac{(1-t)^2}{2} $$

Igualando as duas,

$$ t^2 = \frac{t}{2} + \frac{(1-t)^2}{2} \quad\Longrightarrow\quad t^2 + t - 1 = 0 \quad\Longrightarrow\quad t = \frac{\sqrt5 - 1}{2} \approx 0{,}618 $$

É o inverso da razão áurea. Com esse limiar, cada jogador descarta o primeiro número em cerca de 61,8% das partidas, e cada um vence metade das vezes, por simetria.

O caminho braçal, maximizando a chance de vitória

Sem usar a indiferença, escreva a chance de Ana vencer usando o limiar \( s \) contra Beto no limiar \( t \). Ela troca quando o primeiro número fica abaixo de \( s \) e fica com ele quando passa, então

$$ W(s, t) = \int_0^s \mathbb{E}[F(U)]\,dx + \int_s^1 F(x)\,dx = s\,\mathbb{E}[F(U)] + \int_s^1 F(x)\,dx $$

Derivando em \( s \), \( \partial W/\partial s = \mathbb{E}[F(U)] - F(s) \), que é positiva enquanto \( F(s) \) está abaixo de \( \mathbb{E}[F(U)] \) e negativa depois. O máximo fica onde as duas se igualam, a mesma condição de indiferença, e impondo \( s = t \) volta a equação \( t^2 + t - 1 = 0 \). A indiferença do atalho é a condição de primeira ordem desse problema de máximo, lida direto no jogador que está no limiar.

A intuição

Contra quem nunca troca, o corte era \( 1/2 \). Contra quem também troca, o corte sobe para cerca de 0,618, porque o número final do adversário tende a ser melhor que um sorteio uniforme. Um 0,55, que valia a pena guardar contra o Beto que nunca troca, vira número para descartar. Contra o limiar de equilíbrio, ficar com 0,55 vence com probabilidade de cerca de 0,34, que é o limiar vezes 0,55, e trocar vence com \( t^2 \), cerca de 0,38.

Resposta

  • Contra quem nunca troca, Ana troca abaixo de 0,5 e fica com o número acima disso.
  • Assim ela vence com probabilidade \( 5/8 \), ou 62,5%.
  • No equilíbrio, os dois trocam abaixo de \( (\sqrt5-1)/2 \), cerca de 0,618, e ficam com o número acima disso.

O que foi conferido e como

As respostas contra quem nunca troca foram calculadas com frações exatas, maximizando o polinômio da chance de vitória numa grade de mil limiares. O equilíbrio foi conferido sem a conta da indiferença. A chance de vitória \( W(s,t) \) foi integrada numericamente a partir das regras do jogo, a derivada em \( s \) foi tirada por diferenças finitas, e o ponto em que ela zera bateu com \( (\sqrt5-1)/2 \) até a sexta casa. Numa grade de 10 mil limiares, a melhor resposta ao limiar de equilíbrio é ele mesmo. Uma simulação de 1 milhão de partidas com semente fixa confirmou, dentro de 4,5 erros padrão, a vitória de \( 5/8 \), a indiferença de quem tira o limiar, a fração de partidas com troca e a chance de vitória de três limiares contra o de equilíbrio. Os números da intuição, no fim da solução, também são recalculados e comparados com o texto.