Note: this post assumes knowledge of the definition of stability in two-sided matching markets. A famous result, attributed to Dubbins and Freedman (1981) and Roth (1982), is that when using the Deferred Acceptance procedure in a one-to-one matching market, the proposing side has no incentive to misreport their preferences. However, these proofs are somewhat involved, to the point that I have never tried to teach these proofs to my students, nor have I felt confident that I could reproduce them on demand. While visiting the Simons-Laufer Math Institute at UC Berkeley last month, I was shown a beautifully short proof of this result. Although I have adapted the arguments to make them as clear as possible, a mostly equivalent proof was presented to me by Alex Teytelboym. Alex credits Ravi Jagadeesan for this proof, and Ravi claims that the kernel of these ideas are present in Hatfield and Milgrom’s “Matching with Contracts” paper. All I know is that I have never seen this result written so cleanly, so I thought it was worth sharing with you! I will assume a 1-to-1 matching market matching “men” to “women” for simplicity, though the proof immediately generalizes to many-to-one markets where the side with unit demand proposes. Theorem 1. Suppose that mechanism M always selects a stable matching in a way that is best for individual \(i\). Then \(i\) can never benefit from misreporting. The proof of this result will use the well-known “Rural Hospital Theorem” or “Lone Wolf Theorem” (Alex insists that these terms refer to two separate theorems, but I have always used them interchangeably). Lone Wolf Theorem. The set of matched men is the same in any stable matching. This is fairly easy to prove, and (crucially) does not rely on any results on incentives. I like to provide a “proof by picture” to my class. To focus on the main result, I defer the proof of the Lone Wolf Theorem to a future post. Suppose that Theorem 1 is false. That is, there exist preferences for all other agents such that when \(i\) reports \(\succ\), the resulting matching \(\mu\) gives \(\mu(i) = w\), and when \(i\) reports \(\succ' \ne \succ\), the resulting matching \(\mu'\) gives \(\mu'(i) = w' \succ w\). Consider the market in which \(i\) lists \(w'\) as the only acceptable woman. I claim that in this market, there must exist a stable matching in which \(i\) matches to \(w'\), and another stable matching in which \(i\) goes unmatched. This clearly contradicts the Rural Hospital Theorem (Lone Wolf Theorem). Thus, we only need to establish my claim, which can be seen as follows. I say that a matching is \(\tilde{\succ}\)-stable if it is stable in the market where \(i\) reports \(\tilde{\succ}\). The matching \(\mu'\) assigns \(i\) to \(w'\). Because it is \(\succ'\)-stable, it must also be \(\{w'\}\)-stable: the only difference is that we have removed women from \(i\)’s list, which clearly does not create any new blocking pairs. Let \(\succ''\) be the deviation in which \(i\) truncates \(\succ\) below \(w'\) (\(i\) leaves everyone below \(w'\) off of his list), and let \(\mu''\) be the resulting matching. To recap: \(\mu'\) and \(\mu''\) must both be \(\{w'\}\)-stable, but \(i\) is matched to \(w'\) by \(\mu'\) and unmatched by \(\mu''\) (a contradiction).
Note: this step uses only the definition of stability.
Note: this step uses the definition of stability and fact that \(\mu\) is optimal for \(i\).
Note: this step uses only the definition of stability.