WikiDer > Sekretärsproblem

Deutsche Fotothek, 1951

Es Sekretärin Problem ist ein bekanntes Problem aus der Theorie des optimalen Stoppens. Es wurde ausführlich in der Wahrscheinlichkeit, das Statistik und der Entscheidungstheorie.

Das Sekretariatsproblem besteht darin, zu entscheiden, ob Bewerber für die Stelle von Sekretär zu einem Vorstellungsgespräch eingeladen werden. Nach jedem Vorstellungsgespräch wird sofort entschieden, ob der Bewerber für die Stelle angenommen wird, danach werden die verbleibenden Bewerber nicht mehr berücksichtigt.

Das Sekretariatsproblem gilt für Situationen, in denen eine Auswahl aus einer unsortierten Reihe getroffen werden muss und auf eine vorherige Ablehnung nicht zurückgegriffen werden kann. Die Frage ist dann, wann der beste Zeitpunkt zum Aufhören ist und wie hoch die Chance ist, dass der beste Kandidat ausgewählt wird.

Das Sekretariatsproblem ist auch bekannt als das Eheproblem^[1], die Mitgift des Sultans, und der größte Kuchen.^[2][3] Es hängt mit dem zusammen Problem von Cayley (1875) und Google-Spiel (Spiel von Googol für zwei Spieler).

Martin Gärtner diskutierte das Sekretärsproblem in seiner Kolumne im Februar 1960 Mathematische Erholungen im Magazin Wissenschaftlicher Amerikaner.^[4]

Formulierung

Die Formulierung des Sekretärsproblems lautet:

1. Es gibt eine Stelle für a Sekretär.
2. Die Anzahl der Bewerber${displaystyle n}$ ist bekannt.
3. Die Bewerber werden in zufälliger Reihenfolge interviewt.
4. Die Bewertung der Bewerber ist eindeutig (keine gleichwertigen Bewertungen). Die Ablehnung oder Annahme eines Bewerbers basiert ausschließlich auf den bisherigen Bewertungen. Nach einem Vorstellungsgespräch muss der Bewerber sofort abgelehnt oder angenommen werden.
5. Ein abgelehnter Bewerber kann nicht erneut aufgerufen werden.
6. Wir streben nach dem besten Ergebnis (der optimalen Strategie).

Lösung

Der beste Ansatz scheint zu sein, ${displaystyle k}$ Bewerber interviewen und ablehnen - eine Art Markt-Scout - und dann den nächsten Bewerber auswählen, der besser ist als alle vorherigen. Kommt kein besserer, wird letzterer gewählt. Was ist der günstigste Wert von ${displaystyle k}$? Und wie groß ist die Chance, den besten Kandidaten zu finden? Berechnung lehrt:

1. Für viele Bewerber ${displaystyle n}$ gilt ${Anzeigestil k=n/eapprox 0{,}368,n}$, von e die Basis der natürlicher Logarithmus.
2. Die Chance, dass auf diese Weise der beste Kandidat gefunden wird, nähert sich bei großen Zahlen an ${Displaystil 1/eca. 0{,}368}$.

Deshalb sprechen wir von der 1/e-Regel, die für eine allgemeine Klasse solcher Probleme gilt (Bruss, 1984).

Beweis

Es kann bewiesen werden, dass die optimale Strategie eine Stoppregel der oben genannten Form ist. D.h. die ersten k Kandidaten werden abgelehnt und der nächste, der besser als alle vorherigen ist, wird ausgewählt; wenn keine vorhanden ist, wird letzteres gewählt.

Was ist die Chance? ${Anzeigestil p(km)}$ dass die beste Kandidatennummer ${Anzeigestil km}$ ist und wird gewählt? Die Wahrscheinlichkeit, dass ein zufälliger Kandidat der Beste ist, ist ${Anzeigestil 1/n}$. Als Kandidat ${Anzeigestil km}$ ist der Beste und wird auch ausgewählt, das bedeutet, dass die Kandidaten ${displaystyle k 1,ldots,k m-1}$ wurden nicht ausgewählt, also die erste ${displaystyle k}$ Kandidaten waren besser als dieser ${Anzeigestil m-1}$. So:

${displaystyle P({ ext{nr. }}k 1,ldots ,k m-1{ ext{ sind kleiner als nrs. }}1,ldots ,k|{ ext{nr. }}km{ ext{ ist der beste }})={frac {k}{k m-1}}}$

