Positive Erwartungswerte in einem Spiel unabhängig von Ballmers Strategie

• Steve Ballmers Zahlenratespiel ist ein Spiel, bei dem eine Zahl zwischen 1 und 100 gefunden werden muss. Eine feste binäre Suche kann ausgenutzt werden, aber mit einer gemischten Strategie lässt sich unabhängig von der Wahl des Gegners ein positiver Erwartungswert erzielen
• Ballmer meinte, dass der Erwartungswert selbst bei zufälliger Wahl negativ sei und dass er Zahlen wählen könne, bei denen der Spieler besonders lange braucht. John Graham-Cumming widersprach jedoch und zeigte, dass der Erwartungswert bei zufälliger Wahl $0.20 beträgt
• Bei einem festen Suchmuster erfordern mindestens 37 der 100 Zahlen sechs Fragen und verursachen damit einen Verlust; kennt der Gegner die Strategie, kann er den Spieler jedes Mal verlieren lassen
• Die Lösung ist eine gemischte Strategie aus der Spieltheorie, bei der probabilistisch eine von mehreren reinen Suchstrategien gewählt wird. So werden die Gewinn-/Verlustunterschiede je Zahl gemittelt und nachteilige Zahlen eliminiert
• Eine mit scipy.linprog() per linearer Programmierung gefundene Beispielstrategie erzielt im Schnitt $0.16 erwarteten Gewinn, wenn Ballmer zufällig wählt, und selbst im schlechtesten Fall $0.14, wenn er gegnerisch wählt

---

Das Zahlenratespiel und die bisherige Widerlegung

• Das Rätsel, das Ballmer angeblich mochte, ist ein Spiel, bei dem sich der Gegner eine Zahl zwischen 1 und 100 ausdenkt und dem Spieler bei jedem Tipp sagt, ob die gesuchte Zahl höher oder niedriger ist
• Die Auszahlung beträgt $5, wenn der erste Tipp stimmt, danach $4, $3, $2, $1, $0; ab dann zahlt der Spieler $1, $2, $3 usw.
• Ballmer war aus zwei Gründen der Ansicht, man solle dieses Spiel nicht spielen
  • Er hielt den Erwartungswert für negativ, weil es selbst bei zufälliger Zahlenwahl viele verlustbringende Zahlen gebe
  • Er meinte, er könne strategisch eine Zahl wählen, bei der eine binäre Suche am längsten dauert
• John Graham-Cumming widersprach in „Steve Ballmer’s incorrect binary search interview question“: Wenn Ballmer zufällig eine Zahl wählt, sei der Erwartungswert mit $0.20 positiv
• Darüber hinaus lässt sich sogar für den Fall, dass Ballmer die Zahl strategisch wählt, eine Strategie mit positivem Erwartungswert finden

Die Schwäche einer festen binären Suche

• Wenn der Spieler immer dieselbe binäre Suchstrategie verwendet, benötigen 37 der 100 Zahlen sechs Fragen, bis die Antwort gefunden ist
• Wenn Ballmer diese feste Strategie kennt, kann er eine dieser 37 „verlierenden“ Zahlen wählen und dem Spieler so einen Verlust aufzwingen
• Diese Schwachstelle beschränkt sich nicht auf eine bestimmte binäre Suche
  • Bei jedem festen Suchmuster erzeugen mindestens 37 Zahlen einen Verlust
  • Wählt der Gegner eine dieser Zahlen, verliert der Spieler jedes Mal

Gegenmaßnahme mit gemischter Strategie

• Statt ein Suchmuster festzulegen, bereitet man mehrere Suchmuster vor, wählt zu Spielbeginn eines davon probabilistisch aus und hält es bis zum Ende durch
• In der Spieltheorie nennt man das eine gemischte Strategie auf Basis mehrerer reiner Strategien
• Dieselbe Zahl kann in einem Suchmuster eine Gewinnzahl und in einem anderen eine Verlustzahl sein
• Ziel der gemischten Strategie ist es, die erwarteten Gewinne je Zahl zu mitteln, sodass der Erwartungswert für jede Zahl positiv wird

