Valeur espérée positive d’un jeu, indépendamment de la stratégie de Ballmer

Steve Ballmer avait tort

Il y a quelques jours, un billet de John Graham-Cumming sur la « mauvaise question d’entretien sur la recherche binaire de Steve Ballmer » a beaucoup attiré l’attention sur Hacker News. La devinette préférée de Ballmer est la suivante :

Je pense à un nombre entre 1 et 100. Vous pouvez le deviner, et après chaque tentative je vous dirai si c’est plus haut ou plus bas. Si vous trouvez dès la première tentative, je vous donnerai 5 dollars. Puis 4 dollars, 3 dollars, 2 dollars, 1 dollar, 0 dollar, ensuite c’est vous qui devrez me payer 1 dollar, 2 dollars, 3 dollars.

Joueriez-vous à ce jeu ?

Dans cette interview YouTube, Steve Ballmer avance deux raisons pour lesquelles il ne faudrait pas jouer à ce jeu :

1. Beaucoup de nombres entre 1 et 100 entraînent une perte, donc même si l’on choisit des nombres au hasard, la valeur espérée est négative.
2. Il peut choisir stratégiquement le nombre qui prend le plus de temps à trouver avec une recherche binaire.

John réfute cependant le premier point en montrant que si Ballmer choisit le nombre au hasard, la valeur espérée du jeu est en réalité positive, à 0,20 $.

Je vais réfuter le second point et démontrer que la valeur espérée du jeu est positive, quelle que soit la stratégie de Ballmer.

Comment Ballmer peut choisir le nombre de manière hostile

Supposons que vous utilisiez toujours une stratégie de recherche binaire pour trouver le nombre. Sur les 100 nombres, 37 nécessitent 6 questions pour être trouvés. Si Ballmer connaît votre stratégie, il peut toujours choisir l’un de ces nombres « perdants » et vous faire perdre à chaque partie. Cela reste vrai pour n’importe quel schéma de recherche fixe. Au moins 37 nombres entraîneront une perte, et Ballmer peut en choisir un.

Comment réagir ?

C’est ici qu’on entre dans le domaine de la théorie des jeux. Au lieu d’un seul schéma de recherche fixe, on peut préparer un ensemble de plusieurs schémas. Puis, au début de la partie, on choisit l’un de ces schémas de manière probabiliste et on s’y tient pendant toute la partie.

En théorie des jeux, on appelle cela une stratégie mixte, fondée sur un ensemble de stratégies pures.

Comme un même nombre peut être « gagnant » dans un schéma de recherche et « perdant » dans un autre, ces stratégies mixtes peuvent « lisser » le gain espéré de chaque nombre. Potentiellement, une stratégie mixte peut rendre tous les nombres « gagnants », c’est-à-dire donner un gain espéré positif pour chaque nombre. C’est ce que nous cherchons.

Comment trouver une stratégie mixte gagnante

Remarque : nous cherchons une stratégie qui gagne sur tous les nombres, pas forcément la meilleure stratégie gagnante (équilibre de Nash) qui maximise l’espérance dans le pire cas.

Si la question des équilibres de Nash vous intéresse, Arthur O’Dwyer a étudié une solution fermée pour le jeu jusqu’à 5 nombres, et Bo Waggoner a approché la valeur d’équilibre du jeu à 100 nombres à l’aide de l’apprentissage en ligne sans regret.

Trouver une stratégie mixte gagnante pour tous les nombres peut se voir comme un problème d’optimisation mathématique. Chaque stratégie peut être décrite par un vecteur de « gains » V=(v1,..,v100), où vk est le gain espéré si Ballmer choisit le nombre k. Par exemple, une recherche binaire peut correspondre à un vecteur avec v50=5, v25=4, v0=−1.

Supposons que l’on dispose de stratégies pures V1, V2, ..., Vn, et que la stratégie mixte choisisse la stratégie Vk avec une probabilité pk. Alors le vecteur de « gains » correspondant de la stratégie mixte est simplement une combinaison linéaire : Vmixed=∑i=1npiVi.

Dans cette interprétation, trouver une stratégie gagnante revient à trouver une combinaison linéaire avec deux contraintes :

• chaque élément de la combinaison linéaire est positif (on peut gagner de l’argent en moyenne sur chaque nombre) ;
• les coefficients de cette combinaison linéaire ne sont pas négatifs (ils correspondent à des probabilités).

C’est un problème classique de programmation linéaire, et scipy propose une solution efficace pour cela. J’ai imaginé plusieurs stratégies pures (diverses variantes de recherche binaire), je les ai données à scipy.linprog(), et voilà : la solution fournit une stratégie gagnante.

Exemple de stratégie gagnante

Le code complet se trouve dans gukoff/ballmer_puzzle. Remarque : le résultat initial de 0,07 $ a été fortement amélioré quand Arthur O’Dwyer a ajouté de nouvelles stratégies pures.

• Gain moyen si Ballmer choisit au hasard : 0,16 $
• Gain minimal si Ballmer choisit de manière hostile : 0,14 $

