A stable marriage is a stable set

David Gale’s name turns up in this subject for games. He invented Chomp, which strategy stealing settles and no one has solved, and he invented Bridg-It, which the switching game solves outright. In 1962 he and Lloyd Shapley published a short paper in the American Mathematical Monthly about something that does not sound like a game at all. Given equal numbers of men and women, each ranking all of the other side, there is always a way to pair them off so that no man and woman, not paired together, would both rather be with each other.

That paper is usually read as the beginning of a different field, and within this subject it looks like a coincidence of authorship. It is not one. What a stable set knows about a draw ended by proposing to take the 1944 definition away from players altogether and try it on a bare graph of preferences. The marriage problem is exactly that graph, and its stable sets are exactly the stable marriages. Gale and Shapley’s theorem is an existence theorem for the object von Neumann and Morgenstern defined and Richardson studied. It proves existence on a family of graphs where Richardson’s hypothesis fails half the time, and for a reason that has nothing to do with parity.

The graph on pairs #

The positions are not people. Each position is a pair, one man and one woman, so a table of three men and three women gives nine positions, set out as a grid with men in rows and women in columns. Each cell is marked with how the two rank each other. There is a move from a pair to any pair sharing one person, where that shared person prefers the new one. So a cell has moves within its row toward women the man likes better, and within its column toward men the woman likes better.

Read the two conditions in this graph. A set of pairs has no move inside it. Two pairs in the same row or column always have a move between them, since the shared person prefers one or the other and ties are excluded, so a set with no move inside it has at most one pair in each row and column. That is a partial matching. Now every pair outside the set must have a move into it: that is, either the man of that pair is matched to someone he prefers, or the woman is. If this holds for all pairs then in particular every row must hold a member, because a man with no partner and a woman with no partner, and with equal numbers there would be both, would form a pair with no move into the set. So the set is a complete matching. And the condition now says that no outside pair consists of a man and a woman who both prefer each other to their partners. That is the 1962 definition of stability, word for word.

The translation has no slack in it, and the census confirms there is none to be found. There are 6 ways for each of six people to rank three others, so 46,656 profiles. On every one of them the list of stable sets from the graph search and the list of stable matchings from a direct check over the six possible matchings are identical. Most have one, 34,080 of them, a further 11,484 have two, and 1,092 have the maximum of three.

Why parity cannot be the reason #

Richardson’s theorem says a graph with no odd cycle has a stable set. The obvious hope is that the graph on pairs has no odd cycle, for some structural reason, and that the 1962 theorem is a corollary of the 1953 one. The census rules this out: 22,860 of the profiles, 49 per cent, have an odd cycle in their graph.

The cycle in the figure is seven steps long, on the same profile that has three stable marriages. Each step is somebody trading up, a man taking a better woman along his row or a woman a better man down her column, and after seven trades the token is back where it began. Preferences go round in this way precisely because different people are doing the preferring: A likes x better than y, and x likes B better than A, and so on. Every individual’s list is a clean order. The cycle exists only through handing the token from one person’s list to another’s.

So the graph on pairs is on the far side of Richardson’s theorem half of the time. Some other property is responsible, and it is not hard to name. A clique in this graph is one person’s list. Two pairs are adjacent only if they share a person; three mutually adjacent pairs all share the same person, in a bipartite table, because a triangle of pairs among distinct people would need an odd cycle among the people, and men only ever pair with women. And one person’s list is a strict order, so within any clique there is one cell, that person’s first choice among the clique, that every other cell in it moves to. So no clique contains a cycle of its own, and every clique has a member that the rest of it can move to, which is what the three-cycle lacked.

This local condition on cliques, and not a global condition on cycles, is what stable sets answer to. It is the shape of a much later theorem of Boros and Gurvich, from the 1990s, proving a conjecture of Berge and Duchet: a directed graph whose underlying undirected graph is perfect has a stable set whenever each of its cliques holds a vertex every other member has a move to. The line graph of a bipartite graph, which is what the grid is, is perfect. The 1962 theorem is one small instance of that result, proved first and by a completely different means.

