An improved bound to manipulation in large stable matches

What is it about?

Many cities across the United States rely on centralized matching mechanisms to allocate students to public schools—examples include New York City, Boston, Seattle, Cambridge, Charlotte, Denver, Minneapolis, and Columbus. Globally, centralized matching systems are widely used for university admissions (e.g., Brazil, Chile, China, Turkey) and job placement programs (e.g., the US National Residency Matching Program, Brazil CPNU matching program, and Turkey teacher assignment program). In these systems, students submit ranked preferences for schools, while schools submit their rankings of students and number of available vacancies. A centralized algorithm then processes these inputs to determine the final allocation of students to schools (or candidates to jobs). Due to their desirable properties, stable matching mechanisms are commonly employed in these settings. However, a well-known limitation of stable matching mechanisms is that they cannot be simultaneously strategy-proof for both students and schools. Even when implementing the student-optimal stable match—which is strategy-proof for students—schools may have incentives to misreport their preferences or underreport available spots to secure more favorable matches. In some cases, institutions might even engage in early, informal agreements that could destabilize the market. In this article, I show that while these strategic incentives are theoretically possible, they vanish as the market grows arbitrarily large under stable matching mechanisms. This result builds on the findings of Kojima and Pathak (2009) regarding vanishing manipulability in large stable mechanisms. My analysis, however, relaxes one of their key assumptions: the need for markets to have a significant number of unfilled positions at equilibrium. As a result, my findings are applicable to highly competitive markets where nearly all vacancies are filled. Additionally, the upper bound I establish for the incentives to manipulate the mechanism converges to zero at a much faster rate than previously documented in the literature. These findings provide stronger evidence that, although stable matching mechanisms are not entirely strategy-proof, in practice, they behave as if they were effectively strategy-proof in large markets.

Featured Image

Photo by Nathan Dumlao on Unsplash

Photo by Nathan Dumlao on Unsplash

Why is it important?

The manipulation of college vacancies or attempts to form pre-arranged matches are strategies that could generate inefficiencies in the market. However, the results derived in this article demonstrate that these incentives vanish in large stable matching markets. Therefore, market makers should consider implementing stable matching mechanisms more often in practical settings.

Perspectives