Category Archives: Matching

Dale Mortensen as Micro Theorist

Northwestern’s sole Nobel Laureate in economics, Dale Mortensen, passed overnight; he remained active as a teacher and researcher over the past few years, though I’d be hearing word through the grapevine about his declining health over the past few months. Surely everyone knows Mortensen the macroeconomist for his work on search models in the labor market. There is something odd here, though: Northwestern has really never been known as a hotbed of labor research. To the extent that researchers rely on their coworkers to generate and work through ideas, how exactly did Mortensen became such a productive and influential researcher?

Here’s an interpretation: Mortensen’s critical contribution to economics is as the vector by which important ideas in micro theory entered real world macro; his first well-known paper is literally published in a 1970 book called “Microeconomic Foundations of Employment and Inflation Theory.” Mortensen had the good fortune to be a labor economist working in the 1970s and 1980s at a school with a frankly incredible collection of microeconomic theorists; during those two decades, Myerson, Milgrom, Loury, Schwartz, Kamien, Judd, Matt Jackson, Kalai, Wolinsky, Satterthwaite, Reinganum and many others were associated with Northwestern. And this was a rare condition! Game theory is everywhere today, and pioneers in that field (von Neumann, Nash, Blackwell, etc.) were active in the middle of the century. Nonetheless, by the late 1970s, game theory in the social sciences was close to dead. Paul Samuelson, the great theorist, wrote essentially nothing using game theory between the early 1950s and the 1990s. Quickly scanning the American Economic Review from 1970-1974, I find, at best, one article per year that can be called game-theoretic.

What is the link between Mortensen’s work and developments in microeconomic theory? The essential labor market insight of search models (an insight which predates Mortensen) is that the number of hires and layoffs is substantial even in the depth of a recession. That is, the rise in the unemployment rate cannot simply be because the marginal revenue of the potential workers is always less than the cost, since huge numbers of the unemployed are hired during recessions (as others are fired). Therefore, a model which explains changes in churn rather than changes in the aggregate rate seems qualitatively important if we are to develop policies to address unemployment. This suggests that there might be some use in a model where workers and firms search for each other, perhaps with costs or other frictions. Early models along this line by Mortensen and others were generally one-sided and hence non-strategic: they had the flavor of optimal stopping problems.

Unfortunately, Diamond in a 1971 JET pointed out that Nash equilibrium in two-sided search leads to a conclusion that all workers are paid their reservation wage: all employers pay the reservation wage, workers believe this to be true hence do not engage in costly search to switch jobs, hence the belief is accurate and nobody can profitably deviate. Getting around the “Diamond Paradox” involved enriching the model of who searches when and the extent to which old offers can be recovered; Mortensen’s work with Burdett is a nice example. One also might ask whether laissez faire search is efficient or not: given the contemporaneous work of micro theorists like Glenn Loury on mathematically similar problems like the patent race, you might imagine that efficient search is unlikely.

Beyond the efficiency of matches themselves is the question of how to split surplus. Consider a labor market. In the absence of search frictions, Shapley (first with Gale, later with Shubik) had shown in the 1960s and early 1970s the existence of stable two-sided matches even when “wages” are included. It turns out these stable matches are tightly linked to the cooperative idea of a core. But what if this matching is dynamic? Firms and workers meet with some probability over time. A match generates surplus. Who gets this surplus? Surely you might imagine that the firm should have to pay a higher wage (more of the surplus) to workers who expect to get good future offers if they do not accept the job today. Now we have something that sounds familiar from non-cooperative game theory: wage is based on the endogenous outside options of the two parties. It turns out that noncooperative game theory had very little to say about bargaining until Rubinstein’s famous bargaining game in 1982 and the powerful extensions by Wolinsky and his coauthors. Mortensen’s dynamic search models were a natural fit for those theoretic developments.

I imagine that when people hear “microfoundations”, they have in mind esoteric calibrated rational expectations models. But microfoundations in the style of Mortensen’s work is much more straightforward: we simply cannot understand even the qualitative nature of counterfactual policy in the absence of models that account for strategic behavior. And thus the role for even high micro theory, which investigates the nature of uniqueness of strategic outcomes (game theory) and the potential for a planner to improve welfare through alternative rules (mechanism design). Powerful tools indeed, and well used by Mortensen.


