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\), \(b_2,\dots,b_n\) and \(n\) eligible homesellers \(s_1\), \(s_2,\dots,s_n\). We will arrange \(n\) home sales, each involving one buyer and one seller. In the process, we will try to make everyone happyor 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\), there is a permutation \(\sigma_i\) of \([n]\) so that if \(s_i\) prefers \(b_j\) to \(b_k\), then \(\sigma_i(j)\gt \sigma_i(k)\). 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\), there is a permutation \(\tau_i\) of \([n]\) so that if \(b_i\) prefers \(s_j\) to \(s_k\), then \(\tau_i(j)\gt\tau_i(k)\).

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

1. \(b\)\(s\)
2. \(b'\)\(s'\)
3. \(b\)\(s'\)\(s\)
4. \(s'\)\(b\)\(b'\)

The idea is that given these preferences, \(b\) and \(s'\) may be mutually inclined to arrange for \(s'\) to sell their home to \(b\), 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.

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.