Sekretarka zatrudniająca

Jest to rozszerzenie klasycznego problemu sekretarza .

W grze o zatrudnianie masz zestaw kandydatów i porządek na temat umiejętności każdego pracownika.$\mathcal C=\{c_1,\ldots,c_N\}$

Wlog, zakładamy, że jest najbardziej wykwalifikowany, a następnie itd.$c_1$$c_2$

Kolejność, w jakiej kandydaci są wybierani losowo, jest jednolita i (oczywiście) nieznana pracodawcom.

Załóżmy teraz, że masz rynek z 2 potencjalnymi pracodawcami. W każdej rundzie nowy kandydat przeprowadza rozmowy kwalifikacyjne dla obu firm (nazwij je ). Podczas rozmowy zarówno , jak i obserwują częściowe uporządkowanie wszystkich poprzednich kandydatów, w tym bieżącego rozmówcy. Firmy następnie (niezależnie) decydują, czy zatrudnić dzisiejszego kandydata.$A,B$$A$$B$

Niestety dla , nie może konkurować finansowo z ofertą „s, więc jeśli zarówno rozszerza ofertę dla pracownika, dostaje preferencji.$B$$A$$A$

Ponadto, gdy sekretarz się podpisze, firma nie może przesłuchiwać kolejnych kandydatów, a konkurent dowiaduje się o podpisaniu umowy .

Celem każdej firmy jest zatrudnienie lepiej wykwalifikowanego kandydata (w przeciwieństwie do klasycznego problemu, w którym jedna firma chce znaleźć najlepszego sekretarza), ponieważ wiadomo, że firma z lepszym sekretarzem powinna być w stanie przejąć rynek.

Jaka jest optymalna strategia dla dużej firmy ( )?$A$

Co z mniejszą firmą ( )?$B$

Jeśli obie firmy stosują swoje strategie równowagi, jakie jest prawdopodobieństwo, że dostanie lepszego pracownika?$B$

---

W powiązanej pracy Kalai i in. omawia symetryczną wersję tego problemu, w której obie firmy mają tę samą moc przyciągania kandydatów.

W tej sytuacji prostą (symetryczną) równowagą jest zatrudnienie sekretarki, jeśli szansa, że ​​będzie lepsza niż pozostałych kandydatów, wynosi co najmniej 50%.

Jak ten wynik zmienia się w naszym otoczeniu?

Dla towarzystwa $A$/ firma / gigantyczna korporacja / „big pharma” / „THE MAN”, strategia nie zmienia się od wersji symetrycznej:

Rozważ rundę, w której prawdopodobieństwo zobaczenia tylko mniejszych kandydatów jest później $> .5$. Jeśli firma$A$ trzyma kandydata, wtedy ma szansę wygrać $> .5$. Gdyby$A$ nie zatrzymuje kandydata, a następnie towarzystwa $B$ może zatrudnić kandydata i firmę $A$ ma szansę wygrać $< .5$. Oczywiście firma$A$ zatrudniłby (i firmę $B$ będzie próbował zatrudnić) w tej sytuacji.

Dla kandydata z dokładnie wygranymi szansami $.5$, $A$ może zdecydować się na zatrudnienie, ale nie $B$ wybrałbym zatrudnić, ponieważ $B$ nigdy nie uzyska lepszych szans niż $.5$.

Jeśli firma $A$ zatrudniony zanim zobaczył kandydata z szansą na wygraną $>= .5$, to szanse na istnienie lepszego przyszłego kandydata (i stąd $B$ wygrana) byłoby $> .5$. Więc$A$ nie zatrudni, dopóki nie zobaczy kandydata na wygraną $>= .5$.

W związku z tym, $A$strategia jest identyczna jak w przypadku symetrycznym: zatrudnij pierwszego kandydata, który da szanse wygranej w wysokości $> .5$.

$B$Strategia jest zatem tworzona $A$strategia na uwadze. Oczywiście, jeśli$A$ zatrudnia (w lub) wcześniej $B$, następnie $B$Strategia polega na zatrudnieniu kolejnego kandydata, który jest lepszy niż $A$jeśli jest. Również jeśli kandydat przyjdzie z wygranymi szansami$> .5$, $B$ mimo wszystko powinienem spróbować zatrudnić $A$ spróbuje także zatrudnić (i zmusić $B$ patrzeć dalej).