Nobel 2012, Roth and Shapley

There will be many posts summarizing the modern market design aspect of Roth and Shapley, today’s winners of the Econ Nobel. So here let me briefly discuss certain theoretical aspects of their work, and particularly my read of the history here as it relates to game theory more generally. I also want to point out that the importance of the matching literature goes way beyond the handful of applied problems (school choice, etc.) of which most people are familiar.

Pure noncooperative game theory is insufficient for many real-world problems, because we think that single-person deviations are not the only deviations worth examining. Consider marriage, as in Gale and Shapley’s famous 1962 paper. Let men and women be matched arbitrarily. Do we find such a set of marriages reasonable, meaning an “equilibrium” in some sense? Assuming that every agent prefers being married (to anyone) to being unmarried, then any set of marriages is a Nash equilibrium. But we find it reasonable to think that two agents, a man and a woman, can commit to jointly deviate, breaking their marriage and forming a new one. Gale and Shapley prove that there always exists a match that is “pairwise stable” meaning that no pair of men and women wish to deviate in this way.

Now, if you know your game theory, you may be thinking that such deviations sound like a subset of cooperative games. After all, cooperative (or coalitional) games involve checking for deviations by groups of agents, who may or may not be able to arbitrarily distribute their joint utility among their coalition. Aspects of such cooperation are left unmodeled in their noncooperative sense. It turns out (and I believe this is a result due to Mr. Roth, though I’m not sure) that pairwise stable matches are equivalent to the (weak) core of the same cooperative game in one-to-one or many-to-one matching problems. That means both that checking deviations by one potential set of marrying partners is equivalent to checking deviations by any sized group of marrying partners. But more importantly, this link between the core and pairwise stability allows us to utilize many results in cooperative game theory, known since the 1950s and 60s, to answer questions about matching markets.

Indeed, the link between cooperative games and matching, and between cooperative and noncooperative games, allows for a very nice mathematical extension of many well-known general problems: the tools of matching are not restricted solely to school choice and medical residents, but indeed can answer important questions about search in labor markets, about financial intermediation, etc. But to do so requires reframing matching as simply mechanism design problems with heterogeneous agents and indivisibility. Ricky Vohra, of Kellogg and the Leisure of the Theory Class blog, has made a start at giving tools for such a program in his recent textbook; perhaps this post can serve as a siren call across the internet for Vohra and his colleagues to discuss some examples on this point on their blog. The basic point is that mechanism design problems can often be reformulated as linear programs with a particular set of constraints (say, integer solutions, or “fairness” requirements, etc.). The most important set of constraints, surely, are incomplete information which allows for strategic lying, as Roth discovered when he began working on “strategic” matching theory in the 1980s.

My reading of much of the recent matching literature, and there are obviously exceptions of which Roth and Shapley are both obviously included as well as younger researchers like Kojima, is that many applied practitioners do not understand how tightly linked matching is to classic results in mechanism design and cooperative games. I have seen multiple examples, published in top journals, of awkward proofs related to matching which seem to completely ignore this historical link. In general, economists are very well trained in noncooperative game theory, but less so in the other two “branches”, cooperative and evolutionary games. Fixing that imbalance is worthwhile.

As for extensions, I offer you a free paper idea, which I would be glad to discuss at further length. “Repeated” matching has been less often studied. Consider school choice. Students arrive every period to match, but schools remain in the game every period. In theory, I can promise the schools better matches in the future in exchange for not deviating today. The use of such dynamic but consistent promises is vastly underexplored.

Finally, who is left for future Nobels in the areas of particular interest to this blog, micro theory and innovation? In innovation, the obvious names are Rosenberg, Nelson and Winter; Nelson and Winter’s evolutionary econ book is one of the most cited texts in the history of our field, and that group will hopefully win soon as they are all rather old. Shapley’s UCLA colleagues Alchian and Demsetz are pioneers of agency theory. I can’t imagine that Milgrom and Holmstrom will be left off the next micro theory prize given their many seminal papers (along with Myerson, they made the “new” game theory of the 70s and 80s possible!), and a joint prize with either Bob Wilson or Roy Radner would be well deserved. An econ history prize related to the Industrial Revolution would have to include Joel Mokyr. There are of course many more that could win, but these five or six prizes seem the most realistically next in line.

“Promoting School Competition Through School Choice: A Market Design Approach,” J.W. Hatfield, F. Kojima & Y. Narita (2011)

Matching theory has been quite prominent in economics in the past decade: how ought we match organ donors, or match schools to students, or match medical residents to assignments, or husbands to wives? The basic principle is that financial transfers – “side payments” – are often illegal or contrary to well-established custom, so our standard mechanism design tricks won’t work. In school choice, a network of authors centered around Al Roth has developed mechanisms for matching students to schools in New York, Boston and San Francisco, among other cities, in a way that attempts (imperfectly) to deal with schools and students who will try to game the system. Hatfield and coauthors, including the ridiculously productive young scholar Fuhito Kojima, point out in this new working paper that something has been missing in this literature. The motivation for allowing school choice in the first place was so that schools would have an incentive to improve themselves. Previous work assumed school quality was fixed. Something is incongruous.

Let there be schools with M slots available to students, and a ranking over which students they prefer the most. Let students also rank which schools they like best. Let a mechanism respect improvements if, when it becomes “more preferred” by students, it gets students it prefers more. The authors prove there is no stable, strategy-proof matching mechanism which respects improvements: no matter how we propose to use information, schools sometimes have an incentive to misreport which students they actually like. Restricting the domain of preferences does not help, as the same result applies unless all schools have (almost) the same ranking over which students they prefer. Bronx Science and a School of the Arts surely rank along different criteria.

Why is this? Consider the intuition from the famous Deferred Acceptance algorithm. This algorithm is stable, and the intuition of the example will generalize to any stable matching. Let there be two students (A and B) and two schools (1 and 2). School 1 has 2 spots and School 2 has only 1 spot. Both students prefer school 2. School 1 prefers student A to student B, and School 2 prefers student B to student A. In the student-proposing Deferred Acceptance algorithm, both students apply to school 2 in the first round. School 2 conditionally accepts its preferred student, student B. Since school 2 has only one spot, it has filled its capacity. Student A then proposes to school 1 in the second round, and is accepted. Precisely the same outcome occurs (you can easily check this yourself) if schools propose. A famous theorem says that any the student-propose and school-propose DA algorithms given the worst-case and best-case stable matchings from the students’ perspective, so since these are the same, the preferences here permit a unique stable matching.

But what if school 1 improves itself, so that student B now prefers school 1 to school 2? Consider student-proposing DA again. In round 1, A will apply to 2 and B to 1. Both are conditionally accepted, and the algorithm terminates. So now school 1 winds up with student B rather than student A, a worse outcome in school 1’s eyes! It has been punished for improving itself in a very real sense. (You can check here, very simply, that the only stable matching under these preferences is again unique, for exactly the same reason as in the previous paragraph.)

The authors prove, in a similar manner, that there is no mechanism which is Pareto optimal for students which respects school quality improvement. Lest we be too distraught by these results, it is at least the case that stable matchings (like student-propose Deferred Acceptance) in “large” markets, under some conditions, almost never need worry that improvements will make the school worse off. The intuition is that, in the example above, I wanted a student to rank me low because this created competition at another school he now favor. That other school then may reject a different student that I particularly like, who will then “settle” for my school. These “chains of rejections” depend on some schools having reached their capacity, because otherwise they will just conditionally accept everyone who applies. The conditions on large markets essentially just say that the rejection chain I want to induce is unlikely to reach me because the student I am trying to attract has, with high probability, options she prefers which have not filled their quota as of yet.

https://360269…Fuhito-Kojima/SchoolCompetition20111111.pdf (November 15, 2011 Working Paper; at a delay of less than 2 days, I am sure this is the “freshest” research ever discussed on this site!)

%d bloggers like this: