Matching Theory

Matching theory is an active field in mathematics, economics, and computer science. It ensured a Nobel memorial prize for Alvin E. Roth and Lloyd S. Shapley in 2012. The theory is applied in the real world to match students and colleges, doctors and hospitals, and to organize the allocation of donor organs. It all started with a beautiful paper by David Gale and Lloyd Shapley in 1962: College Admissions and the Stability of Marriage (read it!). In this post, we study the simplest version of what is known as the stable marriage problem and take a look at inherent conflicts. The exposition follows chapter 22 of the wonderful book Game Theory by Michael Maschler, Eilon Solan, and Shmuel Zamir.

What are stable matchings?

There is a set \( G \) of \( n \) girls and a set \( B \) of \( n \) boys. All girls and boys are heterosexual and desperate enough to prefer every member of the opposite sex to staying single. Each girl \( g \) has preferences over the boys, represented by a total order \( \succeq_g \) on \( B \). Similarly, each boy \( b \) has preferences over the girls, represented by a total order \(\succeq_b\) on \( G \).

We want to pair up the girls and the boys. Formally, a matching is simply a bijection \( M \) from \(G\) to \(B\) and if \( f(g)=b \), we say that \( g \) and \( b \) are matched (under \( M\)). Now, nobody can force the girls and boys to be together, so we have to look at matchings in which the boys and girls are relatively content with whom they get. To be precise, a matching is stable if we cannot find a girl and a boy who prefer each other under their preference ordering to whomever they are matched with.

Are there any?

Before we go into a deep study of stable matchings, we ought to make sure that there are stable matchings. We do so by giving an explicit algorithm for finding a stable matching, the boy courtship algorithm.

Theorem: There is at least one stable matching.

The algorithm starts with each boy going to the girl he ranks highest according to his preference ordering. Then each girl who is visited by some boy selects her favorite boy among them (for now) and rejects the others. In the next Pound each boy is going to the girl he ranks highest according to his preference ordering among the girls that have not rejected him yet. This is repeated until each girl is visited by exactly one boy, which provides us with a matching.

There are three properties of this algorithm we are going to use a lot:

(P1) If a boy visits a girl, he must have visited all girls who he prefers before and have been rejected by them.

(P2) If two boys visit the same girl at some point without being immediately rejected, the boy who visited her later must be preferred by her. For a boy will visit a girl until she rejects him (every preferred girl already has) and she will only reject him if someone better comes along.

(P3) If a girl is visited at some point, she will be visited ever after, for she only rejects a boy if someone better comes along and a boy only stops visiting a girl he has visited before if she rejects him.

We first note that the algorithm does terminate. By (P3), if every girl is visited at some time, all girls are visited eventually. Since there are as many girls as there are boys, this can only be if there is a matching. So it suffices to show that every girl is visited eventually. If some girl is not visited, some other girl must be visited by more than one boy and reject at least one boy. Since no boy visits a girl who has rejected him again, after a boy has been rejected by every girl who is visited by some boy, he has to visit a girl who hasn’t been visited before. Eventually, there can be no unvisited girl.

So the algorithm has produced a matching. We want to show it is stable. Suppose it is not then there are a boy, say Bob, and a girl, say Ann, who prefer each other to whomever they are matched with. Since Bob prefers Ann to his current partner, Bob must have visited Ann before and be rejected by her by (1). So Ann’s current partner must be preferred to Bob by (P2) in contradiction to Ann and Bob preferring each other to their current partners.

Who profits?

Now the boy start to complain that the whole system is unfair. They have to do all the proposing and get their ego crushed by rejection, while the girls can just choose and keep the boys coming to be judged. We can formulate the interests of boys by a partial order \( \succeq_B \) on the set of all matchings. If \( M \) and \( L \) are matchings, we have \( M\succeq_B L\) if every boy considers the girl he is matched with under \( M \) to be as least as good as the girl he is matched with under \( L \). Call \( M_B \) be the matching we get from the boy courtship algorithm. It turns out the boys are not that bad off after all:

Theorem: For every stable matching \( M \), we have \( M_B\succeq_B M \).

By (P1), it suffices to show that if a girl rejects a boy under the boy courtship algorithm at some point, there is no stable matching in which he is matched with that girl. We prove this by induction on the steps of the boy courtship algorithm.

If a girl, Ann, rejects a boy, Bob, at the first stage of the algorithm, she does so because there is a boy, Carl, she prefers for whom she is the top choice. So in any matching in which she is matched with Bob, she and Carl would prefer each other to whomever she is matched with. So there can be no stable match in which Ann and Bob are matched.

Now suppose that no boy could be with a girl that has rejected him in the first \( k \) stages of the algorithm and assume that Ann rejects Bob in stage \( k+1 \). So she must choose a guy, Ken, who is visiting her in the same round over Bob. Now by assumption, Ken could be with no girl that has rejected him before in any stable matching and by (P1), these are exactly the girls Ken prefers to Ann. Now suppose there is a stable matching in which Ann and Bob are matched. By assumption Ken is matched to someone worse than Ann. So Ken and Ann would prefer each other to their current partners. This contradiction shows that Ann and Bob cannot be matched under a stable matching.

Do the girls like it?

We can also define a partial order for the girls. For two matchings \( M \) and \( L \), we have \( M\succeq_G L \) if every girl considers the boy she is matched with under \( M \) at least as good as the boy she is matched with under \( L \). By a symmetry argument, we can exchange the roles of the boys and the girls and get a girl courtship algorithm that gives rise to a stable matching \( M_G \). Again by symmetry, we have \( M_G\succeq_G M \) for every stable matching \( M \). So how do \( \succeq_B \) and \( \succeq_G \) relate to each other?

Theorem: For any two stable matchings \( M_1 \) and \( M_2 \), one has \( M_1\succeq_B M_2 \) if and only if \( M_2\succeq_G M_1 \).

Without loss of generality, it suffices to show that \( M_1\succeq_B M_2 \) implies \( M_2\succeq_G M_1 \). Let Ann be a girl that is matched with different boys under \( M_1 \) and \( M_2 \). Say, she is matched with Bob under \( M_1 \) and with Ken under \( M_2 \). We want to show that she prefers Ken to Bob. Since \( M_1\succeq_B M_2 \), Bob prefers Ann to the girl he is matched with under \( M_2 \), Claire. If Ann would prefer Bob to Ken, then Ann and Bob would be better of with each other than with their partners under \( M_2 \). But \( M_2 \) is a stable matching, so Ann does not prefer Bob to Ken. So Ann prefers Ken to Bob.