Some fundamental results on matching and market design by Marilda Sotomayor

When I was at the recent conference Celebrating the 70th Birthday of Marilda Sotomayor, July 25-30 at the University of Sao Paulo, one of the talks I gave was to introduce Marilda before she spoke.

I concentrated on the results in these four papers.

Some Remarks on the Stable Matching Problem,  David Gale and Marilda Sotomayor, Discrete Applied Mathematics, 1985 (decomposition)

Multi-Item Auctions, Gabrielle Demange, David Gale, and Marilda Sotomayor, Journal of Political Economy, 1986 (simultaneous ascending auction)

A Further Note on the Stable Matching Problem, Gabrielle Demange, David Gale, and Marilda Sotomayor, Discrete Applied Mathematics, 1987 (limits to manipulation)

A Non-constructive Elementary Proof of the Existence of Stable Marriages, Marilda Sotomayor, Games and Economic Behavior, 1996 (structure, still to come?)

I pointed out that some theory is fundamental because it plays a big role in producing new theory, and understanding mathematical structure, and some theory is fundamental because it helps us understand the world, make sense of empirical observations, and explains how and why successful market designs work.

In the latter category, I've come to appreciate the theorem about the limits to which stable matching mechanisms can be manipulated by misrepresenting preferences in simple matching markets:

Limits on successful manipulation (Demange, Gale, and Sotomayor). Let P be the true preferences (not necessarily strict) of the agents, and let P differ from P in that some coalition  C of men and women misstate their preferences. Then there is no matching m, stable for P, which is preferred to every stable matching under the true preferences P by all members of C

Taken together with the variety of empirical and theoretical observations that say that the set of stable matchings is generally quite small, this result states that in general very few agents will be in a position to profitably manipulate their preferences. So it can be viewed as providing an explanation of why stable matching mechanisms have succeeded so well empirically, despite the theoretical result in Roth (1982) stating that no stable matching mechanism can always make it a dominant strategy for agents to reveal their true preferences.

Here's a picture of Marilda at the conference:

Here's an interview (in Portugese) about the conference, and here's a newspaper story (for which Google translate does a reasonable job): Uma semana com 4 Nobéis de Economia. (Here's another: Nobel de Economia fala sobre a matemática dos encontros.) And finally here's a video (in English, with music) of an interview I gave about matching and market design, and the kind of work that Marilda and I have done.