Monday, November 14, 2011

A supply and demand model for stable matchings, by Eduardo Azevedo and Jacob Leshno

Much of two-sided matching theory has been developed using discrete mathematics, which has led to beautiful theorems about lattices and stable matchings that are optimal for one side of the market or the other. Since the agents on each side of the market can be quite heterogeneous (which is why who is matched to whom is important), there is a lot of information in each stable matching, which can therefore be hard to summarize succinctly.

Now Eduardo Azevedo and Jacob Leshno have a very nice model of two sided matching in which one side of the market is a continuum, or can be approximated as such via a converging sequence of finite markets, while the other side is finite. Think college admissions, with lots of students and a finite set of colleges. In their model, there is a (generically) unique stable matching, and it can be characterized by a low dimensional set of price-like scalar thresholds, one for each college.

Modeling a continuum of students means that students have to be characterized in some sense, and they find a simple, general way to do this, that works well in the finite case also. A student is characterized by an arbitrary preference over colleges (there are only finitely many of these, since there's a fixed finite set of colleges) and a vector of scores, one for each college, which characterizes each college's preferences over students (each college ranks students in their order on the college's own score). They show that a stable matching becomes a very simple object--it is the solution to a set of supply and demand equations, in which each college is characterized by a threshold, and students are admitted to their most preferred college among those that score them above that college's threshold.

This simple characterization of stability considerably simplifies the investigation of comparative statics.They illustrate this with a price-theoretic analysis of how competition induces schools to improve quality, and why this may not benefit some types of student.

It looks like this will be quite a useful model.

Here's the paper and abstract:

A Supply and Demand Framework for Two-Sided Matching Markets by EDUARDO M. AZEVEDO AND JACOB D. LESHNO

Abstract: "We propose a new model of two-sided matching markets, which allows for complex heterogeneous preferences, but is more tractable than the standard model, yielding rich comparative statics and new results on large matching markets.

"We simplify the standard Gale and Shapley (1962) model in two ways. First, following Aumann (1962) we consider a setting where a finite number of agents on one side (colleges or firms) are matched to a continuum mass of agents on the other side (students or workers). Second, we show that, in both the discrete and continuum model, stable matchings have a very simple structure, with colleges accepting students ranked above a threshold, and students demanding their favorite college that will accept them. Moreover, stable matchings may be found by solving for thresholds that balance supply and demand for colleges. We give general conditions under which the continuum model admits a unique stable matching, in contrast to the standard discrete model. This stable matching varies continuously with the parameters of the model, and comparative statics may be derived as in competitive equilibrium theory, through the market clearing equations. Moreover, given a sequence of large discrete economies converging to a limit economy, the set of stable matchings of the discrete economies converges to the stable matching of the limit economy.

"We bound the rate of convergence of the set of stable matchings of large discrete economies to the continuum approximation, and show that comparative statics regarding the unique stable matching of the continuum model extend to strong set ordering of the sets of stable matchings of approximating discrete economies. We model the transferrable utility case, as in Becker (1973). We characterize the limit of school choice mechanisms used in practice, generalizing previous results of Che and Kojima (2010). Finally, we illustrate the model's applicability by quantifying how competition induced by school choice gives schools incentives to invest in quality. Specifically, we show that schools have muted, and possibly even negative incentives to invest in quality dimensions that benefit lower ranked students."

As I've mentioned in previous blog posts about some of their other papers (here about Eduardo and here about Jacob), they are both on the job market this year. Here are their other papers (Eduardo's; Jacob's). You could hire them both:)

No comments: