Vom Prinzessinnen-/Sekretärinnen-Problem

Ein Leser fragt an:

Prinzessinnen-/SekretärinnenProblem

Hallo Hadmut,

mich verwundert gerade eine Kleinigkeit an dem Prinzessinenproblem das du beschrieben hast.

Wenn der Bestmögliche Kandidat unter den ersten n/e liegt, folgt daraus doch dass sie immer beim letzten Kandidaten hängebliebt, weil es ja unter den Restlichen Kandidaten keinen mehr gibt der besser ist als alle vorherigen.

Ich hätte das nach deiner ursprünglichen Beschreibung mit dem Durchschnitt verstanden, also dass die n/e dazu dienen eben den Durchschnitt zu ermitteln und dann den erstbesten zu nehmen der mindestens diesen Durchschnitt erfüllt bzw. übrschreitet.

Aber dass die Prinzessin in der Restmenge einen finden muss, der besser ist als alle vorherigen ist… und das optimal sein soll ist irgendwie merkwürdig.
Die Eulersche Zahl ist 2,71… also heißt das doch dass rund 37% erstmal “durchgewunken” werden, das ist also ein Solides Drittel aller verfügbaren Kandidaten. – Wenn da schon der Beste drunter war, ist sie dazu verdammt den letzten zu nehmen der ihr vorgestellt wird.
Da hätte ich intuitiv vermutet dass das mit dem Durchschnitt die bessere Lösung des Problems wäre.

Wo liegt hier mein Fehler?

Das ist nicht ganz einfach zu erklären, das braucht etwas mathematisches Verständnis und Erfahrung.

Die Gemeinheit an diesem Prinzessinnen-/Sekretärinnenproblem ist nämlich, und das ist so ganz typisch für Spieltheorie, dass es keine Lösung gibt, keine Methode, keinen Algorithmus, mit der oder dem man den besten Kandidaten findet. Wenn das möglich wäre, wäre das als Aufgabenstellung a) uninteressant und b) gelöst. Wie bei Tic Tac Toe: Wenn jeder perfekt spielt, kann er immer mindestens Unentschieden erzielen.

Solche Spiele, für die es eine perfekte Lösung gibt, sind, wenn diese Lösung bekannt ist, höchstens noch insofern interessant, kürzere Lösungen zu finden. (War eine Aufgabe in der Computeralgebra-Vorlesung bei mir im Studium, Lösungsstrategien für Rubic’s Cube zu optimieren und kürzere Lösungstabellen zu finden.)

Das Prinzessinnenproblem oder Sekretärinnenproblem ist ja gerade so gebaut, dass man es nicht perfekt lösen kann. Man weiß ja nie, ob nicht ein Besserer kommt.

Deshalb geht es darum, eine Strategie, einen Algorithmus, eine Vorgehensweise zu finden, die das bestmögliche statistische Ergebnis findet. Was etwas paradox ist, weil man ja nur einmal (oder wenige Male) im Leben heiratet, Wahrscheinlichkeiten aber eigentlich, genau betrachtet, Grenzwerte sind, gegen die das Spielergebnis konvergiert, wenn die Zahl der gespielten Spiele (oder jedes anderen statistisch betrachteten Vorgangs) gegen Unendlich konvergiert.

Sorry, das ist nicht leicht zu verstehen. Das gehört in die Analysis. Das war eine von den Prüfungen in meinem Vordiplom mit Durchfallquoten von 80 bis über 90 Prozent.

Das gestellte Problem ist nicht perfekt lösbar. Das ist ja gerade so gestellt, dass man in ein Dilemma kommt und das fürchterlich schief gehen kann.

Informatiker schauen sich bei solchen Fällen (auch bei Sortieralgorithmen) gerne die Grenzfälle an, was passiert, wenn die Leute nicht zufällig kommen.

• Beispiel 1:

Stellt Euch vor, die Kandidaten wären in absteigender Qualität sortiert. Dann würde die beschriebene „optimale“ Lösung zwingend den letzten Kandidaten und damit den schlechtesten Wählen.

• Beispiel 2:

