Section 16.4 The Stable Matching Theorem
Now we present a light hearted optimization problem with a quite clever solution, called the Stable Matching Theorem. There are \(n\) eligible homebuyers \(b_1\text{,}\) \(b_2,\dots,b_n\) and \(n\) eligible homesellers \(s_1\text{,}\) \(s_2,\dots,s_n\text{.}\) We will arrange \(n\) home sales, each involving one buyer and one seller. In the process, we will try to make everyone happy—or at least we will try to keep things stable.
Each seller linearly orders the buyers in the order of their preference, i.e., for each \(i=1,2,\dots,n\text{,}\) there is a permutation \(\sigma_i\) of \([n]\) so that if \(s_i\) prefers \(b_j\) to \(b_k\text{,}\) then \(\sigma_i(j)\gt \sigma_i(k)\text{.}\) Different sellers may have quite different preference orders. Also, each buyer linearly orders the sellers (really, the homes they are selling!) in order of their preference, i.e., for each \(i=1,2,\dots,n\text{,}\) there is a permutation \(\tau_i\) of \([n]\) so that if \(b_i\) prefers \(s_j\) to \(s_k\text{,}\) then \(\tau_i(j)\gt\tau_i(k)\text{.}\)
A \(1\)–\(1\) matching of the \(n\) buyers to the \(n\) sellers is stable if there do not exist two buyers \(b\) and \(b'\) and two sellers \(s\) and \(s'\) so that
-
\(b\) is matched to \(s\text{;}\)
-
\(b'\) is matched to \(s'\text{;}\)
-
\(b\) prefers \(s'\) to \(s\text{;}\) and
-
\(s'\) prefers \(b\) to \(b'\text{.}\)
The idea is that given these preferences, \(b\) and \(s'\) may be mutually inclined to arrange for \(s'\) to sell their home to \(b\text{,}\) abandoning the other arrangements that had been in place. (Since \(b\) and \(s'\) are acting in their own best interests, the preferences of \(b'\) and \(s\) are irrelevant here.)
The question is whether, regardless of their respective preferences, we can always generate a stable matching. The answer is “yes” and there is a clever argument. In fact, it is one that yields an efficient algorithm. To start, each buyer knocks on the front door of the seller who is tops on their list. It may happen that some sellers have more than one prospective buyer on their doorstep while others have none. However, if a seller has one or more buyers at their door, then the seller invites the buyer on their doorstep which they prefer most to come in and tells the others, if there are any, to go away. Any buyer rejected at this step proceeds to the front door of the home that is second on their list. Again, a seller with one or more buyers at their door (including the one previously invited to come in, if applicable) chooses the best among them and sends the others away. This process continues until eventually, each seller is has exactly one buyer in their home.
It is interesting to note that each seller’s prospects improve over time, i.e., once they have a buyer, things only get better. Conversely, each buyer’s prospects deteriorate over time. Regardless, we assert that the resulting matching is stable. To see this, suppose that it is unstable and choose buyers \(b\) and \(b'\) and sellers \(s\) and \(s'\) so that \(b\) is matched to \(s\text{,}\) \(b'\) is matched to \(s'\text{,}\) but \(b\) prefers \(s'\) to \(s\) and \(s'\) prefers \(b\) to \(b'\text{.}\) The algorithm requires that buyer \(b\) start at the top of their list and work their way down. Since they eventually landed at the door of seller \(s\text{,}\) and they prefer \(s'\) to \(s\text{,}\) at one stage of the algorithm, buyer \(b\) was actually at the door of \(s'\text{,}\) and seller \(s'\) sent buyer \(b\) away. This means that at that exact moment, \(s'\) had a buyer \(b'\) in hand that they prefer to \(b\text{.}\) Since each seller’s holdings only improve with time, it means that when the matching is finalized, seller \(s'\) has a buyer \(b'\) that they prefer to \(b\text{.}\) Therefore, the matching is not, in fact, unstable.
