No stable rule is safe from a lie

Two rungs of this ladder have been good news. A stable matching always exists, and the construction that finds one hands the proposing side the best stable matching there is. Here is the third rung, and it takes some of that back.

What honesty would have to mean #

A preference profile is the whole input: every member of side one holding a strict ranking of side two, and every member of side two holding a strict ranking of side one. A rule is anything that turns such a profile into a matching, and it is stable when what it returns has no blocking pair — no two participants who would each rather have the other than what they were given.

Nothing in that description says the rule is handed the truth. It is handed whatever the participants submit, and a ranking is not a measurement of anything. So there is a further property a rule might have, and it has a name:

Strategy-proofness. For every profile, every participant, and every ranking that participant could submit instead of its own, the partner obtained by submitting the truth is at least as good — judged by the ranking actually held.

That is a universal claim three times over, which is what makes it fragile. A single profile, a single participant and a single submission that does better ends it. The figure above is that triple, found by looking at all of them.

The instance is four against four, side one lettered and side two numbered, and the rule is deferred acceptance with side one proposing. Member 4 holds the ranking C D A B. Told the truth by everybody, the construction returns A4 B2 C1 D3, so member 4 ends with A, the third of the four names it ranked. Four of the twenty-four rankings it could have submitted instead return D, which stands second on the list it actually holds.

Nothing about that requires member 4 to know anything. It is a fact about the profile, discovered by a machine that tried every ranking.

The ninety-six that pay nothing #

A search that reports found whatever it is pointed at reports nothing by reporting it, and this is the point in the essay where that stops being a slogan.

The lower panel of the first figure runs the identical sweep over every member of the proposing side: each of the four in turn submits each of the twenty-four rankings, the construction is run, and the partner obtained is compared against the partner the truth produced. Ninety-six constructions, and the column of results is four zeros. Counting member 4’s own twenty-four and the seventy-two belonging to the other three members of the receiving side, $24 + 96 + 72 = 192$ rankings were submitted and one hundred and ninety-two matchings were built to answer one question.

Zero is what makes four a number. And the control has to be more than a machine that cannot say found, which is why the second placement matters more than it looks.

Member 1’s twenty-four submissions do not all return the same partner. Eight of them return A, four return C, and twelve return D, and $8 + 4 + 12 = 24$. Its true ranking puts B first, C second, A third and D last, so the outcomes it can reach by lying are the same as the truth or worse, and B — the one it actually wants — never appears in the grid at all. That is a much stronger negative than a search over a space where nothing moves, and it is drawn rather than asserted.

Where the lie lands #

The four profitable submissions do not conjure something new. Every one of them returns the matching A3 B2 C1 D4, and that matching is already stable for the true profile.

This is the mechanism, and it is the reason the previous rung is a prerequisite rather than a courtesy. The stable matchings of a profile form a lattice ordered by side one’s common preference, and deferred acceptance with side one proposing returns its top element — which is simultaneously the worst stable matching for every member of side two. A member of the receiving side that can drag the outcome one step down the lattice improves, by construction, because down is the direction the order was built to mean.

The lie is a refusal. Member 4 submits a ranking that puts A below where it truly stands, so A is turned away when it proposes; A goes elsewhere, the chain of rejections runs its course, and D reaches member 4. The submitted ranking is never consulted again after the construction ends. Only the held ranking decides whether the result was worth it, and the figure judges every one of the twenty-four submissions by the held ranking alone.

So the proposing side’s honesty and the receiving side’s exposure are the same fact seen twice. The construction is already giving side one everything the stable set contains, so there is nowhere better for a proposer to be dragged; it is giving side two the least the stable set contains, so every other stable matching is an improvement worth reaching for.

Small enough to read entirely #

Twenty-four cells is more than most readers will check by hand. Three against three is six.

