Secretaresseprobleem

Het secretaresseprobleem is een beroemd vraagstuk uit de theorie van optimaal stoppen. Het is uitvoerig geanalyseerd in de kansrekening, de statistiek en de beslissingstheorie.

Het secretaresseprobleem is hoe te beslissen als sollicitanten voor de vacature van secretaresse worden opgeroepen voor een gesprek. Na elk sollicitatiegesprek wordt direct beslist of de sollicitant voor de vacature zal worden aangenomen, waarna de resterende sollicitanten niet meer in aanmerking worden genomen.

Het secretaresseprobleem is van toepassing op situaties waarin een keuze gemaakt moet worden uit een ongesorteerde reeks en men niet mag terugkomen op een eerdere afwijzing. De vraag is dan wanneer men het beste kan stoppen en hoe groot de kans is dat men zo de beste kandidaat kiest.

Het secretaresseprobleem staat ook bekend als het huwelijksprobleem^[1], de bruidsschat van de sultan, en de grootste taart.^[2]^[3] Het is verwant aan het probleem van Cayley (1875) en Googols spel (Game of Googol voor twee spelers).

Martin Gardner besprak het secretaresseprobleem in februari 1960 in zijn rubriek Mathematical Recreations in het tijdschrift Scientific American.^[4]

Formulering

De formulering van het secretaresseprobleem luidt

Er is een vacature voor een secretaresse.
Het aantal sollicitanten $n$ is bekend.
De sollicitanten krijgen in een willekeurige volgorde een sollicitatiegesprek.
De beoordeling van de sollicitanten is ondubbelzinnig (geen gelijke beoordelingen). Afwijzing of aanvaarding van een sollicitant berust uitsluitend op de beoordelingen tot dusver. Na een gesprek moet de sollicitant meteen afgewezen of aangenomen worden.
Een afgewezen sollicitant kan niet opnieuw worden opgeroepen.
Er wordt naar het beste resultaat (de optimale strategie) gestreefd.

Oplossing

De beste aanpak blijkt om een aantal van $k$ sollicitanten te spreken en af te wijzen - een soort marktverkenning - en dan de eerstvolgende sollicitant te nemen die beter is dan alle voorgaande. Als er geen betere langskomt, wordt de laatste gekozen. Wat is de gunstigste waarde van $k$ ? En hoe groot is de kans de beste kandidaat te vinden? Berekening leert:

Voor grote aantallen sollicitanten $n$ geldt $k=n/e\approx 0{,}368\,n$ , met e het grondtal van de natuurlijke logaritme.
De kans dat zo de beste kandidaat gevonden wordt, nadert voor grote aantallen tot $1/e\approx 0{,}368$ .

Men spreekt daarom van de 1/e-regel, die geldt voor een algemene klasse van dergelijke problemen (Bruss, 1984).

Bewijs

Het kan bewezen worden dat de optimale strategie een stopregel is van de bovengenoemde vorm. D.w.z. de eerste k kandidaten worden afgewezen en de eerstvolgende die beter is dan alle voorgaande wordt gekozen; als die er niet is wordt de laatste gekozen.

Wat is de kans $p(k+m)$ dat de beste kandidaat nummer $k+m$ is en gekozen wordt? De kans dat een willekeurige kandidaat de beste is, is $1/n$ . Als kandidaat $k+m$ de beste is en ook gekozen wordt, houdt dat in dat de kandidaten $k+1,\ldots ,k+m-1$ niet gekozen zijn, dus de eerste $k$ kandidaten waren beter dan deze $m-1$ . Dus:

P({\text{nrs. }}k+1,\ldots ,k+m-1{\text{ zijn minder dan nrs. }}1,\ldots ,k|{\text{nr. }}k+m{\text{ is de beste}})={\frac {k}{k+m-1}}

en

p(k+m)={\frac {k}{k+m-1}}{\frac {1}{n}}

De kans $p_{n}(k)$ dat met deze strategie de beste kandidaat gekozen wordt is dus:

