Stable pairwise matching won Lloyd Shapley and Alvin Roth the Nobel prize for economics. It is an idea that is simple, slightly illuminating for economists, occasionally useful for everyone – and profoundly misleading.
The matches in question are between members of two groups, for example potential husbands and potential wives, or medical school graduates and hospitals that might employ them. The “stable” is defined narrowly: the pairing off is stable as long as no individual can find a way to improve his or her situation by trading partners. What counts as “improvement”? The game theory of Shapley and Roth does not really address that question.
The simple idea, demonstrated by Shapley a half century ago, is that under certain conditions a methodical process of elimination – many rounds of tentative pairings – leads to stability. Take a pool of equal numbers of would-be brides and grooms. The men keep on proposing to their favoured women. At first, only the irresistible men garner acceptances from the most appealing women. Gradually, though, each less attractive man will win the favour of some less attractive woman, who accepts the sad reality that she cannot do any better. At the end, while many people may wish they had a different spouse, no one will be able to arrange a trade. Any alternative pairing will be less desirable than the current one to one side or the other. That is exactly game theory stability.
The research is illuminating for economists because it teaches them that money is not needed to arrange an efficient allocation. Economists used to assume, and many still do, that cash markets are the best way to ensure that everyone is able to satisfy as many of his or her desires as possible. Shapley showed that in matching, under certain conditions and by some definitions, nothing more is needed than clear and consistent rankings of potential partners.
The illumination should be slight. Indeed, it probably takes a few years of economic training to be surprised that monetary values do not always lurk behind effective allocation decisions. After all, parents need neither game theory nor cash to divide a cake among the children. Money rarely plays a direct role in deciding who gets what in government programmes.