El valor esperado positivo de un juego, sin importar la estrategia de Ballmer

Steve Ballmer estaba equivocado

Hace unos días, una publicación de John Graham-Cumming sobre la "pregunta incorrecta de entrevista sobre búsqueda binaria de Steve Ballmer" recibió mucha atención en HackerNews. El acertijo favorito de Ballmer es el siguiente:

Estoy pensando en un número entre 1 y 100. Puedes adivinarlo, y después de cada intento te diré si es más alto o más bajo. Si aciertas en el primer intento, te daré $5. $4, $3, $2, $1, $0, tú tendrás que pagarme $1, $2, $3.

¿Jugarías este juego?

En esta entrevista de YouTube, Steve Ballmer da dos razones por las que no deberías jugar este juego:

1. Muchos números entre 1 y 100 producen pérdidas, así que incluso si eliges números al azar, el valor esperado es negativo.
2. Él puede elegir estratégicamente el número que más tiempo tome encontrar usando búsqueda binaria.

Sin embargo, John refuta el primer punto al mostrar que, si Ballmer elige el número al azar, el valor esperado real del juego es positivo: $0.20.

Yo voy a refutar el segundo punto y demostrar que el valor esperado del juego es positivo sin importar la estrategia de Ballmer.

Cómo Ballmer puede elegir números de forma adversarial

Supongamos que siempre usas una estrategia de búsqueda binaria para encontrar el número. De los 100 números, 37 requieren 6 preguntas para ser adivinados. Si Ballmer conoce tu estrategia, siempre puede elegir uno de esos números "perdedores" y hacer que pierdas en cada partida. Esto siempre se cumple para cualquier patrón de búsqueda fijo. Al menos 37 números producirán pérdidas, y Ballmer puede escoger uno de ellos.

¿Cómo puedes responder?

Aquí entramos en el terreno de la teoría de juegos. En lugar de un solo patrón de búsqueda fijo, puedes preparar un conjunto de varios patrones de búsqueda. Luego, al comienzo del juego, eliges uno de esos patrones de forma probabilística y te mantienes con él durante toda la partida.

En teoría de juegos, a esto se le llama una estrategia mixta, basada en un conjunto de estrategias puras.

Como el mismo número puede ser "ganador" en un patrón de búsqueda y "perdedor" en otro, estas estrategias mixtas pueden "nivelar" la ganancia esperada de cada número. Potencialmente, una estrategia mixta puede convertir todos los números en "ganadores", es decir, dar una ganancia esperada positiva para cada número. Eso es justo lo que estamos buscando.

Cómo encontrar una estrategia mixta ganadora

Nota: queremos encontrar alguna estrategia que gane para todos los números, no la mejor estrategia ganadora (equilibrio de Nash) con el mayor valor esperado en el peor caso.

Si te interesa el equilibrio de Nash, Arthur O’Dwyer exploró una solución cerrada para el juego de hasta 5 números, y Bo Waggoner aproximó el valor de equilibrio para el juego de 100 números usando aprendizaje online sin arrepentimiento.

Encontrar una estrategia mixta que gane para todos los números puede verse como un problema de optimización matemática. Cada estrategia puede describirse mediante un vector de "ganancias" V=(v1,..,v100), donde vk es la ganancia esperada cuando Ballmer elige el número k. Por ejemplo, la búsqueda binaria podría corresponder a un vector con v50=5, v25=4, v0=−1.

Supongamos que hay estrategias puras V1, V2, ..., Vn, y que la estrategia mixta elige la estrategia Vk con probabilidad pk. Entonces el vector de "ganancias" correspondiente de la estrategia mixta es simplemente una combinación lineal: Vmixed=∑i=1npiVi.

Con esta interpretación, encontrar una estrategia ganadora equivale a encontrar una combinación lineal con dos restricciones:

• Cada elemento de la combinación lineal es positivo (puedes ganar dinero en promedio para cada número).
• Los coeficientes de esa combinación lineal no son negativos (corresponden a probabilidades).

Este es un problema típico de programación lineal, y scipy tiene una solución eficiente para ello. Pensé en varias estrategias puras (diferentes búsquedas binarias) para encontrar una estrategia mixta y las alimenté a scipy.linprog() y, voilà, ¡la solución produjo una estrategia ganadora!

Ejemplo de estrategia ganadora

El código completo está en gukoff/ballmer_puzzle. Nota: el resultado inicial de $0.07 fue mejorado significativamente cuando Arthur O’Dwyer añadió nuevas estrategias puras.

• Ganancia promedio si Ballmer elige al azar: $0.16
• Peor ganancia si Ballmer elige de forma adversarial: $0.14