Stellt Euch aber mal vor, die Kandidaten wären in aufsteigender Qualität sortiert. Dann würde die „optimale“ Lösung den ersten Kandidaten nach den n/e durchgewinkten Kandidaten wählen, also auch einen ziemlich schlechten, weil weit unterdurchschnittlichen.

Es gibt auch keine richtige Methode, die richtigen Lottozahlen zu tippen. Man weiß es eben vorher nicht. Es bleibt ja nichts als raten.

Man kann die Wahrscheinlichkeit, beim Lotto zu gewinnen, mit keinem Algorithmus verbessern oder optimieren.

Man kann aber den durchschnittlichen oder zu erwartenden Gewinn optimieren, verbessern, nämlich wenn man weiß, dass viele Menschen Geburtstage (1 bis 12, 1 bis 31, Jahreszahlen) oder Muster tippen. Wenn man also Zahlen wählt, die nicht nach Muster aussehen und nicht in Geburtsdaten vorkommen können, hat man zwar genau dieselbe Wahrscheinlichkeit zu gewinnen wie mit allen anderen Zahlen – aber mit hoher Wahrscheinlichkeit weniger Leute, die die Zahlen auch getippt haben, und somit weniger Gewinner, durch die das Preisgeld geteilt werden muss.

Man muss sich das klarmachen, dass es auch bei Problemen, die man nicht perfekt lösen kann, weil man einfach nicht weiß, was kommt, trotzdem Methoden, Strategien finden kann, die die Erfolgswahrscheinlichkeit optimieren, also im Mittel das beste Ergebnis liefern, wenn man das Spiel sehr oft spielt. Das kann zwar – siehe Beispiele oben – sein, dass dies im Einzelfall völlig schief geht. Was, wenn der beste Kandidat gleich zu Anfang kommt und man ihn ablehnt, weil man ja noch gar nicht weiß, dass er der beste ist?

Oder man den Schönling wählt, ohne zu wissen, dass Superman noch kommt?

Würde man das Spiel aber sehr häufig wiederholen, würde einem das im Mittel, im Durchschnitt aller Spieldurchläufe, das beste Ergebnis liefern. Das kann zwar sein, dass man da ein paar Mal die Niete zieht. Weil das Spiel so gebaut ist, dass man das überhaupt nicht verhindern kann. Es ist ja auch keine Qualität der Kandidaten zugesichert. Es könnte ja auch sein, dass da 100 Nieten kommen und es völlig egal ist, wen man wählt, die alle Versager sind.

Das ist schwer zu verstehen, das muss man sich erarbeiten, dass es für das Problem keine Lösung gibt, die immer funktioniert. Es gibt keine Wunderlösung. Man kann – siehe Beispiele oben – beweisen, dass jede Herangehensweise scheitern kann.

Aber: Es gibt eben eine Methode, die im Durchschnitt, im Mittel die besten Ergebnisse liefert.

Ich mache jetzt einen großen Fehler. Ich bringe zwei Beispiele, die zwingend zu endlosen bösen Diskussionen führen.

Das Drei-Türen-Problem

Da haben sich schon Generationen bekriegt. Ganz übles Ding, weil es manche verstehen und manche nicht.

Kennt Ihr noch die Fernsehshow mit dem Zonk und Ralf Dräger?

Folgende Problemstellung: Ihr seid Kandidat in einer Fernsehshow. Es gibt drei geschlossene Tore, und hinter einem steht ein toller Gewinn, und hinter den beiden anderen steht eine Niete, also nichts gewonnen. Ihr dürft ein Tor wählen, und wählt eines. Es wird aber noch nicht geöffnet. Der Showmaster sagt: „Ich zeige Dir jetzt was“ und öffnet ein anderes Tor, hinter dem eine Niete steht. Und fragt nun: Bleibst Du bei Deinem Tor, oder möchtest Du das andere der beiden geschlossenen haben?

Die einen (auch ich) meinen, dass es ratsam ist, zu wechseln, weil man mit dem Tor, das man hat, mit einer Wahrscheinlichkeit von 1/3 gewinnt, mit dem Wechsel also eine 2/3-Wahrscheinlichkeit erreicht. Die anderen meinen, es sei egal, weil man jetzt ja nur noch zwei Tore hat, also eine Wahrscheinlichkeit von 50%.

