New papers on matching by Yeon-Koo Che and Olivier Tercieux (large markets and top trading cycles)

In the Cowles Foundation working paper series:

"Efficiency and Stability in Large Matching Markets" 
Cowles Foundation Discussion Paper No. 2013

YEON-KOO CHE, Columbia University
Email: yc2271@columbia.edu
OLIVIER TERCIEUX, Paris-Jourdan Sciences Economiques (PSE)
Email: Tercieux@pse.ens.fr

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.

"An Analysis of Top Trading Cycles in Two-Sided Matching Markets" 
Cowles Foundation Discussion Paper No. 2014

YEON-KOO CHE, Columbia University
Email: yc2271@columbia.edu
OLIVIER TERCIEUX, Paris-Jourdan Sciences Economiques (PSE)
Email: Tercieux@pse.ens.fr

We study top trading cycles in a two-sided matching environment (Abdulkadiroglu and Sonmez (2003)) under the assumption that individuals’ preferences and objects’ priorities are drawn iid uniformly. The distributions of agents’ preferences and objects’ priorities remaining after a given round of TTC depend nontrivially on the exact history of the algorithm up to that round (and so need not be uniform iid). Despite the nontrivial history-dependence of evolving economies, we show that the number of individuals/objects assigned at each round follows a simple Markov chain and we explicitly derive the transition probabilities.

"Payoff Equivalence of Efficient Mechanisms in Large Matching Markets" 
Cowles Foundation Discussion Paper No. 2014

YEON-KOO CHE, Columbia University
Email: yc2271@columbia.edu
OLIVIER TERCIEUX, Paris-Jourdan Sciences Economiques (PSE)
Email: Tercieux@pse.ens.fr

We study Pareto efficient mechanisms in matching markets when the number of agents is large and individual preferences are randomly drawn from a class of distributions, allowing for both common and idiosyncratic shocks. We show that, as the market grows large, all Pareto efficient mechanisms -- including top trading cycles, serial dictatorship, and their randomized variants -- are uniformly asymptotically payoff equivalent “up to the renaming of agents,” yielding the utilitarian upper bound in the limit. This result implies that, when the conditions of our model are met, policy makers need not discriminate among Pareto efficient mechanisms based on the aggregate payoff distribution of participants.