Steve Ballmer lag falsch
Vor einigen Tagen veröffentlichte John Graham-Cumming einen Beitrag über „Steve Ballmers falsche Interviewfrage zur binären Suche“, der auf Hacker News viel Aufmerksamkeit bekam. Ballmers bevorzugtes Denksportproblem lautet wie folgt:
Ich denke mir eine Zahl zwischen 1 und 100 aus. Du darfst raten, und nach jedem Tipp sage ich dir, ob sie höher oder niedriger ist. Wenn du beim ersten Tipp richtig liegst, gebe ich dir 5 Dollar. 4 Dollar, 3 Dollar, 2 Dollar, 1 Dollar, 0 Dollar, du musst mir 1 Dollar, 2 Dollar, 3 Dollar zahlen.
Würdest du dieses Spiel spielen?
Steve Ballmer nennt in diesem YouTube-Interview zwei Gründe, warum man dieses Spiel nicht spielen sollte:
- Viele Zahlen zwischen 1 und 100 führen zu einem Verlust, sodass der Erwartungswert selbst dann negativ ist, wenn er die Zahl zufällig auswählt.
- Er kann strategisch eine Zahl wählen, deren Auffinden mit binärer Suche am längsten dauert.
John widerlegt jedoch den ersten Punkt, indem er zeigt, dass der Erwartungswert des Spiels tatsächlich 0,20 $ beträgt, wenn Ballmer die Zahl zufällig wählt.
Ich werde den zweiten Punkt widerlegen und beweisen, dass der Erwartungswert des Spiels unabhängig von Ballmers Strategie positiv ist.
Wie Ballmer Zahlen auf feindselige Weise auswählen kann
Nehmen wir an, du verwendest immer eine Strategie auf Basis binärer Suche, um die Zahl zu finden. Von den 100 Zahlen benötigen 37 sechs Fragen, um erraten zu werden. Wenn Ballmer deine Strategie kennt, kann er immer eine dieser „Verlierer“-Zahlen wählen und so in jeder Runde einen Verlust verursachen. Das gilt für jedes feste Suchmuster. Mindestens 37 Zahlen werden zu einem Verlust führen, und Ballmer kann eine davon auswählen.
Wie kann man darauf reagieren?
Hier betreten wir den Bereich der Spieltheorie. Statt eines einzigen festen Suchmusters kannst du eine Menge verschiedener Suchmuster vorbereiten. Zu Beginn des Spiels wählst du dann eines dieser Muster probabilistisch aus und bleibst während der Runde dabei.
In der Spieltheorie nennt man das eine gemischte Strategie, basierend auf einer Strategiemenge aus mehreren reinen Strategien.
Da dieselbe Zahl in einem Suchmuster ein „Gewinn“ und in einem anderen ein „Verlust“ sein kann, können solche gemischten Strategien den erwarteten Gewinn für jede Zahl „nivellieren“. Potenziell kann eine gemischte Strategie alle Zahlen in „Gewinne“ verwandeln, also für jede Zahl einen positiven erwarteten Gewinn liefern. Genau das suchen wir.
Wie man eine gewinnende gemischte Strategie findet
Hinweis: Wir wollen irgendeine Strategie finden, die für alle Zahlen gewinnt, nicht die beste Gewinnstrategie (Nash-Gleichgewicht) mit maximalem Erwartungswert im schlimmsten Fall.
Falls dich Nash-Gleichgewichte interessieren: Arthur O’Dwyer hat geschlossene Lösungen für Spiele mit bis zu 5 Zahlen untersucht, und Bo Waggoner hat den Gleichgewichtswert für das Spiel mit 100 Zahlen mithilfe von no-regret online learning approximiert.
Eine gemischte Strategie zu finden, die für alle Zahlen gewinnt, kann als mathematisches Optimierungsproblem betrachtet werden. Jede Strategie lässt sich durch einen „Gewinn“-Vektor V=(v1,..,v100) beschreiben, wobei vk der erwartete Gewinn ist, wenn Ballmer die Zahl k wählt. Beispielsweise könnte die binäre Suche einem Vektor mit v50=5, v25=4, v0=−1 entsprechen.
Angenommen, es gibt reine Strategien V1, V2, ..., Vn, und die gemischte Strategie wählt Strategie Vk mit Wahrscheinlichkeit pk. Dann ist der entsprechende „Gewinn“-Vektor der gemischten Strategie einfach die lineare Kombination: Vmixed=∑i=1npiVi.
In dieser Interpretation bedeutet das Finden einer Gewinnstrategie, eine lineare Kombination mit zwei Nebenbedingungen zu finden:
- Jedes Element der linearen Kombination ist positiv (man verdient für jede Zahl im Mittel Geld).
- Die Koeffizienten dieser linearen Kombination sind nicht negativ (sie entsprechen Wahrscheinlichkeiten).
Das ist ein klassisches Problem der linearen Programmierung, und scipy bietet dafür eine effiziente Lösung. Um eine gemischte Strategie zu finden, habe ich mehrere reine Strategien (verschiedene Varianten der binären Suche) entworfen und sie in scipy.linprog() eingespeist, und voilà – die Lösung liefert eine Gewinnstrategie!
Beispiel einer Gewinnstrategie
Der vollständige Code befindet sich in gukoff/ballmer_puzzle. Hinweis: Das anfängliche Ergebnis von 0,07 $ wurde von Arthur O’Dwyer durch das Hinzufügen neuer reiner Strategien deutlich verbessert.
- Durchschnittlicher Gewinn, wenn Ballmer zufällig wählt: 0,16 $
- Schlechtester Gewinn, wenn Ballmer feindselig wählt: 0,14 $
Die resultierende gemischte Strategie sieht so aus:
- Mit Wahrscheinlichkeit 0,4714 %: Binäre Suche, erster Tipp 29. In jedem Schritt wird das mittlere Element des Intervalls geraten. Bei Gleichstand wird das linke Element gewählt
- Mit Wahrscheinlichkeit 0,1691 %: Binäre Suche, erster Tipp 33. In jedem Schritt wird das mittlere Element des Intervalls geraten. Bei Gleichstand wird das linke Element gewählt
- Mit Wahrscheinlichkeit 0,1299 %: Binäre Suche, erster Tipp 36. In jedem Schritt wird das mittlere Element des Intervalls geraten. Bei Gleichstand wird das rechte Element gewählt
- Mit Wahrscheinlichkeit 3,3341 %: Binäre Suche, erster Tipp 37. In jedem Schritt wird das mittlere Element des Intervalls geraten. Bei Gleichstand wird das rechte Element gewählt
- Mit Wahrscheinlichkeit 1,7818 %: Binäre Suche, erster Tipp 43. In jedem Schritt wird das ganz rechte Element des Intervalls geraten, ohne die Worst-Case-Komplexität zu erhöhen
- Mit Wahrscheinlichkeit 1,1608 %: Binäre Suche, erster Tipp 44. In jedem Schritt wird das ganz linke Element des Intervalls geraten, ohne die Worst-Case-Komplexität zu erhöhen
- Mit Wahrscheinlichkeit 2,1310 %: Binäre Suche, erster Tipp 42. In jedem Schritt wird ein äußerstes Element des Intervalls geraten, ohne die Worst-Case-Komplexität zu erhöhen
...
Die vollständige Strategie umfasst 74 Zeilen und wird der Kürze halber weggelassen. Wenn du interessiert bist, kannst du sie auf GitHub ansehen.
Fazit
Wenn man im Durchschnitt 14 Cent pro Spiel verdienen kann, sollte man beim nächsten Mal auf jeden Fall mitmachen, wenn Steve Ballmer dieses Spiel vorschlägt.
Zusammenfassung von GN⁺
- Dieser Artikel behandelt die Debatte über Steve Ballmers Spiel zur binären Suche.
- Es wird erklärt, wie man mithilfe der Spieltheorie eine gemischte Strategie findet, die unabhängig von Ballmers Vorgehen gewinnt.
- Der Artikel kann für Menschen interessant sein, die sich für Spieltheorie und Optimierungsprobleme interessieren.
- Ähnliche Projekte mit vergleichbaren Themen sind verschiedene spieltheoretische Forschungsarbeiten und wissenschaftliche Veröffentlichungen.
1 Kommentare
Hacker-News-Kommentare
Ballmers Behauptung bezieht sich auf Tail-Risiken
Als Ballmer sagte, er sei „adversarial“, berücksichtigte er, dass er keine feste Zahl wählen muss
Es wird ein Algorithmus namens „Random-Offset-Binärsuche“ vorgeschlagen
Das ist nur eines von vielen Dingen, bei denen Ballmer falschliegt
Das Buch „Little Mathematics Library – Elements of Game Theory“ wird empfohlen
Es wird ein Link geteilt, der eine breiter angelegte Analyse des Nash-Gleichgewichts und eine numerische Lösung für das gesamte Spiel liefert
Der moderne Ablauf von technischen Vorstellungsgesprächen ist ein völlig absurdes Beispiel
Jemand suchte nach einem Kommentar wie „Das scheint richtig zu sein, gut gemacht!“, fand aber keinen und schrieb ihn deshalb selbst
Steve Ballmers Nettovermögen beträgt 120 Milliarden Dollar