Hiring under uncertainty and competition: variations of the secretary problema.

Abstract:

In this talk, we study some variations of the Secretary Problem. In the Secretary Problem, an employer sees a sequence of candidates. Each time a new candidate arrives, the employer makes an irrevocable choice on whether to hire based only on the relative ranking of the candidates seen so far. The employer tries to maximize the probability of hiring the best. It is known that the optimal strategy hires the best with probability 1/e. We consider an infinite arrival regime. This allows us to apply a lemma characterizing the number of “promising candidates” in any given time interval. For a single employer trying to hire k candidates, we produce a tight analysis of some simple strategies. We also study in detail the case k = 2. We derive an optimal algorithm under the objective known as “probability-competitiveness”. We also study the case in which the two selected candidates must be independent in a given matroid. For multiple employers we consider two models. First, for employers seeing the same sequence of candidates, we compute Nash Equilibria for two and three employers. We also derive general properties of the Nash Equilibria for any number of employers. Then, we consider employers with different sets of candidates, competing for whom hires first while trying to get their best candidate. As motivation, imagine different research groups within the same department trying to hire someone in their area. We show that without any regulation, competition pushes employers to hire too early, making extremely unlikely the hiring of a top candidate. We also compute the social optimum and propose different regulations that incentivize employers to align with the social optimum.

Posted on Mar 24, 2026 in ACGO, Seminars