Back to search

University of British Columbia

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

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy - PhD
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Turkieltaub Melo, Abner
Contributors dc:contributor
  • Shepherd, F. Bruce (Frederick Bruce)
  • Fu, Hu

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/91958

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Turkieltaub Melo, Abner. Hiring under uncertainty and competition : a work on various extensions of the secretary problem. doctoral thesis, University of British Columbia, 2025. http://hdl.handle.net/2429/91958