Efficiency and Stability in Large Matching Markets, by Che and Tercieux in the JPE

Efficiency and Stability in Large Matching Markets

Yeon-Koo Che

Columbia University

Olivier Tercieux

Paris School of Economics and Centre National de la Recherche Scientifique

ONLINE: Aug 30, 2019

Abstract

We study efficient and stable mechanisms in matching markets when the number of agents is large and individuals’ preferences and priorities are drawn randomly. When agents’ preferences are uncorrelated, then both efficiency and stability can be achieved in an asymptotic sense via standard mechanisms such as deferred acceptance and top trading cycles. When agents’ preferences are correlated over objects, however, these mechanisms are either inefficient or unstable, even in an asymptotic sense. We propose a variant of deferred acceptance that is asymptotically efficient, asymptotically stable, and asymptotically incentive compatible. This new mechanism performs well in a counterfactual calibration based on New York City school choice data.

"...we develop a new mechanism, called DA with circuit breaker (DACB), that is both asymptotically efficient and asymptotically stable. This mechanism modifies DA to prevent participants from competing excessively. Specifically, all agents are ordered in some manner (for instance, at random), and following that order, each agent applies one at a time to the best object that has not yet rejected him.5 The proposed object then accepts or rejects the applicant, much as in standard DA. If, at any point, an agent applies to an object that holds an application, one agent is rejected, and the rejected agent in turn applies to the best object among those that have not rejected him. This process continues until an agent makes a certain “threshold” number κ of offers for the first time. The stage is terminated at that point, and all tentative assignments up to that point become final. The next stage then begins with the agent who was rejected at the end of the last stage applying to the best remaining object and the number of proposals for that agent being reset to zero. The stages proceed in this fashion until no rejection occurs.

"This “staged” version of DA resembles standard DA except for one crucial difference: the mechanism periodically terminates a stage and finalizes the tentative assignment up to that point. The event triggering the termination of a stage is an agent reaching a threshold number of offers. Intuitively, the mechanism activates a “circuit breaker” whenever the competition “overheats” to such an extent that an agent finds himself at the risk of losing an object he ranks highly to an agent who ranks it relatively lowly (more precisely, above the threshold rank). This feature ensures that each object assigned at each stage goes to an agent who ranks it relatively highly among the objects available at that stage."