Changing preference in Gale-Shapley algorithm?

Question

Suppose, in the context of the classic marriage problem, two equal size groups of $n$ men and $n$ women are being matched, with the GS algorithm.

If a man were to switch the order of a pair of women, low on his preference list, say $x$ and $y$, would this yield any sort of advantage with regards to being matched with a woman higher than $x$ and $y$?

This seems like a fairly simple problem; I don't see how switching a pair low on the preference list would increase the chance of being matched with something higher on the list. How would one prove the existence or non-existence of such an advantage?

I've come to the conclusion that this would not yield an advantage, but would still appreciate some guidance with regards to proving that.

Answer 1

The property your wish to prove is known as strategy proofness: Is it possible for an agent to report a preference $P'$ such that it gets matched to a strictly better result w.r.t. its true preference $P$ than reporting truthfully?

Note that while the GS algorithm is strategy proof for the men, it is not for the women: they can use misrepresenting the preference to their advantage, as you can see with a simple example. In fact, there exists no stable matching mechanism that is strategy proof for all agents.

The proof of strategy proofness for men in the GS matching algorithm is, although it seems an obvious statement, rather involved. The clearest presentation I've been able to find is in the paper Machiavelli and the Gale-Shapely algorithm by Dubins and Freedman. In this paper, after proving strategy proofness, the authors proceed to prove the even stronger property of coalition strategy proofness:

(17) THEOREM Suppose several students collude in a Gale-Shapley algorithm, each using a false rank ordering. They cannot all get better universities. "Better" is relative to each student's true rank ordering, and indicates strict inequality.

---

If you want a simple proof of strategy proofness of some matching mechanism, you can look at the Serial Dictatorship mechanism (also known under the perhaps less ominous name of Deferred Acceptance (DA) with single tie-breaks).

This is perhaps the simplest matching mechanism for the case with one-sides preferences and can relatively simply be shown to be both Pareto efficient and strategy proof.