Sekretärinnenproblem

In der Statistik, der Spieltheorie und der Entscheidungstheorie bezeichnet das Sekretärinnenproblem (auch bekannt als Heiratsproblem, aber nicht zu verwechseln mit der Problemstellung, die dem Heiratssatz zugrunde liegt) die Aufgabe, aus einer Reihe einzeln und nacheinander betrachteter Bewerber den besten auszuwählen. Dabei ist eine Ablehnung unwiderruflich. Wegen der enthaltenen Zufallselemente wird das Problem meist so formuliert, dass die größte Wahrscheinlichkeit für die Auswahl des besten Angebots zu bestimmen ist. Ein Lösungsalgorithmus für dieses Problem wird durch die Odds-Strategie gegeben.

Die Lösung des Problems wird als 37-Prozent-Regel (oder $1/e$-Regel) bezeichnet. Sie wurde von Geoffrey Miller in seinem Buch The Mating Mind beschrieben. Sie besagt, dass man die ersten 37 Prozent (genauer: $\textstyle 1/e\cdot 100$ Prozent) der Bewerber betrachtet und danach den ersten Bewerber akzeptiert, der besser als alle bisherigen (also das bisher gefundene Optimum) ist. Diese einfache $1/e$-Regel sollte aber nicht mit dem 1/e-Gesetz der besten Wahl (s. u.) verwechselt werden, das in einem erweiterten Modell mit einer unbekannten Anzahl von Kandidaten gilt.

Versagen des Verfahrens

Die Wahrscheinlichkeit, den besten Bewerber zu finden liegt bei 37 %, das heißt in knapp 2/3 der Fälle findet man nicht den besten Bewerber. Dies passiert, wenn der beste Bewerber bereits unter den ersten 37 % war (in diesem Fall wird der letzte Bewerber genommen) oder wenn der beste Bewerber später kommt, aber hinter einem, der besser ist als der beste in den ersten 37 %. Sollten die Bewerber gar in qualitativ absteigender Reihenfolge sortiert sein, führt das Verfahren dazu, dass der absolut schlechteste Bewerber genommen werden muss. Das Verfahren ist auch nicht sehr erfolgreich, wenn die ersten 37 % der Bewerber die schlechtesten waren. In diesem Fall wird der Nächstbeste akzeptiert.

Problem

In einer häufig als Beispiel angeführten Variante möchte eine Organisation eine Sekretärin einstellen. Die Bewerberinnen sprechen nacheinander vor; in der Begutachtung kann eine Rangfolge aufgestellt werden, und die Qualitäten einer jeden Bewerberin können festgehalten werden. Allerdings scheidet eine abgelehnte Bewerberin endgültig aus und steht im weiteren Verlauf nicht mehr zur Verfügung, eine Prämisse, die der tatsächlichen Personalbesetzungsrealität widerspricht.

Eine andere Formulierung des Problems geht von der Wahl eines Ehepartners aus einer Reihe von Kandidaten aus. Die Problemstellung schließt mit ein, dass die Wahrscheinlichkeit, den jeweils besten Bewerber auszuwählen, maximiert werden soll. Soll stattdessen der Erwartungswert, bezogen auf alle in Frage kommenden Kandidaten, maximiert werden, wäre eine andere Strategie notwendig.

Beispiel

Es gebe drei Bewerberinnen, die sich in zufälliger Reihenfolge bewerben. Für ihre beobachteten Qualitäten 1, 2, 3 (dabei sei 1 die schlechteste Bewerberin und 3 die beste) gibt es dann 6 = 3! gleichwahrscheinliche Möglichkeiten: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1). Würde nun einfach die erste Bewerberin die Stelle bekommen, so wäre die Wahrscheinlichkeit, die beste einzustellen, gleich ${\tfrac {2}{6}}={\tfrac {1}{3}}$, nämlich in den Fällen (3,1,2) und (3,2,1).

Geschickter ist die folgende Strategie: Die erste Bewerberin wird abgelehnt. Falls die zweite besser als die erste ist, wird die zweite eingestellt, anderenfalls die dritte. Mit dieser Strategie bekommt man die beste Bewerberin in den Fällen (1,3,2), (2,3,1) und (2,1,3), also in 3 von 6 Fällen. Die Wahrscheinlichkeit ist somit ${\tfrac {3}{6}}={\tfrac {1}{2}}$.

Auch allgemein lässt sich zeigen, dass die beste Strategie darin besteht, zunächst eine bestimmte Anzahl $r$ der $n$ Bewerberinnen abzulehnen und dann die erste einzustellen, die besser als die $r$ abgelehnten ist. Dabei ist $r$ in Abhängigkeit von $n$ so zu optimieren, dass die Wahrscheinlichkeit, auf diese Weise die beste Bewerberin einzustellen, maximal wird.

Strategie

Das Problem hat eine sehr einfache Strategie, die dazu auch noch optimal ist:

Betrachte die ersten $r$ der $n$ Kandidaten (mit $1\leq r<n$) – und lehne sie ab.

Wähle von den verbleibenden $n-r$ Bewerbern den ersten, der besser ist als jeder der ersten $r$.

