Abstract
This paper extends the classic secretary problem to a multi-employer competitive setting using a novel edge arrival model. Unlike traditional models where all employers observe candidates simultaneously, the edge arrival model captures decentralized markets where candidate-employer interactions occur independently. We demonstrate that this model leads to unique, symmetric Nash equilibria for both adaptive and non-adaptive strategies. Furthermore, we provide a polynomial-time algorithm to calculate optimal hiring thresholds and show that the competitive market remains highly efficient, with a Price of Anarchy near unity.
Introduction
The classic secretary problem is a foundational challenge in optimal stopping theory. An employer interviews $n$ candidates in a random order and must decide immediately whether to hire or pass, with the goal of selecting the single best candidate. The optimal solution is the well-known $1/e$ rule: reject the first 37% of candidates to establish a baseline, then hire the first candidate who surpasses all previous ones.
While previous research has expanded this problem to include multiple employers, these studies typically rely on a vertex arrival model. In such models, every employer observes the same candidate at the same time. This fails to reflect the reality of decentralized markets—such as job hunting or dating—where candidates meet different employers at different times. This paper addresses this gap by introducing the edge arrival model, where candidate-employer pairs are selected randomly at each time step, creating independent arrival sequences for each competitor.
The Edge Arrival Model
The authors model the market as a complete bipartite graph between $k$ employers and $n$ candidates. In the continuous-time limit (as $n \to \infty$), the arrival of edges (interviews) follows a uniform distribution over the interval $[0, 1]$. This independence is the defining characteristic of the model: an employer’s sequence of candidates is distinct from their competitors', though they are all competing for the same global "best" candidate.
Strategic Framework
The paper investigates two primary classes of strategies:
- Adaptive Strategies: Employers observe when a competitor makes a hire and exits the game. This allows remaining employers to dynamically update their hiring thresholds based on the reduced competition.
- Non-adaptive Strategies: Employers must commit to a single threshold time at the start of the process and cannot deviate, regardless of the actions taken by others.
To solve for Nash equilibria in these settings, the authors derive recursive differential equations representing conditional winning probabilities. They introduce Algorithm 1, a polynomial-time algorithm with $O(k^5)$ complexity, to compute optimal thresholds for any number of employers $k$.
Key Insights and Equilibrium Analysis
Symmetry and Independence
A significant finding of this research is that the edge arrival model naturally yields symmetric pure Nash equilibria. In vertex arrival models, equilibria are often asymmetric, with one employer forced into a more aggressive or passive role. Here, because arrival sequences are independent and identically distributed, all employers adopt the same threshold logic.
The Threshold Cascade
For adaptive players, the equilibrium is characterized by a "threshold cascade" $(r^*_k, r^*_{k-1}, \dots, r^*_1)$. When $k$ players are active, they all utilize the threshold $r^*_k$. The moment one player successfully hires a candidate and leaves the market, the remaining $k-1$ players immediately shift to the next threshold, $r^*_{k-1}$.
As competition increases (higher $k$), the equilibrium threshold $r^*(k)$ decreases at a rate of approximately $1/k$. This indicates that in a crowded market, employers must begin selecting candidates much earlier to preempt their rivals.
Calculated Thresholds
The authors provide specific values for the adaptive equilibrium thresholds:
- $k=1$: $r^*_1 \approx 0.36788$ (recovering the classic $1/e$ result)
- $k=2$: $r^*_2 \approx 0.29574$
- $k=3$: $r^*_3 \approx 0.24006$
For the non-adaptive case with two players, the unique Nash equilibrium occurs at $r^* \approx 0.29533$, a slightly more aggressive threshold than the adaptive counterpart.
Market Efficiency: The Price of Anarchy
To evaluate the efficiency of the competitive equilibrium, the authors calculate the Price of Anarchy (PoA)—the ratio of social welfare in equilibrium to the social optimum. For two players, the PoA is approximately 0.985. This suggests that decentralized competition in the edge arrival model is remarkably efficient; the probability that the best candidate is hired is nearly as high in a competitive market as it would be under a centralized planner. Additionally, the probability that the best candidate remains "unemployed" (not hired by anyone) is shown to be at most $1/k$.
Limitations and Future Directions
While the paper provides a robust framework for competitive optimal stopping, it assumes uniform preferences, meaning all employers rank the candidates identically. Real-world scenarios often involve heterogeneous preferences where different employers value different skill sets. Furthermore, while symmetry was proven for two non-adaptive players, the formal proof for $k > 2$ non-adaptive players remains an open mathematical question. Future research could also explore the Price of Anarchy for the adaptive case to see if the dynamic updating of thresholds further improves social welfare.
Summary updated