Valor esperado positivo em um jogo, independentemente da estratégia de Ballmer

 (gukov.dev)
1 pontos por GN⁺ 2024-09-08 | 1 comentários | Compartilhar no WhatsApp
  • O quebra-cabeça de adivinhar números de Steve Ballmer é um jogo para encontrar um número entre 1 e 100; uma busca binária fixa pode ser explorada, mas, ao usar uma estratégia mista, é possível criar um valor esperado positivo independentemente da escolha do adversário
  • Ballmer acreditava que, mesmo com uma escolha aleatória, o valor esperado seria negativo e que ele poderia escolher números que demorassem mais para serem encontrados, mas John Graham-Cumming refutou isso, afirmando que, com escolha aleatória, o valor esperado é de US$ 0,20
  • Em um padrão de busca fixo, pelo menos 37 dos 100 números exigem 6 perguntas, gerando prejuízo; se o adversário conhecer a estratégia, pode fazer o jogador perder todas as vezes
  • A solução é uma estratégia mista da teoria dos jogos, escolhendo probabilisticamente uma entre várias estratégias puras de busca, de modo a eliminar números desfavoráveis ao nivelar a diferença entre vitórias e derrotas para cada número
  • Uma estratégia de exemplo encontrada ao resolver o problema de programação linear com scipy.linprog() gera lucro esperado médio de US$ 0,16 se Ballmer escolher aleatoriamente e, mesmo que escolha de forma adversarial, lucro esperado de US$ 0,14 no pior caso

O quebra-cabeça de adivinhar números e a refutação anterior

  • O quebra-cabeça de que Ballmer gostava é um jogo em que o adversário pensa em um número entre 1 e 100 e, a cada palpite do jogador, informa se o número é maior ou menor
  • A recompensa é US$ 5 se acertar no primeiro palpite; depois US$ 4, US$ 3, US$ 2, US$ 1, US$ 0 e, a partir daí, o jogador passa a pagar US$ 1, US$ 2, US$ 3, e assim por diante
  • Ballmer via dois motivos para não jogar esse jogo
    • Julgava que, mesmo escolhendo números aleatoriamente, haveria muitos números que gerariam perda, tornando o valor esperado negativo
    • Acreditava que poderia escolher estrategicamente os números que levariam mais tempo em uma busca binária
  • John Graham-Cumming, em “Steve Ballmer’s incorrect binary search interview question”, refutou Ballmer dizendo que, se ele escolhesse números aleatoriamente, o valor esperado seria positivo, de US$ 0,20
  • Indo além, também é possível encontrar uma estratégia com valor esperado positivo mesmo quando Ballmer escolhe os números estrategicamente

A fraqueza da busca binária fixa

  • Se o jogador sempre usa a mesma estratégia de busca binária, 37 dos 100 números exigem 6 perguntas até serem acertados
  • Se Ballmer conhecer essa estratégia fixa, pode escolher um desses 37 números “perdedores” e forçar prejuízo ao jogador
  • Essa vulnerabilidade não se limita a uma busca binária específica
    • Em qualquer padrão de busca fixo, pelo menos 37 números geram perda
    • Se o adversário escolher um desses números, o jogador perde todas as vezes

Resposta com estratégia mista

  • Em vez de fixar um único padrão de busca, prepara-se vários padrões de busca e, no início do jogo, sorteia-se probabilisticamente um deles, mantendo-o até o fim
  • Na teoria dos jogos, isso é chamado de estratégia mista baseada em várias estratégias puras
  • O mesmo número pode ser vencedor em um padrão de busca e perdedor em outro
  • O objetivo da estratégia mista é nivelar a receita esperada para cada número, fazendo com que o valor esperado seja positivo para todos os números

