Remembering Lloyd Shapley: Surprised to Find Himself Speaking Economics

When I heard that 2012 Nobel laureate in economics Lloyd Shapley had died, I was reminded of Molière's well-known 1670 play, "Le Bourgeois Gentilhomme," in which a character named Monsieur Jourdain is astonished to find that he has been speaking prose all his life. Shapley was a mathematician, worked in a department of mathematics, and back in the early 1960s developed at theorem that cracked a problem in mathematics--but then found that he had been speaking economics all along.  When Shapley won the Nobel, along with Alvin Roth, he said: ""I consider myself a mathematician and the award is for economics. I never, never in my life took a course in economics."

Molière's described Monsieur Jourdain's discovery that he was speaking prose like this:

MONSIEUR JOURDAIN: Please do. But now, I must confide in you. I'm in love with a lady of great quality, and I wish that you would help me write something to her in a little note that I will let fall at her feet.
PHILOSOPHY MASTER: Very well.

MONSIEUR JOURDAIN: That will be gallant, yes?

PHILOSOPHY MASTER: Without doubt. Is it verse that you wish to write her?

MONSIEUR JOURDAIN: No, no. No verse.

PHILOSOPHY MASTER: Do you want only prose?

MONSIEUR JOURDAIN: No, I don't want either prose or verse.

PHILOSOPHY MASTER: It must be one or the other.

MONSIEUR JOURDAIN: Why?

PHILOSOPHY MASTER: Because, sir, there is no other way to express oneself than with prose or verse.

MONSIEUR JOURDAIN: There is nothing but prose or verse?

PHILOSOPHY MASTER: No, sir, everything that is not prose is verse, and everything that is not verse is prose.

MONSIEUR JOURDAIN: And when one speaks, what is that then?

PHILOSOPHY MASTER: Prose.

MONSIEUR JOURDAIN: What! When I say, "Nicole, bring me my slippers, and give me my nightcap," that's prose?

PHILOSOPHY MASTER: Yes, Sir.

MONSIEUR JOURDAIN: By my faith! For more than forty years I have been speaking prose without knowing anything about it, and I am much obliged to you for having taught me that.

Economists often find that in trying to convey the precise meaning of their arguments, they are speaking in mathematics. Thus, it's perhaps not a huge surprise that a mathematician like Shapley might discover that he was speaking economics. In a 2012 post on "The 2012 Nobel Prize to Shapley and Roth" (October 17, 2012), I tried to lay out

The fundamental problem looks like this. Imagine that there are two groups, A and B. Members of Group A are to be matched with members of Group B. However, each of the members of Group A has likes and dislikes about the members of Group B, each of the members of Group B has likes and dislikes about the members of Group A, and these likes and dislikes don't necessarily line up. Is there a way to match members of Group A and Group B so that, after the match, everyone won't be ditching their match and trying for another?

Before trying to describe the result, the Gale-Shapley algorithm, it's worth noting that this general situation of finding stable matches applies in many settings. (David Gale was a very prominent mathematical economist who died in 2008, before the Nobel was awarded to Shapley and Roth.) The 1962 paper offered verbal illustrations based on college admissions and on what economists think of as the "marriage market." Later on, Shapley's co-laureate Alvin Roth offered a number of practical applications: for example, processes used in K-12 school lotteries in various cities, in the "matching" process for medical school residencies, and in matching donors and recipients of kidney transplants.

Here is how the Nobel committee describes Gale and Shapley  "deferred acceptance" procedure to get a stable result for their matching problem.

Agents on one side of the market, say the medical departments, make offers to agents on the other side, the medical students. Each student reviews the proposals she receives, holds on to the one she prefers (assuming it is acceptable), and rejects the rest. A crucial aspect of this algorithm is that desirable offers are not immediately accepted, but simply held on to: deferred acceptance. Any department whose offer is rejected can make a new offer to a different student. The procedure continues until no department wishes to make another offer, at which time the students finally accept the proposals they hold.

In this process, each department starts by making its first offer to its top-ranked applicant, i.e., the medical student it would most like to have as an intern. If the offer is rejected, it then makes an offer to the applicant it ranks as number two, etc. Thus, during the operation of the algorithm, the department’'s expectations are lowered as it makes offers to students further and further down its preference ordering. (Of course, no offers are made to unacceptable applicants.) Conversely, since students always hold on to the most desirable offer they have received, and as offers cannot be withdrawn, each student’s satisfaction is monotonically increasing during the operation of the algorithm. When the departments’decreased expectations have become consistent with the students’increased aspirations, the algorithm stops."

Here's how the procedure would work in the marriage market:

"The Gale-Shapley algorithm can be set up in two alternative ways: either men propose to women, or women propose to men. In the latter case, the process begins with each woman proposing to the man she likes the best. Each man then looks at the different proposals he has received (if any), retains what he regards as the most attractive proposal (but defers from accepting it) and rejects the others. The women who were rejected in the first round then propose to their second-best choices, while the men again keep their best offer and reject the rest. This continues until no women want to make any further proposals. As each of the men then accepts the proposal he holds, the process comes to an end."

I described some of context of the result this way in my 2012 post:

Gale and Shapley prove that this procedure leads to a "stable" outcome. Again, this doesn't mean that everyone gets their first choice! It means that when the outcome is reached, there is no combination of medical school and applicant, or of man and woman in the marriage example, who would both prefer a different match from the one with which they ended up. But Gale and Shapley went further. It turns out that there are often many stable combinations, and in comparing these stable outcomes, the question of who does the choosing matters. If women propose to men, women will view the outcome as the best of all the stable matching possibilities, while men will view it as the worst; if men propose to women, men as a group will view it as the best of all stable matching possibilities, while women will view it as the worst. As the Nobel committee writes, "stable institutions can be designed to systematically favor one side of the market." ...

The Nobel prize to Shapley and Roth is one of those prizes that I suspect I will have a hard time explaining to non-economists. The non-economists I know ask practical questions. They want to know how the work done for the prize will spur the economy, or create jobs, or reduce inequality, or help the poor, or save the government money. Somehow, better matching for medical school students won't seem, to some non-economists like it's "big enough" to deserve a Nobel. But economics isn't all about today's public policy questions. The prize rewards thinking deeply about how a matching process works. In a world of increasingly powerful information-processing technology, where we may all find ourselves "matched" in various ways based on questions we answer by software we don't understand, I suspect that Alvin Roth's current applications are just the starting point for ways to apply the insights developed from Lloyd Shapley's "deferred acceptance" mechanism.

Shapley's obituary in the Economist is here, from the New York Times is here, and from the Associated Press is here.