Sekretaris mempekerjakan permainan

Ini merupakan perpanjangan dari masalah sekretaris klasik .

Dalam permainan perekrutan, Anda memiliki satu set kandidat , dan memesan keterampilan masing-masing pekerja. $\mathcal C=\{c_1,\ldots,c_N\}$

Wlog, kami menganggap bahwa adalah yang paling terampil, diikuti oleh , dll. $c_1$ $c_2$

Urutan di mana kandidat diwawancarai dipilih secara acak dan acak (tidak diketahui) oleh pemberi kerja.

Sekarang anggaplah Anda memiliki pasar dengan 2 pengusaha potensial. Di setiap babak, seorang kandidat baru mewawancarai kedua perusahaan (sebut mereka ). Selama wawancara, baik dan mengamati urutan sebagian dari semua kandidat masa lalu, termasuk yang diwawancarai saat ini. Perusahaan kemudian (secara independen) memutuskan apakah akan mempekerjakan pelamar hari ini. $A,B$ $A$ $B$

Sayangnya untuk , tidak dapat bersaing secara finansial dengan menawarkan 's, sehingga jika kedua meluas tawaran untuk pekerja, mendapat preferensi. $B$ $A$ $A$

Juga, sekali seorang sekretaris menandatangani, perusahaan tidak boleh mewawancarai kandidat lebih lanjut dan pesaing mengetahui tentang penandatanganan .

Tujuan dari setiap perusahaan adalah untuk merekrut kandidat berkemampuan yang lebih baik (sebagai lawan dari masalah klasik, di mana satu perusahaan ingin menemukan sekretaris terbaik), karena diketahui bahwa perusahaan dengan sekretaris yang lebih baik harus dapat mengambil alih pasar.

Apa strategi optimal sebagai perusahaan besar ( )? $A$

Bagaimana dengan perusahaan kecil ( )? $B$

Jika kedua perusahaan memainkan strategi keseimbangan mereka, berapakah probabilitas mendapatkan pekerja yang lebih baik? $B$

Dalam karya terkait , Kalai et al. membahas versi simetris dari masalah ini, di mana kedua perusahaan memiliki kekuatan yang sama untuk menarik kandidat.

Dalam pengaturan ini, keseimbangan sederhana (simetris) adalah Anda menyewa seorang sekretaris jika peluang dia menjadi lebih baik daripada kandidat yang tersisa setidaknya 50%.

Bagaimana hasil ini berubah dalam pengaturan kami?

ds.algorithms gt.game-theory BPR
sumber

$A$

$> .5$ $A$ $> .5$ $A$ $B$ $A$ $< .5$ $A$ $B$

$.5$ $A$ $B$ $B$ $.5$

$A$ $>= .5$ $B$ $> .5$ $A$ $>= .5$

$A$ $> .5$

$B$ $A$ $A$ $B$ $B$ $A$ $> .5$ $B$ $A$ $B$

$B$ $<= .5$

$.5 - \epsilon$ $> .5 + \epsilon$ $B$

$d_r$ $r$ $1 <= r <= N$

$B$ $d_r$

$p_{r,i}$ $d_r$ $d_r$ $i$

$p_{r,i} =$ $d_s < d_r$ $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!}$

$p_{r,i}$

$P_{B,r}$ $B$ $1$ $r-1$

$B$ $d_r$ $d_r$ $P_{B,r+1}$

$P_{B,N} = 0$ $A$ $B$

$N-1$ $B$ $A$

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

$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.$

Yang mengarah ke fungsi rekursif:

P_{B, r} = \sum_{i = 1}^{r} \frac{1}{r} {\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} & : & else \end{array}

$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.$

$P_{B,r}$ $B$ $P_{B,1}$ $N$

$B$ $N$ $N$ $B$

bbejot
sumber

Sekretaris mempekerjakan permainan

Jawaban: