Sihteerin ongelma - Secretary problem

Kaaviot todennäköisyyden saada paras ehdokas (punaiset ympyrät) n sovelluksesta ja k / n (siniset ristit), jossa k on otoksen koko

Sihteeri ongelma osoittaa skenaario liittyy optimaalinen pysäytysongelma teoria, joka on tutkittu laajasti aloilla Applied todennäköisyys , tilastoja ja päätösteoria . Se tunnetaan myös nimellä avioliitto -ongelma , sulttaanin myötäjäisongelma , hankala kosija -ongelma , googolipeli ja paras valintaongelma .

Ongelman perusmuoto on seuraava: kuvitelkaa järjestelmänvalvojaa, joka haluaa palkata parhaan sihteerin tehtävään sopivista hakijoista. Hakijoita haastatellaan yksitellen satunnaisessa järjestyksessä. Päätös kustakin hakijasta on tehtävä heti haastattelun jälkeen. Kun hakija on hylätty, häntä ei voida palauttaa. Haastattelun aikana järjestelmänvalvoja saa tietoja, jotka riittävät hakijan sijoittamiseen kaikkien tähän mennessä haastateltujen hakijoiden joukkoon, mutta hän ei ole tietoinen vielä näkemättömien hakijoiden laadusta. Kysymys koskee optimaalista strategiaa ( pysäytyssääntö ) parhaan hakijan valitsemisen todennäköisyyden maksimoimiseksi. Jos päätöstä voidaan lykätä loppuun, tämä voidaan ratkaista yksinkertaisella maksimivalinta -algoritmilla , joka seuraa juoksevaa enimmäismäärää (ja kuka sen on saavuttanut) ja valitsee kokonaismaksimin lopussa. Vaikeus on siinä, että päätös on tehtävä välittömästi. ${\ displaystyle n}$

Lyhin tähän mennessä tunnettu tiukka todiste on kertoimien algoritmi . Se tarkoittaa, että optimaalinen voiton todennäköisyys on aina vähintään (missä e on luonnollisen logaritmin perusta ) ja että jälkimmäinen pätee jopa paljon yleisemmin. Optimaalisen pysäytyssäännön mukaan ensimmäiset haastatellut hakijat hylätään aina ja sitten pysähdytään ensimmäiseen hakijaan, joka on parempi kuin kaikki tähän mennessä haastatellut hakijat (tai jatketaan viimeiseen hakijaan, jos näin ei koskaan tapahdu). Joskus tätä strategiaa kutsutaan pysäytyssääntönä, koska todennäköisyys pysähtyä parhaan hakijan kanssa tällä strategialla on jo noin kohtuullisille arvoille . Yksi syy siihen, miksi sihteeriongelma on saanut niin paljon huomiota, on se, että ongelmaan optimaalinen politiikka (pysäytyssääntö) on yksinkertainen ja valitsee parhaan yksittäisen ehdokkaan noin 37% ajasta riippumatta siitä, onko hakijoita 100 tai 100 miljoonaa. ${\ displaystyle 1/e}$${\ displaystyle \ sim n/e}$${\ displaystyle 1/e}$${\ displaystyle 1/e}$${\ displaystyle n}$

Muotoilu

Vaikka muunnelmia on monia, perusongelma voidaan ilmaista seuraavasti:

• Yksi paikka täytettävä.
• On n hakijoiden tehtävään, ja arvo n on tiedossa.
• Hakijat voidaan kokonaisuudessaan luokitella yksiselitteisesti parhaasta huonoimpaan.
• Hakijoita haastatellaan peräkkäin satunnaisessa järjestyksessä, ja jokainen tilaus on yhtä todennäköinen.
• Heti haastattelun jälkeen haastateltu hakija joko hyväksytään tai hylätään, ja päätös on peruuttamaton.
• Päätös hakijan hyväksymisestä tai hylkäämisestä voi perustua vain tähän mennessä haastateltujen hakijoiden suhteellisiin riveihin.
• Yleisen ratkaisun tavoitteena on saada suurin todennäköisyys valita koko ryhmän paras hakija. Tämä on sama kuin odotetun voiton maksimointi, jolloin voitto on määritelty yhdeksi parhaalle hakijalle ja nolla muuten.

Ehdokas määritellään hakija, kun haastateltiin, on parempi kuin kaikki hakijat haastateltiin aiemmin. Ohita tarkoittaa "hylkää heti haastattelun jälkeen". Koska ongelman tavoitteena on valita paras yksittäinen hakija, hyväksytään vain ehdokkaat. "Ehdokas" tässä yhteydessä vastaa tietueen käsitettä permutaatiossa.

Optimaalisen politiikan laatiminen

Optimaalinen käytäntö ongelmalle on pysäytyssääntö . Sen nojalla, haastattelija hylkää ensimmäisen r  - 1 hakijat (anna hakijalle M paras hakija näistä R  - 1 hakijaa), ja sitten valitsee ensimmäisen myöhempi hakija, joka on parempi kuin hakijan M . Voidaan osoittaa, että optimaalinen strategia on tässä strategialuokassa. (Huomaa, että meidän ei pitäisi koskaan valita hakijaa, joka ei ole paras tähän mennessä näkemämme, koska he eivät voi olla paras hakija kokonaisuudessaan.) Mielivaltaisen raja -arvon osalta todennäköisyys, että paras hakija valitaan, on

