Matchmaker, mathmaker

There you are, but who are you? Are you an anxious young man or woman in search of wedded bliss? Or are you an equally anxious medical student waiting to find out where you’ll be doing your general surgery residency?

Either way, you’re in a scenario with an underlying mathematical algorithm, courtesy of the Princeton math department.

This is the deferred acceptance matching algorithm devised by Lloyd Shapley GS ’53 and David Gale GS ’49, who died last month of a heart attack, leaving behind a tremendous mathematical and matchmaking legacy. Deferred acceptance algorithms model situations in which one side makes proposals while the other either accepts or rejects them, but a final decision is not made until all proposals are on the table.

In their 1962 article “College Admissions and the Stability of Marriage,” published in The American Mathematical Monthly, Gale and Shapley described this algorithm for pairing off groups of men and women into stable couples. What makes a marriage “stable”? Stable means that no two people in the pool would both choose to marry each other over their own spouses. Or, to put another way, neither party would prefer the pool boy.

Despite its guaranteed stability, this algorithm does not play a major role in forming happy marriages, at least in our society. Revised versions of the algorithm, however, are responsible for assigning medical school graduates to residency programs and for pairing students with public schools in Massachusetts and New York.

American universities, however, have not adopted this model, even though Gale and Shapley initially designed it for college admissions. The admissions algorithm matches applicants with colleges in a very similar fashion to the way the marriage algorithm matches husbands and wives, except that the process is modified so that colleges can accept multiple applicants.

Colleges can discard the algorithmic basis for admissions because they are much less sensitive to exactly how many people they get than hospitals or public elementary and high schools are, Harvard economics professor Alvin Roth said. Still, the stable marriages generated by the Gale and Shapley algorithm show some clear parallels with admissions processes. The most desirable spouses, like the most desirable applicants, are likely to pair off with one of their top choices, while the universally undesirable ones also have a tendency to end up together.

In some ways, though, college admissions processes are adopting certain aspects of the Gale and Shapley matchmaking algorithm. Early admission procedures that allow students to designate a school as one of their top choices are just a way of allowing students to make proposals. Early applications complicate the admissions game because many schools have higher acceptance rates for early applicants, creating another strategic layer in the system.

It is a similar problem to the one the Boston public school system had for many years, where families who chose to list schools in their actual orders of preference were sometimes penalized for doing so. Ranking very popular schools first, like applying early to very competitive colleges, meant that if you were not accepted by that first choice, you might also then be rejected by slightly less competitive schools, which would have accepted you had they been your first choice. Roth recently helped redesign Boston’s school-assignment algorithm so that it is always advantageous for families to state their true preferences.

On March 20, less than two weeks after Gale’s death, a modified version of his admissions algorithm matched more than 15,000 fourth-year medical students with residency training programs. The National Resident Match Program (NRMP) has been used in one form or another for more than 50 years and is based on the college admissions model Gale and Shapley presented in their original article.

Roth, who also helped design the NRMP, said the admissions algorithm required some tinkering to meet the demands of the residency match. For instance, one of the biggest complications in the NRMP is the thousand or so people who enter the match as couples — paired off, we hope, in stable arrangements — and want residencies in the same area.

In 2002, a group of former residents filed an anti-trust suit against the NRMP, claiming that illegal use of the algorithm prevented the free market from influencing residents’ salaries, thereby lowering their wages. The charges were dismissed in 2004.

Get the best of the ‘Prince’ delivered straight to your inbox. Subscribe now »

Toward the end of their 1962 article, Gale and Shapley commented on the strikingly non-mathematical appearance of their highly quantitative matchmaking algorithm.

“The argument is carried out not in mathematical symbols but in ordinary English; there are no obscure or technical terms,” they said. “Knowledge of calculus is not presupposed. In fact, one hardly needs to know how to count.”

They end by reflecting on what this says about the very nature of math, concluding that “the reason your friends and ours cannot understand mathematics is not because they have no head for figures, but because they are unable to achieve the degree of concentration required to follow a moderately involved sequence of inferences.”

With pickup lines like that, no wonder they were searching for a fool-proof method of finding true love.