The caller's board
EVERY POSSIBLE PAIRING OF THESE CARDS
Grey squares: all 40,320 pairings, darker where more of them land. Dots: the stable ones. Nearer the top left, happier.
THE STABLE PAIRINGS
Who asks wins
Could lying help?
Cards come from THE DANCE: change them there.
One group, no lines
How often is there an answer?
NEW DOCTORS
In the United States, final-year medical students and hospital training programmes both hand in ranked lists, and the National Resident Matching Program pairs them. It began in 1952 with a method later shown to be deferred acceptance with the hospitals asking, ten years before Gale and Shapley wrote it down. Since 1998 the students ask. In the plain dance that would give the best stable result for every applicant; real complications, such as couples applying together, mean the match can only aim for it.
In the UK, Roth found that the NHS's old regional schemes for placing newly qualified doctors lasted when they gave stable results, and were mostly given up when they did not.
Who asks: the applicants (since 1998).
SCHOOL PLACES
New York City has given out high school places with applicant-asking deferred acceptance since 2003, now for about 80,000 pupils a year. The schools' priorities play the part of the asked side's cards.
Councils in England use "equal preferencing": each school sorts everyone who named it by its own admission rules, whatever place the family gave it, and the child is offered the highest preference they qualify for. That works like deferred acceptance with families asking. Families may name only a few schools, so it is still wise to include one you are sure of.
Who asks: the pupils.
KIDNEY SWAPS
Someone willing to give a kidney to a relative is often not a medical match for them. The UK Living Kidney Sharing Scheme, set up by NHS Blood and Transplant in 2007, looks for swaps: pairs who can give to each other's patient, in loops of two or three, and chains started by people who give to a stranger. Matching runs are held four times a year; since 2008 they have used software from the University of Glasgow.
A cousin of the dance with different sums: nobody can walk off, so the aim is the most (and best) transplants. Roth's prize also recognised his work on kidney exchange in the United States.
WHAT IT MEANS FOR YOU
If you are on the asking side of a deferred acceptance match, list your true favourites in your true order. Putting a "safer" choice higher can never get you a better result, and can get you a worse one.
The asked side can sometimes gain by bluffing, but a bluff that helps with some lists can backfire with others, and in a real match nobody sees everyone's lists. The big matches usually put applicants on the asking side, so for applicants the advice is simple: be honest.
A short list is different: if you can name only a few choices, which ones you name matters, even though their order should still be honest.
The idea, in one line
Pairs that would both rather swap break any arrangement. Deferred acceptance always finds an arrangement with none.
The 1962 paper was about college admissions as much as dances. Places with many spots work the same way: each place keeps its best offers on hold, up to its number of spots, and turns the rest down.
The 2012 Nobel memorial prize in economics went to Lloyd Shapley, for the theory, and Alvin Roth, for putting it to work. David Gale, the paper's other author, had died in 2008.
Try it with your own cards on THE DANCE: swap names on any card, then RUN THE DANCE.