Секретарь найма игры

9

Это расширение классической проблемы секретаря .

В игре найма у вас есть набор кандидатов C={c1,,cN}и приказ о том, насколько квалифицирован каждый работник.

Wlog, мы предполагаем, что c1 самый опытный, а затем c2, так далее.

Порядок проведения собеседования с кандидатами выбирается случайным образом, и он (очевидно) неизвестен работодателям.

Теперь предположим, что у вас есть рынок с 2 потенциальными работодателями. В каждом раунде новый кандидат проводит собеседование для обеих компаний (позвоните имA,B). Во время интервью обаA а также Bсоблюдать частичное упорядочение всех прошлых кандидатов, в том числе текущего собеседника. Затем фирмы (независимо) решают, нанять ли сегодняшнего заявителя.

К сожалению для B, он не может конкурировать в финансовом отношении с Aпредложение, так что если оба расширяют предложение для работника, A получает предпочтение.

Кроме того, после подписания секретарем компания не может проводить собеседование с другими кандидатами, и конкурент узнает о подписании .

Цель каждой компании состоит в том, чтобы нанять более квалифицированного кандидата (в отличие от классической проблемы, когда отдельная компания желает найти лучшего секретаря), поскольку известно, что компания с лучшим секретарем должна иметь возможность взять на себя рынок.

Какова оптимальная стратегия в качестве большой фирмы (A)?

Как насчет небольшой компании (B)?

Если обе компании разрабатывают свои стратегии равновесия, какова вероятность B gets the better worker?


В связанной работе Kalai et al. обсуждается симметричная версия этой проблемы, где обе компании имеют одинаковую силу привлечения кандидатов.

В этом случае простое (симметричное) равновесие заключается в том, что вы нанимаете секретаря, если вероятность того, что она окажется лучше остальных кандидатов, составляет не менее 50%.

Как этот результат изменяется в наших настройках?

RB
источник

Ответы:

8

Для компании A/ фирма / гигантская корпорация / "большая фарма" / "человек", стратегия не отличается от симметричной версии:

Рассмотрим раунд, где вероятность того, что после этого будут видны только меньшие кандидаты, >.5, Если компанияA держит кандидата, значит у него есть шанс на победу >.5, ЕслиA не держит кандидата, тогда компания B может нанять кандидата и компанию A has a chance of winning <.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ϵ, Кроме того, «вероятно» будет (объяснено позже) будущий кандидат с вероятностью выигрыша>.5+ϵ, Тогда было бы полезноB выбрать более раннего кандидата.

Позволять dr быть кандидатом на собеседование в туре r для всех 1<=r<=N,

Официально, BСтратегия такова: "нанять dr если это дает лучшие шансы на выигрыш, чем если бы не ". Ниже показано, как мы рассчитываем такое решение.

Позволять pr,i вероятность выигрыша после собеседования и найма dr данный dr это iЛучший кандидат на собеседование. Затем:

pr,i= вероятность того, что ds<dr за s>r

=(1ir+1)(1ir+2)×...×(1iN)

...

=(Ni)!r!(ri)!N!

Следует отметить, что pr,i легко вычисляется с постоянной точностью.

Позволять PB,r быть вероятностью того, что B выигрывает, учитывая, что ни одна компания не нанята в раундах 1 через r1,

затем B наймет dr если вероятность выигрыша после найма dr лучше, чем PB,r+1.

Note that PB,N=0, because if it is the last round, then A is guaranteed to hire and B will not hire anyone and loose.

Then, in round N1, B is guaranteed to try to hire and will succeed unless A hires as well. So:

PB,N1=i=1N11N1{pN1,i:pN1,i<.51pN1,i:pN1,i>=.5

Which leads to the recursive function:

PB,r=i=1r1r{1pr,i:pr,i>=.5pr,i:PB,r+1<pr,i<.5PB,r+1:else

It's pretty obvious that PB,r can be calculated to constant accuracy in polynomial time. The final question is: "what is the probability of B winning?" The answer is PB,1 and varies with N.

As to the question of how often does B win? I have not calculated exactly, but looking at N from 1 to 100, it appears that as N grows, that B's winning rate approaches .4 or so. This result may be off as I just did a quick python script to check and did not pay close attention to rounding errors with floating numbers. It may very well end up that the real hard limit is .5.

bbejot
источник