Skip to main content

The Globe and Mail

Practical game theory proves the perfect match for Nobel prize winners

2012 Economics Nobel Prize winners Lloyd Shaple, left, of UCLA and Alvin Roth of Stanford University are shown in this combination photograph taken in Los Angeles and Stanford, Calif., respectively on Oct. 15, 2012. Life-saving kidney exchange programs are just one of the practical applications of the market-matching theories for which the two American economists won the 2012 Nobel prize for economics on Monday.

STAFF/REUTERS

The awarding of the 2012 Nobel Prize in Economic Sciences to mathematician Lloyd Shapley and economist Alvin Roth "for the theory of stable allocations and the practice of market design" was unexpected, but certainly deserved. Both Americans found ways to make markets work when traditional economic tools fail.

Professor Roth, 60, teaches at Harvard Business School, and is currently is a visiting professor at Stanford University. Professor Shapley, 89, is a professor emeritus at University of California, Los Angeles.

Their joint $1.2-million (U.S.) award was unexpected because their research was in areas that had recently won Nobel prizes (matching problems in 2010, and mechanism design in 2007).

Story continues below advertisement

Even Prof. Shapley was surprised by the honour. "I consider myself a mathematician and the award is for economics," he told the Associated Press on Monday. "I never, never in my life took a course in economics."

Shapley's theoretical research

Matching problems involve situations where people or institutions need to be paired, such as students with schools, workers with jobs, or spouses with each other. Unlike traditional problems in economics that rely on prices to allocate resources, in many matching problems using cash for transactions is impossible, impractical or unethical.

Prof. Shapley made early inroads into the matching problem by using game theory to analyze different matching methods in the 1950s and 1960s. His primary contribution is the Gale-Shapley deferred acceptance algorithm (his co-author, David Gale, died in 2008).

Ideally, matching systems should have two properties: They should be "stable," meaning there is no way to rearrange the matches to make everyone better off. And they should be "incentive compatible," meaning users should not be able to game the system by cheating. It turns out it is almost impossible to have a system with both properties, but the Gale-Shapley deferred acceptance algorithm minimizes the incentives to cheat while maintaining stability.

The 1962 Gale-Shapley research paper placed the problem in the context of the marriage market. It considers a stylized example in which each of 10 bachelors propose to their preferred mate. The woman either rejects the proposal, or gives a deferred acceptance, which allows her to later reject the offer if a better one comes along. Rejected suitors then propose to their second choice, and the process continued until no man wishes to make any more proposals – at which point the deferred acceptances become final. While it was a wholly unrealistic scenario, it would be the basis of Prof. Roth's research.

Roth's real-world results

Story continues below advertisement

Prof. Roth expanded on the Gale-Shapley research to tackle real-life problems. For example, his matching-system algorithm is used to assign students to high schools in New York and Boston, so more students end up at their preferred school. It is also used to assign medical residents to hospitals.

Perhaps his most important work is in the field of kidney transplants. Many family members want to donate a kidney to their loved on but cannot because of medical incompatibilities. Prof. Roth's research has led to the establishment of complex organ-matching systems, in which donor kidneys go to compatible patients, rather than to their own relative, but the donor's loved one receives a kidney from another donor in the system.

The work of game theorists such as professors Shapley and Roth rarely makes headlines, but has done a great deal to make all our lives better. Honouring them was a strong decision by the Royal Swedish Academy of Sciences.

With files from Associated Press

Mike Moffatt is an assistant professor in the Business, Economics and Public Policy group at the Richard Ivey School of Business, University of Western Ontario

Story continues below advertisement

Report an error
About the Author

Mike Moffatt is an Assistant Professor in the Business, Economics and Public Policy (BEPP) group at the Richard Ivey School of Business – Western University. Mike also does private sector consulting for the chemical industry. More

Comments

The Globe invites you to share your views. Please stay on topic and be respectful to everyone. For more information on our commenting policies and how our community-based moderation works, please read our Community Guidelines and our Terms and Conditions.

We’ve made some technical updates to our commenting software. If you are experiencing any issues posting comments, simply log out and log back in.

Discussion loading… ✨

Combined Shape Created with Sketch.

Combined Shape Created with Sketch.

Thank you!

You are now subscribed to the newsletter at

You can unsubscribe from this newsletter or Globe promotions at any time by clicking the link at the bottom of the newsletter, or by emailing us at privacy@globeandmail.com.