applets.

Matchmaker

← All apps

About Matchmaker

Two lines of eight dancers have to be paired up for the next dance. Everyone has a card ranking all eight people in the other line. A pairing is stable when no two people would both rather dance with each other than with the partners they were given: if two such people exist, they would simply walk off together, and the page joins them with a red string. The surprise is that a stable pairing always exists, for any cards at all, and a simple caller's method always finds one.

THE DANCE: RUN THE DANCE plays the caller's method one ask at a time. Every free dancer on the asking side asks the next person on their card. A person who is asked keeps the best offer they have had so far "on hold" and turns the others down; if someone better asks later, they let the earlier one go, who carries on down their own card. It ends when nobody is free. Names struck through in red are people who turned that dancer down. STEP does one ask. The card sets each show something: VILLAGE is an ordinary mix, SAME TASTES has everyone agreeing on the order, MUTUAL has every first choice wanting them back, CROSSED has each line's favourites liking them least, SHUFFLE deals new cards. ClickTap a name on a card and then another on the same card to swap them. RANDOM PAIRS pairs everyone by chance instead: the red strings show who would walk off, and you can try to get rid of them yourself by clickingtapping a Blue card and then a Gold card to pair those two (their old partners pair with each other).

WHO ASKS WINS: the same cards danced both ways. Every one of the 40,320 possible pairings is plotted by how happy each line is (the average place of their partner on their card; 1 means everyone got their first choice), as grey squares that are darker where more pairings land. The stable pairings are the dots, and the table lists them (with more than eight, the first four and the last three, with the rest counted between). The pairing found when Blue asks is the best stable pairing for every Blue dancer at once and the worst for every Gold dancer; when Gold asks it is the other way round. On the chalkboard, TRY EVERY CARD hands in every possible card (all 40,320 orders) for one person on the asked side, with everyone else honest, to see whether lying could get them a better partner. CHECK BOTH LINES does that for all sixteen dancers.

ROOMMATES: one group in which anyone can partner anyone, as in a set where partners come from the same group. Now a stable pairing may not exist at all. CHECK EVERY PAIRING tries them all (3 for four people, 15 for six, 105 for eight). RUN 10,000 GROUPS deals random cards and counts how often a stable pairing exists, against the Expected share.

REAL WORLD: where the same idea places people today.

THE STORY

David Gale and Lloyd Shapley published "College Admissions and the Stability of Marriage" in the American Mathematical Monthly in 1962. They proved that a stable matching always exists, gave the asking method (now called deferred acceptance) to find one, showed that it is the best stable matching for the asking side, and extended it to colleges that take many students. The same paper gave the four-person example on the ROOMMATES tab, where no stable answer exists.

The method was already in use without anyone knowing its theory. In 1952 the United States began matching graduating medical students to hospital training posts through a national clearing house, now the National Resident Matching Program. Alvin Roth showed in 1984 that the method it adopted, known as the Boston Pool algorithm, was the same as deferred acceptance with the hospitals doing the asking. Since 1998 the match has used a design by Roth and Elliott Peranson in which the applicants ask, adjusted for real complications such as couples who want posts in the same place. Those complications mean the plain theorem no longer promises a stable result that is best for every applicant, but the design aims as close to that as it can.

Lester Dubins and David Freedman showed in 1981, and Roth in 1982, that nobody on the asking side can get a better partner by handing in a dishonest card, and that no group of askers can lie together so that every one of them gains. Roth also showed that no stable method can make honesty safe for everyone: the side being asked can sometimes gain by lying, which the WHO ASKS WINS tab lets you find. In 1985 Robert Irving gave an efficient method for the roommates problem that finds a stable pairing whenever one exists and otherwise shows that none does.

Gale died in 2008. In 2012 Shapley and Roth shared the Nobel memorial prize in economics "for the theory of stable allocations and the practice of market design".

HOW IT WORKS

Everything on the page is worked out exactly. The caller's method runs in rounds: everyone free at the start of a round asks once, in line order, and anyone let go during the round asks again in the next one. The order of asking never changes the final pairing, only how long it takes. A pairing is checked by testing every Blue and Gold pair who are not together. To list every stable pairing, the page checks all 40,320 ways to pair eight with eight. A lie is tested by dancing the whole night again with each of the 40,320 possible cards for that one person. Roommates groups are checked by trying every way to split the group into pairs, which is fine for eight people; Irving's method is what you would use for big groups.

The Expected shares on the ROOMMATES tab are exact values: 26/27 for four people (Boris Pittel, 1993) and about 93.3% for six and 91.0% for eight (Stephan Mertens, 2015). In every case worked out exactly (up to twelve people) the share falls as groups grow, and simulations suggest it keeps falling.

What the page leaves out: every card here ranks everyone with no ties, and everyone must dance. Real matches have short lists (people who would rather not be matched at all), places with many spots, ties, and couples, and with couples a stable answer is no longer guaranteed. The made-up dancers have no sex or gender; the old "marriage" name comes from the 1962 paper.

FURTHER WATCHING AND READING

BLUE SASHESASKING
GOLD SASHESASKED

The caller's board

ASKING SPEED
CARDS

Blue: average place of partner on card Gold: average place of partner on card Asks so far Pairs who would both rather swap