Secretaresseprobleem

Bewijs doe ik binnenkort

Het Secretaresseprobleem is een praktisch vraagstuk uit de kansrekening, de statistiek en de beslissingstheorie. Martin Gardner besprak het in februari 1960 in zijn rubriek Mathematical Recreations in het tijdschrift Scientific American.^[1] Het probleem staat ook bekend als het Huwelijksprobleem, de Bruidsschat van de sultan en De grootste taart. ^[2] Als we iets of iemand moeten kiezen uit een reeks en niet mogen terugkomen op een eerdere afwijzing, wanneer kunnen we dan het beste stoppen en beslissen?

Formulering

Er is een vacature voor een secretaresse.
Het aantal sollicitanten n is bekend.
De sollicitanten krijgen in een willekeurige volgorde een sollicitatiegesprek, met van te voren gelijke kans van slagen.
De beoordeling van de sollicitanten is ondubbelzinnig (geen gelijke beoordelingen). Afwijzing of aanvaarding van een sollicitant berust uitsluitend op de beoordelingen tot dusver.
Een afgewezen sollicitant kan niet opnieuw worden opgeroepen.
Er wordt naar het beste resultaat gestreefd.

Oplossing

De beste aanpak blijkt om een aantal k sollicitanten af te wijzen en dan de eerstvolgende te nemen die beter is dan alle voorgaande. Als geen betere langskomt, nemen we maar de laatste. Berekening geeft dat voor grote aantal sollicitanten $k=n/$ e, met e het grondtal van de natuurlijke logaritme (e = 2,71828..).

Voorbeeld

Dus als we 100 sollicitanten hebben, kunnen we het best de eerste 100 / e = 100 / 2,72 = 36,8 => 37 na het gesprek afwijzen, en de eerstvolgende sollicitant die beter is aannemen.

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")
Ferguson, T.S. (1989). Who solved the secretary problem?. Statistical science 4 (3): 282–296. DOI: 10.1214/ss/1177012493.
Flood, Merrill R., Brief uit 1958 (kopie in de Martin Gardner papers aan de Stanford University Archives, series 1, box 5, folder 19.
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].
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.
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). (For French translation, see cover story in the July issue of Pour la Science (2009))
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.
Miller, Geoffrey F. (2001), The mating mind: how sexual choice shaped the evolution of human nature. Anchor Books. ISBN 0-385-49517-X.
Framing Our Thoughts: Ecological Rationality as Evolutionary Psychology's Answer to the Frame Problem, Timothy Ketelaar and Peter M. Todd, Chapter 5 of Conceptual Challenges in Evolutionary Psychology, p. 187.
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.

Bronnen, noten en/of referenties

↑ 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]
↑ Kennislink.nl Alex van den Brandhof: De grootste taart

Externe links

Nederlandstalig

Engelstalig

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

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

[1]

[2]