p_{n}(k)=\sum _{m=1}^{n-k}p(k+m)=\sum _{m=1}^{n-k}{\frac {k}{k+m-1}}{\frac {1}{n}}={\frac {k}{n}}\left({\frac {1}{k}}+{\frac {1}{k+1}}+{\frac {1}{k+2}}+...+{\frac {1}{n-1}}\right)

Grote aantallen

Voor grote $n$ kan de partiële som van de harmonische reeks benaderd worden door (zie Constante van Euler-Mascheroni):

\sum _{i=1}^{n}{\frac {1}{i}}=1+{\frac {1}{2}}+{\frac {1}{3}}+\ldots +{\frac {1}{n}}\approx \ln(n)+\gamma +{\frac {1}{2n}}+{\frac {1}{12n^{2}}}

Dus is voor grote $n$ en $k$ , met $x=\lim(k/n)$ :

p_{n}(k)={\frac {k}{n}}\left(\sum _{i=1}^{n-1}{\frac {1}{i}}-\sum _{j=1}^{k-1}{\frac {1}{j}}\right)\approx {\frac {k}{n}}\ln {\left({\frac {n-1}{k-1}}\right)}\approx -x\,\ln(x)

Optimum

Het maximum van $p_{n}(k)$ wordt bereikt voor $x=x_{max}$ waarvoor:

{\frac {\rm {d}}{{\rm {d}}x}}\left(-x\,\ln(x)\right)=-\ln(x)-x{\frac {1}{x}}=-\ln(x)-1=0

Dus:

\ln(x_{max})=-1,\quad x_{max}={\frac {k}{n}}={\frac {1}{e}}\approx 0,368

en de maximale kans op de beste kandidaat is bij deze strategie:

p_{max}=-{\frac {1}{e}}\,\ln \left({\frac {1}{e}}\right)={\frac {1}{e}}\approx 0,368

De tweede afgeleide $-{\frac {1}{x}}$ is voor $x=x_{max}$ gelijk aan $-{\frac {1}{x_{max}}}=-e$ , dus kleiner dan 0, zodat in het stationaire punt inderdaad een maximum wordt bereikt.

Voorbeeld voor grote aantallen

Als er in het secretaresseprobleem 100 sollicitanten zijn, kunnen we het best de eerste 100 / e = 100 / 2,72 = 36,8 dus 37 na het gesprek afwijzen, en de eerstvolgende sollicitant aannemen die beter is dan elk van de voorgaande. De kans dat we zo de beste secretaresse krijgen is niet groter dan ongeveer 37%.

Voorbeelden voor kleine aantallen

Hoe pakt de berekening in de praktijk voor een beperkt aantal van n kandidaten uit?

n = 2

Met maar twee kandidaten is het gemakkelijk. De kans dat de beste kandidaat nummer 1 is, is gelijk aan de kans dat het nummer 2 is, namelijk 1/2. Dus of men neemt direct de eerste kandidaat, of men laat de eerste voorbijgaan en kiest dan (noodgedwongen) de tweede.

p_{2}(0)=P(K=1)={\tfrac {1}{2}}

p_{2}(1)=P(K=2)={\tfrac {1}{2}}

n = 3

Bij drie kandidaten geldt:

Direct de eerste kandidaat kiezen:

p_{3}(0)={\tfrac {1}{3}}

De eerste kandidaat voorbij laten gaan:

p_{3}(1)={\tfrac {1}{3}}({\tfrac {1}{1}}+{\tfrac {1}{2}})={\tfrac {1}{2}}

De eerste twee kandidaten voorbij laten gaan:

p_{3}(2)={\tfrac {2}{3}}{\tfrac {1}{2}}={\tfrac {1}{3}}

Dus de eerste kandidaat afwijzen en dan de eerstvolgende betere nemen geeft de grootste kans (1/2) op de beste kandidaat.

n = 4

Met vier kandidaten worden de kansen:

Direct de eerste kandidaat kiezen

p_{4}(0)={\tfrac {1}{4}}

