Sekretærproblemet

Sekretærproblemet er et berømt problem som benytter optimal stansteori (valg av et optimalt tidspunkt for å utføre en bestemt handling). Problemet har blitt studert mye i statistikk og beslutningsteori. Det er også kjent som giftemålsproblemet, sultanens medgift-problemet, googol-spillet og beste-valg-problemet.

Den grunnleggende formuleringen av problemet er som følger: Forestill deg en administrator som ønsker å ansette den beste sekretæren ut av n rangerbare søkere for en stilling. Søkerne blir intervjuet en for en i tilfeldig rekkefølge. En beslutning må treffes umiddelbart etter intervjuet for den enkelte søker. Når søkeren er avvist kan man ikke kalles inn igjen. I løpet av intervjuet kan administratoren rangere søkerne blant alle som er intervjuet så langt, men har ingen kjennskap til kvaliteten til søkere som ennå ikke er intervjuet. Spørsmålet er om den optimale stopp strategi (stopp regelen) som maksimerer sannsynligheten for å velge den beste søkeren. Hvis beslutningen kan utsettes til slutten, kan man løse dette simpelthen med maksimum seleksjons algoritmen og velge den maksimale på slutten. Vanskeligheten er at beslutningen må treffes umiddelbart.

Problemformulering

Selv om det finnes mange måter å formulere problemet på, kan det formuleres som følger:

• Det skal ansettes en person
• Det er n søkere til stillingen, og n er kjent.
• Søkerne, hvis de blir sett under ett, kan rangeres fra best til verst.
• Søkerne er intervjuet sekvensielt i en tilfeldig rekkefølge, med hver orden like sannsynlig.
• Umiddelbart etter intervjuet må søkeren enten aksepteres eller forkastes, man kan ikke gå tilbake på beslutningen.
• Beslutning om å akseptere eller forkaste en søker kan bare være basert på den relative rangeringen av søkerne så langt.
• Målsetning for den generelle løsningen er å velge den beste søkeren ut av en hel gruppe. Dette er det samme som å maksimere forventet forventet avkastning, med avkastning definert som 1 for den beste søkeren, og 0 ellers.

Litteratur

• 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. CS1-vedlikehold: Flere navn: forfatterliste (link)
• 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. CS1-vedlikehold: Flere navn: forfatterliste (link)
• F. Thomas Bruss (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. 
• F. Thomas Bruss (2000). «Sum the odds to one and stop». Annals of Probability. 28 (3): 1384–91. doi:10.1214/aop/1019160340. 
• Ferguson, T. S. (1989). «Who solved the secretary problem?». Statistical Science. 4 (3): 282–296. doi:10.1214/ss/1177012493. 
• Ghirdar, Y., Dudek G. (2009). «Optimal Online Data Sampling or How to Hire the Best Secretaries». Proc. Computer and Robot Vision: 292–298. doi:10.1109/CRV.2009.30. CS1-vedlikehold: Flere navn: forfatterliste (link)
• Gnedin, A. (1994). «A solution to the game of Googol». Annals of Probability. 22 (3): 1588–1595. doi:10.1214/aop/1176988613. 
• Freeman, P.R. (1983). «The secretary problem and its extensions: A review». International Statistical Review / Revue Internationale de Statistique. 51 (2): 189–206. JSTOR 1402748. doi:10.2307/1402748. 
• Hill, T.P. "Knowing When to Stop". American Scientist, Vol. 97, 126-133 (2009). (For fransk oversettelse, se cover story i juliutgaven av Pour la Science (2009))
• 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. CS1-vedlikehold: Flere navn: forfatterliste (link)
• 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. 
• Merrill R. Flood, letter written in 1958, a copy of which can be found in the Martin Gardner papers at Stanford University Archives, series 1, box 5, folder 19.
• Martin Gardner, New Mathematical Diversions from Scientific American. Simon and Schuster, 1966, Chapter 3, Problem 3 [reprints his original column published in February 1960 with additional comments].
• 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. (mars 1999). «Decision Making: A Golden Rule». American Mathematical Monthly. 106 (2): 215. doi:10.2307/2589677. CS1-vedlikehold: Flere navn: forfatterliste (link)
• Robert J. Vanderbei (1980). «The Optimal Choice of a Subset of a Population». Mathematics of Operations Research. 5 (4): 481–486. doi:10.1287/moor.5.4.481. 
• Robert J. Vanderbei "The Postdoc Variant of the Secretary Problem"

Denne artikkelen er en spire. Du kan hjelpe Wikipedia ved å utvide den.