und

${displaystyle p(km)={frac {k}{k m-1}}{frac {1}{n}}}$

Chance ${displaystyle p_{n}(k)}$ dass der beste Kandidat mit dieser Strategie ausgewählt wird:

${displaystyle p_{n}(k)=sum _{m=1}^{nk}p(km)=sum _{m=1}^{nk}{frac {k}{k m-1}}{ frac {1}{n}}={frac {k}{n}}links({frac {1}{k}} {frac {1}{k 1}} {frac {1}{k 2}} . .. {frac {1}{n-1}}Nacht)}$

Große Anzahl von

für große ${displaystyle n}$ kann die Teilsumme der harmonische Reihe angesprochen werden (siehe Euler-Mascheroni-Konstante):

${displaystyle sum _{i=1}^{n}{frac {1}{i}}=1 {frac {1}{2}} {frac {1}{3}} ldots {frac {1}{n }}ungefähr ln(n) Gamma {frac {1}{2n}} {frac {1}{12n^{2}}}}$

Also für groß ${displaystyle n}$ und ${displaystyle k}$, von ${Anzeigestil x=lim(k/n)}$:

${displaystyle p_{n}(k)={frac {k}{n}}left(sum _{i=1}^{n-1}{frac {1}{i}}-sum _{j=1 }^{k-1}{frac {1}{j}}ight)ca. {frac {k}{n}}ln {left({frac {n-1}{k-1}}ight)}ca. - x,ln(x)}$

Optimum

Das Maximum von ${displaystyle p_{n}(k)}$ ist vorher erreicht ${displaystyle x=x_{max}}$ wofür:

${displaystyle {frac {m {d}}{{m {d}}x}}links(-x,ln(x)ight)=-ln(x)-x{frac {1}{x}}=- ln(x)-1=0}$

So:

${displaystyle ln(x_{max})=-1,quad x_{max}={frac {k}{n}}={frac {1}{e}}ungefähr 0,368}$

und die maximale Chance auf den besten Kandidaten mit dieser Strategie ist:

${displaystyle p_{max}=-{frac {1}{e}},ln left({frac {1}{e}}ight)={frac {1}{e}}ca. 0,368}$

Die zweite Ableitung ${displaystyle -{frac {1}{x}}}$ ist für ${displaystyle x=x_{max}}$ gleicht ${displaystyle -{frac {1}{x_{max}}}=-e}$, also kleiner als 0, so dass im stationären Punkt tatsächlich ist ein Maximum erreicht.

Beispiel für große Zahlen

Im Sekretariatsproblem ist es bei 100 Bewerbern am besten, die ersten 100 / e = 100 / 2,72 = 36,8 also 37 nach dem Vorstellungsgespräch abzulehnen und den nächsten Bewerber einzustellen, der besser ist als jeder der vorherigen. Die Chance, auf diese Weise die beste Sekretärin zu bekommen, ist nicht größer als etwa 37%.

Beispiele für kleine Zahlen

Wie funktioniert die Berechnung in der Praxis für eine begrenzte Anzahl von n Kandidaten raus?

n = 2

Mit nur zwei Kandidaten ist es einfach. Die Wahrscheinlichkeit, dass der beste Kandidat Nummer 1 ist, ist gleich der Wahrscheinlichkeit, dass es Nummer 2 ist, also 1/2. Also entweder nimmt man den ersten Kandidaten direkt, oder man lässt den ersten vorbeiziehen und wählt dann (notwendigerweise) den zweiten.

${displaystyle p_{2}(0)=P(K=1)={ frac {1}{2}}}$

${displaystyle p_{2}(1)=P(K=2)={ frac {1}{2}}}$

n = 3

Für drei Kandidaten gilt:

Wählen Sie direkt den ersten Kandidaten:

${displaystyle p_{3}(0)={ frac {1}{3}}}$

Um den ersten Kandidaten zu bestehen:

${displaystyle p_{3}(1)={ frac {1}{3}}({ frac {1}{1}} { frac {1}{2}})={ frac {1}{2}}}$

Loslassen der ersten beiden Kandidaten:

${displaystyle p_{3}(2)={ frac {2}{3}}{ frac {1}{2}}={ frac {1}{3}}}$

Wenn Sie also den ersten Kandidaten ablehnen und dann den nächst besseren Kandidaten wählen, haben Sie die größte Chance (1/2) für den besten Kandidaten.