${\ displaystyle {\ begin {aligned} P (r) & = \ summa _ {i = 1}^{n} P \ vasen ({\ text {hakija}} i {\ teksti {on valittu}} \ cap {101} \ text {hakija}} i {\ teksti {on paras}} \ oikea) \\ & = \ summa _ {i = 1}^{n} P \ vasen ({\ teksti {hakija}} i {\ teksti {on valittu}} | {\ teksti {hakija}} i {\ teksti {on paras}} \ oikea) \ cdot P \ vasen ({\ teksti {hakija}} i {\ teksti {on paras}} \ oikea) \\ & = \ vasen [\ summa _ {i = 1}^{r-1} 0+ \ summa _ {i = r}^{n} P \ vasen (\ vasen. {\ begin {array} {l} {\ text {the first of the}}} i-1 {\ text {hakijat}} \\ {\ text {is in the first}} r-1 {\ text {hakijat}} \ end {array }} \ oikea | {\ teksti {hakija}} i {\ teksti {on paras}} \ oikea) \ oikea] \ cdot {\ frac {1} {n}} \\ & = \ vasen [\ summa _ {i = r}^{n} {\ frac {r-1} {i-1}} oikea] \ cdot {\ frac {1} {n}} \\ & = {\ frac {r-1} {n}} \ sum _ {i = r}^{n} {\ frac {1} {i-1}}. \ end {aligned}}}$

Summaa ei ole määritelty r = 1: lle, mutta tässä tapauksessa ainoa mahdollinen käytäntö on valita ensimmäinen hakija ja siten P (1) = 1/ n . Tämä summa saadaan huomata, että jos hakija i on paras hakija, niin se valitaan, jos ja vain jos paras hakija ensimmäisten joukossa I  - 1 hakijoiden on ensimmäisiä R  - 1 kantajille hylättiin. Jos annat n taipumuksen äärettömyyteen, kirjoitat rajana (r-1) / n , käytät t : tä (i-1) / n: lle ja dt : tä 1 / n: lle , summa voidaan arvioida integraalilla ${\ displaystyle x}$

${\ displaystyle P (x) = x \ int _ {x}^{1} {\ frac {1} {t}} \, dt = -x \ ln (x) \ ;.}$

Ottaen P ( x ): n derivaatan suhteessa , asettamalla sen 0: ksi ja ratkaisemalla x: n , havaitsemme, että optimaalinen x on 1/ e . Siten optimaalinen raja -arvo on yleensä n / e, kun n kasvaa, ja paras hakija valitaan todennäköisyydellä 1 / e . ${\ displaystyle x}$

Pienille arvoille n optimaalinen r voidaan saada myös tavanomaisilla dynaamisilla ohjelmointimenetelmillä . Optimaaliset kynnysarvot r ja todennäköisyys valita paras vaihtoehto P useille arvoille n esitetään seuraavassa taulukossa.

${\ displaystyle n}$	1	2	3	4	5	6	7	8	9
${\ displaystyle r}$	1	1	2	2	3	3	3	4	4
${\ displaystyle P}$	1000	0,500	0,500	0,458	0,433	0,428	0,414	0,410	0,406

Todennäköisyys valita paras hakija klassisessa sihteeri -ongelmassa lähestyy . ${\ displaystyle 1/e \ noin 0,368}$

Vaihtoehtoinen ratkaisu

Tämä ongelma ja useat muutokset voidaan ratkaista (mukaan lukien todiste optimaalisuudesta) yksinkertaisella tavalla kertoimien algoritmilla , jolla on myös muita sovelluksia. Muutokset sihteeriongelmaan, jotka voidaan ratkaista tällä algoritmilla, sisältävät hakijoiden satunnaisen saatavuuden, yleisemmät hypoteesit hakijoiden kiinnostamiseksi päätöksentekijälle, ryhmähaastattelut hakijoille sekä tietyt mallit satunnaiselle hakijamäärälle.

Rajoitukset

Sihteeritehtävän ratkaisulla on merkitystä vain, jos on perusteltua olettaa, että hakijoilla ei ole tietoa käytetystä päätöksentekostrategiasta, koska varhaisilla hakijoilla ei ole mahdollisuutta ollenkaan eikä he välttämättä näy toisin.

Yksi tärkeä haittapuoli klassisen sihteeritehtävän ratkaisun sovelluksissa on, että hakijoiden määrä on tiedettävä etukäteen, mikä on harvinaista. Yksi tapa ratkaista tämä ongelma on olettaa, että hakijoiden määrä on satunnaismuuttuja , jonka jakauma on tunnettu (Presman ja Sonin, 1972). Tässä mallissa optimaalinen ratkaisu on kuitenkin yleensä paljon vaikeampi. Lisäksi optimaalinen onnistumistodennäköisyys ei ole enää noin 1/ e, vaan tyypillisesti pienempi. Tämä voidaan ymmärtää siinä kontekstissa, että "hinta" on maksettava hakijoiden lukumäärän tietämättömyydestä. Tässä mallissa hinta on kuitenkin korkea. Riippuen jakauman valinnasta , optimaalinen voiton todennäköisyys voi lähestyä nollaa. Etsiminen keinoista selviytyä tästä uudesta ongelmasta johti uuteen malliin, joka tuotti ns. 1/e-lain parhaan valinnan. ${\ displaystyle n}$${\ displaystyle N}$${\ displaystyle P (N = k) _ {k = 1,2, \ cdots}}$${\ displaystyle N}$