De eerste kandidaat voorbij laten gaan:

p_{4}(1)={\tfrac {1}{4}}({\tfrac {1}{1}}+{\tfrac {1}{2}}+{\tfrac {1}{3}})={\tfrac {11}{24}}\approx 0{,}458

De eerste twee kandidaten voorbij laten gaan:

p_{4}(2)={\tfrac {2}{4}}({\tfrac {1}{2}}+{\tfrac {1}{3}})={\tfrac {5}{12}}\approx 0{,}417

De eerste drie kandidaten voorbij laten gaan:

p_{4}(3)={\tfrac {3}{4}}{\tfrac {1}{3}}={\tfrac {1}{4}}

Weer is de optimale strategie: de eerste kandidaat afwijzen en dan de eerstvolgende betere nemen.

n = 10

Bij tien kandidaten zijn de kansen:

p_{10}(0)={\tfrac {1}{10}}

p_{10}(1)={\tfrac {1}{10}}({\tfrac {1}{1}}+{\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{4}}+{\tfrac {1}{5}}+{\tfrac {1}{6}}+{\tfrac {1}{7}}+{\tfrac {1}{8}}+{\tfrac {1}{9}})\approx 0{,}283

p_{10}(2)={\tfrac {2}{10}}({\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{4}}+{\tfrac {1}{5}}+{\tfrac {1}{6}}+{\tfrac {1}{7}}+{\tfrac {1}{8}}+{\tfrac {1}{9}})\approx 0{,}366

p_{10}(3)={\tfrac {3}{10}}({\tfrac {1}{3}}+{\tfrac {1}{4}}+{\tfrac {1}{5}}+{\tfrac {1}{6}}+{\tfrac {1}{7}}+{\tfrac {1}{8}}+{\tfrac {1}{9}})\approx 0{,}399

p_{10}(4)={\tfrac {4}{10}}({\tfrac {1}{4}}+{\tfrac {1}{5}}+{\tfrac {1}{6}}+{\tfrac {1}{7}}+{\tfrac {1}{8}}+{\tfrac {1}{9}})\approx 0{,}398

enzovoort.

Tabel:

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
p_n(k)	0,1	0,283	0,366	0,399	0,398	0,373	0,327	0,265	0,189	0,100

Voor k = 3 (k/n = 0,3) vinden we de grootste kans (0,399) dus de eerste drie kandidaten afwijzen en de eerstvolgende betere nemen geeft het beste resultaat.

Overzicht

De volgende tabel toont de gevallen met betrekkelijk weinig kandidaten.

n	2	3	4	5	6	7	8	9	10	..	25	limiet n→∞
k_max	1	1	1	2	2	2	3	3	3	..	9	n/e
k_max/n	0,500	0,333	0,250	0,400	0,333	0,286	0,375	0,333	0,300	..	0,360	1/e ~ 0,368
Beste kans	0,500	0,500	0,458	0,433	0,428	0,414	0,410	0,406	0,399	..	0,381	1/e ~ 0,368

Volgens het bewijs wordt voor grote k en n zowel de verhouding k_max/n als de optimale kans benaderd door 1/e ~ 0,368.

Geschiedenis

Flood en Gardner

Voor zover bekend werd het secretaresseprobleem in 1949 voor het eerst gesteld door de Amerikaanse wiskundige Merrill M. Flood, bekend van het prisoner's dilemma: hij noemde het toen in een college het probleem van de verloofde (the fiancée problem). In de loop van de jaren 50 werd het een vermaard probleem in wiskundige kring. In 1958 stuurde Flood een brief aan vrienden rond met een voorlopig bewijs van de optimale strategie: "wijs de eerste p onvoorwaardelijk af, neem daarna de volgende kandidaat" (bedoeld is de volgende die beter is, Flood 1958).

