Proposer-Optimality and Strategic Truncation

Deferred acceptance is not neutral, and its bias is total rather than statistical: the matching it returns is simultaneously the best stable matching for every proposer and the worst stable matching for every receiver — not on average, not usually, but agent by agent, on every instance. That fact is a corollary of the lattice structure that John Conway found in the set of stable matchings (Conway in Knuth 1976, as reported by Roth 2008 Thm 3), and it propagates directly to incentives. Dubins & Freedman (1981) and Roth (1982) independently proved that truth-telling is a dominant strategy for every proposer, and that no coalition of proposers can all gain together; Roth also proved that no stable mechanism is strategyproof for both sides at once. Receivers, denied that protection, have exactly one useful lie — truncation, declaring the tail of a true list unacceptable — and its power is bounded with knife-edge precision: a truncating receiver can reach their receiver-optimal partner and can never do better, because the lattice has no room above its own bottom element (Gale & Sotomayor 1985 Theorems 1–3; Demange, Gale & Sotomayor 1987 as stated in Roth 2008 Thm 9). And yet the National Resident Matching Program, running this mechanism over 20,000 applicants a year, found that at most 11 to 22 applicants per year could have profited. This note is about that gap: why the ceiling exists, what coalitions can and cannot add, and the three separate mechanisms by which real markets collapse the lattice until the manipulation the theory guarantees becomes something almost nobody can use.

Prerequisite — read the sibling first, this note deliberately does not repeat it

The Gale-Shapley Algorithm (7,117 words) states and proves proposer-optimality and receiver-pessimality, gives the O(n²) implementation in C, measures the rank asymmetry (at n = 4096, proposers average their 8.90th choice and receivers their 467.93rd, on the same instances), and demonstrates the truncation manipulation on a worked 3×3 instance. It also reports the headline experiment this note builds on: over 360,000 receiver-instances, the best single truncation lands exactly on the receiver-optimal partner 100.00 % of the time, 24.7–35.9 % of receivers have a profitable truncation, and 180,000 proposer misreports yielded zero gains. Stable Matching (9,426 words) covers the blocking-pair definition and the lattice. This note picks up where both stop: why the ceiling is exactly the receiver-optimal partner, what changes with coalitions, and why the real NRMP looks nothing like the random instances.

Resolves an open flag in the sibling note

The Gale-Shapley Algorithm carries a [!warning] Uncertain callout asking whether “best truncation == receiver-optimal partner” holds in general or only for the complete-list equal-sides case it measured, and noting that Gale & Sotomayor (1985) “was located but is paywalled at Taylor & Francis and no open mirror was found.” It has now been read. The pareto.uab.es copy is a genuine JSTOR scan with no text layer — pdftotext extracts 0 characters, which is an extraction failure, not a retrieval failure — and rendering it with pdftoppm -png -r 135 produces legible page images. The masthead confirms The American Mathematical Monthly 92(4), April 1985, pp. 261–268. Theorems 1–3 are transcribed below and they settle the question: the bound is general for the marriage model with strict preferences, and it is enforced by the lattice, not by the completeness of the lists.

Mental Model — The Manipulation Is a Walk Down the Lattice

The single idea that makes everything in this note follow is that a receiver who truncates is not conjuring a better outcome out of nothing. They are moving the mechanism’s output from the top of a lattice to a lower point in the same lattice, and the lattice’s bottom element is the floor beneath which they cannot dig.

Conway’s decomposition is worth stating because the ceiling is an immediate consequence of it. Let μ and ν be two distinct stable matchings. Ask every proposer to point at whichever of μ(m), ν(m) they prefer. No two proposers point at the same receiver — if a receiver were pointed at twice, she would prefer one of the two pointers, and would form a blocking pair with him in whichever matching did not pair them, contradicting stability. So “everyone takes their favourite of the two” is itself a matching, and it is itself stable. Define μ >_M ν when every proposer weakly prefers μ. Then:

Lattice Theorem (Conway, in Knuth 1976). “When preferences are strict, the set of stable matchings is a lattice with respect to the partial order >_M. The maximum element of the lattice is μ_M, the stable matching produced by the men-proposing deferred acceptance algorithm, and its minimum element is μ_W, the matching produced by the women-proposing deferred acceptance algorithm” (Roth 2008, Theorem 3).