1/e-laki paras valinta

Mallin ydin perustuu ajatukseen, että elämä on peräkkäistä ja että reaalimaailman ongelmat kohtaavat itsensä reaaliajassa. Lisäksi on helpompi arvioida aikoja, jolloin tiettyjen tapahtumien (hakijoiden saapumiset) tulisi esiintyä useammin (jos niitä esiintyy) kuin arvioida tapahtumien lukumäärän jakautumista. Tämä ajatus johti seuraavaan lähestymistapaan, niin sanottuun yhtenäiseen lähestymistapaan (1984):

Malli määritellään seuraavasti: Hakija on valittava tietyllä aikavälillä tuntemattomasta joukosta hakijoita. Tavoitteena on maksimoida todennäköisyys valita vain parhaat hypoteesin mukaan, että kaikki eriasteiset saapumisjärjestykset ovat yhtä todennäköisiä. Oletetaan, että kaikilla hakijoilla on sama, mutta toisistaan ​​riippumaton, saapumisajan tiheys päällä ja merkitse vastaavaa saapumisajan jakautumistoimintoa, ts. ${\ displaystyle [0, T]}$${\ displaystyle N}$${\ displaystyle f}$${\ displaystyle [0, T]}$${\ displaystyle F}$

${\ displaystyle F (t) = \ int _ {0}^{t} f (s) ds}$, .${\ displaystyle \, 0 \ leq t \ leq T}$

Olkoon sellainen, että harkitse strategiaa odottaa ja tarkkailla kaikkia hakijoita ajoissa ja valita sitten, jos mahdollista, ensimmäinen ehdokas jälkeenpäin, joka on parempi kuin kaikki edelliset. Tällöin tällä strategialla, jota kutsutaan 1/e-strategiaksi , on seuraavat ominaisuudet: ${\ displaystyle \ tau}$${\ displaystyle F (\ tau) = 1/e.}$${\ displaystyle \ tau}$${\ displaystyle \ tau}$

1 / E-strategia

i) tuotto kaikille vähintään 1/e: n menestystodennäköisyydelle,${\ displaystyle N}$

(ii) on ainutlaatuinen strategia, joka takaa tämän pienemmän onnistumistodennäköisyysrajan 1/e ja raja on optimaalinen,

(iii) valitsee, jos on vähintään yksi hakija, ei yhtään, todennäköisyydellä 1/e.

F. Thomas Brussin vuonna 1984 todistama 1/e-laki tuli yllätyksenä. Syynä oli se, että arvoa 1/e oli aiemmin pidetty tavoittamattomana tuntemattomassa mallissa , kun taas tämä arvo 1/e saavutettiin nyt menestyksen todennäköisyyden alarajana, ja tämä mallissa, jossa epäilemättä paljon heikompia hypoteeseja (ks. esim. Math. Reviews 85: m). ${\ displaystyle N}$

1/e-laki sekoitetaan joskus edellä kuvatun klassisen sihteeritehtävän ratkaisuun, koska numero 1/e on samanlainen. Kuitenkin 1/e-laissa tämä rooli on yleisempi. Tulos on myös vahvempi, koska se pätee tuntemattomaan määrään hakijoita ja koska saapumisaikajakaumaan F perustuva malli on sovelluksia paremmin käsiteltävissä.

Peli googol

Mukaan Ferguson ( 1989 ), sihteeri ongelma esiintyi ensimmäisen kerran painettuna, kun se oli esillä on Martin Gardner hänen helmikuu 1960 Matemaattinen Pelit sarake vuonna Scientific American . Näin Gardner 1966 muotoili sen: "Pyydä jotakuta ottamaan niin monta paperilehteä kuin hän haluaa ja kirjoita jokaiselle paperille eri positiivinen luku. Numerot voivat vaihdella pienistä murto -osista 1 googolikokoiseen lukuun ( 1, jota seuraa sata nollaa) tai jopa suurempia. Nämä liuskat käännetään kuvapuoli alaspäin ja sekoitetaan pöydän yläosan päälle. Kierrät ne yksi kerrallaan kuvapuoli ylöspäin. Tavoitteena on lopettaa kääntyminen, kun tulet numeroon, joka arvelet olevasi sarjan suurin. Et voi palata takaisin ja valita aiemmin käännettyä liuskaa. Jos käännät kaikki lipsahdukset ympäri, sinun on tietysti valittava viimeinen käännetty. " harvnb -virhe: ei kohdetta: CITEREFGardner1966 ( ohje )

Artikkelissa "Kuka ratkaisi sihteeriongelman?" Ferguson ( 1989 ) huomautti, että sihteeriongelma jäi ratkaisematta, kuten M. Gardner totesi, eli kahden hengen nollasummapeli, jossa on kaksi antagonistista pelaajaa. Tässä pelissä Alice, tietoinen pelaaja, kirjoittaa salaa eri numeroita kortteihin. Pysähtyvä pelaaja Bob tarkkailee todellisia arvoja ja voi lopettaa korttien kääntämisen milloin tahansa. Voittaa, jos viimeisellä käännetyllä kortilla on suurin maksimimäärä. Ero sihteerin perusongelmaan on, että Bob tarkkailee kortteihin kirjoitettuja todellisia arvoja, joita hän voi käyttää päätöksissään. Korttien numerot vastaavat hakijoiden numeerisia ominaisuuksia joissakin sihteeritehtävän versioissa. Yhteisjakauma numerot on valvonnassa Alice. ${\ displaystyle n}$

