Zuerst einmal muss ich mich entschuldigen: Die Lösung des Dezemberrätsels, die ich für Ende 2015 angekündigt hatte, ließ lange auf sich warten. Mir kamen irgendwie die Weihnachtsferien dazwischen, und eine Menge Arbeit, und die übliche Prokrastination… Und dann hatte ich auch das Gefühl, dass es eigentlich nichts mehr aufzulösen gäbe, da eine hartnäckige Bande von Rätslern am Ende gemeinsam ohnehin schon alles gesagt hatte, was zu sagen war.
Trotzdem, hier also jetzt die “offizielle” Auflösung:
Anna kann gegen einen klugen Bernd ihre Gewinnwahrscheinlichkeit tatsächlich über 50% heben, allerdings nur geringfügig darüber. Dazu müssen wir zunächst klären, was ein “kluger Bernd” eigentlich sein soll. Hinter dieser Formulierung steht die Annahme, Bernd sei gewissermaßen hyperrational – er antizipiert die von Anna gewählte Strategie und reagiert optimal (für ihn gewinnmaximierend) darauf. Annas Ziel ist es also, ihre Gewinnchance durch geschickte Strategiewahl zu erhöhen, gegeben dass Bernd optimal darauf reagiert. Hier sind wir übrigens schon mitten in der Spieltheorie, es handelt sich nämlich technisch ausgedrückt um ein endliches 2-Personen-Konstantsummenspiel, das mit John von Neumanns (1928) Minimax-Theorem lösbar ist.
Bevor wir uns geeignete Strategien für Anna – und für Bernd – überlegen, müssen wir definieren, was überhaupt eine Strategie ist. Als “reine Strategie” bezeichnen wir einen “Verhaltensplan”, also einen vorab festgelegten und deterministischen Plan, der beschreibt, welches Zahlenpaar man wählt (für Bernd) bzw. ob man tauscht oder nicht, wenn man eine bestimmte Zahl sieht (für Anna). Für Bernd ist eine reine Strategie also einfach ein Paar (X,Y) mit X < Y von Zahlen zwischen 1 und 1000, er hat demnach 1000 x 999 / 2 = 499500 reine Strategien. Das klingt zwar nach einer ganzen Menge, ist aber nichts im Vergleich zur Anzahl von Annas möglichen reinen Strategien. Im Grunde kann Anna nämlich eine von 1000 Zahlen sehen, und für jeden dieser 1000 Fälle muss sie sich überlegen, ob sie den entsprechenden Zettel behält oder tauscht. Das sind insgesamt 2^1000 mögliche Strategien, also
1071508607186267320948425049060001810561404811705533607443750388370351051 12493612249319837881569585812759467291755314682518714528569231404359845775 7469857480393456777482423098542107460506237114187795418215304647498358194 1267398767559165543946077062914571196477686542167660429831652624386837205 668069376, was doch deutlich mehr ist.
Allerdings kann keine einzige dieser Strategien Annas Gewinnchance gegen den klugen Bernd erhöhen. Denn für jede dieser reinen Strategien kann Bernd seine beiden Zahlen so wählen, dass Annas Strategie ihr lediglich eine 50%ige Gewinnwahrscheinlichkeit beschert. Wenn Annas Strategie z.B. lautet: “Tausche bei 12, 134 und allen Zahlen größer als 788, ansonsten behalte”, dann kann Bernd z.B. mit der Strategie (401, 645) kontern (oder mit unzähligen anderen). Anna wird dann jedenfalls behalten, und es bleibt bei ihrer 50% Gewinnchance. Ähnliches gilt für jede andere von Annas reinen Strategien.
Glücklicherweise hat Anna aber noch die Möglichkeit, ihre reinen Strategien zu “mischen”. Unter einer “gemischten Strategie” versteht man eine Wahrscheinlichkeitsverteilung auf den reinen Strategien. Anna hat also nicht nur ihre reinen Strategien zur Auswahl, sondern auch unendlich viele gemischte Strategien. Eine solche gemischte Strategie könnte z.B. lauten “Mit Wahrscheinlichkeit 1/3 tausche ich bei 3, 4 und 5, mit Wahrscheinlichkeit 2/3 tausche ich bei 498, 532 und allem von 933 bis 951.” Der Clou dabei ist: Wenn Anna eine gemischte Strategie spielt, dann wird ihr tatsächliches Verhalten zufällig und kann dadurch von Bernd nicht antizipiert werden. (Auch hyperrationale Spieler sind keine Hellseher.)
Anna kann jetzt durch die Wahl einer gemischten Strategie ihre Gewinnchance tatsächlich über 50% heben. Das geht z.B. durch jene Strategie, die wir die Z-Strategie nennen wollen. Sie lautet: “Ich wähle zufällig (gleichverteilt) eine Zahl Z zwischen 1 und 999. Wenn die Zahl auf meinem Zettel kleiner oder gleich Z ist, dann tausche ich, ansonsten behalte ich.” Egal welches Zahlenpaar (X,Y) Bernd nun wählt, gibt es immer eine strikt positive Wahrscheinlichkeit, dass Annas Z in den Bereich X <= Z < Y fällt. Wenn das passiert, dann tauscht Anna, falls sie X zieht, behält aber, falls sie Y zieht, d.h. sie gewinnt dann auf jeden Fall. Wenn Annas Z nicht in diesen Bereich fällt, dann tauscht sie entweder auf jeden Fall oder behält auf jeden Fall, und wahrt damit ihre 50% Chance. Insgesamt hat sie also eine Gewinnwahrscheinlichkeit von mehr als 50%.
Damit wäre das Rätsel an sich gelöst, denn gefragt hatte ich ja nur, ob (bzw. wie) man Annas Chance auf die Million über 50% heben kann, und das leistet die Z-Strategie auf jeden Fall. Einige Kommentatoren haben sich aber zu Recht gefragt, ob die Z-Strategie für Anna eigentlich optimal ist, und was Bernds optimale Reaktion darauf ist, und wie hoch Annas maximale Gewinnchance demnach gegen den klugen Bernd ist.
Dazu kann man folgendes überlegen: Wenn Anna die Z-Strategie spielt und Bernd das wie üblich antizipiert, dann wird Bernd, der seine eigene Gewinnchance maximieren, also Annas Gewinnchance minimieren will, danach trachten, die Wahrscheinlichkeit, dass Z in Annas “Gewinnbereich” fällt, möglichst klein zu machen. Das erreicht er dadurch, dass er jedenfalls ein Zahlenpaar (X,X+1) wählt. Bernd möchte aber auch keine reine Strategie (also kein fixes Zahlenpaar) spielen, denn das könnte von Anna antizipiert werden. Er könnte also z.B. das X in seinem (X,X+1)-Paar zufällig (gleichverteilt) zwischen 1 und 999 wählen, genau wie Anna ihr Z. Nennen wir das die X-Strategie. Einfach ausgedrückt wählen also Anna und Bernd ein Z bzw. ein X gleichverteilt zwischen 1 und 999, und wenn X = Z, dann gewinnt Anna die Million, ansonsten bleibt es bei der 50% Chance für jeden. Annas Vorteil bleibt also bestehen, ist aber ziemlich klein. Ihre Gewinnchance beträgt hier 500/999, was etwa 50,05% entspricht.
Kann Anna noch besser abschneiden, gegeben Bernd spielt die X-Strategie? Offenbar nicht, denn jedes X ist gleich wahrscheinlich. Kann Bernd noch besser abschneiden, gegeben Anna spielt die Z-Strategie? Offenbar ebenfalls nicht, aus demselben Grund. Wir haben also ein Paar von Strategien gefunden, die aufeinander jeweils optimal reagieren – in der Spieltheorie nennt sich sowas ein Nash-Gleichgewicht.
Könnte es aber nicht noch andere Nash-Gleichgewichte geben? Tatsächlich gibt es zwar im allgemeinen Konstantsummenspiele mit mehreren Gleichgewichten. Aber das ändert nichts an der Lösung, denn in Konstantsummenspielen ergeben alle Gleichgewichte dieselben erwarteten Auszahlungen, in unserem Fall dieselben Gewinnchancen. Annas Gewinnchance gegen den klugen Bernd beträgt also tatsächlich maximal 500/999.
PS: Dieses Spiel ist eine Variante des sogenannten Zwei-Zettel-Spiels, in dem die Zahlen, die Bernd wählen kann, eigentlich unbeschränkt sind. Auch dort funktioniert eine Art Z-Strategie für Anna, wenngleich es natürlich keine Gleichverteilung mehr sein kann. Aber dort gibt es dafür keine “optimale” Strategie wie in unserem Fall. Details dazu in der Wikipedia.
PPS: Meine in Annas Gedankengang versteckte Behauptung “Aber ich kenne Bernd, er ist klug und wird sicher nicht die 1 auf einen Zettel schreiben” war ein Versuch der Irreführung. Doch meine Kommentatoren, die ebenfalls klug sind, haben sich davon nicht beirren lassen…
PPPS: Zum Gewinner erkläre ich hiermit Lercherl, der/die sich auch nicht durch meine gezielte und wiederholte Irreführung beeindrucken ließ. Lercherl kam, sah und siegte, und zwar schon im dritten Kommentar, ließ sich allerdings später nie wieder blicken und verriet auch nicht wirklich, wie er auf seine Lösung kam. Außerdem hat er/sie Annas optimale Strategie nicht wirklich erklärt. (Obwohl aus dem Kontext dann doch erschlossen werden kann, welche wohl gemeint ist.) Deshalb erkläre ich den harten und später ebenso erfolgreichen Rätsler-Kern, bestehend aus Karl-Heinz, Joker und Dr. Webbaer hiermit zu Ko-Siegern. Gratulation und herzlichen Dank!
Kommentare (16)