Pozostaje tylko pytanie: czy jest to kiedykolwiek korzystne $B$ zatrudnić, gdy szanse na wygraną są $<= .5$. Odpowiedź brzmi tak.

Intuicyjnie powiedzmy, że jest runda, w której szanse na wygraną z kandydatem są $.5 - \epsilon$. Ponadto „prawdopodobnie będzie” (wyjaśniono później) przyszły kandydat z wygranymi szansami$> .5 + \epsilon$. Wtedy to by skorzystało$B$ wybrać wcześniejszego kandydata.

Pozwolić $d_r$ być kandydatem na rozmowę kwalifikacyjną w rundzie $r$ dla wszystkich $1 <= r <= N$.

Oficjalnie, $B$Strategia to: „zatrudnić $d_r$ jeśli takie postępowanie daje większe szanse na wygraną niż jeśli nie ". Poniżej przedstawiamy sposób obliczenia takiej decyzji.

Pozwolić $p_{r,i}$ prawdopodobieństwo wygranej po rozmowie kwalifikacyjnej i zatrudnieniu $d_r$ dany $d_r$ jest $i$najlepszy kandydat, z którym przeprowadzono wywiady. Następnie:

$p_{r,i} =$ prawdopodobieństwo, że $d_s < d_r$ dla $s > r$

$= (1-\frac{i}{r+1})(1-\frac{i}{r+2})\times ... \times (1-\frac{i}{N})$

...

$= \frac{(N-i)!r!}{(r-i)!N!}$

Szczególnie, $p_{r,i}$ jest łatwo obliczalny do stałej dokładności.

Pozwolić $P_{B,r}$ być prawdopodobieństwem, że $B$ wygrywa, biorąc pod uwagę, że żadna firma nie zatrudniała w rundach $1$ przez $r-1$.

Następnie $B$ zatrudniłby $d_r$ jeśli prawdopodobieństwo wygranej po zatrudnieniu $d_r$ jest lepszy niż $P_{B,r+1}$.

Zauważ, że $P_{B,N} = 0$, ponieważ jeśli jest to ostatnia runda, to $A$ gwarantuje zatrudnienie i $B$ nikogo nie zatrudni i nie zwolni.

Następnie w rundzie $N-1$, $B$ gwarantuje zatrudnienie i odniesie sukces, chyba że $A$wynajmuje również. Więc:

$$P_{B,N-1} = \sum_{i=1}^{N-1}\frac{1}{N-1} \left\{ \begin{array}{lcl} p_{N-1,i} & : & p_{N-1,i} < .5 \\ 1-p_{N-1,i} & : & p_{N-1,i} >= .5 \end{array} \right.$$

Co prowadzi do funkcji rekurencyjnej:

$$P_{B,r} = \sum_{i=1}^{r}\frac{1}{r} \left\{ \begin{array}{lcl} 1-p_{r,i} & : & p_{r,i} >= .5 \\ p_{r,i} & : & P_{B,r+1} < p_{r,i} < .5 \\ P_{B,r+1} & : & \text{else} \end{array} \right.$$

To całkiem oczywiste $P_{B,r}$można obliczyć ze stałą dokładnością w czasie wielomianowym. Ostatnie pytanie brzmi: „jakie jest prawdopodobieństwo$B$ wygrać? ”Odpowiedź brzmi $P_{B,1}$ i różni się w zależności od $N$.

Jeśli chodzi o pytanie, jak często $B$zdobyć? Nie obliczyłem dokładnie, ale patrzę$N$ od 1 do 100 wydaje się, że jako $N$ rośnie $B$wskaźnik wygranych zbliża się do 0,4. Ten wynik może być wyłączony, ponieważ właśnie wykonałem szybki skrypt Pythona, aby to sprawdzić i nie zwracałem szczególnej uwagi na błędy zaokrąglania liczbami zmiennymi. Może się zdarzyć, że prawdziwy twardy limit to .5.