Die Aufgabe ging zur Zeit meiner Uni-Zeit mal in den USA herum und führte fast zu einem Bürgerkrieg der beiden Aufassungen, zumal eine Autorin, Marilyn vos Savant, die laut Guiness-Buch der Rekorde (oder irgendsowas in der Art) den Weltrekord im IQ halte, dass die 1/3-2/3-Lösung richtig sei.

Das ist sie – im Prinzip – auch, obwohl der Gewinn ja hinter beiden Toren stehen kann. Man kann sich das aber so vorstellen, als ob der Moderator fragt „Wollen Sie Ihr Tor, oder wollen Sie das, was hinter den beiden anderen Toren ist, zusammen?“

Der Knackpunkt daran ist, und das schien damals (zumindest an der Uni) niemandem außer mir aufgefallen zu sein, dass die Aufgabenstellung nicht eindeutig, sondern doppeldeutig ist und jede Lösung zu einem Fall gehört, es also darauf ankommt, wie man die Aufgabe versteht:

• Variante 1 ist: Der Moderator weiß, hinter welchem Tor der Gewinn ist, und zeigt einem bewusst und absichtlich ein Tor mit einer Niete. Was er dann ja kann, weil es nach der Wahl eines Tores noch zwei andere gibt, also immer mindestens eines mit einer Niete, und er das also so machen kann. Dann nämlich bleibt es bei der 1/3-2/3 Wahrscheinlichkeit, weil das Verhalten des Moderators die Trefferwahrscheinlichkeit der ersten Wahl nicht ändern kann und man mit dem Wechsel im Prinzip die anderen beiden Tore zusammen bekommt.
• Variante 2 ist aber: Der Moderator weiß nicht, hinter welchem Tor der Gewinn ist, und rät selbst ein Tor. Es könnte also passieren, dass der Moderator selbst mit einer Wahrscheinlichkeit von 1/3 den Gewinn zieht, das nur eben gerade zufällig nicht passiert, man also nur noch die beiden Fälle betrachtet, in denen der Moderator nicht gewinnt, und die dann 50:50 verteilt sind.

Das hat, glaube ich, damals auch die intelligenteste Frau der Welt nicht gemerkt, dass die Aufgabe nicht eindeutig gestellt war, man sie auf zwei Arten verstehen kann, und jede Lösung zu einem Verständnisweg passt.

Aber: Fast niemand hatte den Unterschied bemerkt. Praktisch alle, die für die 50:50-Lösung waren, verstanden entweder die Variante 1 oder dachten gar nicht erst so weit oder begriffen den Unterschied nicht, und waren schlicht nicht in der Lage, das statistische, spieltheoretische Problem zu verstehen, dass man zwar nicht weiß, hinter welchem Tor der Gewinn ist, es im Mittel bei vielen Durchläufen aber die Vor ist, die in 2/3 der Fälle gewinnt, das Tor aufzugeben und zu wechseln. Das kann schief gehen, aber im Mittel ist es die bessere Vorgehensweise. Versteht aber nicht jeder.

Corona-Impfung

Man hat mir übelste Vorwürfe gemachen und ich werde bis heute gelegentlich dafür beschimpft, manche Leute ignorieren oder schneiden mich bis heute dafür, dass ich mir die Corona-Impfung habe geben lassen.

Dabei hatte ich damals ausführlich beschrieben, dass man vor einem ähnlichen Problem steht: Man muss sich entscheiden, bevor man wissen kann, was richtig ist. Es gibt keine im Einzelfall richtige Lösung, weil man nicht Hellsehen kann. Es ist ein Lottospiel, bei dem man erst hinterher weiß, was richtig war. Eine Aufgabenstellung auch aus dem Bereich der Entscheidungstheorie.

Egal, wie man es macht, es kann falsch sein. Deshalb muss man versuchen, sich eine Entscheidungsmethode zu suchen, von der man vermutet (oder weiß), dass sie bei unendlich vielen Durchläufen im Mittel die besten Ergebnisse liefert. Nicht immer richtig, aber möglichst häufig richtig. Was durchaus schwer zu vertehen ist, wenn man die Entscheidung nicht beliebig oft wiederholen kann, sondern sie nur einmal trifft (Heiraten, Corona-Impfung, beim Zonk mitspielen).

