Showing posts with label large markets. Show all posts
Showing posts with label large markets. Show all posts

Tuesday, September 3, 2019

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





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."

Saturday, August 15, 2015

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

In the Cowles Foundation working paper series:

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.

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.

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. 


Friday, February 6, 2015

Large matching markets as limits

One popular way to study large markets is to look at limits as market size goes to infinity. This is often the only tool we have to develop theory for large markets (computer simulations are another story, and a useful complementary tool).

One difficulty of using limit theorems or other models of infinitely large markets to study the actual, finite markets that we are interested in is that, depending on how the limit is taken, the limit market may have properties that are not shared by the finite markets that concern us. So, a lot of care has to be taken in formulating how the market goes to a limit, and in interpreting the theorems that result (or perhaps I should say in discerning which of theorems about the limit market are informative about the finite markets).

A nice example of taking a limit in a thoughtful way is in a recent paper by Konrad Menzel of NYU, called LARGE MATCHING MARKETS AS TWO-SIDED DEMAND SYSTEM. (I don't understand the estimation issues well enough to comment on them, but I liked the way the large market was modeled as a limit.)

He looks at matching markets in which each agent gets a utility payoff based on the observable properties of the person they are matched with, plus a random component drawn from a distribution with full support. So the danger in such a model is that in the limit the random draws will all allow everyone to get a great match (with someone for whom they have a very large random match quality), and no one will be unmatched. But the finite markets in which he's interested don't have that property: some people are unmatched. So, in taking the limit, the outside options that each agent enjoys have to increase proportionally with their growing opportunities to match to someone with whom, randomly, they are a mutually great match...

Here's how he describes that part of his model.

"The rationale for modeling the outside option as the maximum of J independent draws for the idiosyncratic taste shifters is that as the market grows, the typical agent can choose from an increasing number of potential spouses. Since in our setup the shocks ηij and ζji generally have unbounded support, any alternative with a fixed utility level will eventually be dominated by one of the largest draws for the increasing set of potential matching partners. Hence, by allowing the agent to sample an increasing number of independent draws for the outside option, it can be kept sufficiently attractive to ensure that the share of unmatched
agents remains stable along the sequence."

This reminds me of issues that Itai Ashlagi and I  (with Mike Rees and David Gamarnik in various papers) have run into when using limit theorems to understand kidney exchange, while keeping the compatibility graphs as sparse as those in the finite clinical exchanges we wish to study.

This post profits from a discussion with Jacob Leshno, when he and I recently were involved in a very finite, very practical matching event in Southern California.  The dress code was semi-formal: