Hauptmenü öffnen

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 -Regel) bezeichnet. Sie wurde von Geoffrey Miller in seinem Buch The Mating Mind beschrieben. Sie besagt, dass man die ersten 37 Prozent (genauer:  Prozent) der Bewerber betrachtet und danach den ersten Bewerber akzeptiert, der besser als alle bisherigen (also das bisher gefundene Optimum) ist. Diese einfache -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.

Inhaltsverzeichnis

Versagen des VerfahrensBearbeiten

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 zufällig letzte Bewerber genommen. 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.

ProblemBearbeiten

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. Diese Problemeinkleidung ist realitätsnah, sofern es sich um keine Liebesheirat handeln soll. 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.

BeispielBearbeiten

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  , 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  .

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

StrategieBearbeiten

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

Betrachte die ersten   der   Kandidaten (mit  ) – und lehne sie ab.

Wähle von den verbleibenden   Bewerbern den ersten, der besser ist als jeder der ersten  .

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

BeweisBearbeiten

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

Für die Beweisführung sind nur zwei Bewerber von Interesse, der beste Bewerber – wir nehmen an, es sei der  -te – sowie der zweitbeste von den ersten   Bewerbern.

Wenn  , dann ist der beste Bewerber auch unter den pauschal abgewiesenen, womit die Strategie gescheitert ist.

Wenn der zweitbeste von den ersten   nicht zu den pauschal abgewiesenen ersten   gehört, geht er dem  -ten voran, ist zugleich besser als jeder der   ersten und wird also genommen (oder möglicherweise sogar ein anderer Bewerber vor ihm). Wieder scheitert die Strategie.

Es bleibt also der Fall, dass der zweitbeste unter den ersten   Bewerbern schon unter den ersten   Bewerbern ist, dafür ist die Wahrscheinlichkeit  ; dann (und nur dann) wird wirklich der  -te Bewerber genommen.

Der beste Bewerber liegt mit gleicher Wahrscheinlichkeit an jeder Stelle   in der Reihenfolge 1, 2, …  . Wenn man dies berücksichtigt, ergibt sich die Wahrscheinlichkeit   für einen Erfolg der Strategie zu:

 

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

 

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

Verallgemeinerungen und VariantenBearbeiten

Unbekannte Anzahl N von OptionenBearbeiten

Der Hauptnachteil des klassischen Sekretärinnenproblems für mögliche Anwendungen ist die Tatsache, dass die Anzahl   der Optionen (Kandidaten) als im Voraus bekannt vorausgesetzt wird. Eine Möglichkeit dies zu umgehen ist anzunehmen, dass die Verteilung   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 WahlBearbeiten

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   aus einer unbekannten Anzahl von Kandidaten   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   auf   haben. Sei   die entsprechende Ankunftszeitverteilung, d. h.

 ,  .

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

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

Wenn es zumindest einen Kandidaten gibt, dann gilt
(i) S erzielt für alle   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   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 ModellsBearbeiten

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 auchBearbeiten

LiteraturBearbeiten

  • 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.
  • Eric W. Weisstein: Sultan’s Dowry Problem. In: MathWorld. Wolfram, 2004 (mathworld.wolfram.com [abgerufen am 24. Februar 2007]).

WeblinksBearbeiten