Nobel-winning economists' theory applied to finding a mate

Economic theory matches men and women to stable partners using list-based game

PUBLISHED : Sunday, 21 October, 2012, 12:00am
UPDATED : Sunday, 21 October, 2012, 4:06am

How do you find Mr or Ms Right, scientifically? This year's winners of the Nobel memorial prize in economics have much to say about this question, the outcome of which is the basis of many people's happiness or misery.

The dismal science is often accused of favouring abstract mathematical theories with little real-life relevance. But the work of Alvin Roth of Harvard University and Lloyd Shapley of the University of California in Los Angeles, though highly mathematical, are very practical.

Roth and Shapley's theory involves figuring out how to find the right match between people and organisations. It falls under "the theory of stable allocation and the practice of market design", which gives practical solutions to problems we face.

Here is a common allocation issue - how to match students to schools, medical doctors to hospitals, donors of organs with patients in need of a transplant, a group of men and women trying to get married. What is the most efficient way to find the best match? Which methods are beneficial to which groups?

The two scholars have answered these questions. The theory of stable allocations, pioneered by Shapley, was applied by Roth to design market institutions that are stable, efficient and fair to their participants, in what the Royal Swedish Academy of Sciences called "an outstanding example of economic engineering" which ushers in the field of experimental economics.

Shapley used game theory to study various methods that would produce stable matching pairs. Known as the "stable marriage problem", it can be described as a situation where each man in a group of men lists - in order of priority - who he would like to marry among a group of women. At the same time, each female in the women's group lists her preferences among the men.

The problem is how to find the matching pairs in the two groups so all the marriages remain stable in the sense that each person will have no motivation or ability to prefer another partner once a successful match is found for all.

Each person's partner is as good as it gets!

The game starts with each man making a marriage proposal to his favourite woman. Thus it is possible for a woman to receive multiple proposals, in which case she would choose the man who is higher on her list. A man who is rejected by his first choice will have to choose in the next round a woman who is next on his list.

At the end of each round, there are some men who have not found a match because they were rejected, and some women who have not received a proposal from any man. A woman can dump a man, even if she has accepted a proposal from him in the previous round, when a more desirable man proposes to her in later rounds. The game will go on until each man is matched to a woman.

Shapley co-authored a paper in 1962 with David Gale (who died in 2008) which showed that based on game theory, an algorithm can be developed so that a stable match can always be found for each man and each woman, and each pair will not be motivated to or be capable of finding another partner.

The diagrams here show three rounds of proposals among four men and four women. To keep our discussion simple, we will skip their prioritised preferences.

After three rounds, each man and woman has found a stable match.

This is an extremely simplified example of Shapley's mathematical proof of the existence of stable matches. His actual theoretical construct is extremely complex. But Roth saw its practical value and was able to use it to improve the functioning of markets in the real world.

Starting in the 1980s, Roth investigated the problem of matching new doctors to hospitals and realised that it was similar to the stable marriage problem. Finding the best match between employer and employee is, in many respects, similar to a man or woman looking for Ms or Mr Right.

Roth's investigations and experiments, using the Gale-Shapley algorithm, came up with practical designs now being used by the National Resident Matching Program in the United States to allocate new doctors to hospitals during their internship.

He also used a version of the Gale-Shapley algorithm to redesign the admissions process for the New York City and Boston public schools.

In most school admission procedures, students rank their choice of school in order of preference. Schools, meanwhile, have the problem of selecting students with the best records from a pool of applicants. This is similar to the stable marriage problem, i.e. matching one group with another for the most stable result.

Roth's design resulted in a more equitable and efficient admissions process that assigned many more students to their preferred schools.

For once in economics, a set of design tools derived from complex mathematics is capable of solving problems that all societies have to deal with. In Hong Kong, given the intense competition among students for places in prestigious schools, could Roth's reform of school placement procedures apply?

With the growing population of single women in Hong Kong and single men in mainland China, perhaps the Gale-Shapley algorithm could even help find matches for our lonely hearts, giving theoretical stable marriage problem a literal application!

Tom Yam is a Hong Kong-based management consultant with a doctorate in electrical engineering and an MBA from the Wharton School, University of Pennsylvania. He has worked at AT&T, Ernst & Young and IBM