flowchart TB
    TOP["<b>&mu;_M</b> — top of the lattice<br/>proposer-optimal = receiver-PESSIMAL<br/>what honest deferred acceptance returns"]
    MID1["intermediate stable matchings"]
    MID2["..."]
    BOT["<b>&mu;_W</b> — bottom of the lattice<br/>proposer-pessimal = receiver-OPTIMAL<br/>the receivers' ceiling"]
    TOP --> MID1 --> MID2 --> BOT
    R["a receiver r truncating<br/>her stated list"] -->|"can drag the outcome<br/>DOWN the lattice"| MID1
    R -.->|"as far as"| BOT
    R -.->|"NEVER reachable: nothing here is<br/>stable under the TRUE preferences"| FLOOR["outcomes r would like<br/>better than &mu;_W(r)"]
    P["a proposer misreporting"] -.->|"already at his best element:<br/>nowhere to go, so he tells the truth"| TOP

What it shows: the stable set as a one-dimensional cartoon of a lattice, with the two deferred-acceptance runs pinned to its two extremes, and both sides’ manipulation problems drawn as movement within it. The insight to take, and the whole answer to “why can’t truncation do better”: μ_W is not an arbitrary stopping point, it is the bottom of the lattice. Anything a receiver would prefer to μ_W(r) is, by definition of “best achievable partner”, not achievable at any stable matching under her true preferences — and a stable mechanism can only ever hand her something stable.

The asymmetry in the diagram is the asymmetry in the incentives. A proposer under honest play is already at his best element: the top of the lattice. There is nowhere up. A receiver under honest play is at her worst element, with the whole lattice above her — in her own ordering, below her — to walk into.

The Theorems, Stated Exactly

Proposers: truth-telling is dominant, and coalitions do not help

Theorem (Dubins & Freedman 1981, Theorem 9). “Suppose M participates in a Gale-Shapley algorithm, but uses a false rank ordering. The university M gets by this foul play is no better — measured by M’s true rank ordering — than the one M would have got by fair play” (Dubins & Freedman 1981).

Their abstract states the coalitional strengthening, which is the part usually dropped: “no coalition of students can simultaneously improve the lot of all its members if those outside the coalition state their true preferences.” Roth proved the individual result independently and in the many-to-one setting: “In the matching procedure which always yields the optimal stable outcome for a given one of the two sets of agents, truthful revelation is a dominant strategy for all the agents in that set” (Roth 1982, Theorem 5).

Citation hazard — two different Roth 1982 papers

The deferred-acceptance strategyproofness result is Roth, “The Economics of Matching: Stability and Incentives,” Mathematics of Operations Research 7(4), November 1982, pp. 617–632 — the paper read for this note; its opening page numbering (617 onward) is legible in the scan even though the OCR mangles the masthead itself into “MA n i l MA I K S Ol O I T K A I I O N S R] Si,ARCH”. It is not Roth’s Economics Letters 9:127–132 paper of the same year, which is about the strategyproofness of Top Trading Cycles. The two are conflated often enough that a reference list citing “Roth 1982” for deferred acceptance and “Roth 1982” for TTC without disambiguation is almost certainly wrong about one of them.

Both sides: impossible

Theorem (Roth 1982, Theorem 3). “No stable matching procedure for the general matching problem exists for which truthful revelation of preferences is a dominant strategy for all agents.”

This is not a defect of Gale–Shapley; it is a fence around every stable mechanism, in the family of Impossibility Results. Roth pins the boundary from both directions. His Theorem 4 shows that abandoning stability buys universal strategyproofness — serial dictatorship, “which bears some resemblance to the football draft,” is efficient and dominant-strategy truthful for everyone. His Theorem 7 shows you cannot even buy partial protection: “No stable matching procedure exists which never gives any agent an incentive to misrepresent his kth choice, for k > 1.”

Roth 2008 gives the two-by-two instance that proves Theorem 3 in six lines, and it is worth carrying in your head:

   P(m1) = w1, w2        P(w1) = m2, m1
   P(m2) = w2, w1        P(w2) = m1, m2

