- El rompecabezas de adivinar números de Steve Ballmer es un juego para encontrar un número entre 1 y 100; una búsqueda binaria fija puede ser explotada, pero con una estrategia mixta se puede obtener un valor esperado positivo sin importar la elección del oponente
- Ballmer pensaba que incluso con una elección aleatoria el valor esperado era negativo y que además podía escoger el número que más tardara en encontrarse, pero John Graham-Cumming refutó eso al señalar que con elección aleatoria el valor esperado es de $0.20
- En un patrón de búsqueda fijo, al menos 37 de los 100 números requieren 6 preguntas, lo que puede generar pérdidas; si el oponente conoce la estrategia, puede hacer que el jugador pierda en cada partida
- La solución es usar una estrategia mixta de teoría de juegos que elige probabilísticamente una entre varias estrategias puras de búsqueda, promediando las diferencias de ganancia y pérdida por número para eliminar los números desfavorables
- Una estrategia de ejemplo hallada resolviendo un problema de programación lineal con
scipy.linprog()da una ganancia esperada promedio de $0.16 si Ballmer elige al azar y, aun si elige de forma adversarial, una ganancia esperada mínima de $0.14
El rompecabezas de adivinar números y la refutación previa
- El rompecabezas que, según se cuenta, le gustaba a Ballmer consiste en que el oponente piensa un número entre 1 y 100 y, cada vez que el jugador adivina, le dicen si es más alto o más bajo
- La recompensa es $5 si se acierta en el primer intento, luego $4, $3, $2, $1, $0, y a partir de ahí el jugador paga $1, $2, $3
- Ballmer creía que este juego no debía jugarse por dos razones
- Consideraba que, incluso si el número se elegía al azar, había muchos números que generaban pérdidas y por eso el valor esperado era negativo
- Pensaba que podía elegir estratégicamente el número que más tardara en encontrarse con búsqueda binaria
- John Graham-Cumming, en “Steve Ballmer’s incorrect binary search interview question”, respondió que si Ballmer elige el número al azar, el valor esperado es positivo: $0.20
- Yendo más allá, incluso si Ballmer elige el número de forma estratégica, se puede encontrar una estrategia con valor esperado positivo
La debilidad de la búsqueda binaria fija
- Si el jugador usa siempre la misma estrategia de búsqueda binaria, 37 de los 100 números requieren 6 preguntas para acertar
- Si Ballmer conoce esa estrategia fija, puede escoger uno de esos 37 números “perdedores” y forzar una pérdida al jugador
- Esta vulnerabilidad no se limita a una sola búsqueda binaria concreta
- En cualquier patrón de búsqueda fijo, al menos 37 números generan pérdidas
- Si el oponente elige esos números, el jugador pierde siempre
Responder con una estrategia mixta
- En vez de fijar un único patrón de búsqueda, se preparan varios patrones y al inicio de la partida se elige uno de ellos probabilísticamente para mantenerlo hasta el final
- En teoría de juegos, esto se llama una estrategia mixta basada en varias estrategias puras
- Incluso para un mismo número, este puede ser ganador en un patrón de búsqueda y perdedor en otro
- El objetivo de la estrategia mixta es promediar la ganancia esperada de cada número para que el valor esperado sea positivo en todos los casos
Encontrar una estrategia mediante programación lineal
- El objetivo no es hallar la estrategia óptima que maximiza el valor esperado en el peor caso, es decir, un equilibrio de Nash, sino encontrar cualquier estrategia que gane contra todos los números
- Cada estrategia pura puede representarse como un vector de victoria de longitud 100:
V = (v_1, .., v_100)v_kes la ganancia esperada cuando Ballmer elige el númerok- Por ejemplo, una búsqueda binaria puede tener valores como
v_50 = 5,v_25 = 4,v_0 = -1
- Si la estrategia mixta elige una estrategia pura
V_kcon probabilidadp_k, entonces el vector de victoria total esV_mixed = Σ p_i V_i - Para encontrar una estrategia ganadora, se necesita una combinación lineal que cumpla estas condiciones
- Cada elemento debe ser positivo
- Como los coeficientes son probabilidades, no deben ser negativos
- Esto es un problema típico de programación lineal, y puede resolverse con
scipy.optimize.linprogde SciPy - Al construir un conjunto de estrategias puras con varias variantes de búsqueda binaria y pasarlo a
scipy.linprog()en este código, aparece una estrategia mixta ganadora
Estrategia de ejemplo y resultados
- El código completo está en gukoff/ballmer_puzzle
- El resultado inicial era de $0.07 por partida, y Arthur O’Dwyer mejoró el desempeño al añadir nuevas estrategias puras
- El rendimiento de la estrategia mixta mejorada es el siguiente
- Ganancia promedio si Ballmer elige al azar: $0.16
- Ganancia mínima en el peor caso si Ballmer elige de forma adversarial: $0.14
- La estrategia mixta de ejemplo combina varias variantes de búsqueda binaria con probabilidades pequeñas
- Probabilidad 0.4714%: primera conjetura 29; después, adivinar el punto medio del intervalo y, en caso de empate, elegir la izquierda
- Probabilidad 0.1691%: primera conjetura 33; después, adivinar el punto medio y, en caso de empate, elegir la izquierda
- Probabilidad 0.1299%: primera conjetura 36; después, adivinar el punto medio y, en caso de empate, elegir la derecha
- Probabilidad 3.3341%: primera conjetura 37; después, adivinar el punto medio y, en caso de empate, elegir la derecha
- Probabilidad 1.7818%: primera conjetura 43; después, elegir el elemento más a la derecha dentro del intervalo que no aumente la complejidad del peor caso
- Probabilidad 1.1608%: primera conjetura 44; después, elegir el elemento más a la izquierda dentro del intervalo que no aumente la complejidad del peor caso
- Probabilidad 2.1310%: primera conjetura 42; después, elegir un elemento de los extremos del intervalo que no aumente la complejidad del peor caso
- La estrategia completa tiene 74 líneas, y la lista omitida puede verse en winning strategy en GitHub
- Si una ganancia promedio de 14 centavos por partida compensa el tiempo invertido, entonces podría valer la pena jugar aunque Ballmer proponga este juego
1 comentarios
Opiniones en Hacker News
Artículo relacionado reciente: La pregunta de entrevista de búsqueda binaria mal planteada de Steve Ballmer - https://news.ycombinator.com/item?id=41434637 - septiembre de 2024, 240 comentarios
La aplicación de este artículo es interesante, pero parece que se pierde el punto central
El argumento de Ballmer trata, en esencia, sobre el riesgo de cola. Si te importa sobrevivir, el valor esperado no sirve en absoluto como criterio de apuesta. Porque solo tienes una oportunidad. Es la misma razón por la que no tiene sentido apostar todo tu patrimonio cada vez que en póker te sale una mano que “en expectativa” va a ganar; en unas pocas rondas casi seguro acabarías en la ruina
Que el promedio sea +$0.07 o lo que sea, el rango de la distribución claramente también puede bajar de 0. En promedio quizá la probabilidad de ganar sea un poco mayor que la de perder, pero en la práctica solo recibes un resultado. Si el objetivo es ganar o quedar destruido, mejor no hacerlo, a menos que quieras deberle dinero a Ballmer
Lo más interesante sería hacer una simulación Monte Carlo de esta estrategia y ver la distribución de victorias y derrotas. Entonces quizá la elección no sea tan obvia
Si pudieras jugar unos cuantos billones de veces, obviamente podrías exprimirlo sin piedad :P
Tampoco es un buen ejemplo de riesgo de cola. En la estrategia obvia, la cola es extremadamente gruesa
Sam Bankman-Fried era muy fan del valor esperado, y es famoso por haber dicho que lanzaría una moneda que, si sale cara, duplicaría el “valor” del mundo, pero si sale cruz, destruiría el mundo
En resumen, la paradoja de San Petersburgo es así: se lanza una moneda justa hasta que salga cara, y el jugador recibe $2^n, donde n es la cantidad de lanzamientos. Si sale cara en el primero, recibe $2; en el segundo, $4; en el tercero, $8; en el décimo, $1024 (2^10), y así sucesivamente. Es fácil ver que el valor esperado de este juego se acerca al infinito
Por lo tanto, una persona completamente racional debería estar dispuesta a pagar prácticamente cualquier cantidad para jugarlo. Como cualquier suma finita de dinero es menor que infinito, la ganancia esperada siempre es positiva
Pero probablemente casi nadie pagaría millones de dólares para jugar ese juego. Quizá SBF sea una excepción
Solo es una paradoja si uno piensa que esto demuestra que la gente no es “racional”. En realidad, parece significar que el valor esperado no es una buena medida del riesgo, y que todos lo saben
Un artículo muy completo e interesante sobre la paradoja de San Petersburgo: https://plato.stanford.edu/entries/paradox-stpetersburg/
A diferencia de la mayoría aquí, creo que este tipo de preguntas son una forma bastante buena de ver cómo piensa una persona. Si tienes formación en matemáticas/estadística/ciencias de la computación, esperaría que al menos pudieras iniciar una conversación sobre este problema
Pero si ocultas supuestos o agregas restricciones inútiles a tu antojo para convertirlo en una trampa, ahí deja de convencerme
Si la pregunta es “¿jugarías este juego?”, la traducción matemática racional es “determina si el valor esperado es mayor que 0”. Si quieres hablar de riesgo de cola, debes especificar una función de utilidad, que además podría ser asimétrica para los dos jugadores. Y debes decir claramente que esa es la intención
Francamente, creo que Steve no entendió bien la profundidad matemática de este problema
Si apuestas más que la fracción de Kelly, aumenta el riesgo de ruina, especialmente a largo plazo
https://en.m.wikipedia.org/wiki/Kelly_criterion
No digo que aplique a la situación del artículo original. Pero sí es relevante para el comentario padre y es muy útil en muchas situaciones, como inversiones
Cuando Ballmer dijo “adversarial”, pensé en una estrategia como esta. De hecho, al principio no necesita elegir un número fijo en absoluto. En cada intento, basta con dar la respuesta que deje la mayor cantidad posible de números, y así puede garantizar la derrota sin importar la estrategia
El artículo original presenta una estrategia aleatoria compleja que garantiza un promedio mínimo de $0.07 contra cualquier adversario. En cambio, a Ballmer le basta con posponer la “elección” y dar largas para obligarte a adivinar siete veces en cada partida y hacerte pagar 1 dólar
Si esperabas ganar $0.07 en promedio, ¿cuántas partidas jugarías antes de darte cuenta de que te están estafando?
El artículo original es interesante, pero asume una noción muy débil de “adversarial”, en la que Ballmer todavía se compromete con alguna elección inicial
Curiosamente, si Ballmer usa un esquema de compromiso, el jugador puede verificarlo [1]. Por ejemplo, al inicio del juego Ballmer genera 500 bits aleatorios, les agrega el número que eligió en el rango de 1 a 100, hashea el resultado y envía ese hash. Cuando termina el juego, envía los 500 bits aleatorios, y el jugador puede concatenarlos con el número elegido que ahora se reveló y comprobar que, al hashearlos, se obtiene el hash enviado al principio. Para que Ballmer mienta y cambie el número, tendría que encontrar 500 bits que, concatenados con otro número, también produzcan el hash original, y eso es difícil
[1]: https://en.wikipedia.org/wiki/Commitment_scheme
Lo hizo el creador de HATERIS, una variante de Tetris que siempre te da el peor bloque
Edit: ah, no. Este comentario estaba equivocado. Gracias a fgna por señalarlo
Creo que hay una demostración más simple de que se puede vencer a un Ballmer adversarial. Da exactamente el mismo resultado esperado que una búsqueda binaria contra un Ballmer aleatorio
Mi algoritmo se llama “búsqueda binaria con desplazamiento aleatorio”. Funciona así
offsetoffsetal valor y usa el residuo de dividir entre 100Eso es todo. Ahora, aunque Ballmer conozca esta estrategia, no puede elegir un número específico para empeorar el rendimiento. Por lo tanto, el resultado esperado sigue siendo de $0.20 por partida, mejor que la estrategia propuesta en el artículo
Entre las muchas cosas en las que Ballmer se equivocó, parece que esta también es una de ellas
Esto, amigos, es un ejemplo perfecto de por qué los procesos modernos de entrevistas técnicas son pura locura
La pregunta de Ballmer me parece justa, considerando la complejidad de la respuesta que esperaba
El entrevistado probablemente daría una respuesta matemáticamente incorrecta, pero en el proceso mostraría cómo piensa y demostraría un poco de principios de ciencias de la computación
Hay que tener en cuenta lo larga que fue la carrera de Ballmer. Si realmente hizo esta pregunta, probablemente fue en los 80, y en ese momento nadie habría esperado que alguien propusiera la solución compleja descrita en el artículo
Si alguien hubiera dado la respuesta correcta, habría sido algo impresionante y motivo para contratarlo de inmediato. Pero no creo que esta pregunta esté fundamentalmente rota. Porque, apuestes o no, de cualquier manera tienes que justificar bien la respuesta
En general, hay conversación con todos los entrevistadores y no se mira simplemente si “el candidato resolvió el problema”. Personalmente creo que muchos problemas de entrevistas de Big Tech son tontos, pero habiéndolo vivido de ambos lados, no creo que el proceso esté tan roto como se piensa
En este caso, sería algo como demostrar que puedes razonar sobre búsqueda binaria y mostrar que la ganancia promedio es de 0.20 dólares
Aun así, gracias a eso obtuvimos buena ficción como https://aphyr.com/posts/340-reversing-the-technical-intervie... y sus secuelas
Un artículo que analiza con más amplitud el equilibrio de Nash, incluida la solución numérica de todo el juego, está en https://bowaggoner.com/blahg/2024/09-06-adversarial-binary-s...
El patrimonio neto de Steve Ballmer es de 120.000 millones de dólares, así que si una partida tarda 30 segundos, tomaría 1,6 millones de años ganarlo todo
Little Mathematics Library – Elements of Game Theory: https://mirtitles.org/2012/09/06/little-mathematics-library-...
Es un libro muy bueno sobre las estrategias mixtas en teoría de juegos
Los ejemplos motivadores que aparecen en el libro también son excelentes
“Hay dos cartas, un as y un 2. El jugador A toma una de las dos al azar, y B no ve qué carta salió. Si A sacó el as, dice ‘tengo el as’ y le exige 1 dólar al rival. Si A sacó el 2, puede (A1) decir ‘tengo el as’ y exigirle 1 dólar al rival, o (A2) confesar que tiene el 2 y darle 1 dólar al rival
Si el rival recibe voluntariamente 1 dólar, no tiene más opción que aceptarlo. Pero si le exigen 1 dólar, puede (B1) creer que A tiene el as y pagarle 1 dólar, o (B2) pedir que se verifique para ver si lo que dijo A es cierto. Si A realmente tiene el as, B debe pagarle 2 dólares a A. En cambio, si A estaba blufeando y tenía el 2, A le paga 2 dólares a B
Analice este juego y determine la estrategia óptima y el pago esperado de cada jugador”