Online Stochastic Matching

Designing Efficient Interview Graphs for Interim Stable Matchings: A Signaling Approach

3

Sep 24, 2024, 11:15 AM

45m

Amphithéâtre Schwartz (Institut de Mathématiques de Toulouse (IMT))

Morning Session

Speaker

Sophie Yu (University of Pennsylvania)

Description

In many two-sided matching markets agents initially engage in costly interviews in order to refine their interim preferences. We study how signaling mechanisms can reduce the number of interviews in random markets. We are interested in interim stability, which expands the notion of stability to ensure that no two agents regret not interviewing with each other. The final match is almost interim stable if it is interim stable after removing a vanishing small fraction of agents.

For single-tiered markets, we study the impact of short-side (resp. long-side, both-side) signaling, where agents from short-side (resp. long-side, both-side) of the market signal their top $d$ preferred candidates. The interview graphs are formed by including all pairs where at least one party has signaled to the other. When $d=\omega (1)$, we show that short-side signaling leads to almost interim stable matchings for every stable matching. Long-side signaling is effective in weakly imbalanced markets but fails in strongly imbalanced markets. We also demonstrate the failure of both-side signaling when the impact of interviews is negligible. When $d\ge \mathrm{\Omega }({\log }^{2}n)$, short-side signaling achieves interim stability, while long-side signaling fails in imbalanced markets. We extend our results to multi-tiered markets where a proposed signaling mechanism achieves interim stability across tiers, and identify conditions for truthful signaling.

Our analysis for sparse interview markets develops a message-passing algorithm that efficiently determines interim stability and match outcomes by leveraging their local neighborhood structure.

Presentation materials

Slides - Sophie Yu.pdf