Es lässt sich zeigen, dass sich für große $n$ der optimale Wert für $r$ ergibt aus $r\approx n/e$, wobei $e$ die Basis des natürlichen Logarithmus (Eulersche Zahl) ist. Mit dieser Strategie liegt die Wahrscheinlichkeit, den besten Kandidaten zu wählen, bei $1/e$, also etwa 37 %.

Beweis

Wahrscheinlichkeiten P im Falle von n = 12 Bewerberinnen. Die optimale Anzahl der zunächst abgewiesenen Bewerberinnen ist hier r = 4 mit P ≈ 0,3955

Der beste Bewerber kann die Wahl nur gewinnen, wenn er sich nicht unter den ersten $r$ Probekandidaten befindet. Kommt er direkt danach auf Platz $r+1$, gewinnt er. Die Wahrscheinlichkeit, dass er auf diesem Platz steht, beträgt ${\tfrac {1}{n}}$. Steht er einen Platz weiter auf Platz $r+2$ – wieder mit der Wahrscheinlichkeit ${\tfrac {1}{n}}$ –, so gewinnt er genau dann, wenn sich der beste der vorherigen Kandidaten unter den ersten $r$ Probekandidaten befindet. Das ist mit der Wahrscheinlichkeit ${\tfrac {r}{r+1}}$ der Fall, zusammengesetzt gibt das die Wahrscheinlichkeit ${\tfrac {1}{n}}\cdot {\tfrac {r}{r+1}}$.

Geht man die Fälle entsprechend weiter durch bis zur letzten Position für den Besten, so erhält man wieder als Wahrscheinlichkeit für diese Position ${\tfrac {1}{n}}$ und für die Wahrscheinlichkeit, dass der beste Vorgänger zu den ersten $r$ Probekandidaten gehörte, die Wahrscheinlichkeit ${\tfrac {r}{r+n-r-1}}={\tfrac {r}{n-1}}$, zusammen also ${\tfrac {1}{n}}\cdot {\tfrac {r}{n-1}}$.

Insgesamt ergibt sich die Wahrscheinlichkeit $P$ für einen Erfolg der Strategie zu:

$P=\sum _{a=r+1}^{n}{\frac {1}{n}}\cdot {\frac {r}{a-1}}={\frac {r}{n}}\sum _{a=r}^{n-1}{\frac {1}{a}}$

Für die Summe macht man die mit wachsendem $n$ immer besser werdende Integral-Näherung:

$P\approx {\frac {r}{n}}\int _{r}^{n}{\frac {1}{a}}da=-{\frac {r}{n}}\ln {\frac {r}{n}}$

Das Maximum nimmt dieser Näherungsausdruck dort an, wo seine Ableitung gleich 0 ist, nämlich an der Stelle $r={\tfrac {n}{e}}$; es beträgt ${\tfrac {1}{e}}\approx 0{,}368$. Das Maximum ist nicht sehr ausgeprägt: für den weiten Bereich ${\tfrac {n}{4}}\leq r\leq {\tfrac {n}{2}}$ wird nämlich durchweg ${\tfrac {\ln 2}{2}}\approx 0{,}346$ nie unterschritten. Eine genauere auf der Odds-Strategie beruhende Analyse (Bruss 2003) zeigt jedoch mehr, nämlich dass die Erfolgswahrscheinlichkeit immer strikt größer als 1/e= 0,3678... ist, also stets strikt größer als die asymptotische Erfolgswahrscheinlichkeit, wenn die Anzahl der Bewerber gegen unendlich strebt.

Bezieht man den Zweitbesten in die obige Strategie mit ein, so nähert sich die Wahrscheinlichkeit dafür, dass dieser ausgewählt wird, für große $n$ dem Wert $1/e^{2}$. Insgesamt wird damit die Wahrscheinlichkeit, dass man durch diese Strategie den besten oder zweitbesten Kandidaten erhält, für große $n$ etwas größer als 50 %.

Verallgemeinerungen und Varianten

Unbekannte Anzahl N von Optionen

Der Hauptnachteil des klassischen Sekretärinnenproblems für mögliche Anwendungen ist die Tatsache, dass die Anzahl $N$ der Optionen (Kandidaten) als im Voraus bekannt vorausgesetzt wird. Eine Möglichkeit dies zu umgehen ist anzunehmen, dass die Verteilung $P(N=k)_{k=1,2,\cdots }$ dieser Anzahl bekannt ist (Presman und Sonin, 1972). In diesem Modell ist es jedoch im Allgemeinen schwieriger, die optimale Lösung zu bestimmen. Hinzu kommt insbesondere, dass die optimale Gewinnwahrscheinlichkeit oft wesentlich kleiner ist. Es ist intuitiv klar, dass die Unkenntnis der Anzahl N von Optionen ihren Preis haben sollte, doch dieser Preis ist oft sehr hoch. Tatsächlich wird in einigen Fällen die optimale Gewinnwahrscheinlichkeit praktisch null. Eine geschickte Umformulierung dieses Modells löst dieses Problem.