La stratégie mixte obtenue est la suivante :

• probabilité 0,4714 % : recherche binaire, première tentative 29. À chaque étape, on devine l’élément du milieu de l’intervalle. En cas d’égalité, on choisit l’élément de gauche
• probabilité 0,1691 % : recherche binaire, première tentative 33. À chaque étape, on devine l’élément du milieu de l’intervalle. En cas d’égalité, on choisit l’élément de gauche
• probabilité 0,1299 % : recherche binaire, première tentative 36. À chaque étape, on devine l’élément du milieu de l’intervalle. En cas d’égalité, on choisit l’élément de droite
• probabilité 3,3341 % : recherche binaire, première tentative 37. À chaque étape, on devine l’élément du milieu de l’intervalle. En cas d’égalité, on choisit l’élément de droite
• probabilité 1,7818 % : recherche binaire, première tentative 43. À chaque étape, on devine l’élément le plus à droite de l’intervalle sans augmenter la complexité dans le pire des cas
• probabilité 1,1608 % : recherche binaire, première tentative 44. À chaque étape, on devine l’élément le plus à gauche de l’intervalle sans augmenter la complexité dans le pire des cas
• probabilité 2,1310 % : recherche binaire, première tentative 42. À chaque étape, on devine l’élément extrême de l’intervalle sans augmenter la complexité dans le pire des cas

...

La stratégie complète comporte 74 lignes et est omise ici par souci de concision. Si cela vous intéresse, vous pouvez la consulter sur GitHub.

Conclusion

Si l’on peut gagner en moyenne 14 cents par partie, alors la prochaine fois que Steve Ballmer vous proposera ce jeu, il faudra absolument accepter.

Résumé de GN⁺

• Cet article traite du débat autour du jeu de recherche binaire de Steve Ballmer.
• Il explique comment utiliser la théorie des jeux pour trouver une stratégie mixte qui permet de gagner quelle que soit la stratégie de Ballmer.
• L’article peut être utile à celles et ceux qui s’intéressent à la théorie des jeux et aux problèmes d’optimisation.
• Parmi les autres projets aux fonctions similaires, on trouve divers travaux et articles de recherche liés à la théorie des jeux.

[GN⁺]

Avis Hacker News

• L’argument de Ballmer porte sur le risque de queue

  • Si l’on privilégie la survie, la valeur espérée n’est pas une bonne manière de parier
  • C’est la même raison pour laquelle on ne fait pas tapis à chaque fois au poker, même avec une espérance élevée
  • En moyenne, on peut avoir plus de chances de gagner, mais on n’obtient qu’un seul résultat
  • Si l’objectif est de gagner, mieux vaut ne pas devoir d’argent à Ballmer
  • Il serait plus intéressant d’examiner la distribution des victoires et des défaites de cette stratégie via une simulation de Monte-Carlo

• Quand Ballmer dit qu’il est « hostile », il prend en compte le fait qu’il n’a pas besoin de choisir un nombre fixe

  • Pour chaque supposition, il peut donner la réponse qui laisse le plus grand nombre possible de nombres compatibles, et ainsi garantir la défaite quelle que soit la stratégie

• Proposition d’un algorithme appelé « recherche binaire à décalage aléatoire »

  • Choisir un nombre aléatoire entre 0 et 100 et l’appeler « décalage »
  • Exécuter l’algorithme de recherche binaire, mais en ajoutant le « décalage » à chaque étape puis en appliquant un modulo 100
  • Même si Ballmer connaît cette stratégie, il ne peut pas choisir un nombre précis pour en dégrader les performances
  • Le résultat espéré reste donc de 0,20 $ par partie

• C’est simplement une de plus parmi les nombreuses fois où Ballmer a tort

• Recommandation du livre « Little Mathematics Library – Elements of Game Theory »

  • Un bon ouvrage sur les stratégies mixtes en théorie des jeux
  • Le livre présente comme exemple motivant un jeu à deux cartes
    • Si le joueur A tire un as, il demande 1 dollar à l’adversaire
    • S’il tire un deux, il peut soit demander 1 dollar à l’adversaire, soit payer 1 dollar
    • L’adversaire peut accepter volontairement de recevoir 1 dollar, ou demander à vérifier s’il s’agit d’un as
    • Si c’est bien un as, il paie 2 dollars ; si c’était un bluff, il reçoit 2 dollars
    • Le jeu est analysé afin de trouver la stratégie optimale et le gain espéré de chaque joueur

• Partage d’un lien proposant une analyse plus large de l’équilibre de Nash et une résolution numérique du jeu complet

• Un exemple pur et simple de folie dans les processus modernes d’entretien technique

• Je cherchais un commentaire disant « Je pense que c’est correct, bien joué ! », mais comme il n’existait pas, je le laisse moi-même

  • Je pense que c’est correct, bien joué

• La fortune nette de Steve Ballmer est de 120 milliards de dollars

  • En supposant que chaque partie dure 30 secondes, il faudrait 1,6 million d’années pour gagner tout son argent