Incentive Compatibility of Large Centralized Matching Markets

This paper discusses the strategic manipulation of stable matching mechanisms. We provide a model of a two-sided matching market, in which a firm hires a worker, and each of them receives non-transferable utility. Assuming that the utilities are randomly drawn from underlying distributions, we measure the likelihood of differences in utilities from different stable matchings. Our key finding is that in large markets, most agents are close to being indifferent among partners in different stable matchings. Specifically, as the number of firms and workers becomes large, the expected proportion of firms and workers whose utilities from all stable matchings are within an arbitrarily small difference of one another converges to one. It is known that the utility gain by manipulating a stable matching mechanism is limited by the difference between utilities from the most and the least preferred stable matchings. Thus, the finding also implies that the expected proportion of agents who may obtain a significant utility gain from manipulation vanishes in large markets. This result reconciles successful stable mechanisms in practice with the theoretical concerns about strategic manipulation.