The Price of Decentralized Matching
Tawfik Ali and Mustafa Oguz Afacan (MBZUAI, Sabancı University)
When should a job market stop hiring on its own and use a clearinghouse? Count the crossings.
Abstract
In a benchmark market in which all workers agree on how to rank vacancies and all vacancies agree on how to rank workers, decentralized hiring need not follow those rankings. We ask when a centralized clearinghouse that collects participants' rankings and assigns the matches should replace decentralized hiring. One rule values blocking pairs (a worker and vacancy who prefer each other to their assigned partners), while another values the resulting loss in total match output, which we call surplus.
Below a critical cost per position, each rule centralizes at and above a threshold size. Expected surplus loss per expected blocking pair links the rules and rises with randomness in hiring. We prove that the first rule is unchanged on a class of preferences differing on both sides. The surplus loss formula is due to Mallows (1957).
- Blocking pairs
- 11
- Expected
- 12.7
- Surplus lost
- 24
A crossing is a blocking pair. Expected: nq/(1−q) − Σ iqⁱ/(1−qⁱ).