# Vt. teens take on 'stable marriage problem'

By Tim Johnson • Free Press Staff Writer • June 26, 2009

You might suppose that 30 teenagers would be in no position to solve "the stable marriage problem," but you'd be wrong.

True, they're not quite of marrying age. On the other hand, they're high school students, so they know a lot intuitively about pairing up. What's more, the 30 who gathered Thursday in a University of Vermont classroom -- 15 boys, 15 girls, from high schools across the state -- had something else in their favor: They're math whizzes. They're attending the Governor's Institute of Mathematical Sciences this week, thanks to their performances in an annual exam. "Stable marriage" was one of many conundrums they've been exploring throughout the week in seminars led by UVM and Middlebury professors.

It turns out that the solution of "the stable marriage problem" has a practical application -- in the annual "matching" of medical school graduates to hospitals seeking residents.

First, what is the "stable marriage problem"?

Suppose you're a matchmaker with 15 male clients and 15 female clients, each of whom has given you a complete list, ranked in order of preference, of those in the opposite gender they'd like to marry. Your challenge is to pair everyone off so that the final arrangement is "stable" -- that is, to find 15 marriages such that no man and woman who aren't married to each other want to divorce their partners and run away with each other. In other words, there are no two who aren't together but who would rather be together.

For example, what if Bob is married to Carol, and Ted is married to Alice, but Bob and Alice prefer each other to their partners? That's instability: Bob and Alice are inclined to pair off.

Is it always possible, with lots of couples, to find a "stable" arrangement, and if so, how would the matchmaker go about it? These were among the questions posed in a Thursday afternoon seminar by Jeff Dinitz, a UVM math professor. Sure enough, Dinitz said, there's an algorithm, or sequence of steps, discovered in 1962 that will produce a "stable" set of marriages. Normally, Dinitz covers this algorithm in theory -- in an upper-level UVM math course -- but today, he announced, they were going to try it out in practice.

Before they got started, Dinitz remarked that when he was in college, he and two other male math students wound up pairing off with three female English majors -- and they're all still married 30 years later

Did he use the formula, someone asked.

"I didn't know the algorithm back then," he said, smiling, then added: "I would have put my wife first, I have to say that."

Dinitz's field of specialty is combinatorics, which studies sets of discrete, or countable, elements. Some discretion was certainly called for in this exercise.

Dinitz gave everyone a number and soon had them proposing and rejecting each other, round after round until no one was being rejected any more.

Mercifully, no egos were bruised. Before numbers were assigned, everyone had to list their preferences randomly, 1 through 15 -- so, no one got rejected because of who they were or how they were perceived, but just because of the number they were assigned by chance.

Here's how the algorithm works. (One variant has the males doing the proposing, the other, the females.) In the male-proposing version, every man proposes to the woman who is ranked highest on his preference list who has not previously rejected him. Every woman receiving more than one proposal rejects all but the highest-ranking man on her list, who gets a "maybe." The rejected men can't propose to her again. She might reject that "maybe" partner in a following round if someone she has ranked higher proposes to her.

This goes on, round after round, until nobody is rejected. Some of the students had fun with the ritual, proposing marriage on bended knee -- only to be rejected, in many cases.

It took 15 rounds for Neil Guertin of Middlebury to be accepted by Phoenix Kenney of Otter Valley. He didn't seem to mind, because in previous rounds he'd had a "maybe" from his No. 5.

After 23 rounds, there were no more rejections. Dinitz did a spot poll to see if they could find any instability. There was none: No two people wanted to pair up with someone they weren't "married" to.

Then they ran through the same algorithm with the females doing the proposing. Only in the last round did Feresha Patel of Bennington get paired up -- with Tegan Garon of Stowe.

How did it feel to be the last one chosen?

"Very disappointing," Feresha said, with a smile and some sarcasm. "Very disappointing!"

The National Resident Matching Program uses the algorithm every year, Dinitz said, to match graduating medical students with hospitals. In 2009, according to the program's Web site, 25,185 residency positions were filled in this way.

The algorithm must work. After all, how many cases are there of a resident and hospital who aren't assigned to each other running off together? None; doesn't happen.