Sekretärinnenproblem

Kernidee und Ziel

Das Sekretärinnenproblem ist ein Entscheidungsproblem aus Statistik, Spieltheorie und Entscheidungstheorie. Es beschreibt die Aufgabe, aus mehreren nacheinander betrachteten Bewerberinnen oder Kandidaten die beste Person auszuwählen. Die Anzahl der Bewerber ist im klassischen Modell vorher bekannt. Nach jeder Begutachtung muss sofort entschieden werden, ob die Person angenommen oder abgelehnt wird; eine Ablehnung ist unwiderruflich.

Das Ziel der klassischen Formulierung ist nicht, irgendeine gute Person zu finden, sondern die Wahrscheinlichkeit zu maximieren, wirklich den besten Bewerber auszuwählen. Die bekannte Lösung heißt 37-Prozent-Regel oder 1/e-Regel. Dabei ist e die Eulersche Zahl; es gilt 1/e · 100 ≈ 37. Man betrachtet zuerst ungefähr 37 % der Bewerber, lehnt sie alle ab und nutzt sie nur zum Vergleich. Danach nimmt man den ersten Bewerber, der besser ist als alle bisher gesehenen.

Diese Strategie ist optimal, wenn es darum geht, die Chance auf den besten Kandidaten zu maximieren. Sie hat aber einen wichtigen Nachteil: Die mittlere Platzierung des ausgewählten Bewerbers ist nicht optimal. Wenn der beste Bewerber bereits in den ersten 37 % vorkommt, wird er abgelehnt; dann wird im ungünstigen Fall später der letzte Bewerber genommen, der im Mittel keine gute Platzierung hat.

Klassische Problemstellung

In der häufig genannten Variante will eine Organisation eine Sekretärin einstellen. Die Bewerberinnen kommen nacheinander zu Gesprächen. Nach jedem Gespräch kann man die Bewerberin in eine Rangfolge einordnen und ihre Qualität festhalten. Die bisher gesehenen Personen können also verglichen werden.

Die entscheidende Einschränkung lautet: Jede abgelehnte Bewerberin scheidet endgültig aus und steht später nicht mehr zur Verfügung. Diese Annahme ist für die mathematische Modellierung wichtig, auch wenn sie der tatsächlichen Personalbesetzungsrealität widerspricht. Unter dieser Bedingung soll die Wahrscheinlichkeit maximiert werden, die beste Bewerberin einzustellen.

Ein einfaches Beispiel

Bei drei Bewerberinnen gibt es 3! = 6 gleichwahrscheinliche Reihenfolgen ihrer Qualität. Wenn 1 die schlechteste und 3 die beste Bewerberin ist, sind die möglichen Reihenfolgen: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).

Wenn man immer einfach die erste Bewerberin einstellt, bekommt man die beste nur in den Fällen (3,1,2) und (3,2,1). Die Wahrscheinlichkeit beträgt also 2/6 = 1/3.

Besser ist folgende Strategie: Die erste Bewerberin wird abgelehnt. Ist die zweite Bewerberin besser als die erste, wird sie eingestellt; sonst wird die dritte genommen. Damit erhält man die beste Bewerberin in den Fällen (1,3,2), (2,3,1) und (2,1,3). Das sind 3 von 6 Fällen, also eine Wahrscheinlichkeit von 3/6 = 1/2. Das Beispiel zeigt, warum es sinnvoll sein kann, anfangs Informationen zu sammeln, statt sofort zu wählen.

Optimale Strategie bei bekannter Bewerberzahl

Für n Bewerber funktioniert die optimale Grundstrategie so: Zuerst betrachtet man r der n Bewerber, wobei 1 ≤ r < n gilt, und lehnt sie alle ab. Diese ersten r Bewerber bilden das Explorationsset. Es dient dazu, das allgemeine Qualifikationsniveau kennenzulernen.

Danach wählt man unter den übrigen n − r Bewerbern den ersten aus, der besser ist als alle Bewerber aus dem Explorationsset. Für große n ist der optimale Wert ungefähr r ≈ n/e. Die Erfolgswahrscheinlichkeit, den besten Kandidaten zu wählen, liegt dann bei 1/e, also etwa 37 %.

Das bedeutet zugleich: In etwa 63 % der Fälle findet man nicht den besten Bewerber. Das geschieht zum Beispiel, wenn der beste Bewerber bereits im Explorationsset war. Dann wurde er schon abgelehnt. Es kann auch passieren, dass der beste Bewerber zwar später kommt, aber vorher bereits jemand akzeptiert wurde, der besser war als alle aus dem Explorationsset. Wenn die Bewerber zufällig in absteigender Qualität kommen, führt die Strategie sogar dazu, dass am Ende der schlechteste Bewerber genommen werden muss. Wenn die ersten 37 % zufällig die schlechtesten sind, wird der nächstbeste Bewerber akzeptiert, nicht unbedingt der beste.