1/e-Gesetz der besten Wahl

Das Wesentliche des umformulierten Modells (der sogenannte verallgemeinerte Ansatz in stetiger Zeit) beruht auf der Idee, dass es leichter ist, abzuschätzen wann Kandidaten mehr oder weniger wahrscheinlich kommen werden (unter der Hypothese, dass sie kommen) als die Verteilung der Anzahl selbst einzuschätzen.

Das verallgemeinerte Modell: Ein Kandidat ist im Zeitintervall $[0,T]$ aus einer unbekannten Anzahl von Kandidaten $N$ auszuwählen. Ziel ist es, die Wahrscheinlichkeit zu maximieren, bei gleich wahrscheinlichen Ankunftsreihenfolgen verschiedener Ränge den besten Kandidaten auszuwählen. Man nimmt an, dass alle Ränge unabhängig voneinander die gleiche Ankunftszeitdichte $f$ auf $[0,T]$ haben. Sei $F$ die entsprechende Ankunftszeitverteilung, d. h.

$F(t)=\int _{0}^{t}f(s)\,\mathrm {d} s$, $\,0\leq t\leq T$.

Das 1/e-Gesetz (Bruss 1984) besagt dann: Sei $\tau$ die Lösung der Gleichung $F(\tau )=1/e.$ Weiterhin sei S die Strategie, alle Kandidaten bis zur Zeit $\tau$ abzuwarten und dann, wenn möglich, den ersten Kandidaten auszuwählen, der besser ist als alle Vorgänger vor der Zeit $\tau$.

Diese sogenannte 1/e-Strategie S hat folgende Eigenschaften:

Wenn es zumindest einen Kandidaten gibt, dann gilt

(i) S erzielt für alle $N$ eine Gewinnwahrscheinlichkeit von mindestens 1/e;

(ii) S ist die einzige Strategie, die diese untere Schranke 1/e erreichen kann, und diese untere Schranke ist scharf;

(iii) S wählt keinen Kandidaten mit der Wahrscheinlichkeit 1/e (genau).

Das 1/e-Gesetz wurde mit Überraschung aufgenommen (s. Math. Reviews 85:m), denn eine Gewinnwahrscheinlichkeit von 1/e schien für eine unbekannte Anzahl von Kandidaten $N$ nicht realisierbar, wohingegen dieser Wert nun als untere Schranke gilt, und dies sogar in einem Modell mit anerkannterweise schwächeren Hypothesen. Das 1/e-Gesetz wird gerne mit der Lösung des Sekretärinnenproblems verwechselt, weil 1/e dort eine ebenfalls wichtige Rolle spielt. Man beachte jedoch, dass das 1/e-Gesetz wesentlich weiter geht, da es einerseits für eine unbekannte Anzahl von Kandidaten gilt und zudem einem anwendungsfreundlichen Modell in kontinuierlicher Zeit entspringt.

Weitere Varianten des klassischen Modells

Das Problem ist in vielen verschiedenen Varianten untersucht worden, darunter:

• Die Wahl darf auf zwei Kandidaten fallen (anstatt nur auf einen).
• Die Zahl der Bewerber ist unbekannt.
• Gleichwertige Kandidaten sind von Bedeutung.
• Abgelehnte Bewerber sind nicht endgültig ausgeschieden.
• Die Wahl darf auch auf den zweitbesten Bewerber fallen.

Siehe auch

• Entscheidung unter Unsicherheit
  • Gefangenenparadoxon
  • Odds-Strategie
  • Umtauschparadoxon
  • Ziegenproblem
  • Zwei-Zettel-Spiel
• Gesetz der kleinen Zahlen

Literatur

• Eugene Dynkin: Optimal choice of the stopping time of a Markov process. In: Sov. Math. Dokl. Nr. 02, 1963, S. 238–240. 

• Franz Thomas Bruss: Sum the Odds to One and Stop. In: Annals of Probability. Band 28, Nr. 03, 2000, S. 1384–1391. 

• Franz Thomas Bruss: A Note on Bounds for the Odds Theorem of Optimal Stopping. In: Annals of Probability. Band 31, Nr. 04, 2003, S. 1859–1861. 

• Franz Thomas Bruss: A Unified Approach to a Class of Best Choice Problems with an Unknown Number of Options. In: Annals of Probability. Band 12, Nr. 3, 1984, S. 882–889. 

• Franz Thomas Bruss: Strategien der besten Wahl. In: Spektrum der Wissenschaft. Nr. 05, 2004, S. 102–104 (spektrum.de). 

• Stephen M. Samuels: A Best-Choice Problem with Linear Travel Cost. In: Journal of the American Statistical Association. Band 80, Nr. 390, 1985, S. 461–464, doi:10.1080/01621459.1985.10478141. 

• Eric W. Weisstein: Sultan’s Dowry Problem. In: MathWorld. Wolfram, 2004 (mathworld.wolfram.com [abgerufen am 24. Februar 2007]). 

Weblinks

• Mathematik-Online: Sekretärinnenproblem
• Lieses Verehrer oder das „Sekretärinnen-Problem“ (PDF; 120 kB)