Bob haluaa arvata suurimman mahdollisen todennäköisyyden, kun taas Alicen tavoitteena on pitää tämä todennäköisyys mahdollisimman pienenä. Ei ole optimaalista, että Alice ottaa näytteitä itsenäisesti jostain kiinteästä jakaumasta, ja hän voi pelata paremmin valitsemalla satunnaislukuja jollakin riippuvalla tavalla. Sillä Alicella ei ole minimax -strategiaa, joka liittyy läheisesti T. Coverin paradoksiin . Mutta peli on ratkaisu: Alice valita satunnaisia numeroita (jotka ovat riippuvaisia satunnaismuuttujia) siten, että Bob ei voi pelata paremmin kuin käyttämällä klassisen pysäyttäminen strategiaa, joka perustuu suhteellisen riveissä ( Gnedin 1994 ). ${\ displaystyle n = 2}$${\ displaystyle n> 2}$

Heuristinen suorituskyky

Artikkelin loppuosa käsittelee jälleen tiedossa olevan hakijan sihteeriongelmaa.

Odotetut menestystodennäköisyydet kolmelle heuristiikalle.

Stein, Seale & Rapoport 2003 johtivat odotetut menestystodennäköisyydet useille psykologisesti uskottaville heuristiikoille, joita saatetaan käyttää sihteeriongelmassa. Heuristiikka, jota he tutkivat, olivat:

• Katkaisusääntö (CR): Älä hyväksy ensimmäistä y hakijaa; valitse sen jälkeen ensimmäinen kohdattu ehdokas (eli hakija, jolla on suhteellinen asema 1). Tällä säännöllä on erityistapauksena optimaalinen käytäntö klassiselle sihteeritehtävälle, jolle y  =  r .
• Ehdokkaiden laskusääntö (CCR): Valitse y -edellinen ehdokas. Huomaa, että tämä sääntö ei välttämättä ohita hakijoita; siinä otetaan huomioon vain se, kuinka monta ehdokasta on havaittu, ei se, kuinka syvällä päätöksentekijä on hakijajärjestyksessä.
• Perättäinen ei-ehdokas-sääntö (SNCR): Valitse ensimmäinen kohdattu ehdokas sen jälkeen, kun olet tarkkaillut y ei-ehdokkaita (eli hakijoita, joiden suhteellinen asema> 1).

Jokaisella heuristiikalla on yksi parametri y . Kuva (näkyy oikealla) näyttää odotetut onnistumistodennäköisyydet kullekin heuristille y : n funktiona ongelmille, joiden n  = 80.

Cardinal payoff -vaihtoehto

Parhaan yksittäisen hakijan löytäminen saattaa tuntua melko tiukalta tavoitteelta. Voidaan kuvitella, että haastattelija palkkaa mieluummin korkeamman arvosanan hakijan kuin alhaisemman hakijan eikä pelkästään saada parasta. Toisin sanoen haastattelija saa jonkin arvon hakijan valitsemisesta, joka ei välttämättä ole paras, ja johdettu arvo kasvaa valitun arvon kanssa.

Mallin tämän ongelman olettaa, että hakijat ovat "tosi" arvot satunnaismuuttujat X vedetään iid peräisin tasaisen jakaantumisen on [0, 1]. Samanlainen klassisen edellä kuvatun ongelman, haastattelija vain huomauttaa onko kukin hakija on paras tähän mennessä (ehdokkaan), on hyväksyttävä tai hylättävä kunkin paikan päällä, ja on hyväksyttävä viimeinen, jos hän / hän on saavutettu. (Selvyyden vuoksi haastattelija ei opi kunkin hakijan todellista suhteellista asemaa . Hän tietää vain, onko hakijalla suhteellinen asema 1.) Tässä versiossa kuitenkin voitto annetaan valitun hakijan todellisen arvon perusteella. Jos hän esimerkiksi valitsee hakijan, jonka todellinen arvo on 0,8, hän ansaitsee 0,8. Haastattelijan tavoitteena on maksimoida valitun hakijan odotettu arvo. ${\ displaystyle n}$

Koska kantajan arvot ovat iid kiinnittää tasaisesta jakaumasta on [0, 1] odotettu arvo on t th kantaja Annetut että saadaan ${\ displaystyle x_ {t} = \ max \ left \ {x_ {1}, x_ {2}, \ ldots, x_ {t} \ right \}}$

${\ displaystyle E_ {t} = E \ vasen (X_ {t} | I_ {t} = 1 \ right) = {\ frac {t} {t+1}}.}$

