TL;DR
This paper introduces a novel multi-agent secretary problem where agents can defer their decisions, leading to endogenous competition. They analyze two tie-breaking rules (random and ranked) and show that in equilibrium, social welfare is nearly optimal, and agents' winning probabilities converge to those in the simpler, immediate-decision model as the number of agents grows.
What Problem Does This Paper Address?
The classic secretary problem involves a single decision-maker choosing the best candidate from a sequence of arrivals, with the constraint of making an immediate and irrevocable decision. This constraint often stems from an implicit understanding of competition: if you don't take the offer now, someone else will. While previous work has explored multi-agent secretary problems, these typically retain the immediate-decision constraint.
This paper tackles a more realistic scenario: a multi-agent setting where competition is endogenous. Agents compete for awards that arrive sequentially, but crucially, they don't have to decide immediately. An award, once revealed, remains available until taken. This means an agent's strategy can involve when to select an award, not just whether to select it. The core challenge is to understand how this deferred decision-making, combined with competition, affects agent strategies, equilibrium outcomes, and overall social welfare.
Methods
The authors model this as a game with $k$ agents and $n$ awards. They consider two primary tie-breaking mechanisms when multiple agents select the same award:
- Random Tie-Breaking: Ties are broken uniformly at random.
- Ranked Tie-Breaking: Agents have a pre-defined global ranking, and ties are broken in favor of the higher-ranked agent.
For both scenarios, they analyze Subgame Perfect Equilibria (SPE), which are strategy profiles that are Nash equilibria in every possible subgame of the game.
- Random Tie-Breaking: They characterize the SPEs and show that a simple time-threshold strategy (where agents decide to pick an award only after a certain time point) guarantees each agent a minimum winning probability. They then prove that the social welfare in the SPE where all agents play this strategy is at least a fraction of the optimal social welfare.
- Ranked Tie-Breaking: They show that as the number of agents ($k$) increases, the winning probabilities of agents in their non-immediate selection model converge to their winning probabilities in the immediate-selection model. They also provide a full characterization of equilibria for the specific case of a 3-agent game.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Endogenous Competition: The ability to defer decisions, rather than being forced by rules, becomes a strategic element. Agents might wait longer to gather more information, but risk another agent taking the award.
- Near-Optimal Social Welfare: Despite competition and deferred decisions, the authors demonstrate that the expected social welfare in equilibrium is remarkably close to the optimal possible welfare, especially under random tie-breaking.
- Convergence to Immediate Decisions: For ranked tie-breaking, as the number of competing agents grows, the strategic advantage of deferring decisions diminishes. Agents' winning probabilities in this model approach those of the simpler, immediate-decision secretary problem. This highlights how intense competition can drive behavior towards immediate action.
- Simple Strategies Suffice: For random tie-breaking, simple time-threshold strategies are shown to be optimal for guaranteeing individual winning probabilities and are central to the SPE.
Key Results
- Random Tie-Breaking:
- Characterized SPEs using time-threshold strategies.
- Showed that the expected social welfare in SPE is at least $\frac{1}{k}$ of the sum of the top $k$ awards.
- Ranked Tie-Breaking:
- Proved that for any agent $i$, their winning probability in the non-immediate model converges to their winning probability in the immediate model as the number of agents $k \to \infty$.
- Fully characterized the equilibria for the 3-agent game, with agent 1 (highest ranked) winning with probability $\approx 0.38$ and agents 2 and 3 winning with probability $\approx 0.31$.
Limitations and Future Work
- Ranked Tie-Breaking Generalization: While the 3-agent case is fully characterized, extending the equilibrium characterization to an arbitrary number of agents ($k > 3$) for ranked tie-breaking remains an open problem.
- Additional Problems: The authors suggest exploring competition in other optimal stopping problems like prophet and pandora box settings.
- Varied Tie-Breaking: Investigating competition under non-uniform random tie-breaking or rules that allow splitting awards is proposed.
- Feasibility Constraints: Extending the model to include additional constraints, such as agents being able to select up to $k$ awards or matroid constraints, is a natural next step.
- Objective Functions: Exploring alternative objective functions beyond maximizing the probability of winning the highest ranks would be valuable.
Summary updated