There are exactly two stable matchings, μ_M = {m1–w1, m2–w2} and μ_W = {m1–w2, m2–w1}, so any stable mechanism h must return one of them. Say h(P) = μ_M. Then if w1 declares m1 unacceptable — submitting P'(w1) = m2 — the unique stable matching under P' is μ_W, so h(P') = μ_W, and w1 has profited. The argument is symmetric if h(P) = μ_W. The manipulation used in the proof is a truncation, which is not a coincidence.

The ceiling: Gale & Sotomayor 1985

This is the result the sibling note could not obtain, and it is the direct answer to “why can truncation not do better than the receiver-optimal partner.”

Theorem 1 (Gale & Sotomayor 1985). “If there is more than one stable matching, then there is at least one woman who will be better off by falsifying, assuming the others tell the truth.”

Their proof is the truncation construction, stated in one line: take any w with μ_W(w) ≠ μ_M(w), and “let w falsify by removing from her preference list all men who rank below μ_W(w).” Then μ_W is still stable under the new preferences (deleting entries can only remove blocking pairs), Proposition 1 guarantees w is not left unmatched, and since every man she likes less than μ_W(w) is gone, she must get someone she likes at least as well as μ_W(w) — which she strictly prefers to μ_M(w). That is the whole manipulation, and it establishes the lower bound: truncation always reaches μ_W(w).

The upper bound is Theorem 3, and it is the lattice argument:

Theorem 3 (Gale & Sotomayor 1985). “Suppose the women choose any set of strategies P'_W (preference lists) that form an equilibrium point for the matching game. Then the corresponding M-optimal matching for (M, W; P') is one of the stable matchings of `(M, W; P).”

Read that carefully: any equilibrium of the manipulation game produces a matching that is stable under the TRUE preferences. And the set of matchings stable under the true preferences is exactly the lattice, whose bottom element is μ_W. The paper draws the conclusion itself, in a sentence that is the thesis of this whole note:

“By falsifying appropriately the women can achieve by equilibrium point strategies any stable matching, thus, in particular, the W-optimal matching. On the other hand, the women cannot get too greedy for if any set of strategies gives some woman w a mate whom she likes better than μ_W(w), this will not be an equilibrium point, by Theorem 3, so some other woman can change the matching to her advantage by choosing a different strategy.”

So the ceiling is not “truncation happens to be weak.” It is: a stable mechanism can only output something stable, an equilibrium of the manipulation game outputs something stable under the true preferences, and μ_W is the bottom of that set. No amount of cleverness in choosing the lie changes what the mechanism is allowed to emit.

The individual version of the same bound, for arbitrary misreports rather than just truncations and for coalitions rather than individuals, is:

Theorem 9 (Demange, Gale & Sotomayor 1987, as stated in Roth 2008). “Let P be the true preferences (not necessarily strict) of the agents, and let P' differ from P in that some coalition A of men and women mis-state their preferences. Then there is no matching μ, stable for P', which is preferred to every stable matching under the true preferences P by all members of A.”

Take A = {r} a single receiver. “Preferred to every stable matching under P” means “strictly better than r’s best achievable partner”, i.e. better than μ_W(r). Theorem 9 says no such outcome exists. That is the sibling note’s measured 100.00 % ceiling, derived.

flowchart LR
    subgraph LOWER["the FLOOR of the manipulation: Gale-Sotomayor Thm 1"]
        L1["truncate the true list<br/>immediately after &mu;_W(r)"] --> L2["&mu;_W stays stable<br/>(deleting entries only<br/>removes blocking pairs)"] --> L3["Proposition 1: the set of<br/>unmatched agents is the same<br/>at every stable matching<br/>-> r is NOT left unmatched"] --> L4["r gets &mu;_W(r) or better;<br/>everything worse was deleted"]
    end
    subgraph UPPER["the CEILING: Gale-Sotomayor Thm 3 / DGS Thm 9"]
        U1["a stable mechanism can only<br/>output a matching stable<br/>under the STATED preferences"] --> U2["at any equilibrium of the<br/>manipulation game, that matching<br/>is stable under the TRUE preferences"] --> U3["the true-preference stable set<br/>is the lattice, with bottom &mu;_W"] --> U4["so no equilibrium hands r<br/>anything better than &mu;_W(r)"]
    end
    LOWER --> EQ["floor == ceiling == &mu;_W(r)<br/>the bound is TIGHT and ATTAINED"]
    UPPER --> EQ

What it shows: the two halves of the tight bound, each traced to the result that supplies it. The insight to take: the reason the measured figure is 100.00 % rather than 99-point-something is that both bounds are theorems, not tendencies. A measurement that came out at 99.9 % would be a bug in the measurement, not an interesting exception.

Verified: the ceiling, and what coalitions add

The sibling note attacked the individual case with honest opponents. The open ground — and what is measured here — is what happens when more than one agent lies at once. Exhaustive search over small instances, gcc 16.1.1 -O2, splitmix64 with seed 13579 + 7919n, complete strict preference lists on both sides, proposers proposing.

For receivers, every joint truncation profile was enumerated: each of the n receivers independently chooses a cut point in 1..n (with n meaning honest), giving nⁿ joint reports per instance, evaluated in full. For proposers, every pair of arbitrary permutation misreports was enumerated: all C(n,2) pairs times all (n!)² joint misreports.

	`n = 4`, 3,000 instances	`n = 5`, 400 instances	`n = 6`, 40 instances
receivers with a profitable solo truncation	3,009 / 12,000 = 25.07 %	559 / 2,000 = 27.95 %	75 / 240 = 31.25 %
solo truncations landing strictly better than `μ_W(r)`	0	0	0
joint truncations where ALL deviators beat `μ_W`	0	0	0
joint truncations where SOME deviator beats `μ_W`	98,856	273,206	554,556
coalitions (size ≥ 2) where all members gain vs. honest	31,418	21,684	31,625
instances where all receivers truncating at `μ_W` yields exactly `μ_W`	3,000 / 3,000	400 / 400	40 / 40
proposer pair misreports tested (all perms × all perms)	10,350,000	57,596,000	—
… pairs where BOTH strictly gain	0	0	—
… reports where one gains and the partner is not hurt	40,314	218,697	—

Six readings, in increasing order of how much they change the picture.

1. The solo figures independently reproduce the sibling. 25.07 % at n = 4 and 31.25 % at n = 6 against the sibling’s 24.73 % and 31.09 %, arrived at by a completely different route — the sibling searched truncation points exhaustively, this measurement simply compares each receiver’s partner under the two deferred-acceptance orientations and counts the disagreements, which by Roth & Sotomayor’s Theorem 7 is exactly the manipulable set. Two independent implementations landing within 0.3 points is the cross-check that the sibling’s headline number deserved and did not have.

2. 0 solo truncations beat μ_W. Demange–Gale–Sotomayor’s Theorem 9 for singleton coalitions, confirmed. This is the sibling’s 100.00 % restated as an absence.

3. 0 proposer pairs both gain, across 57.6 million joint misreports at n = 5. Dubins & Freedman’s coalitional theorem, confirmed at a scale that would have caught a subtle error. Note the misreports here are arbitrary permutations, not truncations — the theorem’s strength is that it covers every lie a proposer can tell.

4. But 218,697 reports have one proposer gaining while his partner is not hurt. The word “all” in “no coalition can simultaneously improve the lot of all its members” is doing real work, and this is what its absence would look like. A proposer coalition can absolutely shift the outcome in one member’s favour; what it cannot do is make that a Pareto improvement over honesty for the coalition. Anyone quoting Dubins–Freedman as “proposer coalitions are pointless” has dropped the quantifier.

5. The genuinely surprising row: 554,556 joint truncations in which SOME deviating receiver ends up strictly better than her own μ_W partner — while ZERO have all deviators doing so. This is not a contradiction of anything; DGS Theorem 9 forbids only the simultaneous case. But it sharpens the sibling’s headline in a way worth stating plainly: the “best truncation lands exactly on the receiver-optimal partner” ceiling holds against honest opponents. It does not hold against lying ones. A receiver can be carried above her own μ_W partner by someone else’s truncation — she just cannot arrange it, because Gale & Sotomayor’s Theorem 3 says any configuration in which she is above μ_W(r) is not an equilibrium, so whoever carried her there has an incentive to stop.

6. All receivers truncating at their μ_W partner yields exactly μ_W, in 100 % of instances at every size. This is Gale & Sotomayor’s Theorem 2 measured: “Let μ be any stable matching for (M, W, P) and suppose each woman in μ(M) chooses the strategy of listing only μ(m) on her preference list. This is an equilibrium point.” Taking μ = μ_W, the receiving side can collectively guarantee itself the bottom of the lattice, and no member wants to deviate. Gale and Sotomayor add the sting in §5: this equilibrium is the only strong one — for any other stable μ, a subset of receivers can profitably deviate together. So the receivers’ coalition-proof outcome is precisely the receiver-optimal matching, and nothing beyond it.

The net answer to “what do coalitions add?” in the one-to-one marriage model is therefore: nothing, for either side. Proposers gain nothing individually and nothing collectively. Receivers gain individually up to μ_W, and collectively also only up to μ_W. The lattice is the binding constraint at every coalition size.

Uncertain

Verify: whether “coalitions add nothing” survives into the many-to-one (hospital–residents) model. Reason: it does not, and the difference is important, but the primary sources were not fetched. Roth & Peranson note that programs with more than one position “may, at least in theory, profit both from truncating their ROLs, and from reducing the number of positions they submit to the match,” citing Sönmez (1997, 1999) — neither read here. Roth 1982’s Theorem 5 is stated for the one-to-one and the many-to-one proposing side, but the coalitional Dubins–Freedman result is a marriage-model theorem. To resolve: read Sönmez, “Manipulation via capacities in two-sided matching markets,” JET 77 (1997), and Roth & Sotomayor, Two-Sided Matching (1990), ch. 5. A recent arXiv treatment of two-sided coalitional manipulation (Hosseini, Umar & Vaish 2022) was fetched and confirms the topic is live, but its results were not used to support any claim above. #uncertain

The Real-Market Gap

Here is the puzzle the theory leaves behind. Roth & Peranson’s computational study of actual NRMP data found the scope for manipulation to be negligible. Yet in random instances with complete preference lists, the manipulable set does not shrink with market size — it grows to swallow almost everyone.

Measured here on uniformly random complete preference lists, counting receivers whose partner differs between the proposer-optimal and receiver-optimal matchings (which by Roth & Sotomayor Theorem 7 is exactly the set with a profitable manipulation):

`n`	trials	receivers with >1 achievable partner	proposers with >1
4	4,000	25.00 %	25.00 %
8	4,000	35.79 %	35.79 %
16	4,000	46.19 %	46.19 %
32	4,000	58.02 %	58.02 %
64	4,000	68.58 %	68.58 %
128	4,000	78.66 %	78.66 %
256	800	85.81 %	85.81 %
512	800	91.06 %	91.06 %
1,024	200	94.60 %	94.60 %
2,048	200	96.73 %	96.73 %
4,096	200	98.07 %	98.07 %

The two columns are identical at every size, which is forced: the two extreme matchings differ on the same set of agents viewed from either side. And the trend is unambiguous — in a random complete-list market of 4,096, 98 % of receivers have a profitable lie available. The sibling note’s “24.7–35.9 %, rising with n” was reading the very bottom of this curve.

So why does the NRMP not look like this? Three separate mechanisms collapse the lattice, and they compound.

flowchart TB
    BIG["random market, COMPLETE preference lists<br/>lattice is huge: 98% of receivers manipulable at n=4096"]
    BIG --> M1["<b>1. SHORT LISTS</b><br/>agents interview a bounded number of partners<br/>Roth-Peranson: most NRMP applicants ranked <= 15 programs<br/>Immorlica-Mahdian 2005; Kojima-Pathak 2007"]
    BIG --> M2["<b>2. IMBALANCE</b><br/>one extra agent on one side flips the whole picture<br/>Ashlagi, Kanoria &amp; Leshno 2017"]
    BIG --> M3["<b>3. INFORMATION</b><br/>the manipulation requires knowing where to cut<br/>Roth-Rothblum 1999; cut one short and you go UNMATCHED"]
    M1 --> OUT["measured NRMP exposure:<br/>11-22 applicants per year<br/>out of 20,000-25,000"]
    M2 --> OUT
    M3 --> OUT

What it shows: the three independent routes from “manipulable in theory” to “unmanipulable in practice.” The insight to take: these are not excuses, they are structural features of real markets that the uniform-random-complete-list model happens to omit. Each one is separately sufficient to shrink the lattice; the NRMP has all three.

Mechanism 1: short lists

Interviewing is expensive, so applicants rank a bounded number of programs regardless of how big the market gets. Roth’s account is that “most rank order lists submitted by applicants had no more than fifteen residency programs listed,” and that Roth & Peranson “showed computationally that if, as such a market gets large, the number of places that a given applicant interviews (and hence the size of his rank order list) does not grow, then the set of stable matchings becomes small” (Roth 2008 §4). Immorlica & Mahdian (2005) proved it analytically for the marriage model; Kojima & Pathak (2007) extended it to many-to-one:

Theorem 14 (Kojima & Pathak 2007, as stated in Roth 2008). “In the limit, as n goes to infinity in a regular sequence of random markets, the proportion of employers who might profit from (any combination of) preference or capacity manipulation goes to zero in the worker proposing deferred acceptance algorithm.”

Measured directly here, with each proposer ranking a uniformly random subset of k receivers and each receiver ranking exactly the proposers who listed her:

`k`	`n = 50`	`n = 200`	`n = 1,000`	`n = 5,000`	`n = 20,000`	unmatched proposers
5	1.3400 %	0.3325 %	0.0515 %	0.0063 %	0.0043 %	~9.1 %
10	5.2667 %	1.2033 %	0.2260 %	0.0473 %	0.0063 %	~3.4 %
15	12.8633 %	2.5258 %	0.5275 %	0.1140 %	0.0225 %	~1.6 %
40	55.8100 %	26.6692 %	5.2870 %	0.6930 %	0.2313 %	~0.14 %

Compare row-wise against the complete-list table: at n = 1,000, complete lists give 94.60 % manipulable; lists of length 15 give 0.53 %. The effect is not a modest attenuation, it is three orders of magnitude, and it strengthens as n grows — exactly the Kojima–Pathak limit.

The k = 15, n = 20,000 cell is the one to stare at: 0.0225 %, which on 20,000 receivers is about 4.5 agents. Roth & Peranson’s measured upper bound on NRMP applicants who could profit from truncation under the program-proposing algorithm was 12 (1987), 22 (1993), 13 (1994), 16 (1995), 11 (1996) out of populations of 20,071 to 24,749 applicants — that is 0.05–0.09 %. A crude uniform-random simulation with k = 15 lands within a factor of a few of a real clearinghouse’s measured strategic exposure. The mechanism is not a hand-wave.

Correction to a widely repeated figure

The number “4 out of more than 60,000” attaches to a different Roth & Peranson experiment and is often misquoted as the count of manipulable applicants. It is not. It comes from a preliminary test of whether the NRMP’s “match variations” (couples, supplemental lists) cause the algorithm to backtrack: all ROLs were truncated at the match point, which in a simple market provably changes nothing, and the paper reports “over the more than 60,000 applicants involved in these experiments, only four were affected by truncations of applicants’ ROLs… they affect on the order of 0.01 percent of applicants” (Roth & Peranson 1999 §V.B.1). That result licenses the methodology — it justifies studying only truncations rather than all misreports — it is not the headline finding. The manipulability upper bounds are Table 4, quoted above. Programs, incidentally, fare differently: their upper bounds run 12–23 under the pre-existing algorithm and 27–36 under applicant-proposing, and a refined 50 %-sampling experiment cut the 1995 applicant-proposing figure from 36 to 22, confirming these are overestimates.

Mechanism 2: imbalance

The second collapse is the least intuitive and the most violent. Ashlagi, Kanoria & Leshno (2017) showed that adding one single extra agent to one side of an otherwise balanced random market destroys the proposing side’s advantage entirely. As summarised in a recent treatment: they “consider random markets with n+1 candidates and n jobs and complete preference lists… They show that on average each candidate is matched to their Ω(n / ln n)th ranked job, a stark drop from their O(ln n)th ranked job in the balanced setting… Thus, the huge advantage of being on the proposing side (over the non-proposing side) is lost as soon as there is any competition” (Potukuchi & Singh 2024 §1).

Measured here, same instances, complete lists, proposer-proposing deferred acceptance throughout — the only change between adjacent rows is one extra proposer:

proposers	receivers	avg rank of matched proposers	avg rank of receivers	receivers manipulable	`ln n`	`n / ln n`
100	100	4.967	20.411	75.84 %	4.61	21.7
101	100	20.598	4.795	14.08 %	4.61	21.7
500	500	6.799	75.041	91.00 %	6.21	80.5
501	500	75.377	6.753	14.01 %	6.21	80.5
1,000	1,000	7.549	135.581	94.32 %	6.91	144.8
1,001	1,000	135.673	7.516	13.11 %	6.91	144.8
2,000	2,000	8.261	246.578	96.69 %	7.60	263.1
2,001	2,000	246.034	8.254	11.96 %	7.60	263.1
4,000	4,000	9.067	448.192	98.05 %	8.29	482.3
4,001	4,000	467.992	8.678	9.26 %	8.29	482.3

At n = 4,000, adding one proposer moves the proposing side’s average rank from 9.07 to 467.99 — a factor of 51.6 — and moves the receiving side from 448.19 to 8.68. The two sides swap places entirely, without changing who proposes. Both figures track the theory: the favoured side sits near ln n (8.29) and the disfavoured near n / ln n (482.3), in both orientations.

And the manipulable fraction collapses from 98.05 % to 9.26 %. The proposing side’s advantage and the receiving side’s manipulation opportunity are the same quantity — the height of the lattice — and competition flattens it. A real market is essentially never exactly balanced. The NRMP has more positions than applicants in some years and fewer in others, and either way it is nowhere near knife-edge. The balanced-random-complete-list model that produces 98 % manipulability is, in this precise sense, a measure-zero pathology.

Mechanism 3: information

The third collapse is the one a participant actually feels. Truncation requires knowing where to cut, and cutting one position too short leaves you unmatched. Roth & Peranson state it flatly: “even in the case of a simple match without match variations, an applicant generally would not have the information needed to submit such a truncation (and if he submitted a truncation that was one program too short he would become unmatched).”

Roth & Rothblum (1999) turned that into theory by modelling what an agent with symmetric beliefs — no ability to distinguish two firms — can rationally do.

Theorem 1 (Roth & Rothblum 1999). A worker whose information about two firms f and f' is symmetric can never improve her outcome, regardless of risk attitude, by reversing her stated preference between them: the resulting random outcome is stochastically dominated by truthful revelation (Roth & Rothblum 1999 §5).

Their Corollary 1 extends this to any reordering under fully symmetric beliefs, and their Lemma 1 adds that a worker who is not going to truncate should never list an unacceptable firm. Together: “if a worker with {F}-symmetric information isn’t going to truncate her preferences, she had better state her true preferences.” Theorem 2 completes it — any non-truncation strategy is dominated — which is why the entire NRMP analysis can restrict attention to truncations without loss.

Corollary 3 is the practical punchline, and it is the design lever: “In games that use the F-optimal stable mechanism with the restriction that all positions must be ranked (i.e. all firms are acceptable), truthful revelation of preferences P_w is a stochastically dominant strategy for a worker with {F}-symmetric information.” If participants must rank everything — as with graduates of a service academy who will be taking some posting — the only manipulation available is truncation, truncation is forbidden, and honesty becomes dominant even on the unprotected side. The impossibility is escaped by removing the option rather than by removing the incentive.

Failure Modes and Gotchas

Truncating one position too short. The failure that makes the whole manipulation unattractive in practice. The gamble is asymmetric: the upside is bounded by the height of the lattice above you — often one or two rank positions in a real market — and the downside is going unmatched entirely. Roth & Rothblum’s dermatology anecdote from the 1997 NRMP is the canonical illustration: a student competing for a scarce specialty asked whether to drop his Internal Medicine fallbacks. The honest answer they give is that “a student whose preferences for Dermatology are lexicographic should truncate his list after the last Dermatology position, while one who finds an Internal Medicine position much more desirable than scrambling for any position in the secondary market following the match should not.” The theory cannot answer without the student’s utility function, which is a good reminder of what “profitable manipulation exists” does and does not mean.

Assuming the ceiling holds when others also lie. Measured above: 554,556 joint truncations at n = 6 in which some deviator lands above her own μ_W partner. The 100.00 % ceiling in The Gale-Shapley Algorithm is stated against honest opponents and is exactly right there. Quoting it as an unconditional bound is wrong; the correct unconditional statement is the equilibrium one from Gale & Sotomayor Theorem 3.

Dropping the quantifier in Dubins–Freedman. “No coalition of proposers can improve” is false. “No coalition of proposers can improve all of its members simultaneously” is the theorem, and the difference showed up here as 218,697 counterexamples to the sloppy version at n = 5 alone.

Reasoning about manipulability from balanced random complete-list simulations. As the tables above show, that model produces 98 % manipulability at n = 4096 and is wrong by three orders of magnitude about any real market. If you simulate a matching market to estimate strategic exposure, you must model list length and imbalance, or your answer is about nothing.

Confusing “proposer-optimal” with “good for proposers in absolute terms.” It means best among stable matchings. Roth 1982’s Theorem 5 (per Roth 2008) says μ_M is only weakly Pareto optimal for proposers among all matchings, and Roth’s Example 1 exhibits an unstable matching in which two of three proposers do strictly better and the third is no worse. Stability costs the proposing side something even at the top of the lattice.

Assuming which side proposes is an implementation detail. It is the single largest distributional decision in the system, and it is often made by whoever wrote the loop. The NRMP ran program-proposing for decades and switched to applicant-proposing in the 1990s redesign; that switch is what the whole Roth & Peranson study exists to evaluate. See Hospital-Residents and the NRMP.

Assuming a stable mechanism can be made two-sided strategyproof with enough cleverness. Roth 1982 Theorem 3 forbids it. Every proposal to “fix” the asymmetry either abandons stability or moves the unfairness somewhere else.

Alternatives and When to Choose Them

Goal	Mechanism	What you get	What you give up
Protect applicants	Applicant-proposing deferred acceptance	Dominant-strategy truthfulness for applicants; applicant-optimal stable matching	Programs unprotected and, per Roth & Peranson, more exposed than under the reverse
Protect institutions	Program-proposing deferred acceptance	Same properties, mirrored	Applicants unprotected; this is the arrangement the 1990s NRMP controversy was about
Protect everyone	Serial dictatorship	Dominant-strategy truthful for all; efficient (Roth 1982 Thm 4)	Stability. Blocking pairs everywhere; historically these mechanisms fail in the field
Protect everyone, keep stability	—	Impossible (Roth 1982 Thm 3)	—
Neutralise the asymmetry structurally	Require complete rank-order lists	Truthfulness becomes stochastically dominant for the receiving side too (Roth & Rothblum Cor. 3)	Participants must accept any assignment; only viable where that is already true
Neutralise it by market design	Keep lists short; tolerate imbalance	Measured collapse of the manipulable set to <0.1 %	Nothing deliberate — but note these are consequences of interview costs, not policy choices
Split the difference	Randomise between the two orientations	Ex-ante symmetry	Ex-post, someone still gets `μ_M` and someone `μ_W`; and the randomisation itself may be manipulable

The honest summary: there is no symmetric option. Choosing deferred acceptance is choosing which side to protect, and the only real question is which side you would rather have lying to you.

Production Notes

The NRMP switch is the case study. The pre-1998 National Resident Matching Program used a program-proposing algorithm; the redesign moved to applicant-proposing. Roth & Peranson’s evaluation found the change affected only 14 to 21 applicants per year out of 20,071–24,749 — about 0.1 % — with most of those preferring the new outcome, and about 0.5 % of programs affected. The strategic consequence was the point: under the pre-existing algorithm the upper bound on applicants who could profit from truncation was 11–22 per year; under applicant-proposing it fell to 0, 0, 2, 2 and 9 in 1987 and 1993–1996. The redesign did not so much reduce manipulability as move it to the side better able to absorb it — programs’ upper bounds rose from 12–23 to 27–36. That is the trade being made, and it is a policy choice about whom to protect, not a technical improvement.

The public controversy was about incentives, not efficiency. Roth & Peranson open by noting the pre-redesign dispute “was most clearly expressed” in terms of whether participants “could ‘game the system’ by strategically manipulating the ROLs they submitted.” The measured answer — that essentially nobody could — is what made the redesign defensible, and it is the reason the computational experiments were run at all. This is Mechanism Design as engineering practice: the theorem said manipulation was possible, and the only way to find out whether it mattered was to run the algorithm on five years of real data.

Advice that survived contact with participants. The deployable version of all of this is short. If you are on the proposing side: tell the truth, it is a dominant strategy and no coalition changes that. If you are on the receiving side and you have no special information about anyone else: rank truthfully and consider only where to stop the list, because every non-truncation strategy is stochastically dominated (Roth & Rothblum Theorem 2). If you do not know where the cut is, do not cut — the downside is being unmatched and the upside is bounded by a lattice that, in a real market with short lists and any imbalance, is probably one element tall.

Where the asymmetry recurs in systems work. Any clearinghouse that resolves mutual preferences by letting one side initiate has this structure, usually unnamed: job-offer systems, school assignment, kidney-exchange chain initiation, and — in a different vocabulary — every protocol where one party proposes and the other accepts or defers. The lesson transfers even where the theorem does not: “who speaks first” is a distributional parameter, and if nobody chooses it deliberately, the implementation chooses it. See Stock Exchange Order Matching System Design for price-time priority read the same way, and Rate Limiting as a Mechanism for allocation rules with the same hidden asymmetry.

The 2012 Nobel citation frames it exactly this way. The prize to Shapley and Roth was for “the theory of stable allocations and the practice of market design” — the pairing is the point, and this note’s subject is the seam between the two halves (Nobel Prize 2012, popular background).

vault

Explorer

Proposer-Optimality and Strategic Truncation

Proposer-Optimality and Strategic Truncation

Mental Model — The Manipulation Is a Walk Down the Lattice

The Theorems, Stated Exactly

Proposers: truth-telling is dominant, and coalitions do not help

Both sides: impossible

The ceiling: Gale & Sotomayor 1985

Verified: the ceiling, and what coalitions add

The Real-Market Gap

Mechanism 1: short lists

Mechanism 2: imbalance

Mechanism 3: information

Failure Modes and Gotchas

Alternatives and When to Choose Them

Production Notes

See Also

Graph View

Table of Contents

Backlinks