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.

Deutsche Fotothek, 1951

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]

FormuleringBewerken

De formulering van het secretaresseprobleem luidt

  1. Er is een vacature voor een secretaresse.
  2. Het aantal sollicitanten   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.

OplossingBewerken

De beste aanpak blijkt om een aantal van   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  ? En hoe groot is de kans de beste kandidaat te vinden? Berekening leert:

  1. Voor grote aantallen sollicitanten   geldt  , met e het grondtal van de natuurlijke logaritme.
  2. De kans dat zo de beste kandidaat gevonden wordt, nadert voor grote aantallen tot  .

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

BewijsBewerken

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   dat de beste kandidaat nummer   is en gekozen wordt? De kans dat een willekeurige kandidaat de beste is, is  . Als kandidaat   de beste is en ook gekozen wordt, houdt dat in dat de kandidaten   niet gekozen zijn, dus de eerste   kandidaten waren beter dan deze  . Dus:

 

en

 

De kans   dat met deze strategie de beste kandidaat gekozen wordt is dus:

 

Grote aantallenBewerken

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

 

Dus is voor grote   en  , met  :

 

OptimumBewerken

Het maximum van   wordt bereikt voor   waarvoor:

 

Dus:

 

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

 

De tweede afgeleide   is voor   gelijk aan  , dus kleiner dan 0, zodat in het stationaire punt inderdaad een maximum wordt bereikt.

Voorbeeld voor grote aantallenBewerken

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 aantallenBewerken

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

n = 2Bewerken

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.

 
 

n = 3Bewerken

Bij drie kandidaten geldt:

Direct de eerste kandidaat kiezen:

 

De eerste kandidaat voorbij laten gaan:

 

De eerste twee kandidaten voorbij laten gaan:

 

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

n = 4Bewerken

Met vier kandidaten worden de kansen:

Direct de eerste kandidaat kiezen

 

De eerste kandidaat voorbij laten gaan:

 

De eerste twee kandidaten voorbij laten gaan:

 

De eerste drie kandidaten voorbij laten gaan:

 

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

n = 10Bewerken

Bij tien kandidaten zijn de kansen:

 
 
 
 
 

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
pn(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.

OverzichtBewerken

De volgende tabel toont de gevallen met betrekkelijk weinig kandidaten.

n 2 3 4 5 6 7 8 9 10 .. 25 limiet n→∞
kmax 1 1 1 2 2 2 3 3 3 .. 9 n/e
kmax/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 kmax/n als de optimale kans benaderd door 1/e ~ 0,368.

GeschiedenisBewerken

Flood en GardnerBewerken

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 spelBewerken

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

VariantenBewerken

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 onderzoekBewerken

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.

LiteratuurBewerken

Externe linksBewerken

NederlandstaligBewerken

EngelstaligBewerken

Wetenschappelijke artikelen en boekBewerken

Lesmateriaal en overigBewerken

FranstaligBewerken