Sekretärinnenproblem

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 nacheinander betrachteter Kandidaten unterschiedlicher Qualität 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 optimale Lösung des Problems wird als 37%-Regel (oder 1/e-Regel) bezeichnet und wurde von Geoffrey Miller in seinem Buch „The mating mind“ beschrieben. Sie besagt, dass man die ersten 37 % (genauer: 1/e) Bewerber betrachtet und danach den ersten Kandidaten akzeptiert, der besser als alle bisherigen (also das bisher gefundene Optimum) ist. Dabei kann es passieren, dass die Regel versagt: Der beste Bewerber war vielleicht bereits unter den ersten 37 Prozent, somit wird der letzte Kandidat genommen. Auch ist die Regel nicht sehr erfolgreich, wenn die ersten 37 Prozent der Bewerber die schlechtesten waren, dann wird lediglich der Nächstbeste akzeptiert.

Problem[Bearbeiten]

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.

Strategie[Bearbeiten]

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[Bearbeiten]

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

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

Wenn der zweitbeste von den ersten a nicht zu den pauschal abgewiesenen ersten r gehört, geht er dem a-ten voran, ist zugleich besser als jeder der r 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 a Bewerbern schon unter den ersten r Bewerbern ist, dafür ist die Wahrscheinlichkeit \tfrac{r}{a-1}; dann (und nur dann) wird wirklich der a-te Bewerber genommen.

Der beste Bewerber liegt mit gleicher Wahrscheinlichkeit an jeder Stelle a in der Reihenfolge 1, 2, … n. Wenn man dies berücksichtigt, 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}

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

P \approx \frac{1}{n}\int_r^n \frac{r}{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 n4 \leq r \leq \tfrac n2 wird nämlich durchweg \tfrac{\ln2}{2}  \approx 0{,}346 nie unterschritten.

Anwendbarkeit in der Praxis[Bearbeiten]

Die praktische Anwendbarkeit des Problemes dürfte in diesem Modell (klassisches Sekretärinnenproblem) sehr eingeschränkt sein. (Zum Vergleich siehe unten das alternative Modell, auf dem das „1/e-Gesetz der besten Wahl“ beruht.) Problematisch ist zunächst, dass, um die optimale „Stoppzahl“ bestimmen zu können, von Anfang an bekannt sein muss, wie groß n ist. Dies mag noch möglich sein, wenn eine feststehende Zahl von Bewerbungsgesprächen vereinbart ist; in der Einkleidung des „Heiratsproblemes“ ist diese Prognose jedoch schwierig.

Weiterhin setzt das „Sekretärinnenproblem“ voraus, dass die Qualität der Kandidaten zufällig und unabhängig von der Platzziffer ist. Auch diese Voraussetzung mag im Bewerbungsfall unter Umständen gegeben sein. Ein Gegenbeispiel ist jedoch das „Heiratsproblem“, wie man exemplarisch unter Zugrundelegung traditioneller Rollenbilder zeigen kann: Mit zunehmendem Alter der Frau wird die Qualität der potentiell interessierten Partner tendenziell sinken, dagegen wird bei zunehmendem Wohlstand des Mannes oder einer Verbesserung seiner gesellschaftlichen Position die Qualität seiner potentiell interessierten Partnerinnen möglicherweise steigen. In diesem Setting ist der Frau zu einer gewichteten Verringerung der „Stoppzahl“ zu raten, dem Mann eher zu einer Erhöhung der „Stoppzahl“. Ein weiteres Problem ist zudem, dass aufgrund der hinausgezögerten Entscheidungsphase eine längere Zeit ohne Problemlösung überwunden werden muss, was zu Wohlfahrtsverlusten führen kann.

Eine weitere Schwierigkeit ist, dass die Lösung des Sekretärinnenproblems daraufhin optimiert ist, die beste Lösung zu wählen, wofür eine vergleichsweise hohe Wahrscheinlichkeit in Kauf genommen wird, dass schließlich die platzziffermäßig letzte, möglicherweise deutlich schlechtere Lösung gewählt wird. In der Praxis, in der eine derartige Optimierung hin zur besten Lösung oftmals unnötig ist, dürfte eine risikomeidende Strategie (z.B. Minimax-Regel) oftmals günstiger sein. Wenn also bereits vor Erreichen der Stoppzahl eine Lösung als guter Kompromiss oder sogar als objektiv gut erscheint, dann sollte diese Lösung – abweichend von der Strategie – sofort gewählt werden (satisficing).

Unbekannte Anzahl N von Optionen[Bearbeiten]

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[Bearbeiten]

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 ds , \, 0\le t\le T.

Das 1/e-Gesetz besagt dann: Seit \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 die folgenden 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, 1984 entdeckt, 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 andererseits einem wesentlich anwendungsfreundlicheren Modell entspringt.

Weitere Varianten des klassischen Modells[Bearbeiten]

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[Bearbeiten]

Literatur[Bearbeiten]

  •  Franz Thomas Bruss: Strategien der besten Wahl. In: Spektrum der Wissenschaft. Nr. 05, 2004, S. 102–104 (PDF).
  •  Eugene Dynkin: Optimal choice of the stopping time of a Markov process. In: Sov. Math. Dokl.. Nr. 02, 1963, S. 238-240.
  •  Eric W. Weisstein: Sultan’s Dowry Problem. In: MathWorld. Wolfram, 2004 (HTML, abgerufen am 24. Februar 2007).
  •  Franz Thomas Bruss: A unified approach to a class of best choice problems with an unknown number of options. In: Annals of Probability. Wolfram, 1984.
  •  Stephen M. Samuels: In: Math. Reviews 85:m. 1985.

Weblinks[Bearbeiten]

Einzelnachweis[Bearbeiten]