Strategie per linearer Programmierung finden

• Ziel ist nicht, die optimale Strategie zu finden, die den Erwartungswert im schlechtesten Fall maximiert, also ein Nash-Gleichgewicht, sondern irgendeine Strategie, die bei jeder Zahl gewinnt
• Jede reine Strategie lässt sich als Gewinnvektor V = (v_1, .., v_100) der Länge 100 darstellen
  • v_k ist der erwartete Gewinn, wenn Ballmer die Zahl k wählt
  • Eine binäre Suche könnte zum Beispiel Werte wie v_50 = 5, v_25 = 4, v_0 = -1 haben
• Wählt eine gemischte Strategie die reine Strategie V_k mit Wahrscheinlichkeit p_k, ergibt sich der gesamte Gewinnvektor als V_mixed = Σ p_i V_i
• Um eine gewinnende Strategie zu finden, braucht man eine Linearkombination, die folgende Bedingungen erfüllt
  • Jedes Element muss positiv sein
  • Die Koeffizienten dürfen nicht negativ sein, da es Wahrscheinlichkeiten sind
• Das ist ein typisches Problem der linearen Programmierung und lässt sich mit SciPys scipy.optimize.linprog lösen
• Aus dem Code, der mehrere Varianten der binären Suche zu einer Menge reiner Strategien macht und sie an scipy.linprog() übergibt, ergibt sich eine gewinnende gemischte Strategie

Beispielstrategie und Ergebnisse

• Der vollständige Code ist unter gukoff/ballmer_puzzle verfügbar
• Das erste Ergebnis lag bei $0.07 pro Spiel; Arthur O’Dwyer verbesserte die Performance durch Hinzufügen neuer reiner Strategien
• Die verbesserte gemischte Strategie erzielt folgende Ergebnisse
  • Durchschnittlicher Gewinn, wenn Ballmer zufällig wählt: $0.16
  • Gewinn im schlechtesten Fall, wenn Ballmer gegnerisch wählt: $0.14
• Die Beispielstrategie mischt mehrere Varianten der binären Suche mit kleinen Wahrscheinlichkeiten
  • Wahrscheinlichkeit 0.4714%: erster Tipp 29, danach die Mitte des Intervalls tippen und bei Gleichstand links wählen
  • Wahrscheinlichkeit 0.1691%: erster Tipp 33, danach die Mitte tippen und bei Gleichstand links wählen
  • Wahrscheinlichkeit 0.1299%: erster Tipp 36, danach die Mitte tippen und bei Gleichstand rechts wählen
  • Wahrscheinlichkeit 3.3341%: erster Tipp 37, danach die Mitte tippen und bei Gleichstand rechts wählen
  • Wahrscheinlichkeit 1.7818%: erster Tipp 43, danach das rechteste Element innerhalb des Intervalls wählen, das die Worst-Case-Komplexität nicht erhöht
  • Wahrscheinlichkeit 1.1608%: erster Tipp 44, danach das linkeste Element innerhalb des Intervalls wählen, das die Worst-Case-Komplexität nicht erhöht
  • Wahrscheinlichkeit 2.1310%: erster Tipp 42, danach ein Element am Rand des Intervalls wählen, das die Worst-Case-Komplexität nicht erhöht
• Die vollständige Strategie umfasst 74 Zeilen; die ausgelassene Gesamtliste ist als winning strategy auf GitHub zu sehen
• Wenn ein durchschnittlicher Gewinn von 14 Cent pro Spiel den Zeitaufwand wert ist, lohnt es sich, mitzuspielen, falls Ballmer dieses Spiel vorschlägt

[GN⁺]

Hacker-News-Kommentare

• Jüngster verwandter Beitrag: Steve Ballmers falsche Binärsuche-Interviewfrage – https://news.ycombinator.com/item?id=41434637 – September 2024, 240 Kommentare