Side one holds A: 1 2 3, B: 1 2 3, C: 2 1 3, and side two holds 1: C A B, 2: A C B, 3: A B C. Truthfully, A and B both propose to 1 in the first round; 1 prefers A and keeps it; B is passed down to 2, which already holds C and prefers C; B ends at 3. The matching is A1 B3 C2 and member 1 has A, the second of the three names it holds.

Submitting C B A instead moves A below B in what member 1 declares. Now 1 keeps B in the first round and rejects A. A proposes to 2, which prefers A to the C it is holding and takes it. C, displaced, proposes to 1 — and C is what member 1 truly wanted all along, so B is released and ends at 3 as before. The matching is A2 B3 C1.

At this size the whole phenomenon is visible at once: two stable matchings, the rule returning the one side one prefers, and one member of side two able to reach the other by rearranging a list of three names. Every three-by-three instance that has a profitable submission at all has exactly one, which is a small and pleasant fact and is emphatically not a rate for anything larger.

An instance where nothing pays at all #

The theorem coming at the end of this essay says that no stable rule escapes lying somewhere. It does not say that lying pays everywhere, and the difference is worth a placement of its own.

Member 3 is in the worst position the instance offers anyone and can do nothing about it. The reason is structural: this profile has exactly one stable matching, so there is no lattice to be dragged down and no second stable outcome to reach. Every stable rule returns the same thing here, and every submission that leaves the construction’s output stable leaves it identical.

That is the general shape of the exemption. Where the stable set is a single point, honesty is safe for everybody; where it has more than one point, somebody on the receiving side has an interest in the other points and, given the right instance, a submission that gets there. The impossibility is therefore not a statement about matching in general but about matching where the stable set is large enough to have an inside.

What counts as a lie #

Every figure on this page searches the same space: complete strict rankings of the other side, the same shape of object as the truth. That is a choice, it is the one the generator states, and it does not cover everything a participant could hand in.

A submission could also be shorter than the truth: a list that names some partners and declares the rest unacceptable, so that a proposal from an unnamed member is refused outright rather than merely ranked low. Those are not rankings of side one and no cell of any grid above stands for one. Widening the space that way changes several of the zeros on this page — member 1 of the four-by-four instance, which no ranking helps, ends with B if it submits the single-name list naming only B — and that is a computation these figures do not draw, stated here to mark the edge of what their zeros cover.

What survives the widening is the proposing side’s column. No member of side one does better by any submission at all, short or long, and that is a theorem rather than a census. What does not survive is the reading that a zero in the receiving side’s column means safety; it means safety against rankings.

That distinction is the whole reason the theorem below needs shortened lists to prove itself, and it is a good instance of the general habit: the answer to can anyone gain? depends on a stated set of permitted moves, exactly as the answer to what four circles can separate depends on a stated set of permitted regions.

What the picture cannot show #

Here is the honest position, and it belongs before the theorem rather than after it.

Everything above is a census of one profile under one rule. Twenty-four submissions for member 4, twenty-four for each of seven other participants, one hundred and ninety-two constructions, and a verdict on each. A reader can redo any of it. What it establishes is a statement with existential quantifiers on the outside: there is a profile and there is a participant for whom there is a better submission. That is enough to end strategy-proofness for deferred acceptance with side one proposing, because strategy-proofness is a claim about every profile and one counterexample is fatal to it.

The theorem is a different sentence. It says that for every rule that always returns a stable matching there is such a profile — and every rule is not a finite set. The quantifier sits on the outside and points at an unbounded collection, and the order of the quantifiers is the whole content: for each rule, some profile defeats it is not some profile defeats every rule, and only the second could conceivably be drawn.

No finite search reaches the first. A machine can be pointed at a rule and told to look; it cannot be pointed at the rules. This is the same admission the transcendence essay has to make about $\pi$ — a search over polynomials of bounded degree is evidence and the claim is about all of them — and the same one the incompleteness essay makes about proofs. The drawing settles the finite half honestly and hands the rest to an argument in prose. That is the arrangement, and pretending otherwise would be the one thing a page of exhaustive searches cannot afford.