Das Problem – genau wie bei der Aufgabe mit den drei Türen – ist, dass es Leute gibt, die das verstehen können, und andere, die das nicht können, denen das partout nicht ins Hirn geht. Das könnte mit Hirnstrukturen und Präferenzen zu tun haben, was ja auch meine Überzeugung nährt, dass eben nicht jeder alles kann, sondern manche können das, und andere können was anderes (und manche auch einfach gar nichts).

Greedy-Algorithmen

Noch eine Anmerkung aus der Algorithmentechnik: Die Problemstellung ist eng verwandt mit der Gruppe der Greedy-Algorithmen. Greedy = habgierig, gefräßig. Damit bezeichnet man Algorithmen, die aus mehreren Alternativen etwas wählen, und dann darauf beharren, sich nicht verbessern können, sondern an die getroffene Entscheidung gebunden sind.

Klassisch lernt man so etwas vor allem bei rekursiven Lösungssuchen wie der Wegsuche durch ein Labyrinth. Es gibt Algorithmen, die an einer einmal gefundenen Lösung irreversibel festhalten, auch wenn sie später bessere, kürzere Wege finden könnten. Beispiel: Es gibt eine Methode, den Weg durch ein Labyrinth zu finden, indem man immer, wenn möglich, links abbiegt und einfach immer links an der Wand entlang geht. Je nach Bauweise des Labyrints führt dies immer zum Ausgang. Es könnte aber viel kürzer sein, rechts abzubiegen, etwa wenn der Ausgang gleich rechts neben dem Eingang ist, statt rekursiv das gesamte Labyrinth abzumarschieren.

Ich hatte oben die Algebra-Aufgabe mit Rubic’s Cube erwähnt. Den genauen Algorithmus habe ich jetzt nach fast 40 Jahren nicht mehr im Kopf. Man sucht rekursiv nach Kombinationen, indem an Drehungen ausprobiert und sich anschaut, welche Felder sie verändern und welche sie gleich lassen. Man baut sich also Tabellen auf, die einem zu jedem Feld X, das nach Position Y muss, Lösungszüge sammeln, die aber zunnehmend komplexer werden, je nachdem, wieviele Felder dabei unverändert bleiben müssen. Beim ersten Feld ist egal, was man durcheinander bringt. Beim zweiten Feld, das man löst, muss man aber darauf achten, das erste Feld nicht zu verändern, darf also nur solche Züge verwenden, die das erste Feld im Ergebnis unverändert lassen. Beim dritten Feld müssen das erste und das zweite Feld unverändert bleiben, und so weiter und so fort.

Sobald die Tabelle vollständig ist, hat man den Rubic’s Cube als Aufgabe gelöst, weil man zu jeder beliebigen Stellung sagen kann, mit welcher Abfolge von Zügen – aus der Tabelle – man ihn wieder zurückdrehen kann.

Aber: Die Tabelle ist dann, wenn sie zum ersten Mal vollständig ist, lausig schlecht. Schlechte, lange, Züge. Also lässt man den Algorithmus weiter suchen, damit er bekannte Züge mit bestimmten Eigenschaften durch bessere, nämlich kürzere Züge mit denselben Eigenschaften ersetzt. Je länger man den Rechner rechnen lässt, desto besser, nämlich kürzer werden die Züge in der Tabelle, und desto weniger Züge braucht das Verfahren, um Würfel zu lösen. Das ist also das Gegenteil eines Greedy Algorithmus, der kann Entscheidungen aufgeben und durch bessere ersetzen. Ist die Rekursionstiefe länger als der bis dahin längste bekannte Zug, ist man fertig, weil man dann keinen besseren Zug mehr finden kann. Man kann also die optimale Lösung finden.

Das Sekretärinnenproblem ist aber so gestellt, dass man seine Entscheidung nicht revidieren kann. Die Entscheidung ist endgültig, und man muss sie treffen, bevor man das nötige Wissen dazu hat.

