Jogo de contratação de secretário

Esta é uma extensão do problema clássico da secretária .

No jogo de contratação, você tem um conjunto de candidatos e solicita a qualificação de cada trabalhador. $\mathcal C=\{c_1,\ldots,c_N\}$

Wlog, assumimos que é o mais qualificado, seguido por etc. $c_1$ $c_2$

A ordem em que a entrevista dos candidatos é escolhida uniformemente aleatoriamente e é (obviamente) desconhecida pelos empregadores.

Agora, suponha que você tenha um mercado com 2 potenciais empregadores. A cada rodada, um novo candidato está entrevistando as duas empresas (chame-as de ). Durante a entrevista, e observam a ordem parcial de todos os candidatos anteriores, incluindo o atual entrevistado. As empresas então (independentemente) decidem se devem contratar o candidato de hoje. $A,B$ $A$ $B$

Infelizmente para , ele não pode competir financeiramente com oferta 's, por isso, se ambos se estende uma oferta para um trabalhador, fica preferência. $B$ $A$ $A$

Além disso, uma vez que o secretário assine, a empresa não poderá entrevistar outros candidatos e o concorrente tomar conhecimento da assinatura .

O objetivo de cada empresa é contratar o candidato mais qualificado (em oposição ao problema clássico, em que uma única empresa deseja encontrar a melhor secretária), pois é sabido que a empresa com a melhor secretária deve poder assumir o cargo. mercado.

Qual é a estratégia ideal para a grande empresa ( )? $A$

E a empresa menor ( )? $B$

Se as duas empresas adotam suas estratégias de equilíbrio, qual é a probabilidade de obter o melhor trabalhador? $B$

Em um trabalho relacionado , Kalai et al. discute a versão simétrica desse problema, em que ambas as empresas têm o mesmo poder de atrair candidatos.

Nesse cenário, o equilíbrio simples (simétrico) é que você contrata uma secretária se a chance de ela ser melhor que os demais candidatos é de pelo menos 50%.

Como esse resultado muda em nossa configuração?

ds.algorithms gt.game-theory RB
fonte

Para a empresa / a empresa / empresa gigante / "big pharma" / "THE MAN", a estratégia não muda da versão simétrica: $A$

Considere uma rodada em que a probabilidade de ver apenas candidatos menores a partir de então seja . Se a empresa mantiver o candidato, ela poderá ganhar . Se não mantiver o candidato, a empresa poderá contratá-lo e a empresa terá chance de ganhar . Portanto, obviamente, a empresa contrataria (e a empresa tentaria contratar) nessa situação. $> .5$ $A$ $> .5$ $A$ $B$ $A$ $< .5$ $A$ $B$

Para um candidato com chances de ganhar exatamente , pode ou não optar por contratar, mas escolheria contratar, porque nunca pode obter chances melhores que . $.5$ $A$ $B$ $B$ $.5$

Se a empresa contratada antes de ver um candidato com chance de ganhar , as chances de um futuro candidato melhor existir (e, portanto, ganhar ) seriam . Portanto, não contratará até ver um candidato com chances de ganhar . $A$ $>= .5$ $B$ $> .5$ $A$ $>= .5$

Portanto, 's estratégia é idêntico ao caso simétrico: contratar o primeiro candidato que os rendimentos ganhando chances de . $A$ $> .5$

'estratégia de s, então, é formado com ' estratégia de s em mente. Obviamente, se contratar (at ou) antes de ,a estratégia de é contratar o próximo candidato que seja melhor que , se houver. Além disso, se um candidatoaparecercom chances de ganhar , deve tentar contratar, mesmo que também tente contratar (e force a continuar procurando). $B$ $A$ $A$ $B$ $B$ $A$ $> .5$ $B$ $A$ $B$

A única questão que resta é: é sempre benéfico para contratar quando as chances de ganhar são . A resposta é sim. $B$ $<= .5$

Intuitivamente, digamos que haja uma rodada em que as chances de ganhar com o candidato sejam . Além disso, "é provável que exista" (explicado mais adiante) um futuro candidato com chances de ganhar . Então, beneficiaria escolher o candidato anterior. $.5 - \epsilon$ $> .5 + \epsilon$ $B$

Deixe ser o candidato entrevistando em rodada para todos . $d_r$ $r$ $1 <= r <= N$

Oficialmente, a estratégia de é: "contratar se isso resultar em melhores chances de ganhar do que se não". A seguir, mostramos como calculamos essa decisão. $B$ $d_r$

Deixe ser a probabilidade de ganhar depois de entrevistar e contratar dada é o th melhor candidato entrevistado. Então: $p_{r,i}$ $d_r$ $d_r$ $i$

probabilidade de que para $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!}$

Notavelmente, é facilmente computável com precisão constante. $p_{r,i}$

Seja a probabilidade de vencer, já que nenhuma empresa contratou nas rodadas a . $P_{B,r}$ $B$ $1$ $r-1$

Então contrataria se a probabilidade de ganhar após contratar for melhor que . $B$ $d_r$ $d_r$ $P_{B,r+1}$

Note-se que , porque se for a última rodada, então é garantido para contratar e não vai contratar ninguém e perder. $P_{B,N} = 0$ $A$ $B$

Então, na rodada , é garantido para tentar contratar e terá sucesso, a menos que contrate. Então: $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.$

O que leva à função recursiva:

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

É bastante óbvio que pode ser calculado a precisão constante em tempo polinomial. A pergunta final é: "qual é a probabilidade de ganhar?" A resposta é e varia com . $P_{B,r}$ $B$ $P_{B,1}$ $N$

Quanto à questão de quantas vezes vence? Não calculei exatamente, mas olhando de 1 a 100, parece que à medida que cresce, a taxa de vitórias de aproxima de 0,4 ou mais. Esse resultado pode estar desativado, pois eu apenas fiz um script python rápido para verificar e não prestei muita atenção aos erros de arredondamento com números flutuantes. Pode muito bem acabar que o limite real é 0,5. $B$ $N$ $N$ $B$

bbejot
fonte

Jogo de contratação de secretário

Respostas: