Lloyd Shapley (1923-2016)

In March Lloyd Shapley sadly passed away . His paper with D. Gale, “College Admissions and the Stability of Marriage”, is fascinating. I am unsure if Shapley set out in 1962 to answer questions in economics explicitly. I say this because this paper really does speak like an economics paper.  Supposing you are matching pairs of people (i.e. marriage), stability is defined as a position in which any person from at least two pairs can leave the pairing for another also willing to leave. A stable position leaves no more room for ordering. Similar to Pareto optimality, you can’t make another person better off without making some else worse off.

The stable marriage problem and the solution to gain optimality and stability is surprisingly easy to understand. Shapley and Gale wrote the paper in very clear English. In fact, they comment on their use of plain English and precise definitions in the concluding remarks:

Most mathematicians at one time or another have probably found themselves in the position of trying to refute the notion that they are people with “a head of figures,” or that they “know a lot of formulas.” At such times it may be convenient to have an illustration at hand to show that mathematics need not be concerned with figures, either numerical or geometrical. For this purpose we recommend the statement and proof of our Theorem 1.

Many more results from this seemly simple problem and their solution to it have been discovered, some in fact very simple but only recognized a few years after the paper. The stable marriages problem algorithm is commonly summarized as:

Screen Shot 2016-04-09 at 6.15.46 PM

Result 1: For any equal number of men and women, the algorithm terminates

Simple Proof:

No single man can be rejected by every single woman. This is because that would mean that all the women are married. But since there are equal numbers of woman and men, this is impossible.

Result 2: When men propose all the men have the best pairing they can get in any stable matching, and women have the worst possible

Simple Proof:

Suppose after the first execution of the algorithm, by contradiction, you create a set of pairs so that any man prefers w’. In the original execution this means he was rejected by w’ in place for m’. So in the arbitrary matching there is no stable position for (m’,w’) as both rather be together. Thus in the executed algorithm, and not the contradictory one, not only does giving each man his best possible stable match give the only stable match for the same set over and over but it is also the best the man can do, assuming they are proposing.

For the women’s choice, supposing again a contradictory set of matchings, M’, but compared to the algorithm’s results the woman prefers the m (from the algorithm) matched to her to m’ matched to her. This means that m, w cause M’ to be unstable unless in the initial algorithm (which we know to be optimal for the man) he prefers the match in M’ to w, which contradicts the fact found in the first part of proof, as the man always prefers the outcome from the algorithm (assuming men propose).

There are various other results, and lots of interesting literature by economists (particularly Alvin Roth) discussing stabling matching algorithms applied to various problems. For instance, matching residences to medical students. Also, there is even more literature in computer science on matching.

Some extra reading on Shapley’s influence can be found here and another piece of mathematics he completed to further economics (with Folkman) can be found here.

For detailed proofs (precise in the way Shapely discusses), and a video worth watching discussing some of the theorems.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s