Encontrando a estratégia por programação linear

  • O objetivo não é encontrar a estratégia ótima que maximiza o valor esperado no pior caso, ou seja, o equilíbrio de Nash, mas sim encontrar alguma estratégia vencedora para todos os números
  • Cada estratégia pura pode ser representada por um vetor de vitória V = (v_1, .., v_100) de comprimento 100
    • v_k é o lucro esperado quando Ballmer escolhe o número k
    • Por exemplo, a busca binária pode ter valores como v_50 = 5, v_25 = 4, v_0 = -1
  • Se uma estratégia mista escolhe a estratégia pura V_k com probabilidade p_k, o vetor de vitória total se torna V_mixed = Σ p_i V_i
  • Para encontrar uma estratégia vencedora, é necessária uma combinação linear que satisfaça as seguintes condições
    • Cada elemento deve ser positivo
    • Os coeficientes, por serem probabilidades, não podem ser negativos
  • Esse é um problema típico de programação linear, que pode ser resolvido com scipy.optimize.linprog do SciPy
  • Ao criar um conjunto de estratégias puras com várias variantes de busca binária e colocá-las no código que usa scipy.linprog(), obtém-se uma estratégia mista vencedora

Estratégia de exemplo e resultados

  • O código completo está em gukoff/ballmer_puzzle
  • O resultado inicial era de US$ 0,07 por jogo, e Arthur O’Dwyer melhorou o desempenho adicionando novas estratégias puras
  • O desempenho da estratégia mista melhorada é o seguinte
    • Lucro médio quando Ballmer escolhe aleatoriamente: US$ 0,16
    • Lucro no pior caso quando Ballmer escolhe de forma adversarial: US$ 0,14
  • A estratégia mista de exemplo combina várias variantes de busca binária com pequenas probabilidades
    • Probabilidade de 0,4714%: primeiro palpite 29; depois, palpitar o meio do intervalo e, em caso de empate, escolher a esquerda
    • Probabilidade de 0,1691%: primeiro palpite 33; depois, palpitar o meio e, em caso de empate, escolher a esquerda
    • Probabilidade de 0,1299%: primeiro palpite 36; depois, palpitar o meio e, em caso de empate, escolher a direita
    • Probabilidade de 3,3341%: primeiro palpite 37; depois, palpitar o meio e, em caso de empate, escolher a direita
    • Probabilidade de 1,7818%: primeiro palpite 43; depois, escolher o elemento mais à direita dentro do intervalo que não aumenta a complexidade no pior caso
    • Probabilidade de 1,1608%: primeiro palpite 44; depois, escolher o elemento mais à esquerda dentro do intervalo que não aumenta a complexidade no pior caso
    • Probabilidade de 2,1310%: primeiro palpite 42; depois, escolher um elemento próximo à extremidade do intervalo que não aumenta a complexidade no pior caso
  • A estratégia completa tem 74 linhas, e a lista completa omitida pode ser vista na winning strategy no GitHub
  • Se um lucro médio de 14 centavos por jogo compensar o tempo gasto, vale a pena jogar caso Ballmer proponha esse jogo

Leituras relacionadas