• Dieser Beitrag wirkt, als sei die Anwendung cool, verfehle aber den Kern.
  Ballmers Argument dreht sich im Wesentlichen um Tail-Risiko. Wenn dir Überleben wichtig ist, ist der Erwartungswert als Wettkriterium überhaupt nicht gut. Man hat nur eine Chance. Das ist derselbe Grund, warum es beim Poker keinen Sinn ergibt, jedes Mal sein gesamtes Vermögen zu setzen, wenn man „im Erwartungswert“ das Gewinnerblatt hat, denn in wenigen Runden geht man mit hoher Wahrscheinlichkeit bankrott.
  Ob der Mittelwert nun +$0.07 ist oder sonst etwas: Die Verteilung kann offensichtlich auch unter 0 fallen. Im Durchschnitt mag die Gewinnwahrscheinlichkeit etwas höher sein als die Verlustwahrscheinlichkeit, aber tatsächlich bekommt man nur ein einziges Ergebnis. Wenn das Ziel Sieg oder Aus bedeutet, ist es besser, es nicht zu tun, sofern man Ballmer kein Geld schulden möchte.
  Interessanter wäre es, diese Strategie per Monte-Carlo-Simulation zu untersuchen und die Verteilung von Sieg und Niederlage anzuschauen. Dann ist die Entscheidung vielleicht nicht mehr so eindeutig.
  Wenn man das Spiel natürlich ein paar Billionen Mal spielen kann, dann kann man sich selbstverständlich bis aufs Hemd ausziehen :P

  • Ich weiß nicht, woher die Aussage kommt, „Ballmers Argument drehe sich im Wesentlichen um Tail-Risiko“. Im Interview scheint er so etwas nicht zu behaupten. Problem und Erklärung der Antwort werden nur aus Sicht des Erwartungswerts eines einzelnen Spieldurchlaufs dargestellt, und der Twist ist die adversariale Wahl der Zahl, nicht das Bankrottrisiko.
    Auch als Beispiel für Tail-Risiko taugt es nicht besonders. Bei der offensichtlichen Strategie sind die Tails extrem dick.
  • Stimmt. Das Sankt-Petersburg-Paradoxon zeigt, dass wir das intuitiv wissen. Ich setze „Paradoxon“ in Anführungszeichen, weil ich es eher für eine normale Reaktion als für ein Paradoxon halte.
    Sam Bankman-Fried mochte Erwartungswerte sehr und ist berüchtigt für die Aussage, er würde einen Münzwurf machen, der beim Kopf den „Wert“ der Welt verdoppelt, bei Zahl aber die Welt zerstört.
    Kurz gesagt funktioniert das Sankt-Petersburg-Paradoxon so: Man wirft eine faire Münze, bis zum ersten Mal Kopf erscheint, und der Spieler erhält $2^n, wobei n die Anzahl der Würfe ist. Bei Kopf im ersten Wurf bekommt man $2, im zweiten $4, im dritten $8, im zehnten $1024 (2^10) und so weiter. Es ist leicht zu sehen, dass der Erwartungswert dieses Spiels gegen unendlich geht.
    Daher sollte eine vollkommen rationale Person bereit sein, praktisch jeden Betrag zu zahlen, um dieses Spiel zu spielen. Jeder endliche Geldbetrag ist kleiner als unendlich, also ist der erwartete Gewinn immer positiv.
    Trotzdem würden vermutlich nur sehr wenige Menschen Millionen von Dollar zahlen wollen, um dieses Spiel zu spielen. SBF ist vielleicht eine Ausnahme.
    Es ist nur dann ein Paradoxon, wenn man glaubt, dass dies zeigt, dass Menschen nicht „rational“ sind. Tatsächlich scheint es eher zu bedeuten, dass der Erwartungswert kein gutes Maß für Risiko ist und dass das alle wissen.
    Ein sehr vollständiger und interessanter Artikel zum Sankt-Petersburg-Paradoxon: https://plato.stanford.edu/entries/paradox-stpetersburg/
  • Dem stimme ich nicht zu. Ich denke, Ballmer lag einfach falsch.
    Anders als die meisten hier halte ich solche Fragen für eine ziemlich gute Möglichkeit zu sehen, wie jemand denkt. Wenn man einen Hintergrund in Mathematik/Statistik/Informatik hat, sollte man meiner Meinung nach zumindest in der Lage sein, ein Gespräch über dieses Problem zu beginnen.
    Wenn man daraus aber eine Falle macht, indem man Annahmen versteckt oder willkürlich sinnlose Einschränkungen hinzufügt, dann finde ich das nicht mehr überzeugend.
    Wenn die Frage lautet: „Würdest du dieses Spiel spielen?“, dann ist die rationale mathematische Übersetzung: „Entscheide, ob der Erwartungswert größer als 0 ist.“ Um über Tail-Risiko zu sprechen, müsste man die Nutzenfunktion explizit machen, und sie könnte für zwei Spieler asymmetrisch sein. Und dann sollte man klar sagen, dass genau das beabsichtigt ist.
  • Ich glaube nicht, dass das zutrifft. Die meisten Menschen gehen nicht bankrott, wenn sie 1 Dollar verlieren. Wenn das der Kontext gewesen wäre, dann hätte Steve diesen Kontext sehr schlecht vermittelt.
    Ehrlich gesagt glaube ich, dass Steve die mathematische Tiefe dieses Problems nicht wirklich erfasst hat.
  • Kelly-Kriterium
    Wenn man mehr als den Kelly-Anteil setzt, steigt insbesondere langfristig das Risiko des Bankrotts.
    https://en.m.wikipedia.org/wiki/Kelly_criterion
    Ich sage nicht, dass das auf die Situation im ursprünglichen Beitrag anwendbar ist. Für den übergeordneten Kommentar ist es aber relevant, und in vielen Situationen wie etwa beim Investieren sehr nützlich.

