From Signaling to Interviews in Random Matching Markets

Many two-sided labor markets conduct interviews before matching. The growing number of interviews in medical residency markets has increased demand for signaling mechanisms, where applicants send limited signals to communicate interest. We study the role of signaling mechanisms to reduce interviews in centralised random matching markets where initial preferences are refined through interviews. Agents can only match with those they interview. For the market to clear, we focus on perfect interim stability: no pair of agents—even if they never interviewed each other—prefers each other to their assigned partners under their interim preferences. A matching is almost interim stable if it is perfect interim stable after removing a vanishingly small fraction of agents.

We analyse signaling mechanisms in random matching markets with $n$ agents where agents on the short side, long side, or both sides signal their top $d$ preferred partners. The interview graph connects pairs where at least one party signaled the other. We reveal a fundamental trade-off between almost and perfect interim stability. For almost interim stability, $d=\omega(1)$ signals suffice: short-side signaling is always effective, whereas long-side signaling is effective only when the market is weakly imbalanced, i.e., when any size difference between the two sides becomes negligible as the market grows. For perfect interim stability, at least $d=\Omega(\log^2 n)$ signals are necessary, and short-side signaling becomes crucial in any imbalanced market. We establish that truthful signaling is a Bayes-Nash equilibrium and extend our analysis to markets with hierarchical structure. Moreover, we develop a message-passing algorithm that efficiently determines the matching outcome by leveraging local neighborhood structures.