Wahrscheinlichkeit und Begründung

Die Erfolgswahrscheinlichkeit lässt sich berechnen, indem man betrachtet, an welcher Position der beste Bewerber steht. Er kann nur ausgewählt werden, wenn er nicht unter den ersten r Probekandidaten ist. Steht er direkt an Position r + 1, gewinnt er sicher, weil nach dem Explorationsset noch niemand akzeptiert wurde. Die Wahrscheinlichkeit für diese Position beträgt 1/n.

Steht der beste Bewerber an Position r + 2, gewinnt er nur dann, wenn der beste der vorherigen Kandidaten unter den ersten r Probekandidaten war. Diese Wahrscheinlichkeit beträgt r/(r+1). Entsprechend geht man für alle späteren Positionen weiter. Insgesamt ergibt sich für die Erfolgswahrscheinlichkeit P der Strategie:

P = Σ von a = r+1 bis n aus (1/n) · (r/(a−1)) = (r/n) · Σ von a = r bis n−1 aus 1/a.

Für große n kann diese Summe durch ein Integral angenähert werden:

P ≈ (r/n) · ∫ von r bis n (1/a) da = −(r/n) · ln(r/n).

Dieser Ausdruck wird maximal bei r = n/e. Der maximale Wert beträgt 1/e ≈ 0,368. Das Maximum ist nicht sehr scharf: Für n/4 ≤ r ≤ n/2 unterschreitet die Näherung den Wert ln(2)/2 ≈ 0,346 nicht. Eine genauere Analyse mit der Odds-Strategie zeigt außerdem, dass die Erfolgswahrscheinlichkeit immer strikt größer als 1/e ≈ 0,368 ist und sich diesem Wert erst asymptotisch annähert, wenn die Zahl der Bewerber gegen unendlich geht.

Bezieht man auch den zweitbesten Kandidaten in die Betrachtung ein, nähert sich die Wahrscheinlichkeit, dass dieser ausgewählt wird, für große n dem Wert 1/e². Insgesamt wird die Wahrscheinlichkeit, mit dieser Strategie den besten oder zweitbesten Kandidaten zu erhalten, für große n etwas größer als 50 %.

Varianten und andere Ziele

Eine wichtige Variante behandelt den Fall, dass die Anzahl N der Optionen oder Kandidaten vorher unbekannt ist. Im klassischen Modell ist N bekannt; das ist für Anwendungen oft ein Nachteil. Man kann zwar annehmen, dass eine Verteilung P(N = k) bekannt ist, doch dann ist die optimale Lösung im Allgemeinen schwieriger zu bestimmen. Außerdem kann die optimale Gewinnwahrscheinlichkeit deutlich kleiner werden und in einigen Fällen praktisch null sein.

Das sogenannte 1/e-Gesetz der besten Wahl gehört zu einem erweiterten Modell mit unbekannter Kandidatenzahl und darf nicht mit der einfachen 1/e-Regel des klassischen Problems verwechselt werden. Im verallgemeinerten Ansatz in stetiger Zeit kommt ein Kandidat in einem Zeitintervall [0,T] aus einer unbekannten Anzahl N von Kandidaten. Alle Ränge haben unabhängig voneinander dieselbe Ankunftszeitdichte f auf [0,T]. Die zugehörige Verteilung ist F(t) = ∫ von 0 bis t f(s) ds für 0 ≤ t ≤ T.

Das 1/e-Gesetz besagt: Sei τ die Lösung der Gleichung F(τ) = 1/e. Die Strategie S wartet alle Kandidaten bis zur Zeit τ ab und wählt danach, wenn möglich, den ersten Kandidaten, der besser ist als alle Vorgänger vor τ. Wenn es mindestens einen Kandidaten gibt, erzielt S für alle N eine Gewinnwahrscheinlichkeit von mindestens 1/e. S ist die einzige Strategie, die diese untere Schranke erreichen kann; die Schranke ist scharf. Außerdem wählt S mit Wahrscheinlichkeit 1/e keinen Kandidaten.

Ein anderes Ziel ist nicht, die Chance auf den allerbesten Kandidaten zu maximieren, sondern im Mittel eine möglichst gute Platzierung zu erreichen. Dann ist eine andere Strategie nötig: Zunächst wird wieder eine bestimmte Anzahl von Kandidaten abgelehnt. Danach wird der erste Kandidat akzeptiert, der unter den bisher betrachteten Kandidaten mindestens eine bestimmte Platzierung erreicht. Tabellen im Artikel geben für kleine Kandidatenzahlen die passende Strategie sowie die mittlere Platzierung und die mittlere Anzahl der Einladungen an.