De eerste publicatie schijnt van Martin Gardner te zijn in de Scientific American van februari 1960. Hij had van John H. Fox, Jr. en L. Gerald Marnie over het probleem gehoord. Zij hadden in 1958 een gelijkwaardig probleem bedacht, dat ze het Googolspel (game of Googol) noemden, maar kenden de optimale oplossing niet. Gardner vroeg om hulp en Leo Moser leverde met J. R. Pounder een juiste analyse voor Scientific American. De 1/e-regel of -wet is te danken aan F. Thomas Bruss (1984). Ferguson (1989) geeft een uitgebreide bibliografie en noemt soortgelijke problemen van Arthur Cayley (1875) en Johannes Kepler.

Googols spel

Martin Gardner goot het secretaresseprobleem in 1960 in de vorm van Googols spel voor twee spelers, dat als volgt verloopt:

Speler 1 mag zoveel (n) kaartjes gebruiken als gewenst, en moet op ieder kaartje een ander positief getal schrijven. De getallen mogen lopen van een kleine positieve breuk tot meer dan een googol (een 1 met honderd nullen). Speler 2 ziet niet welke getallen opgeschreven worden. De kaartjes worden geschud en met het getal naar beneden op tafel gelegd. Een voor een keert speler 2 de kaartjes om. De bedoeling is dat deze stopt als hij of zij denkt het grootste getal gevonden te hebben: is dit juist, dan heeft speler 2 gewonnen. Men mag niet terugkomen op een eerdere keuze. Als alle kaartjes worden omgedraaid, moet het laatste gekozen worden.

Voor $n>2$ is er een oplossing (Gnedin 1994): speler 1 kan op zo'n manier willekeurige getallen (afhankelijke random variabelen) kiezen dat de beste stopstrategie van speler 2 de methode van de relatieve volgorde (relative ranks) niet kan overtreffen.

Varianten

Verschillende varianten van het secretaresseprobleem zijn onderzocht, onder meer:

Er mogen twee sollicitanten gekozen worden in plaats van één enkele.
Het aantal sollicitanten is onbekend (Bruss 1984).
Sollicitanten mogen een gelijke beoordeling krijgen.
Afgewezen sollicitanten mogen worden teruggeroepen.
De keuze mag ook op de een na beste sollicitant vallen.

Experimenteel onderzoek

Psychologen en experimentele economen hebben het gedrag onderzocht van proefpersonen die het secretaresseprobleem in de praktijk moesten oplossen.^[5] In het algemeen bleek dat men te snel stopte met zoeken, deels vanwege de moeite die de beoordeling van kandidaten kost. Toegepast op dagelijkse situaties wijst dit erop dat men te snel opgeeft als alternatieven zich na elkaar voordoen. Bijvoorbeeld als een automobilist moet tanken, wordt mogelijk een te duur benzinestation gekozen.

Literatuur

