Olivier Tercieux (PSE)

“Efficiency and Stability in Large Matching Markets”

Abstract

We study efficient and stable mechanisms in many-to-one matching markets when the number of agents is large. We first consider an environment where individuals’ preferences are drawn randomly from a class of distributions allowing for both common value and idiosyncratic components. In this context, as the market grows, all Pareto efficient mechanisms (including top trading cycles, serial dictatorship, and their randomized variants) generate total payoffs that converge to the utilitarian upper bound. This result implies that Pareto-efficient mechanisms are asymptotically payoff equivalent in the population distribution sense — that is, “up to renaming of agents.” In an environment where objects’ priorities are also randomly drawn, we show that the agents’ payoffs under any stable matching mechanism approximate those achieved by Pareto-efficient mechanisms in large markets. Therefore, stable mechanisms tend to be efficient as the market grows. However, Pareto-efficient mechanisms may not become (approximately) stable in large economies. In particular, we show that under the top-trading cycle mechanism a non-vanishing proportion of blocking pairs remains present as the economy grows. Those results help discriminate between two of the most prominent mechanisms discussed in the literature and used in practice.