Kuten klassisessa ongelmassa, optimaalisen politiikan antaa kynnys, jota tälle ongelmalle merkitsemme , jolloin haastattelijan pitäisi alkaa hyväksyä ehdokkaita. Parta 2006 osoitti, että c on joko tai . (Itse asiassa, kumpi on lähimpänä .) Tämä johtuu siitä, että hakijoiden ongelman vuoksi odotettavissa oleva voitto joistakin mielivaltaisista kynnyksistä on ${\ displaystyle c}$${\ displaystyle \ lfloor {\ sqrt {n}} \ rfloor}$${\ displaystyle \ lceil {\ sqrt {n}} \ rceil}$${\ displaystyle {\ sqrt {n}}}$${\ displaystyle n}$${\ displaystyle 1 \ leq c \ leq n}$

${\ displaystyle V_ {n} (c) = \ summa _ {t = c}^{n-1} \ vasen [\ prod _ {s = c}^{t-1} \ vasen ({\ frac {s -1} {s}} \ oikea) \ oikea] \ vasen ({\ frac {1} {t+1}} \ oikea)+\ vasen [\ prod _ {s = c}^{n-1} \ vasen ({\ frac {s-1} {s}} \ oikea) \ oikea] {\ frac {1} {2}} = {\ frac {2cn- {c}^{2}+cn} {2cn} }.}$

Erottaa suhteen c , kukaan ${\ displaystyle V_ {n} (c)}$

${\ displaystyle {\ frac {\ osittainen V} {\ osittainen c}} = {\ frac {-{c}^{\, 2}+n} {2 {c}^{\, 2} n}}. }$

Oppiminen osittaisen tiedon peräkkäisessä hakuparadigmassa. Numerot näyttävät hakijoiden odotetut arvot perustuen heidän suhteelliseen sijoitukseensa (kaikista tähän mennessä nähtyistä hakijoista) haun eri kohdissa. Odotukset lasketaan tapauksen perusteella, kun niiden arvot jakautuvat tasaisesti välille 0 ja 1. Suhteelliset sijoitustiedot antavat haastattelijalle mahdollisuuden arvioida hakijoita tarkemmin, kun he keräävät enemmän datapisteitä vertailuun.

Koska kaikkien sallittujen arvojen kohdalla , se on maksimoitu . Koska V on kupera , optimaalisen kokonaislukukynnyksen on oltava joko tai . Siten useimmat haastattelijan arvot alkavat hyväksyä hakijoita nopeammin kardinaalin voiton versiossa kuin klassisessa versiossa, jossa tavoitteena on valita paras yksittäinen hakija. Huomaa, että tämä ei ole asymptoottinen tulos: se koskee kaikkia . Tämä ei kuitenkaan ole paras käytäntö tunnetun jakelun odotetun arvon maksimoimiseksi. Tunnetun jakauman tapauksessa optimaalinen toisto voidaan laskea dynaamisen ohjelmoinnin avulla. ${\ displaystyle \ osittainen ^{\, 2} V/\ osittainen c ^{\, 2} <0}$${\ displaystyle c}$${\ displaystyle V}$${\ displaystyle c = {\ sqrt {n}}}$${\ displaystyle c}$${\ displaystyle \ lfloor {\ sqrt {n}} \ rfloor}$${\ displaystyle \ lceil {\ sqrt {n}} \ rceil}$${\ displaystyle n}$${\ displaystyle n}$

Palleyn ja Kremerin (2014) esittämä tämän ongelman yleisempi muoto olettaa, että jokaisen uuden hakijan saapuessa haastattelija tarkkailee heidän sijoitustaan ​​suhteessa kaikkiin hakijoihin, joita on havaittu aiemmin. Tämä malli on yhdenmukainen haastattelijan oppimisen käsitteen kanssa, kun he jatkavat hakuprosessia keräämällä joukon aiempia datapisteitä, joita he voivat käyttää uusien ehdokkaiden arvioimiseen saapuessaan. Tästä niin kutsutusta ositietomallista on hyötyä siinä, että suhteellisia sijoitusinformaatioita käyttäen saavutettuja päätöksiä ja tuloksia voidaan verrata suoraan vastaaviin optimaalisiin päätöksiin ja tuloksiin, jos haastattelijalle olisi annettu kaikki tiedot kunkin hakijan arvosta. Moser (1956), Sakaguchi (1961) ja Karlin (1962) ratkaisivat tämän täydellisen tiedon ongelman, jossa hakijat valitaan riippumattomasti tunnetusta jakelusta ja haastattelija pyrkii maksimoimaan valitun hakijan odotetun arvon.

Muut muutokset

Sihteeriongelmasta on useita muunnelmia, joihin on myös yksinkertaisia ​​ja tyylikkäitä ratkaisuja.

Yksi vaihtoehto korvaa halun valita paras toiveella valita toiseksi paras. Robert J. Vanderbei kutsuu tätä "postdoc" -ongelmaksi väittäen, että "paras" menee Harvardiin. Tässä ongelmassa todennäköisyys menestyä parillisella hakijamäärällä on täsmälleen . Tämä todennäköisyys on yleensä 1/4, kun n taipuu äärettömyyteen, mikä osoittaa, että paras on helpompi valita kuin toiseksi paras. ${\ displaystyle {\ frac {0.25n^{2}} {n (n-1)}}}$

