Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper studies bandit learning in two-sided matching markets where agents and firms conduct interviews to learn preferences. The authors introduce strategic deferral, allowing firms to delay hiring decisions and recover from suboptimal matches, and model interviews as low-cost hints that reveal partial preference information. They develop novel algorithms for centralized and decentralized settings that achieve time-independent regret, improving upon logarithmic regret bounds for learning stable matchings without interviews.
Firms can strategically "defer" hiring decisions to recover from early mistakes, enabling surprisingly effective decentralized learning in two-sided matching markets with uncertain preferences.
Two-sided matching markets rely on preferences from both sides, yet it is often impractical to evaluate preferences. Participants, therefore, conduct a limited number of interviews, which provide early, noisy impressions and shape final decisions. We study bandit learning in matching markets with interviews, modeling interviews as \textit{low-cost hints} that reveal partial preference information to both sides. Our framework departs from existing work by allowing firm-side uncertainty: firms, like agents, may be unsure of their own preferences and can make early hiring mistakes by hiring less preferred agents. To handle this, we extend the firm's action space to allow \emph{strategic deferral} (choosing not to hire in a round), enabling recovery from suboptimal hires and supporting decentralized learning without coordination. We design novel algorithms for (i) a centralized setting with an omniscient interview allocator and (ii) decentralized settings with two types of firm-side feedback. Across all settings, our algorithms achieve time-independent regret, a substantial improvement over the $O(\log T)$ regret bounds known for learning stable matchings without interviews. Also, under mild structured markets, decentralized performance matches the centralized counterpart up to polynomial factors in the number of agents and firms.