Nobel laureate in Economics talks about the mathematics of matching

Economist Alvin Roth addressed game theory applications in the market and daily life during the São Paulo School of Advanced Science held at the University of São Paulo.

By Diego Freire

Agência FAPESP – What do students and schools looking for new talent, organ donors seeking compatible recipients, and singles looking for soul mates have in common? Interestingly, all of these relationships depend on the right match for the parties to be happy. It was precisely by developing strategies that facilitate lucky hits such as these and other combinations that garnered American Alvin Roth the 2012 Nobel Prize in Economics.

On a visit to Brazil to give a course at the International Workshop on Game Theory and Economic Applications of the Game Theory Society (IWGTS) held at the University of São Paulo School of Economics, Business Administration and Accounting (FEA-USP) under the scope of the São Paulo School of Advanced Science (SPSAS), a FAPESP grant mechanism, the economist spoke to Agência FAPESP about game theory, his field of study, and how it can help change destinies in the market and in life.

In addition to Roth, three other Nobel laureates in economics participated in the IWGTS, which ran through July 31, 2013: mathematicians John Nash from Princeton University (1994 winner) and Robert Aumann (2005) from the Hebrew University of Jerusalem, and economist Eric Maskin (2007) from Harvard University. The event commemorated the 70th birthday of Marilda Sotomayor, FEA-USP professor and the foremost authority on game theory in Brazil.

Roth’s participation referred to the organization of markets through matching, a branch of game theory. “In the field of applied mathematics, a game is understood to be a mathematical model that represents situations in life where different people, or players, make decisions and interact according to pre-established rules that affect each other. Game theory studies these interactions and matching acts to develop strategies to make the best combinations,” the Stanford University professor explained.

It is a mechanism for situations that require making choices and being selected, such as the job market. “Not only do you have to decide where you want to work, but you also have to be allowed in. Employers also cannot simply decide who they want to work with – they need to make offers that people accept,” he said, by way of example.

Roth won the Nobel in 2012 together with mathematician Lloyd Shapley of the University of California, Los Angeles, for their work on the Gale-Shapley algorithm that arises from the preferences of two groups arriving at stable combinations among their elements.

Roth provided several practical applications of the algorithm, such as matching medical residents to hospitals all over the United States, donors to compatible recipients, and students to schools.

According to him, matching is used to organize different types of markets. “The branch of game theory I work in is called market design. We try to understand how to organize markets so they work better and so we can fix them when they’re not working well,” he said.

So Brazil can join the game

Roth feels that Brazil needs to become involved in the field to try to stay ahead of other emerging countries. “Much of what defines a nation as prosperous is the existence of well-functioning markets. Something important for Brazilian economists to do is to look to the local markets, determine which ones are not functioning properly, and improve them by finding new ways or new rules to organize them.”

According to Marilda Sotomayor, Brazil lacks training in the field. “Besides the fact that matching is a very mathematical field that does not seem to interest Brazilian economists, schools don’t teach game theory in any great depth. Our event is trying to provide students and anyone else interested in the field with a dynamic and intellectually stimulating environment that can promote interaction between participants,” she said.

Sotomayor is co-author with Roth of the reference work in the field, a book entitled Two-sided matching: A study in Game-Theoretic Modeling and Analysis, published in 1990. “It was an important milestone because, up to that point, matching was something that only interested mathematicians. The publication has attracted economists to the theory, and Roth’s work over the years has further expanded the application to other fields, which was why he won the Nobel.”

Roth’s studies, as well as the studies by Shapley, have led, among other things, to important changes in the high school admission process in the United States.

Because few candidates were being admitted to the best schools, many candidates would select a less worthy one to prevent being left with no choice at all. This was the practice until a system was developed that allowed students to select 12 schools that interested them while the institutions also selected profiles of the students they wanted. The system used matching to select the best combination of interests.

The same mechanism can be used in the search for organ donors. Roth was one of the founders of the New England Program for Kidney Exchange, which includes 14 kidney transplant centers in New England that enable patients and donors anywhere in that area to find suitable matches.

The various applications of the theory have their origin in research performed in 1962 by Shapley along with mathematician and economist David Gale for the purpose of finding stable marriages for a group of 10 men and 10 women. In a series of rounds of marriage proposals, potential partners could accept or refuse the proposals by analyzing the interests at stake, changing partners whenever one was found to be more interesting than the other and ensuring, in the end, a stable marriage.

There are other factors involved in a stable relationship, such as unpredictability in human behavior and the possibility of individual preferences changing over time – something theorists still need to address. “Predictability is very hard in this branch. But we try to understand why some rules work better than others,” Roth said.