Secretaresseprobleem

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Deutsche Fotothek, 1951

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 probleem 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] 

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 en dan 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.

Formulering[bewerken]

Als secretaresseprobleem luidt de formulering

  1. Er is een vacature voor een secretaresse.
  2. Het aantal sollicitanten n is bekend.
  3. De sollicitanten krijgen in een willekeurige volgorde een sollicitatiegesprek.
  4. 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.
  5. Een afgewezen sollicitant kan niet opnieuw worden opgeroepen.
  6. Er wordt naar het beste resultaat (de optimale strategie) gestreefd.

Oplossing[bewerken]

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 op een optimaal resultaat? Berekening leert:

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

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

Bewijs[bewerken]

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

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 1i=1+\frac 12+\frac 13 + \ldots + \frac 1n \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 1i - \sum_{j=1}^{k-1} \frac 1j\right)\approx \frac{k}{n} \ln{\left(\frac{n-1}{k-1}\right)}\approx -x\,\ln(x)

Optimum[bewerken]

Het maximum van p_{k,n} 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[bewerken]

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 die beter is aannemen. De kans dat we zo de beste secretaresse krijgen is niet groter dan ongeveer 37%.

Voorbeelden voor kleine aantallen[bewerken]

Hoe pakt de berekening in de praktijk voor een beperkt aantal kandidaten uit (dus k en n niet heel groot)?

n = 2[bewerken]

Met maar twee kandidaten is het makkelijk. We kunnen één kandidaat bekijken en daarna de eerst volgende beste kiezen of de laatste: dat is hier de onvermijdelijke kandidaat nummer 2. De kans moet 1/2 zijn. Klopt dat? We noteren het totaal aantal als index van de p: p_{totaal} (voor k=1) = p_2(k=1) = \frac{1}{2}( \frac{1}{1}) = \frac{1}{2}.

n = 3 en 4[bewerken]

Met drie kandidaten krijgen we

p_{totaal}(voor k=1) = p_3(k=1) = \frac{1}{3}( \frac{1}{1} + \frac{1}{2}) = \frac{1}{2}
p_{totaal}(voor k = 2) = p_3(k=2) = \frac{2}{3}( \frac{1}{2}) = \frac{1}{3}

Dus de eerste kandidaat (k = 1, k/n = 0,333) afwijzen en dan de eerste betere nemen geeft de grootste kans (1/2) op een optimaal resultaat. Met vier kandidaten worden de kansen

p_4(k=1) = \frac{1}{4}( \frac{1}{1} + \frac{1}{2} + \frac{1}{3}) = 0,458
p_4(k=2) = \frac{2}{4}( \frac{1}{2} + \frac{1}{3}) = 0,417
p_4(k=3) = \frac{3}{4}( \frac{1}{3}) = 0,250

Weer geeft de eerste kandidaat (k = 1, k/n = 0,25) afwijzen en de eerste betere nemen de grootste kans (0,458) op het beste resultaat.

n = 10[bewerken]

We hebben nu tien kandidaten. De eerste (twee) kandidaten afwijzen en de eerste betere nemen levert de kansen:

p_{10}(k=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}) = 0,283
p_{10}(k=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}) = 0,366 enzovoorts.

In tabelvorm:

n = 10
k 1 2 3 4 5 6 7 8 9
k/n 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9
Kans 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[bewerken]

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

Flood en Gardner[bewerken]

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

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

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

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

  • 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., The mating mind: how sexual choice shaped the evolution of human nature, Anchor Books, 2001. 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. (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[bewerken]

Nederlandstalig[bewerken]

Engelstalig[bewerken]

Wetenschappelijke artikelen en boek[bewerken]

Lesmateriaal en overig[bewerken]

Franstalig[bewerken]