The Stable Marriage Problem has been introduced in a previous post. In this post, let us view this problem in a game theoretic view. In particular, let’s consider the following scenario:

Each man and woman has a preference list P_i of his/her possible partners and this preference list is private information only known by himself/herself. When the game starts, each person i states a preference list, Q_i. An algorithm h produces a stable matching according to the stated preference lists \vec{Q} = (Q_1, Q_2, \ldots, Q_{2n}).

Now the question is:

Does any incentive exist such that someone can propose a Q(i) \neq P(i) and get a better partner?

The answer is YES. Formally, there does not exist an algorithm such that it can produce a stable matching according to the stated preference lists and telling truth is a dominant strategy for all players. The prove that truth revelation is not a dominant strategy, we need to prove for some strategies Q_{-i} other players use, player i has a better strategy Q_i than stating the truth preference list P_i.

To prove this, Roth uses an instance of size 3. In this instance, only 2 matchings M_1, M_2 (man-optimal and woman optimal, respectively) are possible. Therefore any stable matching algorithm must produce either M_1 or M_2. Let’s consider the algorithm finding $M_1$ first. If all the others tell the truth, we can find a woman w such that giving a particular preference list will leads the algorithm to find M_2, which is more preferable to w. Therefore true telling is not a dominant strategy when we use algorithm to produce M_1. The case of M_2 is similar