The means: a search that cannot get stuck #

What Gale and Shapley supply is not a proof by parity or by perfection. It is an algorithm, and on this graph it behaves like a player with a safe policy. Each man proposes to his favourite woman who has not yet refused him. Each woman holds on to the best man to have asked her so far and refuses the rest. Refused men ask again, further down their lists. It ends, because a man never asks the same woman twice. And what it ends on is stable, because a woman’s position only improves, so any woman a man prefers to his final partner has already refused him in favour of someone she prefers.

The run in the figure is short enough to read through. A and B both want x first, and C wants y. A asks x and is held. B asks x and displaces A, since x ranks B above A. C asks y and is held, and then A, asking further down, asks y and displaces C. C now asks x and displaces B, since x ranks C first of all. B asks z and the run stops. Six proposals, two men displaced at x and one at y, with every woman ending on her own first choice and every man on his second. That is not a contradiction of the rule that the proposing side does best: on this table it is the only stable marriage there is. No man was ever going to get his first choice, because the women’s first choices do not include him there, and the proposals discover this in the only order they could.

In terms of the graph, a man’s proposal moves down his row, and a woman’s refusal rules out a cell for good. The algorithm never undoes anything. That is remarkable when set beside what finding a stable set generally costs. On an arbitrary graph, the search is as hard as satisfying a formula. On this family it is a matter of asking down lists. The existence proof and the efficient algorithm are the same argument, and it is an argument about the orders inside the cliques, in the way that Bouton’s criterion is an existence proof and a move-finder at once. A row’s order and a column’s order are used directly, one to decide who asks next, and one to decide who is kept.

The asymmetry deserves a remark, because it is a choice, and the stable set found depends on it. Men asking gives the set that every man prefers to every other stable set, and women asking gives the opposite. In the table of the first figure, men asking stops at once: each man asks his first choice and all three accept, since their first choices are all different. Women asking also stops at once, on the other corner of the table. The third stable set sits in between, and neither run ever visits it. On the graph, these are simply three stable sets. Nothing in the definition prefers any of them, and the freedom among them is exactly the freedom the extra stable sets of a drawn game record.

The same table played as a game #

Because the graph on pairs is a graph, it can be played. A token sits on a pair. A player moves it to any pair that one member of the current pair prefers. A player with no move loses. It is an absurd game with no one in it wanting anything, and it has outcomes all the same, which the essay on draws has already said how to read.

A pair whose members are each other’s first choice has no moves at all. So it is lost, and the theorem of the last essay then says it belongs to every stable set. That is the marriage result in game-theoretic clothing: a pair of mutual first choices appears in every stable marriage, because neither will settle for anything else. Any pair sharing someone with it moves to it in one step, and so is won. Remove those, and the remaining table is smaller; if it again has mutual first choices, these in turn are lost, and so on. The lost positions are the marriages forced by this peeling. Beyond that, a block of preferences that go round each other is drawn, and that block is where the stable sets are free to differ.

The figure’s table is the smallest clean example of both. Its pair A with x is mutually first, and it is lost. The remaining two men and two women have preferences that go round, with B and C each preferring the woman who prefers the other, and that is a cycle of four, which has two stable sets. So the table has two stable marriages, sharing A with x and differing on the rest, and the labelling says lost, then won along the same row and column, then drawn on the four cells in the corner.

It is worth noticing how little the labelling is doing here compared with what backward labelling does for a finite game. On a game that ends, the labels are everything. On this graph, they find the marriages that were never in doubt and hand over the rest.

Across all 46,656 profiles, 27 per cent of pairs are drawn, and on 9,984 profiles, 21 per cent, all nine are. So labelling usually says something and often says nothing, while the marriage theorem says the same thing every time. On those wholly drawn profiles nothing about the game’s outcomes picks out any pair. The stable set still exists and it still has an exact meaning, and it is the meaning from the previous essay: a policy of moving into this set means never being stuck. There, what never gets stuck is a matching.

