The side that proposes wins

The rung below ends with a matching that nothing can pull apart, and it is very easy to read that as the end of the question. It is not the end of the question. The same instance has three more.

What stability leaves undecided #

Stability is a property a matching either has or does not have. It says nothing about which of the ones that have it is to be taken, and on a preference profile of any size there is usually more than one to choose from.

Four out of twenty-four. The definition of stability was designed to rule things out, and here it rules out five sixths of the matchings — which is a great deal of ruling out and still leaves a choice to be made. Nothing in the definition of a blocking pair prefers one survivor to another, and nothing in the census does either; the strip is sorted by how many blocking pairs each matching has, and the four that have none at all are simply four.

So the interesting object is not the individual stable matching. It is the set of them, and the set turns out to have far more structure than a set of survivors of an exclusion test has any business having.

An order that has no right to exist #

Put one stable matching above another when every member of side one weakly prefers the partner the first gives them. That is a demanding condition and it is a partial order rather than a ranking: it is reflexive, it is transitive, and it declares two matchings incomparable the moment one member of side one disagrees with another.

There is every reason to expect it to declare almost everything incomparable. Side one is four separate members with four separate lists, and they are in competition with each other — the whole difficulty of the subject is that A wanting 1 and D wanting 1 cannot both be satisfied. Two matchings on which A does better and D does worse would be incomparable, and on the face of it most pairs should look like that.

They do not. A partial order on four elements can leave as many as all six of its pairs incomparable, and this one leaves one. Of the six unordered pairs the four stable matchings form, exactly one is incomparable: M2 gives A its third choice and B its second, M3 gives A its second and B its fourth, and neither dominates. Every other pair is ordered, and the whole set has a single top and a single bottom.

That top is worth pausing on. At M1, which pairs A with 4, B with 2, C with 1 and D with 3, every one of the four members of side one has its second choice, and the diagram prints the ranks so that this can be read off rather than taken on trust. No stable matching gives any of them a first choice, and this one gives all of them the best they can have.

The other half of the same fact runs the opposite way. Side two’s fortunes are exactly inverted: at M1 every member of side two holds the worst partner that any stable matching would give it, and the generator asserts that member by member across the whole stable set before it draws anything. The order is one order read two ways, which is why the argument for it is a counting of the same objects twice rather than two separate arguments.

The two extremes are the two constructions #

The top and the bottom are not abstractions to be searched for. They are what deferred acceptance hands back, and which one it hands back depends entirely on who does the proposing.

The two runs, on one profile, return the two ends. Neither construction was told to look for an extreme; each simply lets the proposing side work down its own list and lets the receiving side hold the best offer so far, and the extreme falls out.

The consequence is blunt enough to be the title of this essay. The choice of who proposes is not a detail of the procedure. It is the choice of which end of the stable set the instance lands on, and every member of the proposing side does at least as well at their end as at any stable matching whatever, while every member of the receiving side does at worst.

How many proposals either run takes, and how that number would grow, is a question about cost; another site in this fleet owns computation read as cost and the question belongs there. Nothing here compares eight to anything.

Better, taken one member at a time #

The order alone would already be a surprise. The lattice is more.

Take two stable matchings and build a third by letting every member of side one keep whichever of their two partners they prefer. Call it the join. Do it the other way — everyone keeps the one they prefer less — and call it the meet.

Two separate things have to go right and neither is remotely obvious. The join is defined member by member with no coordination at all, so nothing prevents two members of side one from choosing the same partner, in which case the result is not a matching. And even when it happens to be a matching, there is no reason for it to be free of a blocking pair: stability is a condition on all $n^2$ pairs, and the join was assembled without consulting a single one of them.

Both hold. On the diamond above, M2 and M3 are the incomparable pair, and their join is M1 and their meet is M4 — so the two things neither of them dominates are the top and the bottom, both already in the set. The figure checks this on every ordered pair, all 16 of them, and asserts of all 32 results both that the pointwise choice is one-to-one and that it is stable. If either failed on this instance the figure would refuse to draw.

A set with an order in which any two elements have a least upper bound and a greatest lower bound is a lattice, and that is the whole claim: the stable matchings of a preference profile form one.

The same object as a number’s divisors #

The word “lattice” arrives here out of preferences, which makes it worth saying where else this collection has met it. The divisors of sixty, ordered by divisibility, are a lattice: any two of them have a greatest common divisor and a least common multiple, and on the exponent vectors those are the componentwise minimum and the componentwise maximum.

Set the two side by side and they are the same manoeuvre performed on different material.

• Divisors: an element is a vector of exponents, one coordinate per prime, and the meet and the join take the smaller and the larger exponent in each coordinate independently.
• Stable matchings: an element is a vector of partners, one coordinate per member of side one, and the meet and the join take the worse and the better partner in each coordinate independently.