La estrategia mixta resultante es la siguiente:

• Probabilidad 0.4714%: búsqueda binaria, primer intento 29. En cada paso se adivina el elemento medio del intervalo. En caso de empate, se adivina el elemento de la izquierda
• Probabilidad 0.1691%: búsqueda binaria, primer intento 33. En cada paso se adivina el elemento medio del intervalo. En caso de empate, se adivina el elemento de la izquierda
• Probabilidad 0.1299%: búsqueda binaria, primer intento 36. En cada paso se adivina el elemento medio del intervalo. En caso de empate, se adivina el elemento de la derecha
• Probabilidad 3.3341%: búsqueda binaria, primer intento 37. En cada paso se adivina el elemento medio del intervalo. En caso de empate, se adivina el elemento de la derecha
• Probabilidad 1.7818%: búsqueda binaria, primer intento 43. En cada paso se adivina el elemento más a la derecha del intervalo que no aumente la complejidad en el peor caso
• Probabilidad 1.1608%: búsqueda binaria, primer intento 44. En cada paso se adivina el elemento más a la izquierda del intervalo que no aumente la complejidad en el peor caso
• Probabilidad 2.1310%: búsqueda binaria, primer intento 42. En cada paso se adivina un elemento extremo del intervalo que no aumente la complejidad en el peor caso

...

La estrategia completa tiene 74 líneas, que se omiten aquí por brevedad. Si te interesa, puedes revisarla en GitHub.

Conclusión

Si puedes ganar en promedio 14 centavos por partida, la próxima vez que Steve Ballmer te proponga este juego, definitivamente deberías aceptar.

Resumen de GN⁺

• Este artículo trata la discusión sobre el juego de búsqueda binaria de Steve Ballmer.
• Explica cómo usar teoría de juegos para encontrar una estrategia mixta que permita ganar sin importar la estrategia de Ballmer.
• Este artículo puede ser útil para quienes estén interesados en teoría de juegos y problemas de optimización.
• Otros proyectos con funciones similares incluyen diversas investigaciones y artículos sobre teoría de juegos.

[GN⁺]

Opiniones de Hacker News

• El argumento de Ballmer trata sobre el riesgo de cola

  • Si priorizas la supervivencia, el valor esperado no es una buena forma de apostar
  • Es como la razón por la que en póker no vas all-in cada vez que el valor esperado es alto
  • En promedio podrías tener más probabilidades de ganar, pero solo obtienes un único resultado
  • Si el objetivo es ganar, es mejor no deberle dinero a Ballmer
  • Sería más interesante ver la distribución de victorias y derrotas de esta estrategia mediante una simulación de Monte Carlo

• Cuando Ballmer dijo que era "adversarial", estaba considerando que no necesitaba elegir un número fijo

  • Podría dar una respuesta que deje el mayor número posible de candidatos para cada intento, garantizando la derrota sin importar la estrategia

• Se propone un algoritmo llamado "búsqueda binaria con desplazamiento aleatorio"

  • Elegir un número aleatorio entre 0 y 100 y llamarlo "desplazamiento"
  • Ejecutar el algoritmo de búsqueda binaria, pero en cada paso sumar el "desplazamiento" al valor y aplicar módulo 100
  • Incluso si Ballmer conoce esta estrategia, no puede elegir un número específico para degradar su rendimiento
  • Por lo tanto, el resultado esperado sigue siendo de $0.20 por juego

• Es una más de las muchas cosas en las que Ballmer estaba equivocado

• Se recomienda el libro "Little Mathematics Library – Elements of Game Theory"

  • Es un buen libro sobre estrategias mixtas en teoría de juegos
  • El libro presenta como ejemplo motivador un juego de cartas de dos cartas
    • Si el jugador A saca un as, le pide $1 al oponente
    • Si saca un dos, puede pedirle $1 al oponente o pagar $1
    • El oponente puede aceptar voluntariamente recibir $1 o pedir que se verifique si realmente era un as
    • Si sí era un as, paga $2; si era un farol, recibe $2
    • Se analiza el juego y se encuentran la estrategia óptima y la recompensa esperada de cada jugador

• Se comparte un enlace que ofrece un análisis más amplio del equilibrio de Nash y una solución numérica para el juego completo

• El proceso moderno de entrevistas técnicas es un ejemplo de absoluta locura

• Estaba buscando un comentario de "esto parece correcto, ¡bien hecho!", pero como no había uno, lo dejo yo mismo

  • Esto parece correcto, ¡bien hecho!

• El patrimonio neto de Steve Ballmer es de 120 mil millones de dólares

  • Suponiendo que cada juego toma 30 segundos, tomaría 1.6 millones de años ganar todo su dinero