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
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))
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].
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.
Robert J. Vanderbei "The Postdoc Variant of the Secretary Problem"
Kategori:Beslutningsteori