In Which Matching Markets Do Costly Compatibility Inspections Lead to a Deadlock?

A key feature of many real-world matching markets is congestion; that is, market participants struggle to find match partners. We characterize congestion in a model of random matching markets where an agent pair must perform a mutual inspection to verify compatibility prior to matching with each other. Motivated by the notion of regret-free stability, we assume an agent pair is only willing to perform a mutual inspection if they are each other’s current favorite agent, which guarantees a match if the inspection finds compatibility. We ask when, in large random two-sided markets, will information deadlocks arise in which many agents delay inspections indefinitely awaiting a match guarantee. The market consists of N women and $\alpha N$ men. We characterize the existence and size of information deadlock as a function of the men-to-women ratio $\alpha$, women’s average consideration-set size K, and an inspection’s success probability p, as the number of women N grows. We find a phase transition from a deadlock-free regime (where a vanishingly small fraction of agents is stuck waiting) to the information deadlock regime as K increases, $\alpha$ decreases, or p decreases. Several market-design insights emerge from our characterization. For example, the level of market connectivity K that maximizes the number of matches formed is the level that places the market at the phase boundary between the deadlock-free regime and the deadlock regime. Vertical differentiation between agents reduces deadlock, as does a willingness by agents to inspect with their top k current favorites for $k>1$. Our analysis is inspired by the machinery of message passing and density evolution from statistical physics, and the emergence of deadlock corresponds to a branching process of preferred partners becoming supercritical.

Funding: This work was supported by the National Science Foundation [Grant 1653477], the National Natural Science Foundation of China [Grants 72401245 and 72192805], and the Guangdong Key Lab of Mathematical Foundations for Artificial Intelligence.

Supplemental Material: All supplemental materials, including the code, data, and files required to reproduce the results, are available at https://doi.org/10.1287/opre.2022.0630.