Hiring under uncertainty and competition : a work on various extensions of the secretary problem

In this dissertation, we study different online hiring problems related to 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 study several extensions. For many of them, we work on an infinite arrival regime. This allows us to apply a lemma we prove 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 three 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. For employers seeing the same set of candidates, but in different order, we compute a Nash Equilibria for two employers. Finally, 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. Finally, we study oblivious Online Contention Resolution Schemes (OCRSs) for matroids. This problem has an interesting link to the Matroid Secretary Conjecture. We provide an optimal 1/e-selectable oblivious OCRS for selecting a single item. We also prove non-existence of constant-selectable oblivious OCRSs for general matroids.