• Als Ballmer „antagonistisch“ sagte, musste ich sofort an diese Strategie denken. Tatsächlich muss er anfangs überhaupt keine feste Zahl wählen. Er kann bei jedem Tipp einfach die Antwort geben, bei der die meisten möglichen Zahlen übrig bleiben, und so jede Strategie sicher schlagen

  • Genau. Ich weiß nicht, ob das wirklich so gemeint war, aber falls ja, ist es witzig, dass dadurch die ganze mathematische Analyse völlig bedeutungslos wird.
    Der Originalbeitrag präsentiert eine komplizierte Randomisierungsstrategie, die gegen jeden Gegner im Mittel mindestens $0.07 garantiert. Ballmer dagegen kann einfach die „Wahl“ aufschieben und Zeit schinden, sodass man in jeder Runde siebenmal raten und 1 Dollar zahlen muss.
    Wenn man erwartet hätte, im Schnitt $0.07 zu verdienen, wie viele Runden würde man wohl spielen, bevor man merkt, dass man betrogen wird?
  • Dieser Kommentar sollte weiter oben stehen.
    Der Originalbeitrag ist interessant, nimmt bei „antagonistisch“ aber nur eine sehr schwache Bedeutung an, nämlich dass Ballmer sich trotzdem auf irgendeine anfängliche Wahl festlegt.
    Interessanterweise könnte der Spieler überprüfen, ob Ballmer tatsächlich so ein Commitment verwendet, wenn Ballmer ein Commitment-Schema benutzt [1]. Zum Beispiel könnte Ballmer zu Beginn des Spiels 500 Zufallsbits erzeugen, die von ihm gewählte Zahl aus dem Bereich 1–100 anhängen, das Ergebnis hashen und diesen Hash schicken. Am Ende des Spiels sendet er die 500 Zufallsbits, und der Spieler kann prüfen, ob der Hash aus der nun offengelegten Zahl zusammen mit diesen Bits dem anfangs gesendeten Hash entspricht. Um zu lügen und die Zahl zu ändern, müsste Ballmer 500 Bits finden, die auch in Kombination mit einer anderen Zahl wieder den ursprünglichen Hash ergeben, und das ist schwer.
    [1]: https://en.wikipedia.org/wiki/Commitment_scheme
  • Dachte ich auch. Das wirkt wie Absurdle, die antagonistische Variante von Wordle: https://qntm.org/files/absurdle/absurdle.html
    Vom Entwickler von HATERIS, der Tetris-Variante, die einem immer den schlimmstmöglichen Stein gibt
  • Vom Wortlaut der Regeln her klingt es so, als würde er eine Zahl wählen und dabei bleiben. Es heißt schließlich, er „hat eine Zahl im Kopf“. Klar, manche Interviewer verdrehen die Regeln gern zu einer Art Gedankenspiel, um klug zu wirken, aber hier scheint das nicht die Absicht zu sein
  • Bei der Analyse des Competitive Ratio von Online-Algorithmen macht man genau das. Der Gegner darf seine Meinung beliebig ändern und muss sich nur an Entscheidungen binden, die bereits in der Vergangenheit getroffen wurden