There is a second thing no figure here decides. How often a profitable submission exists — among instances of this size, or of any other — is not a question a census of one instance touches, and four out of twenty-four is not a frequency. It is a count.

The theorem, and the shape of its proof #

The statement, in the vocabulary this ladder has built:

No stable rule is strategy-proof. For every rule that always returns a stable matching, there is a preference profile and a participant for whom some submission returns a strictly better partner than the truth does.

The proof is short and it is the reason shortened lists had to be introduced above. Take a profile whose stable set has two elements, $\mu_1$ best for side one and $\mu_2$ best for side two — the three-by-three instance drawn earlier is one. A stable rule must return one of the two, and it can only return one.

Suppose it returns $\mu_1$. Then some member of side two strictly prefers $\mu_2$, since $\mu_2$ is the better of the two for all of that side and the two matchings differ. Let that member submit the list truncated just after its $\mu_2$ partner. On the new profile $\mu_1$ is not stable, because that member would rather be unmatched than hold what $\mu_1$ gives it; $\mu_2$ still is. Whatever the rule returns must be stable for what it was given, and everything stable there pairs the truncating member with its $\mu_2$ partner or better. The lie paid.

Suppose instead it returns $\mu_2$. The same argument runs with the sides exchanged and a member of side one lying. A rule has to do one or the other, so no rule escapes. That is a proof by cases with no gap between them, and it is finite in a way the claim it proves is not — the work is done on one profile, and the conclusion is about every rule, because the profile defeats each of them separately.

Note what the argument does not do. It never asks how the rule computes anything: a rule here is a function from profiles to matchings and nothing else, and whether it is deferred acceptance, an exhaustive search of the sort the census figure runs, or a table written out in advance makes no difference to a single line. Questions about what a procedure costs to run belong to another site in this collection and none is raised here.

Where the impossibility came from #

Gale and Shapley’s existence theorem is from 1962 and says nothing about incentives. The two incentive results arrived twenty years later and in the order that made the second one sting.

Dubins and Freedman proved in 1981 — in a paper titled, with some relish, Machiavelli and the Gale–Shapley algorithm — that the proposing side cannot gain by any misreport whatsoever. That is the positive half, and it is the ninety-six zeros in the first figure, established for all profiles rather than counted on one. Roth proved the negative half in 1982: no stable rule at all, however cleverly built, makes honesty safe for every participant.

The pairing is what makes the result more than a disappointment. Strategy-proofness is not lost to a defect in one construction that a better construction might repair; it is incompatible with stability itself. Any rule that repairs it must return something with a blocking pair on some profile, and a matching with a blocking pair is one two participants have a standing reason to abandon — which is the property the first rung of this ladder exists to establish and the only reason stability was asked for.

So the choice is forced and there are exactly two things on offer, which is the recurring shape of every impossibility in this field. A voting rule faces the same trade between respecting a profile and being safe from a misreport, and the resemblance is not decorative: both are conditions on a function from profiles to outcomes, both are individually satisfiable, and both collapse when required together. Different objects, same collision.

Where this anchor ends #

Three rungs, three verdicts, and each one is smaller than the last. Something exists. The construction that finds it favours a side. And the whole arrangement can be worked by the disfavoured side, on some profiles, under any rule that keeps the property the arrangement was for.

What the figures contributed is precisely the finite part: one profile, one rule, one hundred and ninety-two constructions, four submissions that beat the truth and a hundred and eighty-eight that do not. What they could not contribute is the quantifier over rules, and the page would be dishonest if the pictures were allowed to imply it. The census of blocking pairs shows what a complete search looks like when the claim is finite; the theorem above shows what has to happen when it is not.

The next anchor changes the object entirely. Preferences give way to numbers and constraints, the outcome stops being a pairing and becomes a point, and the impossibility gives way to an equality — two quantities defined by unrelated procedures that are forced to meet.