Efficient Interview Scheduling for Stable Matching

A team of computer scientists—Moshe Babaioff, Rotem Gil, and Assaf Romm—has published a significant paper titled 'Efficient Interview Scheduling for Stable Matching' on arXiv. The research tackles a core limitation in classic stable matching theory, which assumes agents have complete and known preferences. In real-world markets like job interviews or medical residency matches, preferences are often uncertain and must be revealed through costly, time-consuming interviews. The authors formalize the goal of reaching an 'interim-stable matching,' where all matched pairs have interviewed and agents use expected utilities for unknown values, while minimizing both the total number of interviews and the number of scheduling rounds.

The paper introduces two novel adaptive algorithms. The first is a sequential algorithm proven to require only 2 interviews per agent in expectation under the common case where agents are ex-ante indifferent. The authors complement this with a lower-bound proof showing that any algorithm performing fewer than 2 interviews per agent cannot guarantee interim-stability. Their second, more powerful contribution is a hybrid algorithm that begins by scheduling some interviews in parallel before continuing sequentially. This hybrid approach dramatically reduces coordination time, requiring only a polylogarithmic expected number of rounds while still maintaining the efficient ~2 interviews per agent. Critically, both algorithms guarantee that running the standard Deferred-Acceptance mechanism on the gathered preference data will yield a final stable matching. This work provides a rigorous, practical framework for designing efficient two-sided matching markets where preference discovery is an explicit, costly part of the process.