It's a dominant strategy for deferred acceptance proposers to state true preferences in the marriage problem: simple proof

This post is not entirely self-contained, it is in some sense a continuation of and addition to my talk last year at the Simons Institute, which you can see at this link: 

Simple Proofs of Important Results in Market Design-- (video of my talk at Berkeley's Simons Institute)

In that talk (based on work I'm doing with Mike Ostrovsky) I defined the marriage model of Gale and Shapley, gave necessary definitions,  and following the style of their original article, I showed simple, verbal proofs of a number of results, including the constant employment ("lone wolf") theorem:

Constant employment theorem: In a "marriage market"(M,W, P) with strict preferences, the set of people who are single is the same for all stable matchings.

Now based on that theorem, here's a simple proof of the dominant strategy theorem, inspired by a  very short proof (with attributions to Alex Teytelboym and Ravi Jagadeesan) in Nick Arnosti's recent blog post A Short Proof of the Truthfulness of DA by Nick Arnosti 2023/10/01 

Here's the theorem to be proved:

Dominant Strategy Theorem (Dubins and Freedman, Roth): In the M-optimal stable mechanism for the marriage problem (e.g. when the man-proposing deferred acceptance algorithm is used, which produces the most favorable stable matching for every man) it is a dominant strategy for each man i to state a preference list corresponding to his true preferences ≻.

Notation: for any preference ≻′ of player i, an outcome is ≻′-stable if it is stable when i reports ≻′ and everyone else's preferences remain constant.

Proof (following Arnosti)

Suppose that the theorem is false. That is, suppose there exist preferences for all other agents such that when i reports ≻, the resulting ≻-stable matching μ gives μ(i)=w, and when i reports ≻′ ≠ ≻, the resulting ≻′-stable matching μ′ gives μ′(i)=w′≻w. (Note that the final comparison is ≻, i.e. take ≻ to be i's true preference list.)

Consider the market in which i lists w′ as the only acceptable woman (and everyone else's preferences remain fixed). We'll see that this will lead to a contradiction with the constant employment theorem, by implying that there must exist a {w'}-stable matching in which i matches to w′, and another {w'}-stable matching in which i is unmatched. 

1. The matching μ′ assigns i to w′. Because it is ≻′-stable, it must also be {w′}-stable: the only difference between ≻′ and {w'} is that we have removed women from i’s list, which clearly does not create any new blocking pairs.

Note: this step uses only the definition of stability.

2. Let ≻′′ be the deviation in which i truncates ≻ below w′ (i leaves everyone below w′ off of his list), and let μ′′ be the resulting matching.

a. The matching μ′′ leaves i unassigned.  This follows from the fact that, if it matched i, then μ″ would be ≻-stable, since ≻ differs from ≻'' only in that it restores the truncated elements of i's preference, which would be below i's match and hence not introduce any new blocking pairs (since it wouldn't change i's match). But  μ″ can't be ≻-stable,  because w is i’s best ≻-stable partner by assumption, and is worse than all women listed in ≻′′.*

Note: this step uses the definition of stability and fact that μ is optimal for i.

b. Because μ′′  (which leaves i unassigned) is ≻′′-stable, it is also {w′}-stable: the only difference between ≻′′ and {w′} is that we have removed women from i’s list, which does not create any new blocking pairs).

Note: this step uses only the definition of stability.

To recap: μ′ and μ′′ must both be {w′}-stable, but i is matched to w′ by μ′ and unmatched by μ′′ (a contradiction).

This completes the proof.

*Note that the reason μ′′ isn't ≻-stable is that it leaves i unassigned, and so creates new blocking pairs involving i with respect to his true full preferences.