Steve Ballmer estava errado
Há alguns dias, John Graham-Cumming publicou um texto sobre a "pergunta errada de entrevista sobre busca binária de Steve Ballmer", que recebeu muita atenção no HackerNews. O quebra-cabeça favorito de Ballmer é o seguinte:
Estou pensando em um número entre 1 e 100. Você pode tentar adivinhar, e depois de cada tentativa eu direi se é mais alto ou mais baixo. Se você acertar na primeira tentativa, eu lhe darei US$ 5. US$ 4, US$ 3, US$ 2, US$ 1, US$ 0; depois você terá de me pagar US$ 1, US$ 2, US$ 3.
Você jogaria este jogo?
Steve Ballmer apresenta duas razões, nesta entrevista no YouTube, para não jogar esse jogo:
- Muitos números entre 1 e 100 levam a prejuízo, então mesmo escolhendo números aleatoriamente o valor esperado é negativo.
- Ele pode escolher estrategicamente o número que leva mais tempo para ser encontrado usando busca binária.
No entanto, John rebate o primeiro ponto ao mostrar que, se Ballmer escolher o número aleatoriamente, o valor esperado do jogo é na verdade US$ 0,20, ou seja, positivo.
Vou rebater o segundo ponto e provar que o valor esperado do jogo é positivo independentemente da estratégia de Ballmer.
Como Ballmer pode escolher o número de forma adversarial
Vamos supor que você sempre use uma estratégia de busca binária para encontrar o número. Entre os 100 números, 37 exigem 6 perguntas para serem descobertos. Se Ballmer conhece sua estratégia, ele pode sempre escolher um desses números de "derrota", causando prejuízo em toda partida. Isso sempre vale para qualquer padrão fixo de busca. Pelo menos 37 números causarão prejuízo, e Ballmer pode escolher um deles.
Como responder a isso?
Aqui entramos no campo da teoria dos jogos. Em vez de um único padrão fixo de busca, podemos preparar um conjunto de vários padrões de busca.
Em seguida, no início do jogo, escolhemos um desses padrões probabilisticamente e mantemos esse padrão durante toda a partida.
Na teoria dos jogos, isso é chamado de estratégia mista, baseada em um conjunto de estratégias de várias estratégias puras.
Como o mesmo número pode ser "vitória" em um padrão de busca e "derrota" em outro, essas estratégias mistas podem "nivelar" o retorno esperado de cada número. Potencialmente, uma estratégia mista pode transformar todos os números em "vitórias", isto é, ter retorno esperado positivo para cada número. É isso que estamos procurando.
Como encontrar uma estratégia mista vencedora
Observação: queremos encontrar alguma estratégia que vença para todos os números, e não a melhor estratégia vencedora (equilíbrio de Nash) com o maior valor esperado no pior caso.
Se você tiver curiosidade sobre equilíbrio de Nash, Arthur O’Dwyer explorou uma solução em forma fechada para o jogo com até 5 números, e Bo Waggoner aproximou o valor de equilíbrio do jogo com 100 números usando aprendizado online sem arrependimento.
Encontrar uma estratégia mista vencedora para todos os números pode ser visto como um problema de otimização matemática. Cada estratégia pode ser descrita por um vetor de "vitória" V=(v1,..,v100), em que vk é o ganho esperado quando Ballmer escolhe o número k. Por exemplo, a busca binária pode corresponder a um vetor com v50=5, v25=4, v0=−1.
Suponha que tenhamos estratégias puras V1, V2, ..., Vn, e que a estratégia mista escolha a estratégia Vk com probabilidade pk. Então o vetor de "vitória" correspondente da estratégia mista é simplesmente a combinação linear: Vmixed=∑i=1npiVi.
Nessa interpretação, encontrar uma estratégia vencedora significa encontrar uma combinação linear com duas restrições:
- Cada elemento da combinação linear é positivo (é possível ganhar dinheiro, em média, para cada número).
- Os coeficientes dessa combinação linear não são negativos (pois correspondem a probabilidades).
Este é um problema típico de programação linear, e o scipy tem uma solução eficiente para isso. Para encontrar uma estratégia mista, pensei em várias estratégias puras (diferentes buscas binárias) e as alimentei em scipy.linprog(), e voilà — a solução apresentou uma estratégia vencedora!
Exemplo de estratégia vencedora
O código completo está em gukoff/ballmer_puzzle. Observação: o resultado inicial de US$ 0,07 foi bastante melhorado por Arthur O’Dwyer ao adicionar novas estratégias puras.
- Ganho médio se Ballmer escolher aleatoriamente: US$ 0,16
- Pior ganho se Ballmer escolher de forma adversarial: US$ 0,14
A estratégia mista resultante é a seguinte:
- Probabilidade de 0,4714%: busca binária, primeiro palpite 29. Em cada etapa, adivinhar o elemento do meio do intervalo. Em caso de empate, adivinhar o elemento da esquerda
- Probabilidade de 0,1691%: busca binária, primeiro palpite 33. Em cada etapa, adivinhar o elemento do meio do intervalo. Em caso de empate, adivinhar o elemento da esquerda
- Probabilidade de 0,1299%: busca binária, primeiro palpite 36. Em cada etapa, adivinhar o elemento do meio do intervalo. Em caso de empate, adivinhar o elemento da direita
- Probabilidade de 3,3341%: busca binária, primeiro palpite 37. Em cada etapa, adivinhar o elemento do meio do intervalo. Em caso de empate, adivinhar o elemento da direita
- Probabilidade de 1,7818%: busca binária, primeiro palpite 43. Em cada etapa, adivinhar o elemento mais à direita do intervalo que não aumente a complexidade no pior caso
- Probabilidade de 1,1608%: busca binária, primeiro palpite 44. Em cada etapa, adivinhar o elemento mais à esquerda do intervalo que não aumente a complexidade no pior caso
- Probabilidade de 2,1310%: busca binária, primeiro palpite 42. Em cada etapa, adivinhar o elemento da extremidade do intervalo que não aumente a complexidade no pior caso
...
A estratégia completa tem 74 linhas e foi omitida por brevidade. Se tiver interesse, você pode conferi-la no GitHub.
Conclusão
Se é possível ganhar, em média, 14 centavos por jogo, então da próxima vez que Steve Ballmer oferecer esse jogo, você definitivamente deveria aceitar.
Resumo do GN⁺
- Este artigo trata da controvérsia sobre o jogo de busca binária de Steve Ballmer.
- Explica como usar teoria dos jogos para encontrar uma estratégia mista que vence independentemente da estratégia de Ballmer.
- O artigo pode ser útil para pessoas interessadas em teoria dos jogos e problemas de otimização.
- Outros projetos com funcionalidade semelhante incluem várias pesquisas e artigos relacionados à teoria dos jogos.
1 comentários
Opiniões do Hacker News
O argumento de Ballmer é sobre risco de cauda
Quando Ballmer disse "hostil", ele estava considerando que não precisa escolher um número fixo
Foi proposto um algoritmo chamado "busca binária com deslocamento aleatório"
Isso é apenas mais uma das muitas coisas em que Ballmer estava errado
Recomendaram o livro "Little Mathematics Library – Elements of Game Theory"
Foi compartilhado um link com uma análise mais ampla do equilíbrio de Nash e uma solução numérica para o jogo completo
O processo moderno de entrevistas técnicas é um exemplo de pura insanidade
Eu estava procurando um comentário do tipo "isso parece certo, bom trabalho!", mas como não havia um, deixo o meu
O patrimônio líquido de Steve Ballmer é de US$ 120 bilhões