Gale-Shapley at the milonga: stable does not mean fair
The algorithm behind the 2012 Nobel prize guarantees that no couple will walk off the floor together. It guarantees nobody a dance. Between those two promises the gap is wider than it looks.
A milonga is an Argentine tango evening: a room, records or a live orchestra, and people who have come to dance with strangers. The night there divides into tandas: three or four pieces with the same person, then a break, and everybody sits down again. A four-hour evening holds about twenty of them, that is, as many occasions to dance or to stay seated.
By the end, some have danced nearly everything and others nearly nothing. It is put down to level, to shyness, to the luck of the glances. Those explanations are plausible and this piece does not dismiss them. But a room where people rank each other is also a market, and there is a theory of such markets: a 1962 paper, a Nobel prize in 2012, and assignments running today over tens of thousands of people. Which leaves what it promises about an evening like this, and what it does not.
The detour is not mine. Loren Shure published a post on stable matching on the MathWorks blog in 2020, and it starts from a challenge set at a milonga. The code already chains tandas while forbidding a repeat partner, and handles the unequal sides of a dance evening. It explicitly leaves three things aside: matching within one camp, incomplete lists and ties. This piece takes up the first two, turning the hard rules into proportions along the way, because a room is never wholly of one mind.
David Gale and Lloyd Shapley published in 1962 a paper with a deceptively academic title, “College Admissions and the Stability of Marriage”. The reading followed here is the one the mathematician Emily Riehl gives in two Numberphile videos. The problem: given two groups whose members each rank the members of the other, can one always form couples such that nobody runs off? Instability is given an exact definition, on which the whole statement depends: two people who prefer each other to the partner they were assigned. Nothing else counts as instability.
Instability is if and only if two people simultaneously prefer each other to their assigned spouses.
The proof is constructive, which is the useful part. The algorithm is told in days. On the first day everyone on the inviting side turns to their first choice. Those receiving several proposals keep the best and refuse the rest; the engagements are provisional. On the second day each refused person turns to their next choice, free or not, and those receiving break off as soon as better comes along. Repeat until nobody is refused. The whole of it fits in one loop.
You wait at the edge of the floor. An invitation crosses the room; whoever receives several keeps one and lets the others go, and the refused sit back down to try again next round. Couples that hold step into the middle. Six inviters to eight invited, as in a real room: two will stay seated, without that making the matching unstable. These are the algorithm’s real rounds going past, not a drawn story.
while (free.length) {
const a = free.pop()!;
if (next[a] >= list[a].length) continue; // nobody left to ask
const b = list[a][next[a]++]; // ask the next one down
const held = partner[b];
if (held === -1) { // b is free: provisionally taken
partner[b] = a;
partner[a] = b;
} else if (rank[b][a] < rank[b][held]) { // b trades up, held goes back
partner[b] = a;
partner[a] = b;
partner[held] = -1;
free.push(held);
} else {
free.push(a); // refused, ask again tomorrow
}
}Riehl draws four theorems from it. Zero: the loop always stops, because a proposal is never repeated. One: the result is stable, and she is insistent that no restriction is needed either on how many are on each side or on the preference lists. Two: the inviting side gets, simultaneously for all of them, the best partner any stable matching could give. Three: the receiving side gets the worst. The last two share a single proof, and it took about ten years for anybody to notice the second half. The 1962 paper had the men proposing, it was seen at once that they gained by it, and much later that the women lost.
Set the room, then watch who dances. One row per person, one column per tanda, the least danced at the top. The blocking-pair count is the only judge: at zero the matching is stable in Gale-Shapley’s sense; above it, the theorem no longer says anything. The partner obtained reads as a percentage of one’s own list: twenty per cent means within the top fifth.
Each row is a person, each column a tanda, a filled cell a tanda danced. Rows are sorted from least to most danced, so that whoever the evening leaves out rises to the top of the block instead of being lost inside it. The only figure that settles it is the blocking-pair count: at zero, the matching is stable in Gale-Shapley’s exact sense. The three sections that follow each push on one premise of the theorem, to see which gives; the four after that are about what it says nothing of.
A milonga almost never has as many men as women. You expect the imbalance to break something, and it breaks nothing: set eighteen women against six men and the blocking-pair count stays at zero. Twelve people do not dance, but none of them can point to anybody who would prefer them back. Imbalance produces people sitting down, not instability. This is what theorem one states, and the measurement confirms it across every draw.
The “share of the room each person refuses” slider truncates the lists: past a certain rank, sitting down is preferred. That is the cabeceo, the look sent out and not returned, and it is the truest reading of “not dancing this tanda”. The theorem survives here too: over three hundred draws crossed with nine settings of refusal and etiquette, at six men against eighteen women, the counter never rose above zero. A market with incomplete lists still has a stable matching, and the same loop finds it.
Refusal does not break the guarantee, then. It changes everything else. With complete lists the market clears almost entirely and the number of people with no dance at all tends to zero. Refusal is therefore the necessary condition for anyone to be excluded. But it does not suffice on its own, and neither does agreement on taste: in a room of twenty-eight over four hours, either one pushed to its limit leaves nobody without a dance. The two have to meet, and the size of the room then decides the rest. We come back to it further down.
One premise remains, and Riehl states it in the video’s first minute before setting it aside for the day: only heterosexual marriages are on the table, which, she says, “is actually really important to the mathematics”. The line passes as a turn of phrase. That premise conditions the entire result. The theorem holds on a bipartite graph: two camps, couples that cross between them, never inside one.
But at a milonga two women dance together, and it is unremarkable. The slider does exactly one thing: it sets the share of the women open to the idea, a pair needing both of them to be. The graph stops being bipartite and the problem becomes the roommates problem, for which Gale and Shapley themselves give, in the same paper, an example with no stable solution at all.
The guarantee does not lapse at a threshold: it decreases continuously with the proportion, which a switch could not show. At ten per cent of the women open to it, one draw in two hundred already carries a blocking pair. At thirty per cent, twenty-three out of two hundred. At a hundred, a hundred and ninety-five, with six pairs on average. The bipartite premise is therefore not a convenience one could approximately satisfy: the smallest breach is enough. This is no failure of the code: the loop still stops and still returns a matching, it has simply stopped promising anything.
That leaves the most quoted theorem, the one saying it is far better to invite than to be invited. It is true, and the simulator shows it: at equal sides, complete lists and independent tastes, the inviting side dances with someone it placed on average at fourteen per cent of its own list, the other at twenty-eight, twice as far down. A partner “at fourteen per cent of your list” is the one you would have ranked fourteenth out of a hundred: the smaller the figure, the better the partner. Have the other side invite and the gap turns over identically. That is enormous, it is perfectly symmetrical, and it is the figure people take away from the talks.
The gap becomes negligible as soon as the textbook premises are lifted. Push agreement on taste to eighty per cent and the gap shrinks to almost nothing. Cut more than half of every list through refusal, and both sides land at twenty-eight per cent, within half a point, whoever does the inviting. The reason is mechanical and says itself in one sentence: the proposer’s advantage is the spread between the best and the worst stable matching, and the more people agree on who is desirable the fewer stable matchings exist, until only one is left, where best and worst are the same.
The proposer’s advantage amounts to half a point. Another effect, measured in the same unit, amounts to seventeen. Eight men to eighteen women, with the men proposing: the men obtain a partner at seventeen per cent of their list, the women at thirty-four. Invert the numbers and the gap inverts identically: thirty-three against seventeen. The scarce side wins, whoever does the inviting. It wins roughly what the right to invite was worth under textbook conditions, except that here, that right is worth nothing at all.
This is the result I was not looking for and the one that makes the evening legible. The theorem is exact and its effect measurable, but it is an order of magnitude below that of a variable it does not treat. “Invite rather than wait” is sound advice, proved, and without measurable effect in a real room. “Come on the night your side is outnumbered” is proved nowhere, and doubles how high you dance in your own list.
Nor does the theorem say anything about the rules a room gives itself. The most visible one at a milonga is that you do not dance twice with the same person in one night. Shure codes it hard: in his version nobody repeats. Here it is a slider, because a room never keeps a convention as one body: at zero his constraint is back exactly, at a hundred the etiquette is gone.
The result has the opposite sign to the one I expected. When nobody repeats, nobody sits out: across a four-hour evening not one of the twenty-eight ends without a dance. When everybody may repeat, nine of them get no tanda at all. And the partner obtained is better for everyone: twenty-one per cent of one’s own list against thirty-eight. A convention of use therefore produces a redistributive effect: forbidding a repeat partner imposes a rotation, which bounds the number of tandas any one person can capture.
This is not a case for the etiquette. The model knows nothing of the pleasure of dancing again with someone it works with, and it measures one thing only: how many people stay seated. On that indicator the rule is effective, and effective without coordination: the effect comes from the constraint, not from the participants’ intentions.
A neighbourhood milonga gathers thirty people, a festival gathers a hundred. You expect the larger room to protect: more people, more possible partners, better odds for everyone. The measurement gives the opposite result. At three men to four women over four hours: at fourteen, nobody is left sitting; at twenty-eight, nobody either; at fifty-six, a tenth of the room; at ninety-two, better than a quarter.
Size is not, however, the explanatory variable. Run the same rooms with independent tastes: nobody is left out, at any size. Run them with closely agreeing tastes but no refusals at all: nobody either, at any size. It takes the two together, agreement on who is desirable and refusal of the bottom of one’s list, and only then does size decide how hard it bites. A festival does not manufacture exclusion. It supplies a conjunction already present with the numbers above which its effect becomes measurable.
Each section above measures one variable. Set together, they become comparable: the only one the theorem treats is the right to invite, and it is the one whose effect is smallest in a realistic room.
The table reads in two parts. The first two rows give the theorem, then what remains of it once the textbook premises are lifted: the gap goes to zero. The four below concern variables Gale and Shapley do not treat, namely the composition of the room, the rule of use applied, the size, and the pairings allowed. Each produces an effect larger than the one the theorem guarantees.
None of this stayed theoretical. In the nineteen-fifties, assigning medical graduates to American hospitals was done by private dealing and produced unstable matchings. The national programme that replaced it runs exactly this loop every March, in the United States and Canada. It first had the hospitals proposing, and so favoured them; in the mid-nineties, once it was understood which way theorem three leaned, the direction was reversed in favour of the residents. Riehl adds a fourth theorem explaining why the mechanism holds socially: the proposing side gains nothing by lying about its preferences.
The same algorithm also runs in a machine room. A content delivery network has to assign billions of requests an hour to tens of thousands of edge servers, and Akamai does it with a Gale-Shapley variant: clients are grouped by area and traffic type, servers into clusters rated on capacity and latency, each side ranking the other. Client groups want the best-rated clusters, clusters want the least demanding groups. The reason for the choice is not elegance: the other combinatorial approaches were too slow, and this one holds the throughput.
It is the servers that propose, Shure notes. Theorem three then says exactly who is served best, and it is not the request. The direction of the proposal is therefore no implementation detail: it is the one place in the system where who holds the advantage is decided, and in both cases named here somebody had to settle it. For the medical residents the direction was eventually reversed. In the case of web requests, it has never been revisited.
The Nobel prize in economics went in 2012 to Lloyd Shapley and Alvin Roth, for the theory of stable allocations and the design of markets. Gale, who died in 2008, was no longer eligible.
The model ignores much of what makes a real evening. The etiquette did get in, but coarsely: it forbids taking a partner again for the whole night, where the custom is mostly about two tandas in a row. Level, tiredness, the music of the tanda, arriving with somebody, the geography of the tables: none of it exists. Tastes are drawn afresh each tanda around a fixed reputation, which is a strong assumption and not an observed fact. And the cabeceo is not a proposal: it is a look one may fail to see, which makes it an incomplete-information mechanism this model does not represent.
Above all, none of these figures comes from a milonga. They come from the simulator above, with the settings stated each time, and they describe the model rather than the room. What comes out of it is narrower, and firmer, than a dancing lesson: a stability guarantee says nothing about distribution, it survives unequal sides and refusals, and it falls entirely the moment a couple can form inside one camp.