Bearden, J.N. (2006). A new secretary problem with rank-based selection and cardinal payoffs. Journal of Mathematical Psychology 50: 58–9. DOI: 10.1016/j.jmp.2005.11.003.
Bearden, J.N., Murphy, R.O. Rapoport, A. (2005). A multi-attribute extension of the secretary problem: Theory and experiments. Journal of Mathematical Psychology 49 (5): 410–425. DOI: 10.1016/j.jmp.2005.08.002.
Bearden, J.N., Rapoport, A., Murphy R.O. (2006). Sequential observation and selection with rank-dependent payoffs: An experimental test. Management Science 52 (9): 1437–49. DOI: 10.1287/mnsc.1060.0535.
Bruss, F. Thomas (1984). A unified Approach to a Class of Best Choice problems with an Unknown Number of Options. Annals of Probability 12 (3): 882–891. DOI: 10.1214/aop/1176993237.
Bruss, F. Thomas (2000). Sum the odds to one and stop. Annals of Probability 28 (3): 1384–91. DOI: 10.1214/aop/1019160340.
Chow, Y.S., Moriguti, S., Robbins, H., & Samuels, S.M.: Optimal selection based on relative rank (the "secretary problem"). Chow et al.: optimal selection based on relative rank
Ferguson, T.S. (1989). Who solved the secretary problem?. Statistical science 4 (3): 282–296. DOI: 10.1214/ss/1177012493. Ferguson: Who solved the secretary problem?
Flood, Merrill R., Brief uit 1958 (kopie in de Martin Gardner papers aan de Stanford University Archives, series 1, box 5, folder 19.
Freeman, P.R. (1983). The secretary problem and its extensions: A review. International Statistical Review / Revue Internationale de Statistique 51 (2): 189–206. DOI: 10.2307/1402748. Freeman: The secretary problem and its extensions: A review
Gardner, Martin, New Mathematical Diversions from Scientific American, Simon and Schuster, 1966, Chapter 3, Problem 3 [herdruk van oorspronkelijke column van februari 1960 met commentaar].
Gnedin, A. (1994). A solution to the game of Googol. Annals of Probability 22 (3): 1588–1595. DOI: 10.1214/aop/1176988613.
Hill, T.P., "Knowing When to Stop". American Scientist, Vol. 97, 126-133 (2009). (Een Franse vertaling stond in Pour la Science (juli 2009) Savoir quand s' arrêter)
Ketelaar, Timothy en Todd, Peter M., Framing Our Thoughts: Ecological Rationality as Evolutionary Psychology's Answer to the Frame Problem, , Hoofdstuk 5 in Conceptual Challenges in Evolutionary Psychology, p. 187., Harmon R. Holcomb III (Ed.), Kluwer Academic Publishers, Dordrecht, 2001, pdf
Miller, Geoffrey F. (2001). The mating mind: how sexual choice shaped the evolution of human nature. Anchor Books. ISBN 0-385-49517-X.
Sardelis, D., Valahas, T. (March 1992). Decision Making: A Golden Rule. American Mathematical Monthly 99 (3): 935–942.
Seale, D.A., Rapoport, A. (1997). Sequential decision making with relative ranks: An experimental investigation of the 'secretary problem'. Organizational Behavior and Human Decision Processes 69 (3): 221–236. DOI: 10.1006/obhd.1997.2683.
Soto, José: Secretary problems, October 21 2010, SPAMS Secretary problems . Presentatie, bespreekt varianten.
Stein, W.E., Seale, D.A. en Rapoport, A.Stein, W.E., Seale, D.A., Rapoport, A. (2003). Analysis of heuristic solutions to the best choice problem. European Journal of Operational Research 151: 140–152. DOI: 10.1016/S0377-2217(02)00601-X.

Externe links

Nederlandstalig

Engelstalig

Wetenschappelijke artikelen en boek

Lesmateriaal en overig

Franstalig

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

Bronnen, noten en/of referenties

↑ Wiskundemeisjes.nl Ionica Smeets: Echte liefde (toepassing op partnerkeuze), 21 november 2009
↑ Kennislink.nl Alex van den Brandhof: De grootste taart
↑ Nwo.nl Nationale Wetenschapsquiz 2006 vraag 16
↑ Gardner, Martin, New Mathematical Diversions from Scientific American, Simon and Schuster, 1966, Chapter 3, Problem 3 [herdruk van oorspronkelijke column van februari 1960 met commentaar]
↑ Bearden, Murphy, and Rapoport, 2006; Bearden, Rapoport, and Murphy, 2006; Seale and Rapoport, 1997

[1] Wiskundemeisjes.nl Ionica Smeets: Echte liefde (toepassing op partnerkeuze), 21 november 2009

[grootste_taart-2] Kennislink.nl Alex van den Brandhof: De grootste taart

[3] Nwo.nl Nationale Wetenschapsquiz 2006 vraag 16

[4] Gardner, Martin, New Mathematical Diversions from Scientific American, Simon and Schuster, 1966, Chapter 3, Problem 3 [herdruk van oorspronkelijke column van februari 1960 met commentaar]

[5] Bearden, Murphy, and Rapoport, 2006; Bearden, Rapoport, and Murphy, 2006; Seale and Rapoport, 1997

[1]

[2]

[3]

[4]

[5]