Dehsalb ist die Aufgabenstellung so haarig, und im Sinne der Spieltheorie und Entscheidungstheorie interessant: Es gibt keine richtige, keine perfekte Lösung. Jede Methode kann schief gehen. Egal, was man macht, man kann immer die schlechteste Entscheidung treffen und an Quasimodo kommen. Das Problem ist nicht lösbar.

Aber: Man kann sich Methoden suchen, die im Durchschnitt, im Mittel, würde man das Spiel oft, theoretisch unendlich oft, spielen, konvergierend, asymptotisch die besten Ergebnisse erzielen.

Wenn das trivial und leicht zu verstehen wäre, müsste man Mathe und Informatik nicht studieren.

Vor allem muss man sich von der naiven Sichtweise lösen (Stichwort der Witz vom Männerkaufhaus), dass man sich irgendwie so optimieren könnte, dass man den besten Kandidaten wählen kann. Die Aufgabe ist so gestellt, dass man das nicht systematisch, nur zufällig kann.

Der erste Weg zu Verständnis ist deshalb, einzusehen, dass schon die Frage „Aber was, wenn der Beste schon unter den ersten n/e war“ falsch ist und man so nur fragen kann, wenn man das Problem nicht verstanden hat. Das Problem ist nicht perfekt lösbar. Es geht nicht. Man kann den Besten höchstens zufällig als Glückstreffer, aber nicht systematisch finden.

Der Haken an dem Ding ist, zu begreifen, dass die Aufgabe nicht „Finde den besten Kandidaten“ lautet, sondern „Mach das Beste draus!“, „Finde die beste Entscheidungsmethode“. Wie beim Männer- und beim Frauenkaufhaus. Einzusehen, dass die Aufgabe nicht perfekt lösbar ist. (Für Film-Fans: So ähnlich wie der Kobayashi-Maru-Test, aber nicht gleich, der war gar nicht lösbar, und es ging darum, mit einer unlösbaren Aufgabe umzugehen.)

Die Aufgabenstellung ist, aus einer unlösbaren Aufgabe noch mit einem nach Wahrscheinlichkeit möglichst guten Ergebnis rauszugehen und damit zufrieden zu sein. Es gibt keine Lösung für den Einzelfall, so wenig, wie man die nächsten Lottozahlen auswählen kann. Der Leser fragt wie „Aber was ist, wenn ich die 15 ankreuze und die die 27 ziehen?“ Dann haste Pech gehabt. Die Aufgabe ist im Prinzip eine Kandidatenlotterie. Man kann nicht blind den Treffer landen. Aber: Weil man nicht aus der Tomobola einfach einen zieht, sondern einen nach dem anderen sieht und ja/nein sagen muss, hat man einen Ansatzpunkt, um eine Methode zu entwickeln, in der Annahme, dass sie wirklich zufällig verteilt sind.

Bei einem einzelnen Durchlauf könnte man auch einfach vorher sagen „Egal, ich nehme den Ersten oder den Letzten, oder auch den Siebzehnten“. Weil jeder davon mit gleicher Wahrscheinlichkeit der Beste sein könnte. Man weiß es nicht. Wenn man aber davon ausgeht, dass die Kandidaten sich in einem gewissen Werteraum bewegen, ist es sinnvoll, sich erst einmal ein paar anzuschauen, um einen Maßstab zu bilden, und dann den ersten zu nehmen, der besser ist. Spieltheorie. Entscheidungstheorie.

Die Aufgabe ist nicht, den besten Gatten zu finden. Sondern die beste Entscheidungsmethode.

Und das hat vielleicht, oder ziemlich sicher damit zu tun, dass so viele Frauen in ihrem Selbstoptimierungswahn auf den Besten warten, weil ihnen die Einsicht fehlt, dass dieses Problem gar nicht lösbar ist, und dann mit Mitte 30 angewelkt als Single kinderlos der Menopause entgegenwelken.

Und das ist der Grund, warum es ein Fehler war, Mädchen in der Schule von Mathematik zu befreien.

Das wäre übrigens etwas, ebenso wie die Aufgabe mit den drei Toren, worüber ich mit einem Bewerber in einem Bewerbungsgespräch diskutieren würde, um zu sehen, ob der mathematisch, asymptotisch denken kann.