Toisen variantin kohdalla valintojen määrä on määritetty suuremmaksi kuin yksi. Toisin sanoen haastattelija ei palkkaa vain yhtä sihteeriä vaan pikemminkin ottaa vastaan ​​esimerkiksi opiskelijaluokan hakijaryhmästä. Olettaen, että menestys saavutetaan silloin ja vain, jos kaikki valitut ehdokkaat ovat parempia kuin kaikki valitsemattomat ehdokkaat, se on jälleen ongelma, joka voidaan ratkaista. Vanderbei 1980 osoitti, että kun n on parillinen ja halutaan valita täsmälleen puolet ehdokkaista, optimaalinen strategia tuottaa menestystodennäköisyyden . ${\ displaystyle {\ frac {1} {n/2+1}}}$

Toinen vaihtoehto on valita parhaat sihteerit joukosta , jälleen online-algoritmilla. Tämä johtaa strategiaan, joka liittyy klassiseen ja raja -arvoon , jonka klassinen ongelma on erityistapaus Ghirdar 2009 . ${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle {\ frac {0.25n^{2}} {n (n-1)}}}$harvnb -virhe: ei kohdetta: CITEREFGhirdar2009 ( ohje )

Monivalintaongelma

Pelaaja saa tehdä valintoja, ja hän voittaa, jos jokin valinta on paras. Gilbert & Mosteller 1966 osoitti, että optimaalisen strategian antaa kynnysstrategia (rajastrategia ). Optimaalinen strategia kuuluu strategialuokkaan, jonka määrittelee kynnyslukujen joukko , missä . Ensimmäistä vaihtoehtoa käytetään ensimmäisissä hakijoissa, jotka alkavat ensimmäisestä hakijasta, ja kun ensimmäinen vaihtoehto on käytetty, toista vaihtoehtoa käytetään ensimmäisessä hakijasta alkaen ensimmäisestä hakijasta jne. ${\ displaystyle r}$${\ displaystyle (a_ {1}, a_ {2}, ..., a_ {r})}$${\ displaystyle a_ {1} <a_ {2} <\ cdots <a_ {r}}$${\ displaystyle a_ {1}}$${\ displaystyle a_ {2}}$

Gilbert ja Mosteller osoittivat sen . Muita tapauksia , katso Matsui & Ano 2016 (esimerkiksi ). ${\ displaystyle \ vasen ({\ frac {a_ {1}} {n}}, {\ frac {a_ {2}} {n}}, {\ frac {a_ {3}} {n}}, {\ frac {a_ {4}} {n}} \ oikea) \ oikea nuoli \ vasen (e^{-1}, e^{-{\ frac {3} {2}}}, e^{-{\ frac { 47} {24}}}, e^{-{\ frac {2761} {1152}}} \ oikea) (n \ oikea nuoli \ infty)}$${\ displaystyle r = 5,6, ..., 10}$${\ displaystyle {\ frac {a_ {5}} {n}} \ rightarrow e^{-{\ frac {4162637} {1474560}}}}$

Milloin , voiton todennäköisyys lähenee ( Gilbert & Mosteller 1966 ). Matsui & Ano 2016 osoitti, että minkä tahansa positiivisen kokonaisluvun kohdalla todennäköisyys voittaa ( valintasihteerin ongelma) lähenee mihin . Näin ollen voiton todennäköisyys lähenee ja milloin . ${\ displaystyle r = 2}$${\ displaystyle e^{-1}+e^{-{\ frac {3} {2}}} (n \ oikea nuoli \ infty)}$${\ displaystyle r}$${\ displaystyle r}$${\ displaystyle p_ {1}+p_ {2}+\ cdots+p_ {r}}$${\ displaystyle p_ {i} = \ lim _ {n \ rightarrow \ infty} {\ frac {a_ {i}} {n}}}$${\ displaystyle e^{-1}+e^{-{\ frac {3} {2}}}+e^{-{\ frac {47} {24}}}}$${\ displaystyle e^{-1}+e^{-{\ frac {3} {2}}}+e^{-{\ frac {47} {24}}}+e^{-{\ frac { 2761} {1152}}}}$${\ displaystyle r = 3,4}$

Kokeelliset tutkimukset

Kokeellinen psykologit ja ekonomistit ovat tutkineet päätöksen käyttäytymistä todellisten ihmisten sihteeri ongelmatilanteissa. Tämä työ on osoittanut suurelta osin, että ihmiset lopettavat haun liian aikaisin. Tämä voidaan selittää ainakin osittain ehdokkaiden arviointikustannuksilla. Todellisessa ympäristössä tämä saattaa viitata siihen, että ihmiset eivät etsi tarpeeksi aina, kun he kohtaavat ongelmia, joissa päätösvaihtoehdot kohtaavat peräkkäin. Esimerkiksi kun yritetään päättää, missä moottoritien varrella olevassa huoltoasemassa kaasu pysäytetään, ihmiset eivät ehkä etsi tarpeeksi ennen pysähtymistä. Jos totta, he maksaisivat enemmän kaasusta kuin jos olisivat etsineet pidempään. Sama voi olla totta, kun ihmiset etsivät lentolippuja verkossa. Kokeellista tutkimusta ongelmista, kuten sihteeriongelmasta, kutsutaan joskus käyttäytymistoimintatutkimukseksi .

Neuraaliset korrelaatiot

Vaikka on huomattava määrä neurotieteen tutkimusta tiedon integrointi, tai edustus uskomus, vuonna havainto päätöksenteossa tehtäviä käyttämällä sekä eläinten että ihmisten aiheita, on suhteellisen vähän tiedetään miten päätös lopettaa tietojen kerääminen on saapunut.