n = 4

Bei vier Kandidaten sind die Chancen:

Wählen Sie direkt den ersten Kandidaten aus

${displaystyle p_{4}(0)={ frac {1}{4}}}$

Um den ersten Kandidaten zu bestehen:

${displaystyle p_{4}(1)={ frac {1}{4}}({ frac {1}{1}} { frac {1}{2}} { frac {1}{3}})={ frac {11}{24}}ungefähr 0{,}458}$

Loslassen der ersten beiden Kandidaten:

${displaystyle p_{4}(2)={ frac {2}{4}}({ frac {1}{2}} { frac {1}{3}})={ frac {5}{12}}ungefähr 0{,}417}$

Lassen Sie die ersten drei Kandidaten passieren:

${displaystyle p_{4}(3)={ frac {3}{4}}{ frac {1}{3}}={ frac {1}{4}}}$

Auch hier besteht die optimale Strategie darin, den ersten Kandidaten abzulehnen und dann den nächst besseren zu nehmen.

n = 10

Bei zehn Kandidaten stehen die Chancen:

${displaystyle p_{10}(0)={ frac {1}{10}}}$

${displaystyle p_{10}(1)={ frac {1}{10}}({ frac {1}{1}} { frac {1}{2}} { frac {1}{3}} { frac { 1}{4}} { frac {1}{5}} { frac {1}{6}} { frac {1}{7}} { frac {1}{8}} { frac {1}{9} })ungefähr 0{,}283}$

${displaystyle p_{10}(2)={ frac {2}{10}}({ frac {1}{2}} { frac {1}{3}} { frac {1}{4}} { frac { 1}{5}} { frac {1}{6}} { frac {1}{7}} { frac {1}{8}} { frac {1}{9}})ungefähr 0{,}366}$

${displaystyle p_{10}(3)={ frac {3}{10}}({ frac {1}{3}} { frac {1}{4}} { frac {1}{5}} { frac { 1}{6}} { frac {1}{7}} { frac {1}{8}} { frac {1}{9}})ungefähr 0{,}399}$

${displaystyle p_{10}(4)={ frac {4}{10}}({ frac {1}{4}} { frac {1}{5}} { frac {1}{6}} { frac { 1}{7}} { frac {1}{8}} { frac {1}{9}})ungefähr 0{,}398}$

und so weiter.

Tisch:

k	0	1	2	3	4	5	6	7	8	9
k/n	0	0,1	0,2	0,3	0,4	0,5	0,6	0,7	0,8	0,9
Pn(k)	0,1	0,283	0,366	0,399	0,398	0,373	0,327	0,265	0,189	0,100

Für k = 3 (k/n = 0,3) finden wir die größte Wahrscheinlichkeit (0,399), so dass die Ablehnung der ersten drei Kandidaten und die Auswahl des nächst besseren Kandidaten das beste Ergebnis liefert.

Überblick

Die folgende Tabelle zeigt die Fälle mit relativ wenigen Kandidaten.

Nach dem Beweis ist für große k und n sowohl das Verhältnis k_max/n als optimale Wahrscheinlichkeit angenähert durch 1/e ~ 0,368.

Geschichte

Flut und Gardner

Soweit wir wissen, wurde das Sekretärsproblem erstmals 1949 von dem amerikanischen Mathematiker Merrill M. Flood gestellt, der für seine Gefangenendilemma: er hat es damals in einem Vortrag erwähnt das Problem der Verlobten (das verlobte problem). In den 1950er Jahren wurde es in mathematischen Kreisen zu einem bekannten Problem. 1958 verbreitete Flood einen Brief an Freunde mit vorläufigen Beweisen für die optimale Strategie: "den ersten p bedingungslos ablehnen, dann den nächsten Kandidaten nehmen" (also den nächsten, der besser ist, Flood 1958).

Die erste Veröffentlichung scheint von . zu sein Martin Gärtner in der sein Wissenschaftlicher Amerikaner vom Februar 1960. Er hatte von John H. Fox, Jr. und L. Gerald Marnie über das Problem. 1958 hatten sie sich ein ähnliches Problem ausgedacht, dass sie Google-Spiel (Spiel von googol), kannte aber nicht die optimale Lösung. Gardner bat um Hilfe und Leo Moser mit J. R. Pounder lieferte eine angemessene Analyse für Scientific American. Die 1/e-Regel oder -Gesetz geht auf F. Thomas Bruss (1984) zurück. Ferguson (1989) gibt eine ausführliche Bibliographie und erwähnt ähnliche Probleme von Arthur Cayley (1875) und Johannes Kepler.