1 comentários

 
GN⁺ 2024-09-08
Opiniões no Hacker News

  • Post relacionado recente: a pergunta errada de busca binária em entrevista de Steve Ballmer - https://news.ycombinator.com/item?id=41434637 - setembro de 2024, 240 comentários

  • A aplicação deste texto é legal, mas parece que ele deixa escapar o ponto central
    O argumento de Ballmer é, essencialmente, sobre risco de cauda. Se você dá importância à sobrevivência, valor esperado não é nem de longe um bom critério para apostar. Porque você só tem uma oportunidade. É o mesmo motivo pelo qual, no pôquer, não faz sentido apostar todo o seu patrimônio toda vez que você tem uma mão que “em valor esperado” deve ganhar; em poucas rodadas, você quase certamente vai quebrar
    Seja a média +US$0,07 ou o que for, a amplitude da distribuição claramente pode ir para abaixo de 0. Em média, talvez a probabilidade de ganhar seja um pouco maior do que a de perder, mas, na prática, você só recebe um resultado. Se o objetivo é ganhar ou estar acabado, e se você não quer ficar devendo dinheiro ao Ballmer, é melhor não jogar
    O mais interessante seria fazer uma simulação de Monte Carlo dessa estratégia e ver a distribuição de vitórias e derrotas. Aí a escolha talvez não seja tão óbvia
    Se desse para jogar alguns trilhões de vezes, aí claro que poderia arrancar tudo dele :P

    • Não sei de onde veio essa ideia de que “o argumento de Ballmer é essencialmente risco de cauda”. Não parece que ele tenha feito essa afirmação na entrevista. O problema e a explicação da resposta são apresentados apenas pela perspectiva do valor esperado de uma única execução do jogo, e a reviravolta é a escolha adversarial do número, não o risco de falência
      Mesmo como exemplo de risco de cauda, não é muito bom. Na estratégia óbvia, a cauda é extremamente grossa
    • Certo. O paradoxo de São Petersburgo mostra que sabemos disso intuitivamente. Coloco “paradoxo” entre aspas porque vejo isso menos como um paradoxo e mais como uma reação normal
      Sam Bankman-Fried gostava muito de valor esperado e ficou famoso por dizer que faria um lançamento de moeda que, se desse cara, dobraria o “valor” do mundo, mas, se desse coroa, destruiria o mundo
      Em resumo, o paradoxo de São Petersburgo é assim. Você lança uma moeda justa até sair cara, e o jogador recebe US$2^n, em que n é o número de lançamentos. Se sair cara no primeiro, recebe US$2; no segundo, US$4; no terceiro, US$8; no décimo, US$1024 (2^10), e assim por diante. É fácil mostrar que o valor esperado desse jogo se aproxima do infinito
      Portanto, uma pessoa perfeitamente racional deveria estar disposta a pagar praticamente qualquer quantia para jogar esse jogo. Como qualquer quantia finita é menor que o infinito, o ganho esperado é sempre positivo
      Mas provavelmente quase ninguém pagaria milhões de dólares para jogar esse jogo. Talvez SBF seja uma exceção
      Isso só é um paradoxo se você achar que mostra que as pessoas não são “racionais”. Na prática, parece significar que valor esperado não é uma boa medida de risco, e todo mundo sabe disso
      Um texto bastante completo e interessante sobre o paradoxo de São Petersburgo: https://plato.stanford.edu/entries/paradox-stpetersburg/
    • Não concordo. Acho que Ballmer estava simplesmente errado
      Ao contrário da maioria aqui, acho que esse tipo de pergunta é uma forma razoavelmente boa de ver como uma pessoa pensa. Se alguém tem formação em matemática/estatística/ciência da computação, eu esperaria que pelo menos conseguisse iniciar uma conversa sobre esse problema
      Mas, se você esconde premissas ou acrescenta restrições arbitrárias e infundadas para transformá-la em pegadinha, é aí que deixa de fazer sentido para mim
      Se a pergunta é “você jogaria este jogo?”, a tradução matemática racional é “determine se o valor esperado é maior que 0”. Se quiser falar de risco de cauda, é preciso especificar uma função de utilidade, que pode inclusive ser assimétrica para os dois jogadores. E é preciso dizer claramente que essa é a intenção
    • Acho que isso não está certo. A maioria das pessoas não vai à falência por perder 1 dólar. Se esse era o contexto, Steve falhou muito em comunicar esse contexto
      Sinceramente, parece que Steve não entendeu direito a profundidade matemática desse problema
    • Critério de Kelly
      Se você apostar mais do que a fração de Kelly, o risco de falência aumenta, especialmente no longo prazo
      https://en.m.wikipedia.org/wiki/Kelly_criterion
      Não estou dizendo que ele se aplique à situação do post original. Mas é relevante para o comentário-pai e é muito útil em várias situações, como investimentos

  • Quando Ballmer disse “adversarial”, pensei numa estratégia assim. Na verdade, ele não precisa escolher um número fixo no início. A cada palpite, basta dar a resposta que deixa o maior conjunto possível de números restantes; assim, contra qualquer estratégia, ele consegue garantir a derrota

    • Exato. Não sei se essa era mesmo a intenção, mas, se era, é engraçado como isso torna toda essa análise matemática completamente sem sentido
      O post original apresenta uma estratégia aleatória complexa que garante uma média mínima de $0.07 contra qualquer adversário. Já Ballmer, por outro lado, só precisa adiar a “escolha” e enrolar para forçar sete palpites toda vez e fazer você pagar 1 dólar
      Se você esperasse ganhar $0.07 em média, quantas rodadas jogaria antes de perceber que está sendo enganado?
    • Este comentário deveria estar mais acima
      O post original é interessante, mas assume um sentido bem fraco de “adversarial”, no qual Ballmer ainda se compromete com alguma escolha inicial
      Curiosamente, se Ballmer usar um esquema de compromisso, o jogador consegue verificar isso [1]. Por exemplo, no início do jogo, Ballmer gera 500 bits aleatórios, anexa a eles o número escolhido no intervalo de 1 a 100 e envia o hash do resultado. Ao fim do jogo, ele envia os 500 bits aleatórios, e o jogador pode então concatená-los com o número escolhido agora revelado e verificar se o hash resultante é o mesmo hash enviado no início. Para mentir e trocar o número, Ballmer teria de encontrar 500 bits que, concatenados a outro número, ainda produzissem o hash original, o que é difícil
      [1]: https://en.wikipedia.org/wiki/Commitment_scheme
    • Também pensei nisso. Parece uma variante adversarial de Wordle, como o Absurdle: https://qntm.org/files/absurdle/absurdle.html
      Foi feito pelo criador do HATERIS, uma variante de Tetris que sempre dá o pior bloco
    • Pela formulação das regras, parece que ele escolhe um número e o mantém. Ele disse que “tem um número na cabeça”. Claro que alguns entrevistadores distorcem as regras como se fosse uma disputa mental para parecerem inteligentes, mas aqui não parece ter sido essa a intenção
    • Na análise da razão competitiva de algoritmos online, é assim que se faz. O adversário pode mudar de ideia à vontade e só precisa se comprometer com as decisões já tomadas no passado

  • Edit: ah, não. Este comentário está errado. Obrigado ao fgna por apontar isso
    Acho que há uma prova mais simples de que dá para vencer um Ballmer adversarial. O resultado esperado é exatamente o mesmo de uma busca binária contra um Ballmer aleatório
    O nome do meu algoritmo é “busca binária com deslocamento aleatório”. Funciona assim

    1. Escolha um número aleatório entre 0 e 100 e chame-o de offset
    2. Execute o algoritmo de busca binária, mas, em cada etapa, some offset ao valor e use o resto da divisão por 100
      Só isso. Agora, mesmo que Ballmer conheça essa estratégia, ele não consegue escolher um número específico para piorar o desempenho. Portanto, o resultado esperado continua sendo $0.20 por jogo, melhor que a estratégia proposta no texto
    • Infelizmente, os números não são circulares :( Se você aplica um deslocamento ao número inicial, a busca binária deixa de funcionar de forma ótima, não? Imagine que o número seja menor que 50, mas você começa chutando 60; agora há 30 números a procurar, não 25, então não é ótimo
    • Legal. Fica fácil entender imaginando os números de 1 a 100 dispostos ao redor de um mostrador de relógio. É como girar o relógio aleatoriamente antes de começar a busca binária tradicional a partir do topo

  • Entre muitas coisas em que Ballmer esteve errado, parece que esta foi mais uma

    • Ballmer acertou ao apostar na Microsoft
    • Eu gostaria de estar errado como Ballmer. O saldo líquido das decisões dele foi de dezenas de bilhões de dólares
    • Você também precisa mostrar as coisas em que errou, para que possamos julgar
    • Minha favorita pessoal: https://www.youtube.com/shorts/rCszxibClKE

  • Isto, meus amigos, é um exemplo perfeito de por que o processo moderno de entrevistas técnicas é pura insanidade

    • Isso é mesmo um exemplo perfeito de entrevistas técnicas modernas quebradas?
      A pergunta de Ballmer parece justa considerando a complexidade da resposta que ele esperava
      O candidato provavelmente daria uma resposta matematicamente incorreta, mas, no processo, mostraria seu raciocínio e demonstraria um pouco de princípios de ciência da computação
      É preciso considerar que a carreira de Ballmer foi longa. Se ele realmente fez essa pergunta, provavelmente foi nos anos 80, e naquela época ninguém esperaria a solução complexa descrita no texto
      Dar a resposta correta seria algo impressionante e motivo para contratação imediata. Mas a pergunta não me parece fundamentalmente quebrada, porque, apostando ou não, qualquer resposta precisa ser bem justificada
    • Para ser justo, Steve Ballmer foi um líder péssimo e, se tivesse de passar por uma entrevista técnica, não teria sido aprovado. A Microsoft ficou estagnada por 10 anos até Satya Nadella assumir e reerguer a empresa
    • Será mesmo? Como entrevistador, se eu fosse obrigado a fazer essa pergunta e o candidato dissesse “na verdade, isso está errado; eis o motivo”, eu veria isso como um sinal muito bom. Não é isso que as pessoas normalmente fazem?
      Em geral há uma discussão com todos os entrevistadores, e não se olha apenas “o candidato acertou o problema?”. Pessoalmente, acho muitas perguntas de entrevistas de big tech idiotas, mas, tendo passado pelo processo dos dois lados, acho que ele não é tão quebrado quanto parece
    • Não trabalho na área de tecnologia, mas sempre achei que perguntas assim fossem desenhadas para mostrar capacidade de resolver problemas, independentemente de haver uma resposta certa
      Neste caso, bastaria mostrar que você consegue raciocinar sobre busca binária e demonstrar que o lucro médio é de 0,20 dólar
    • Acho válido enquanto for usado para descobrir se seria agradável as duas partes trabalharem juntas. Mas, cada vez mais, isso vira um quiz ou algo pior
      Ainda assim, graças a isso ganhamos boa ficção como https://aphyr.com/posts/340-reversing-the-technical-intervie... e suas continuações

  • Um texto que analisa o equilíbrio de Nash de forma mais ampla, incluindo a solução numérica do jogo completo, está em https://bowaggoner.com/blahg/2024/09-06-adversarial-binary-s...

  • O patrimônio líquido de Steve Ballmer é de US$ 120 bilhões; se uma partida do jogo leva 30 segundos, levaria 1,6 milhão de anos para ganhar tudo

    • Basta fazer computadores jogarem entre si. A IA do meu computador contra a IA de Ballmer. Seria rodar 1 trilhão 683 bilhões 605 milhões 1984 partidas de computador em 30 segundos

  • Little Mathematics Library – Elements of Game Theory: https://mirtitles.org/2012/09/06/little-mathematics-library-...
    É um livro muito bom sobre estratégias mistas em teoria dos jogos
    O exemplo motivacional apresentado no livro também é excelente
    “Há duas cartas: um ás e um 2. O jogador A tira aleatoriamente uma delas, e B não vê qual carta foi tirada. Se A tirou o ás, ele diz ‘tenho o ás’ e exige 1 dólar do adversário. Se A tirou o 2, pode (A1) dizer ‘tenho o ás’ e exigir 1 dólar do adversário, ou (A2) confessar que tem o 2 e dar 1 dólar ao adversário
    Se o adversário receber voluntariamente 1 dólar, não tem escolha a não ser aceitar. Mas, se for cobrado 1 dólar, ele pode (B1) acreditar que A tem o ás e pagar 1 dólar, ou (B2) exigir uma verificação para ver se a afirmação de A é verdadeira. Se A realmente tiver o ás, B deve pagar 2 dólares a A. Por outro lado, se A estava blefando e tinha o 2, A paga 2 dólares a B
    Analise este jogo e encontre a estratégia ótima de cada jogador e o payoff esperado”