In both cases the operation is defined coordinatewise, and in both cases the substantial content is that the result stays inside the set. For divisors that is nearly free — every componentwise minimum of exponent vectors bounded by $n$’s is another such vector, so every result is a divisor. For matchings it is a theorem, because the set is cut out by a condition on pairs rather than by coordinate bounds, and the coordinatewise operation knows nothing about that condition.

That is why the divisor lattice is drawn as a box and this one is not. The stable set has no coordinates of its own; it is whatever survived the exclusion, and the fact that it survives coordinatewise combination too is the surprise. Both are drawn as Hasse diagrams — which is what a Hasse diagram is for, since a partial order is exactly the thing a diagram of covers determines — both have a top and a bottom, and John Conway noticed in the 1970s that both are distributive lattices — a stronger property that the figures here do not check and that this essay therefore does not claim on their authority.

One caution, since this collection uses the word twice. The lattice of points reached by whole-number steps is a different object with the same name: it is a subgroup of the plane, not an ordered set, and nothing about joins and meets carries over. A shared name is not a shared structure.

There is a third relative worth one sentence. Deferred acceptance can be read as iterating a monotone map on this order until it stops moving, which makes the extremes the extreme fixed points of that map — a fixed-point theorem of a rather different flavour from the one this collection draws, and a route to the same two matchings that never mentions a proposal.

When the lattice is a single point #

None of this is automatic, and the honest way to show it is an instance where the gap between the extremes closes entirely.

On that profile the question “who proposes?” has no consequences at all, because the exclusion left one survivor and both constructions have to find it. It is the control the previous sections need: the gap between the top and the bottom is a feature of a profile, not of the definition, and a reader who took the diamond as the general picture would have taken an accident of these lists for a theorem.

The extreme case in the other direction is worth naming too. When every member of one side has the same list, the pairs are decided almost immediately and the stable set is usually tiny; the profiles with rich stable sets are the ones where the two sides’ rankings disagree in a coordinated way, and finding one is a search rather than a construction. Both of the varied instances below were found that way, by generating random profiles and keeping the ones with the shape wanted.

Chains, and wider instances #

The diamond is not the only shape the order takes. Here is the same size of instance with a stable set that runs in a single line.

A chain is a lattice, so nothing is violated; it is simply a lattice in which the join never produces anything new. The diamond is more informative precisely because M2 and M3 have a join that is neither of them.

That last row is the point of enlarging the instance. In the diamond the join of the incomparable pair was the top and the meet was the bottom, which could be mistaken for the extremes being the only place a join can land. At five it is not: M4 and M6 sit in the middle of the order, three of the twenty-eight pairs are incomparable, and combining that pair coordinatewise produces two matchings that neither of them was near.

What the pictures decide and what they do not #

Every figure above is a complete search of one preference profile. That fixes exactly what can be concluded from it, and the boundary is sharper here than in most of this field.

What the drawings settle. That the stable set of this instance is closed under the pointwise better and the pointwise worse, for every one of its ordered pairs, with each result tested against the definition of stability rather than assumed. That the top of the order is what side one proposing returns and the bottom what side two proposing returns, on this instance, checked coordinate by coordinate. That every member of side two holds its worst stable partner at the top, checked against every member of the stable set. And that stability can leave one survivor as easily as four, since one profile above does exactly that.

What they cannot settle. That any of it holds anywhere else. The lattice property is a theorem quantified over every preference profile, and a complete search of a four-by-four instance is a single confirming case — the same asymmetry an exhaustive search always has, pointing the wrong way. One instance can refute a universal claim and never establish one, and this essay’s claims are all universal. The figures are honest witnesses and the proof is elsewhere: it is the argument that a member of side one rejected at the join would have to have been rejected in one of the two matchings it came from, and that argument does not look at any lists at all.

Two further limits are worth stating because a picture invites the opposite reading. Nothing here handles ties or incomplete lists — every ranking drawn is strict and complete, and the stable set stops being a lattice in the same clean way the moment either assumption is dropped. And the number of stable matchings drawn — four, one, eight — is a property of the profile that produced it and not a rate; a reader who averages them has averaged three deliberately chosen instances.

Where the ladder goes next #

The lattice settles which stable matching a stated procedure returns, and it does so in the strongest terms available: the proposing side gets the best stable matching it could have and the receiving side the worst.

That immediately raises the question the next rung is about. If the receiving side is handed its worst stable partner by the rule, and the rule takes submitted lists as its input, then a member of the receiving side has a reason to submit something other than the truth — and the question of whether that ever pays is settled the way everything in this anchor is settled, by forming every list the member could hand in and running the construction on each. It does pay, and the search that finds it also runs the same sweep over the proposing side and comes back empty.