Gale-Shapley at the milonga: stable does not mean fair
The algorithm recognised by the 2012 Nobel prize guarantees that no pair of dancers would prefer to form outside the matching produced. It guarantees nobody a dance, and the gap between those two properties is larger than it seems.
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 every tanda and others almost none. This is put down to level, to shyness, to chance glances. Those explanations are plausible and this article does not dismiss them. But a room where everyone ranks the others is also a market, and there is a theory of such markets: a 1962 paper, a Nobel prize in 2012, and assignments that now involve tens of thousands of people. What remains is to see what that theory guarantees for such an evening, and what it does not.
The connection comes from Loren Shure, who published a post on stable matching on the MathWorks blog in 2020, prompted by a challenge set at a milonga. The code already chains tandas while forbidding a repeat partner, and handles the unequal numbers of a dance evening. It explicitly leaves aside three points: matching within the same group, incomplete lists and ties. This article takes up the first two and replaces those strict rules with proportions, because the people in a room never all hold the same view.
David Gale and Lloyd Shapley published a paper in 1962 with a seemingly academic title, “College Admissions and the Stability of Marriage”. The reading followed here is the one given by the mathematician Emily Riehl in two Numberphile videos. The problem is this: given two groups whose members each rank the members of the other, can couples always be formed so that no pair would rather form differently? Instability has a precise definition, on which the whole statement depends: two people who each prefer the 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 makes it useful. The algorithm is described day by day. On the first day, everyone on the inviting side approaches their first choice. Those who receive several proposals keep the best and refuse the others; the engagements are provisional. On the second day, each refused person approaches their next choice, whether free or not, and those receiving proposals break off as soon as a better one arrives. This repeats until nobody is refused. The algorithm fits in a single loop.
Dancers wait at the edge of the floor. An invitation crosses the room; anyone who receives several accepts one and declines the rest, and those declined try again in the next round. Couples move to the centre. There are six inviters and eight invited, as in a real room: two of the invited stay seated, and the matching is stable all the same. The animation replays the algorithm’s actual rounds.
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 Riehl insists 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 and watch who dances. One row per person, one column per tanda, those who danced least at the top. The blocking-pair count is the test: at zero the matching is stable in the Gale-Shapley sense; above zero the theorem no longer applies. The partner obtained is shown as a rank in each person’s preference list: twenty per cent means within the top fifth.
Each row is a person, each column a tanda, and a filled cell a tanda danced. Rows are sorted from the person who danced least to the one who danced most, so that those left out appear at the top of the block. The only criterion is the number of blocking pairs: at zero, the matching is stable in the exact Gale-Shapley sense. The next three sections each change one premise of the theorem to see which one no longer holds; the four after that concern what it says nothing about.
A milonga almost never has as many men as women. You might expect this imbalance to make the matching unstable, but it does not. With eighteen women and six men, the blocking-pair count stays at zero. Twelve people do not dance, but none of them can name anyone who would prefer them in return. The imbalance leaves people seated without creating instability. That is what theorem one states, and the measurement confirms it on every draw.
The “share of the room each person refuses” slider truncates the lists: beyond a certain rank, people prefer to stay seated. That is the cabeceo, the glance offered and not returned, and it is the closest translation of “not dancing this tanda”. The theorem still holds in this case: over three hundred draws combined with nine settings of refusal and etiquette, with six men and eighteen women, the count never rose above zero. A market with incomplete lists always has a stable matching, and the same loop finds it.
Refusal therefore does not undermine the guarantee. It does, however, change everything else. With complete lists, almost everyone finds a partner, and the number of people with no dance at all tends to zero. Refusal is therefore necessary for anyone to be excluded. It is not sufficient on its own, nor is agreement on taste: in a room of twenty-eight over four hours, either one pushed to the maximum leaves nobody without a dance. Both are needed together, and the size of the room then determines the rest, as shown further down.
One premise remains, which Riehl states in the first minute of the video before setting it aside: only heterosexual marriages are considered, which, in Riehl’s words, “is actually really important to the mathematics”. The remark seems to be a mere matter of wording, but this premise conditions the entire result. The theorem holds on a bipartite graph: two groups, couples formed between them, never within a group.
Yet at a milonga two women dance together, and it is common. The corresponding slider sets the share of women open to this, a pair forming only if both are. The graph is then no longer 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 disappear at a threshold: it degrades progressively with the proportion, which a simple switch could not show. With ten per cent of women open to it, one draw in two hundred already contains a blocking pair. At thirty per cent, twenty-three in two hundred. At a hundred per cent, a hundred and ninety-five in two hundred, with six pairs on average. The bipartite premise therefore cannot be satisfied approximately: the slightest exception is enough for blocking pairs to appear. The code still works: the loop stops and returns a matching, but that matching is no longer guaranteed to be stable.
That leaves the most quoted theorem, according to which it is far better to invite than to be invited. It is correct, and the simulator shows it: with equal numbers, complete lists and independent tastes, the inviting side dances with someone placed on average at fourteen per cent of its own list, the other side at twenty-eight, twice as far down. A partner “at fourteen per cent of your list” is one you would have ranked fourteenth out of a hundred: the smaller the figure, the better the partner. If the other side invites, the gap reverses exactly. The gap is large and perfectly symmetrical, and it is the figure that talks on the subject retain.
The gap becomes negligible as soon as the textbook case is left behind. With eighty per cent agreement on taste, it shrinks to almost nothing. If refusal truncates more than half of every list, both sides end up at twenty-eight per cent, within half a point, whoever invites. The reason is mechanical: the proposer’s advantage is the difference between the best and the worst stable matching. The more people agree on who is desirable, the fewer stable matchings there are, until only one remains, in which the best and the worst coincide.
The proposer’s advantage is half a point. Another effect, measured in the same unit, reaches seventeen points. With eight men and eighteen women, and the men proposing, the men get a partner at seventeen per cent of their list, the women at thirty-four. Reverse the numbers and the gap reverses exactly: thirty-three against seventeen. The smaller group has the advantage, whoever invites. Its advantage is of the same order as that of the right to invite in the textbook case, whereas that right brings almost nothing here.
I was not looking for this result, but it explains the evening best. The theorem is correct and its effect measurable, but that effect is an order of magnitude smaller than that of a variable it does not cover. “Invite rather than wait” is sound, proven advice, with no measurable effect in a real room. “Come on the night your side is in the minority” is proven nowhere, and gets you a partner ranked twice as high in your own list.
Nor does the theorem say anything about the rules a room sets for itself. The most visible one at a milonga is that you do not dance with the same person twice in an evening. Shure imposes it without exception: in that model nobody dances twice with the same partner. Here it is a slider, because a room never follows a convention uniformly: at zero that constraint applies exactly, at a hundred the etiquette has gone.
The result goes in the opposite direction to what I expected. When nobody dances twice with the same partner, nobody stays seated: over a four-hour evening, none of the twenty-eight people ends without a dance. When everyone 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 therefore has a redistributive effect: forbidding a repeat partner imposes a rotation, which limits the number of tandas any one person can obtain.
I am not defending the etiquette here. The model ignores the pleasure of dancing again with someone you dance well with, and measures only one thing: the number of people left seated. On that measure the rule is effective, and without any 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, however, is not the explanatory variable. With independent tastes, nobody is left out, whatever the size of the room. With strongly shared tastes but no refusals, nobody either. Both conditions are needed together, agreement on who is desirable and refusal of the bottom of one’s list, and size then determines how large the exclusion is. A festival therefore does not create exclusion; it reaches the size at which the effect of those two conditions 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 is also used in web infrastructure. A content delivery network has to assign billions of requests an hour to tens of thousands of edge servers, and Akamai does so with a variant of Gale-Shapley. Clients are grouped by area and traffic type, servers into clusters rated on capacity and latency, and each side ranks the other. Client groups want the best-rated clusters, clusters want the least demanding groups. The choice comes down to performance: the other combinatorial approaches were too slow for this throughput.
It is the servers that propose, Shure notes. Theorem three then shows who is served best, and it is not the request. The direction of proposals therefore decides who is favoured, and in both cases mentioned here someone had to choose it. For medical residents, the direction was eventually reversed. For web requests, it has never been questioned.
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 is included, but crudely: it forbids taking the same partner again for the whole evening, whereas the custom mostly concerns two consecutive tandas. Level, tiredness, the music of the tanda, arriving with someone, the layout of the tables are not represented. Tastes are drawn at random for each tanda around a fixed reputation, which is a strong assumption, not an observed fact. Finally, the cabeceo differs from a proposal: it is a glance the other person may not notice, which makes it a mechanism with incomplete information that 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 describe the model, not a real room. Three points can be drawn from them. A stability guarantee says nothing about how dances are distributed. It holds with unequal numbers and with refusals. It disappears as soon as a couple can form within the same group.