• Korrektur: Ah, nein. Dieser Kommentar war falsch. Danke an fgna für den Hinweis.
  Es scheint einen einfacheren Beweis dafür zu geben, dass man den antagonistischen Ballmer schlagen kann. Man erhält genau denselben Erwartungswert wie bei binärer Suche gegen einen zufälligen Ballmer.
  Mein Algorithmus heißt „binäre Suche mit zufälligem Offset“. Er funktioniert so:

  1. Wähle eine zufällige Zahl zwischen 0 und 100 und nenne sie offset
  2. Führe den Binärsuchalgorithmus aus, verwende dabei aber in jedem Schritt den Wert plus offset, modulo 100
     Das ist alles. Selbst wenn Ballmer diese Strategie kennt, kann er keine bestimmte Zahl wählen, um sie schlechter zu machen. Daher bleibt der Erwartungswert bei $0.20 pro Spiel und ist damit besser als die im Beitrag vorgeschlagene Strategie
  • Leider sind die Zahlen nicht kreisförmig :( Wenn man die Anfangszahl verschiebt, arbeitet die Binärsuche dann nicht suboptimal? Stell dir vor, die Zahl ist kleiner als 50, aber man beginnt mit 60 zu raten. Dann muss man jetzt 30 Zahlen statt 25 durchsuchen, also ist es nicht optimal
  • Cool. Leicht vorstellbar, wenn man sich die Zahlen 1–100 entlang eines Zifferblatts angeordnet denkt. Man dreht die Uhr einfach zufällig, bevor man die normale Binärsuche von oben startet

• Von all den Dingen, bei denen Ballmer falschlag, scheint das wohl auch eins davon zu sein

  • Auf Microsoft zu setzen war für Ballmer allerdings richtig
  • Ich wünschte, ich könnte so falschliegen wie Ballmer. Seine Netto-Entscheidungsbilanz lag bei mehreren Milliarden Dollar
  • Du musst uns auch zeigen, womit du falschlagst, damit wir urteilen können
  • Mein persönlicher Favorit: https://www.youtube.com/shorts/rCszxibClKE

• Das hier ist, Freunde, ein perfektes Beispiel dafür, warum moderne technische Interviewprozesse reiner Wahnsinn sind

  • Ist das wirklich ein perfektes Beispiel für kaputte moderne technische Interviews?
    Ballmers Frage wirkt fair, wenn man bedenkt, welche Komplexität der Antwort er vermutlich erwartet hat.
    Der Bewerber würde wahrscheinlich eine mathematisch falsche Antwort geben, dabei aber seinen Denkprozess zeigen und nebenbei ein bisschen Informatik-Grundlagen demonstrieren.
    Man muss bedenken, wie lange Ballmers Karriere zurückreicht. Wenn er diese Frage tatsächlich gestellt hat, dann vermutlich in den 80ern, und damals hätte niemand erwartet, dass jemand die im Beitrag beschriebene komplizierte Lösung liefert.
    Eine richtige Antwort wäre beeindruckend und ein sofortiger Einstellungsgrund gewesen. Aber grundsätzlich kaputt wirkt die Frage nicht. Ob man die Wette eingeht oder nicht: Jede Antwort muss gut begründet werden
  • Fairerweise muss man sagen, dass Steve Ballmer ein schrecklicher Anführer war und ein technisches Interview, hätte er selbst eins machen müssen, wohl nicht bestanden hätte. Microsoft wäre auch nicht ein Jahrzehnt lang stagniert, bis Satya Nadella übernahm und das Unternehmen wieder auf Kurs brachte
  • Wirklich? Wenn ich als Interviewer diese Frage zwangsläufig stellen müsste und der Kandidat sagte: „Eigentlich ist die Frage falsch, und zwar aus folgendem Grund“, dann wäre das ein sehr gutes Zeichen. Machen die Leute das normalerweise nicht?
    Im Allgemeinen gibt es mit allen Interviewern eine Diskussion, und es geht nicht einfach nur darum, ob „der Kandidat das Problem gelöst hat“. Ich persönlich halte viele Big-Tech-Interviewfragen für dumm, aber nachdem ich den Prozess von beiden Seiten erlebt habe, würde ich sagen, dass er nicht so kaputt ist, wie man oft denkt
  • Ich arbeite zwar nicht in der Tech-Branche, aber ich dachte immer, solche Fragen seien unabhängig von einer richtigen Lösung dazu da, Problemlösefähigkeit zu zeigen
    In diesem Fall also etwa, dass man über Binärsuche nachdenken und zeigen kann, dass der erwartete Gewinn 0.20 Dollar beträgt
  • Solange es darum geht herauszufinden, ob die Zusammenarbeit beiden Spaß machen würde, finde ich es in Ordnung. Aber immer öfter wird daraus ein Quiz oder etwas noch Schlimmeres
    Immerhin verdanken wir dem hochwertige Fiktion wie https://aphyr.com/posts/340-reversing-the-technical-interview und den Nachfolgeartikel

• Einen Artikel mit einer umfassenderen Analyse des Nash-Gleichgewichts, einschließlich der numerischen Lösung für das gesamte Spiel, gibt es unter https://bowaggoner.com/blahg/2024/09-06-adversarial-binary-s...

• Steve Ballmers Nettovermögen beträgt 120 Milliarden Dollar, also würde es, wenn eine Runde 30 Sekunden dauert, 1,6 Millionen Jahre dauern, alles zu gewinnen

  • Man kann einfach Computer gegeneinander spielen lassen. Die KI auf meinem Computer gegen Ballmers KI. Das heißt, innerhalb von 30 Sekunden 1.683.036.051.984 Computerpartien durchlaufen zu lassen

• Little Mathematics Library – Elements of Game Theory: https://mirtitles.org/2012/09/06/little-mathematics-library-...
  Ein sehr gutes Buch über gemischte Strategien in der Spieltheorie
  Auch das Motivationsbeispiel im Buch ist hervorragend
  „Es gibt zwei Karten, ein Ass und eine 2. Spieler A zieht zufällig eine der beiden, und B kann nicht sehen, welche Karte gezogen wurde. Wenn A das Ass gezogen hat, sagt A: ‚Ich habe ein Ass‘, und verlangt 1 Dollar vom Gegner. Wenn A die 2 gezogen hat, kann A entweder (A1) sagen: ‚Ich habe ein Ass‘, und 1 Dollar vom Gegner verlangen, oder (A2) gestehen, dass A eine 2 hat, und dem Gegner 1 Dollar geben
  Der Gegner kann 1 Dollar, den er freiwillig bekommt, nur annehmen. Wird jedoch 1 Dollar von ihm verlangt, kann er entweder (B1) glauben, dass A ein Ass hat, und 1 Dollar zahlen, oder (B2) eine Überprüfung verlangen, um zu sehen, ob As Aussage wahr ist. Hat A tatsächlich ein Ass, muss B A 2 Dollar zahlen. Hat A dagegen geblufft und eine 2, dann zahlt A B 2 Dollar
  Analysiere dieses Spiel und bestimme die optimale Strategie sowie die erwartete Auszahlung für jeden Spieler.“