Roommates, and what the two sides were for #

Gale and Shapley finished their paper by noting that one side is essential. Suppose four people are to share two rooms, all ranking the others, with no division into two kinds. The same two-condition definition applies, on the same kind of graph, whose positions are now the six possible pairs. And stable pairings can fail to exist.

The census is small enough to read completely. There are 1,296 profiles of four people. Of those, 1,098 have exactly one stable pairing, 150 have more than one and 48 have none. And the 48 are all of one form, which can be counted rather than searched for. Pick the unwanted person, in four ways. Everyone else ranks that person last. The other three prefer each other in a circle, which can run in two directions. The unwanted person’s own list, which is any of six orders, does not matter. Four times two times six is 48, exactly the census’s count.

So the failure has a very specific cause, and it is what the last section said was excluded from a marriage table. The three pairs AB, BC and CA all share a person two at a time, so they are three mutually adjacent positions in the graph, a clique. But it is not one person’s list. Each of the three adjacencies is decided by a different person, and when those three decisions run in a circle, the clique is a directed cycle of three with nothing inside it for the others to reach. Whichever of the three is left out with D, that person prefers someone in the remaining pair, who prefers them right back. That triangle is the same triangle as the first essay’s three-position graph with no solution. It has been in the structure all along. A marriage table cannot produce it, because men pair only with women and three pairs mutually sharing people always share the same one. The two sides in the marriage problem are not a social detail. They are a condition on the cliques of a graph.

Robert Irving gave a polynomial algorithm for the roommates problem in 1985, deciding existence and finding a stable pairing where one exists. So this is not where the general hardness of finding a stable set comes from either. That family is still far narrower than arbitrary graphs, and the circular triangles are its only trouble.

The convention under the census #

All of this assumes complete, strict lists. Every man ranks every woman, with no ties and no one declared unacceptable. Allow incomplete lists and a stable set need not be a complete matching, since some people may stay single, and the graph’s reading adjusts: a pair is in the graph only when both accept it. Allow ties and “prefers” stops being a total order on a clique, and the strict arcs of this graph no longer settle the matter, because there are then several different notions of stability in use. The census here covers the strict case and speaks to no other.

And the arrow’s direction is doing work. A move goes to a pair a member prefers, which means the stable set is on the receiving end. Reverse that and a stable set would describe matchings in which every other pair is preferred by a member over something else, which is a different and much less useful notion.

What this cannot show #

Anything past three and four. The agreement between stable sets and stable marriages is a proof for all sizes, and the census only illustrates it. But the percentages are not general. The share of profiles with an odd cycle at three-by-three says little about four-by-four and larger, and the expectation that it rises towards all of them is an expectation.

Why people end up paired as they do. A stable set says which arrangements are consistent with a set of preferences. It describes no process by which actual people arrive at one, and no theorem here says that any actual pairing is stable. The word “marriage” belongs to the 1962 paper’s example and is not a claim about marriages.

How much of the graph’s structure is doing the work. Clique orders are named here as the reason, and the Boros–Gurvich theorem is the general form. That theorem is not checked here, and whether a family of graphs strictly between the marriage tables and the perfect graphs admits an equally simple algorithm is a question the census cannot reach.

Still open: a stable set used as a tool #

Everything so far has asked whether a stable set exists and what it means. The marriage result invites a different use, in which the existence of a stable set on every part of a graph is not the conclusion but a step inside some other proof. Since deferred acceptance works on any sub-table, a stable set is available wherever it is wanted. And there was an old problem about colouring a square whose difficulty came down to choosing, again and again, a large enough set of cells that do not conflict. It had resisted serious attack for fifteen years. Its solution is a page long, uses nothing but this, and is the last thing anyone expected Gale and Shapley’s theorem to be good for.