Tutkijat ovat tutkineet hermoperustoja sihteeriongelman ratkaisemiseksi terveillä vapaaehtoisilla käyttämällä toiminnallista magneettikuvausta . Markov päätöksentekoprosessi (MDP) käytettiin paljon hyötyä jatkaa etsiä vs. sitoutumalla nykyistä vaihtoehto. Päätökset tehdä tai hylätä vaihtoehto sisälsivät parietaalisen ja dorsolateraalisen prefrontaalisen aivokuoren sekä ventraalisen striatumin , etuosan ja etureunan . Siksi aivojen alueet, jotka aiemmin osallistuivat todisteiden integrointiin ja palkitsemiseen, koodaavat kynnysrajoja, jotka laukaisevat päätökset sitoutua valintaan.

Historia

Sihteeriongelman esitteli ilmeisesti vuonna 1949 Merrill M. Flood , joka kutsui sitä sulhanenongelmaksi tuona vuonna pitämässään luennossa. Hän viittasi siihen useita kertoja 1950 -luvulla, esimerkiksi Purduessa 9. toukokuuta 1958 pidetyssä konferenssipuheessa . Vuonna 1958 hän lähetti Leonard Gillmanille kirjeen , jossa oli kopioita tusinoille ystäville, kuten Samuel Karlinille ja J. Robbinsille, jossa esitettiin todiste optimaalisesta strategiasta, ja R. Palermon liite, joka osoitti, että kaikkia strategioita hallitsee strategia lomake "hylkää ensimmäinen p ehdoitta ja hyväksy sitten seuraava parempi ehdokas". (Katso tulva (1958).)

Ensimmäinen julkaisu oli ilmeisesti Martin Gardner julkaisussa Scientific American, helmikuu 1960. Hän oli kuullut siitä John H. Fox Jr. ja L. Gerald Marnie, jotka olivat itsenäisesti keksineet vastaavan ongelman vuonna 1958; he kutsuivat sitä "googolin peliksi". Fox ja Marnie eivät tienneet optimaalista ratkaisua; Gardner pyysi neuvoja Leo Moserilta , joka (yhdessä JR Pounderin kanssa) toimitti oikean analyysin julkaisemiseksi lehdessä. Pian sen jälkeen useat matemaatikot kirjoittivat Gardnerille kertomaan hänelle vastaavasta ongelmasta, jonka he olivat kuulleet rypäleiden välityksellä, ja kaikki tämä voidaan todennäköisesti jäljittää Floodin alkuperäiseen työhön.

Parhaan valinnan 1/ e -laki johtuu F. Thomas Brussista (1984).

Fergusonilla (1989) on laaja bibliografia ja hän huomauttaa, että samanlainen (mutta erilainen) ongelma oli pohdittu Arthur Cayleyssä vuonna 1875 ja jopa Johannes Kepler kauan ennen sitä.

Yhdistelmä yleistys

Sihteeriongelma voidaan yleistää tapaukseen, jossa on useita erilaisia ​​töitä. Jälleen on hakijoita satunnaisessa järjestyksessä. Kun ehdokas saapuu, hän paljastaa joukon ei -negatiivisia numeroita. Jokainen arvo määrittää hänen pätevyytensä johonkin työhön. Ylläpitäjän on paitsi päätettävä, ottaako hän hakijan vai ei, vaan jos on, hänen on myös määrättävä hänet pysyvästi johonkin työtehtävistä. Tavoitteena on löytää tehtävä, jossa pätevyyksien summa on mahdollisimman suuri. Tämä ongelma on identtinen maksimipainotuksen löytämisen kanssa reunapainotetussa kaksipuolisessa kaaviossa, jossa toisen puolen solmut saapuvat verkkoon satunnaisessa järjestyksessä. Kyseessä on siis erityinen tapaus online -kahdenvälisen täsmäytysongelman suhteen . ${\ displaystyle n}$${\ displaystyle n}$

Yleistämällä sihteeritehtävän klassista algoritmia on mahdollista saada tehtävä, jossa odotettu pätevyyksien summa on vain kerroin, joka on pienempi kuin optimaalinen (offline) tehtävä. ${\ displaystyle e}$

Katso myös

• Tehtäväongelma
• Kertoimien algoritmi
• Optimaalinen pysäytys
• Robbinsin ongelma
• Hakuteoria
• Vakaa avioliitto -ongelma

Huomautuksia

Viitteet

