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:

No comments: