You are currently browsing the tag archive for the ‘Scarf’s Lemma’ tag.

In my salad days, school masters would assign boys returning from the summer hols an essay: What I did during the summer’. Yes, masters and boys. I served a portion of my youth in a misbegotten penal colony upon a wind blasted heath’. The only females present were master’s wives, matrons and the French mistress. No, not that kind, the kind that offers instruction in French. As you can see, to the lascivious minds of boys, there was no end to the double entendres. However, I digress.

Over the summer Thanh Nguyen and myself completed a paper about stable matchings. The abstract is reproduced below.

The National Resident Matching program strives for a stable matching of medical students to teaching hospitals. With the presence of couples, stable matchings need not exist. For any student preferences, we show that each instance of a stable matching problem has a `nearby’ instance with a stable matching. The nearby instance is obtained by perturbing the capacities of the hospitals. Specifically, given a reported capacity $k_h$ for each hospital $h$, we find a redistribution of the slot capacities $k'_h$ satisfying $|k_h-k'_h|\le 4$ for all hospitals $h$ and $\sum_h k_h\le \sum k'_h \le \sum_h k_h+9$, such that a stable matching exists with respect to $k'$. Our approach is general and applies to other type of complementarities, as well as matchings with side constraints and contracts.

In other words, with the addition of at most 9 additional slots, one can guarantee the existence of a stable matchings. This is independent of the size of the market or doctors preferences (it does assume responsive preferences on the part of hospitals). The key tool  is Scarf’s lemma which is a wonderful device for converting results about cardinal matching problems into results about ordinal matching problems. For more on this, consult the paper by Kiralyi and Pap, who should be credited with a formulation of Scarf’s lemma that makes its usefulness evident.