Google-Spiel

Martin Gardner hat das Sekretärsproblem 1960 in Form von Google-Spiel für zwei Spieler, die wie folgt abläuft:

Spieler 1 darf so viele (n) Karten wie gewünscht und muss auf jede Karte eine andere positive Zahl schreiben. Die Zahlen können von einem kleinen positiven Bruch bis zu mehr als eins reichen googol (eine 1 mit hundert Nullen). Spieler 2 sieht nicht, welche Zahlen aufgeschrieben sind. Die Karten werden gemischt und verdeckt auf den Tisch gelegt. Spieler 2 dreht die Karten nacheinander um. Die Absicht ist, dass es aufhört, wenn er oder sie glaubt, die größte Zahl gefunden zu haben: Wenn dies richtig ist, hat Spieler 2 gewonnen. Man kann nicht auf eine frühere Wahl zurückgreifen. Wenn alle Karten aufgedeckt sind, muss die letzte gewählt werden.

Vor dem ${Anzeigestil n>2}$ Gibt es eine Lösung (Gnedin 1994): Spieler 1 kann Zufallszahlen (abhängige Zufallsvariablen) so wählen, dass die beste Stoppstrategie von Spieler 2 die Methode der relativen Reihenfolge verwendet (relative Ränge) kann nicht übersteigen.

Varianten

Mehrere Varianten des Sekretärsproblems wurden untersucht, darunter:

• Anstelle eines Bewerbers können auch zwei Bewerber ausgewählt werden.
• Die Zahl der Bewerber ist unbekannt (Bruss 1984).
• Bewerber können eine gleichwertige Bewertung erhalten.
• Abgelehnte Bewerber können zurückgerufen werden.
• Die Wahl kann auch auf den zweitbesten Bewerber fallen.

Experimentelle Forschung

Psychologen und experimentelle Ökonomen untersuchte das Verhalten von Probanden, die das Sekretariatsproblem in der Praxis lösen mussten.^[5] Im Allgemeinen stellte sich heraus, dass die Suche zu früh eingestellt wurde, zum Teil wegen des Aufwands für die Bewertung der Kandidaten. Angewendet auf Alltagssituationen deutet dies darauf hin, dass Menschen zu schnell aufgeben, wenn sich Alternativen nacheinander ergeben. Muss beispielsweise ein Autofahrer tanken, kann eine überteuerte Tankstelle gewählt werden.

Literatur

• Bearden, J. N. (2006). Ein neues Sekretärsproblem mit rangbasierter Auswahl und Kardinalzahlen. Zeitschrift für Mathematische Psychologie 50: 58–9. DOI: 10.116/j.jmp.2005.11.003.
• Bearden, J. N., Murphy, R. O. Rapport, A. (2005). Eine multiattributive Erweiterung des Sekretärsproblems: Theorie und Experimente. Zeitschrift für Mathematische Psychologie 49 (5): 410–425. DOI: 10.1016/j.jmp.2005.08.002.
• Bearden, J. N., Rapoport, A., Murphy R. O. (2006). Sequentielle Beobachtung und Selektion mit rangabhängigen Auszahlungen: Ein experimenteller Test. Managementwissenschaft 52 (9): 1437–49. DOI: 10.1287/mnsc.1060.0535.
• Bruss, F. Thomas (1984). Ein einheitlicher Ansatz für eine Klasse der besten Auswahlprobleme mit einer unbekannten Anzahl von Optionen. Annalen der Wahrscheinlichkeit 12 (3): 882–891. DOI: 10.1214/aop/1176993237.
• Bruss, F. Thomas (2000). Summiere die Quoten zu eins und höre auf. Annalen der Wahrscheinlichkeit 28 (3): 1384–91. DOI: 10.1214/aop/1019160340.
• Chow, Y.S., Moriguti, S., Robbins, H., & Samuels, S.M.: Optimale Auswahl aufgrund des relativen Rangs (das "Sekretärproblem"). Chow et al.: optimale Auswahl basierend auf dem relativen Rang
• Ferguson, T. S. (1989). Wer hat das Sekretariatsproblem gelöst?. Statistische Wissenschaft 4 (3): 282–296. DOI: 10.1214/ss/1177012493.Ferguson: Wer hat das Sekretärsproblem gelöst?
• Flut, Merrill R., Brief von 1958 (Kopie im Martin Gardner Papiere im Stanford University Archives, Serie 1, Box 5, Faltblatt 19.
• Freeman, P. R. (1983). Das Sekretärsproblem und seine Erweiterungen: Ein Rückblick. Internationale Statistische Überprüfung / Revue Internationale de Statistique 51 (2): 189–206. DOI: 10.2307/1402748.Freeman: Das Sekretärsproblem und seine Erweiterungen: Ein Rückblick
• Gärtner, Martin, Neue mathematische Ablenkungen von Scientific American, Simon und Schuster, 1966, Kapitel 3, Problem 3 [Nachdruck der ursprünglichen Kolumne vom Februar 1960 mit Kommentar].
• Gnedin, A. (1994). Eine Lösung für das Spiel von Google. Annalen der Wahrscheinlichkeit 22 (3): 1588–1595. DOI: 10.1214/aop/1176988613.
• Hill, T. P., "Wissen, wann man aufhören muss". Amerikanischer Wissenschaftler, Voll. 97, 126-133 (2009). (Eine französische Übersetzung war in Gießen Sie die Wissenschaft (Juli 2009) Savoir quand s'arrêter)
• Ketelaar, Timothy und Todd, Peter M., Framing Our Thoughts: Ökologische Rationalität als Antwort der Evolutionspsychologie auf das Rahmenproblem, , Kapitel 5 in Konzeptionelle Herausforderungen in der Evolutionspsychologie, P. 187., Harmon R. Holcomb III (Hrsg.), Kluwer Academic Publishers, Dordrecht, 2001, pdf
• Müller, Geoffrey F., Der Paarungsgeist: Wie sexuelle Entscheidungen die Evolution der menschlichen Natur geprägt haben. Ankerbücher (2001). ISBN 0-385-49517-X .
• Sardelis, D., Valahas, T. (März 1992). Entscheidungsfindung: Eine goldene Regel. Amerikanische mathematische Monatszeitschrift 99 (3): 935–942.
• Seale, D.A., Rapoport, A. (1997). Sequentielle Entscheidungsfindung mit relativen Rängen: Eine experimentelle Untersuchung des 'Sekretärproblems'. Organisatorisches Verhalten und menschliche Entscheidungsprozesse 69 (3): 221–236. DOI: 10.106/obhd.1997.2683.
• Soto, Jose: Probleme mit der Sekretärin, 21. Oktober 2010, SPAM Probleme mit der Sekretärin . Präsentation, bespricht Varianten.
• Stein, W. E., Seale, D. A. und Rapoport, A. (2003). Analyse heuristischer Lösungen für das Best-Choice-Problem. European Journal of Operational Research 151: 140–152. DOI: 10.1016/S0377-2217(02)00601-X.

Externe Links

Niederländisch sprechend

• Mathematicsgirls.nl Ionica Smeets: Echte Liebe
• Kennislink.nl Alex van den Brandhof: Der größte Kuchen
• Weetlogs.scilogs.be Rudi Penne und Paul Levrie: Ein Mathematiker hat die besten Chancen auf die besten Schnäppchen

Englisch

Wissenschaftliche Artikel und Buch

• (und) Ferguson: Wer hat das Sekretärsproblem gelöst?
• (und) Thomas S. Ferguson: Optimales Stoppen und Anwendungen (Buch)
• (und) Freeman: Das Sekretärsproblem und seine Erweiterungen: Ein Rückblick
• (und) Chow et al.: Optimale Auswahl basierend auf dem relativen Rang

Unterrichtsmaterialien und anderes

• (und) University of Alabama in Huntsville, Virtual Laboratories in Probability and Statistics: Sekretärsproblem
• (und) Online-Dienstprogramm zur Berechnung des optimalen r
• (und) MathWorld.wolfram.com Weisstein, Eric W.: Sultans Mitgiftproblem
• (und) Neil Beardens optimale Suchseite
• (und) MathPages: Optimieren Sie Ihre Frau
• (und) Ein praktisches Beispiel für die Theorie des Treffens von Entscheidungen und die Theorie des optimalen Stoppens.

Französisch

• (NS) Pourlascience.fr Savoir quand s 'arrêter