Das Sekretärinnen-Problem

Ich hatte – wieder einmal – das „Prinzessinnen“-Problem erwähnt.

Ich hatte das noch aus ungefähr der Zeit meines Studiums in Erinnerung, wusste aber ad hoch keine Quelle mehr dazu. Es ging um die Aufgabe, dass die Prinzessin sich einen Gatten aussuchen muss und ihr der Reihe nach n Kandidaten (z. B. n=100) einzeln vorgestellt werden, die sie vorher nicht kennt und sieht. Nach dem Kandidaten muss sie – unwiderruflich – sofort „Ja“ oder „Nein“ sagen und spätestens den letzten Kandidaten dann nehmen. Das kann natürlich fürchterlich schief gehen, wenn einem keiner gut genug ist und als Letzter dann Quasimodo oder Honecker reinkommen. Wie vorgehen? Welche Strategie wählen?

Leser wussten, wo zu suchen ist. Das Problem ist unter vielen, für Publikationen aber dem (soweit ich mich jetzt erinnern kann, bisher nicht geläufigen) Namen „Sekretärinnen-Problem“ bekannt, aber eben auch das Prinzessinnen- oder Heiratsproblem. Egal, wie es heißt, es geht immer um dasselbe Problem, und dazu gibt es in der deutschen und der englischen Wikipedia Hinweise.

Gibt es in unzähligen Varianten, in Form des Chefs, der eine Sekretärin einstellen oder des Gebrauchtwagenhändlers, der ein Auto zum besten Preis verkaufen muss.

Ein Detail hatte ich offenbar nicht mehr richtig in Erinnerung. Ich hatte mich zwar korrekt daran erinnert, dass man zuerst n/e Kandidaten durchwinken und nur betrachten sollte, war mir aber nicht mehr sicher, ob man den ersten nimmt, der besser als alle dieser n/e Kandidaten oder nur besser als der Durchschnitt, und hatte dann falsch besser als der Durchschnitt geschrieben. Die Vorgehensweise ist aber, nach den n/e Kandidaten den ersten zu nehmen, der besser als alle bisherigen Kandidaten ist.

In beiden Seiten steht auch was zur Lösung, in der englischen aber ausführlicher, und das erklärt auch, wie die Eulersche Zahl in die Lösung kommt, weil es dabei um ein Integral über 1/t nach dt geht, was sich nach den bekannten Integralregeln (Ein Integral heißt Bronstein-integrierbar, …) in ein Produkt mit ln(..) umformen lässt, und damit hat man dann die Eulersche Zahl mit rein.

Die Herangehensweise ist auch als Odds-Strategie oder Bruss algorithm.

Wenn man jetzt also exakt wüsste, wieviele Heiratskandidaten einem im Leben begegnen, wüsste man genau, nach welchem Algorithmus man auswählt.

Mir kommt das Problem auch von der Job- und Wohnungssuche und von Sonderangeboten bekannt vor. Eigentlich bin ich bei der Wohnungssuche auch immer so vorgangen, dass ich mir erst einige ansehe, selbst wenn ich vorher schon weiß, dass ich die bestimmt nicht nehme, um meine Erwartungen zu kalibrieren, und dann nach einer gewissen Weile in den Entscheidungsmodus zu gehen.