• Parta, JN (2006). "Uusi sihteeri-ongelma sijoituspohjaisen valinnan ja kardinaalien voittojen kanssa". Matemaattisen psykologian lehti . 50 : 58–9. doi : 10.1016/j.jmp.2005.11.003 .
• Bearden, JN; Murphy, RO; Rapoport, A. (2005). "Sihteeriongelman moniominaisuuslaajennus: Teoria ja kokeilut". Matemaattisen psykologian lehti . 49 (5): 410–425. CiteSeerX  10.1.1.497.6468 . doi : 10.1016/j.jmp.2005.08.002 .
• Bearden, J. Neil; Rapoport, Amnon; Murphy, Ryan O. (syyskuu 2006). "Peräkkäinen havainnointi ja valinta sijoituksesta riippuvilla voitoilla: kokeellinen tutkimus". Johtamistiede . 52 (9): 1437 - 1449. doi : 10.1287/mnsc.1060.0535 .
• Bruss, F. Thomas (kesäkuu 2000). "Laske kertoimet yhteen ja lopeta" . Todennäköisyyden Annals . 28 (3): 1384–1391. doi : 10.1214/aop/1019160340 .
• Bruss, F. Thomas (lokakuu 2003). "Huomautus rajoista optimaalisen pysähtymisen kertoimelle" . Todennäköisyyden Annals . 31 (4): 1859–1961. doi : 10.1214/aop/1068646368 .
• Bruss, F. Thomas (elokuu 1984). "Yhtenäinen lähestymistapa parhaiden valintaongelmien luokkaan, jossa on tuntematon määrä vaihtoehtoja" . Todennäköisyyden Annals . 12 (3): 882–889. doi : 10.1214/aop/1176993237 .

• Freeman, PR (1983). "Sihteeriongelma ja sen laajennukset: arvostelu". International Statistical Review / Revue Internationale de Statistique . 51 (2): 189–206. doi : 10.2307/1402748 . JSTOR  1402748 .
• Girdhar, Yogesh; Dudek, Gregory (2009). "Optimaalinen online -näytteenotto tai kuinka palkata parhaat sihteerit". 2009 Kanadan tietokone- ja robottinäkökonferenssi . s. 292–298. CiteSeerX  10.1.1.161.41 . doi : 10.1109/CRV.2009.30 . ISBN 978-1-4244-4211-9. S2CID  2742443 .
• Gilbert, J; Mosteller, F (1966). "Jakson suurimman tunnistaminen". Journal of the American Statistical Association . 61 (313): 35–73. doi : 10.2307/2283044 . JSTOR  2283044 .
• Gnedin, A. (1994). "Ratkaisu Googolin peliin" . Todennäköisyys Annals . 22 (3): 1588–1595. doi : 10.1214/aop/1176988613 .
• Hill, TP " Tietäen milloin lopettaa ". American Scientist , Voi. 97, 126-133 (2009). (Ranskan käännös, katso pääjuttu heinäkuun numerossa Pour la Science (2009))
• Ketelaar, Timothy; Todd, Peter M. (2001). "Ajatuksemme kehystäminen: ekologinen rationaalisuus evoluutiopsykologian vastauksena kehysongelmaan". Käsitteelliset haasteet evoluutiopsykologiassa . Kognitiivisten järjestelmien opinnot. 27 . s. 179–211. doi : 10.1007/978-94-010-0618-7_7 . ISBN 978-94-010-3890-4.
• Martin Gardner , New Mathematical Diversions from Scientific American. Simon ja Schuster, 1966, luku 3, tehtävä 3 [tulostaa uudelleen helmikuussa 1960 julkaistun alkuperäisen sarakkeensa lisäkommentteilla].
• Matsui, T; Ano, K (2016). "Alemmat rajat Brussin todennäköisyysongelmalle, jossa on useita pysäytyksiä". Operaatiotutkimuksen matematiikka . 41 (2): 700–714. arXiv : 1204.5537 . doi : 10.1287/moor.2015.0748 . S2CID  31778896 .
• Merrill R. Flood, kirje, joka on kirjoitettu vuonna 1958.
• Miller, Geoffrey F. (2001). Parittelu mieli: kuinka seksuaalinen valinta muokkasi ihmisluonnon kehitystä . Ankkurikirjat. ISBN 978-0-385-49517-2.
• Sardelis, Dimitris A .; Valahas, Theodoros M. (maaliskuu 1999). "Päätöksenteko: kultainen sääntö". American Mathematical Monthly . 106 (3): 215. doi : 10.2307/2589677 . JSTOR  2589677 .
• Seale, DA; Rapoport, A. (1997). "Peräkkäinen päätöksenteko suhteellisilla riveillä:" Sihteeriongelman " kokeellinen tutkimus ". Organisaatiokäyttäytyminen ja ihmisen päätöksentekoprosessit . 69 (3): 221–236. doi : 10.1006/obhd.1997.2683 .
• Stein, ME; Seale, DA; Rapoport, A. (2003). "Heurististen ratkaisujen analyysi parhaan valinnan ongelmaan". European Journal of Operational Research . 151 : 140–152. doi : 10.1016/S0377-2217 (02) 00601-X .
• Vanderbei, RJ (marraskuu 1980). "Väestön osajoukon optimaalinen valinta". Operaatiotutkimuksen matematiikka . 5 (4): 481–486. doi : 10.1287/moor.5.4.481 .
• Vanderbei, Robert J. (2012). "Sihteeriongelman postdoc -muunnelma" (PDF) . CiteSeerX  10.1.1.366.1718 . Cite journal vaatii |journal=( apua )

Ulkoiset linkit

• OEIS -sarja A054404 (tyttärien lukumäärä, jotka odottavat ennen poimimista sulttaanin myötäjäisongelmassa n tyttären kanssa)
• Weisstein, Eric W. "Sultanin myötäjäisten ongelma" . MathWorld .
• Neil Bearden. "Optimaalinen haku (sihteeriongelmat)" . Arkistoitu alkuperäisestä 4. tammikuuta 2017.
• Optimaalisen pysäytyksen ja sovellusten kirja, Thomas S. Ferguson