On the Work of Shapley

http://www.nobelprize.org/nobel_prizes/economics/laureates/2012/

Shapley and Roth won the Noble Prize in economics for the theory of stable allocations and the practice of market design.

I am now studying matching and search theory and it is a good timing. This is a focus on the work of Dr. Shapley and a reminder for myself; the below largely depends on Wiki, Nobelprize.org, and the article of the Washington Post(2012.Oct.15),

(1)Shapley Value(1953)
In a game where n players play cooperatively, how important is each player to the overall cooperation, and what payoff can he or she expect? The Shapley value provides one possible answer to this question.

(2)Shapley-Shubik power index(1954)
In a voting game, players with the same preferences form coalitions. Any coalition that has enough votes to pass a bill or elect a candidate is called winning, and the others are called losing. Based on Shapley value, Shapley and Shubik concluded that the power of a coalition was not simply proportional to its size.

The power index is normalized between 0 and 1. A power of 0 means that a coalition has no impact at all on the result of the game; and a power of 1 means a coalition brings the outcome of the game.

(3)Gale-Shapley deffered-acceptance algorithm(1962)
This is the reason Dr. Shapley won the Prize: In a large group of men and women considering marriage, both partners feel that they have gotten the most attractive possible match; Shapley and his colleague David Gale developed a process for ensuring that those matches are as stable as possible.

In the process, there are a series of rounds in which men and women rank potential mates, and matches are made until everyone finds a spouse and the system is stable.

Here's the excerpt:

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. Gale and Shapley proved mathematically that this algorithm always leads to a stable matching.

The specific setup of the algorithm turned out to have important distributional consequences; it matters a great deal whether the right to propose is given to the women – as in our example – or to the men. If the women propose, the outcome is better for them than if the men propose, because some women wind up with men they like better, and no woman is worse off than if the men had been given the right to propose. 

Indeed, the resulting matching is better for the women than any other stable matching. Conversely, the reverse algorithm – where the men propose – leads to the worst outcome
from the women’s perspective. (Nobelprize.org)

This idea is based on the idea of market/mechanism design and actually applied to how to match doctors and hospitals, students and public high-schools and kidney donors and patients.