An easy exercise of matching in the marriage market


#1

The economy has six agents: three men (m1, m2, m3) and three women (w1,w2, w3). A match is every feasible pair of men and women. So every match has to be between a man and a woman (like the marriage problem we studied in Chapter 3).

Their preferences are described as follows (where “P” means that he/she strictly prefers one alternative over the other):

m1: w2 P w1 P w3 w1: m1 P m3 P m2
m2: w1 P w3 P w2 w2: m3 P m1 P m2
m3: w1 P w2 P w3 w3: m1 P m3 P m2

In this economy, matches are randomly assigned, so there are six different assignations possible. Suppose every assignation is equally probable.

For example, one assignation possible is:
{m1, w1}
{m2, w3}
{m3, w2}

A match is stable if and only if there exists no pair {m, w} such that both agents strictly prefer marrying between them than the match they where assigned.

Question: Which assignations are stable?

This exercise is from the Roth&Sotomayor book on matching.


#2

Hi Emilio,

From the six possible assignations only two are stable:

{(m1, w1), (m2, w3), (m3, w2)}
Notice that in this assignation w1 and w2 are matched with their most preferred option. w3 would prefer to be with m1 or m3 than her actual partner, but none of them would like to be with her. Also notice that m1 and m2 prefer women that are happy with their match. m2 would like to be with w1 or w2 rather than w3, but none of them would match with him. So it follows that it doesn’t exist (m,w) such that both agents strictly prefer marrying between them than the match they were assigned.

{(m1,w2), (m2,w3), (m3, w1)}
In this allocation, m1 and m3 are matched with their most preferred partner. w1 would like to be matched with m1 and w2 would like to be with m3, so there is no partner that would strictly prefer to be with them. w3 also prefers the guys that are happy with their match (m1 and m3). m2 is the only men who would like to change his partner, but women are better off with their actual partner. So, it doesn’t exist (m,w) such that both agents strictly prefer marrying between them than with their actual match.

For the other assignations it is possible to find a blocking partner. For example, for the assignation {(m1, w3), (m2,w1), (m3,w2)} a pair (w1, m3) would prefer to marry between them than with their actual partner.

Let me know if you have any questions.


#3

Yes, I have the same answer!!

I haven´t come up with a set of preferences that leads to an economy with no stable assignations though. I don´t know if that is possible in this environment.

Thank you.


#4

Hi Emilio and Maria,

I found this exercise very interesting and went to look further into this. I found out that the answer to this problem was given by David Gale and Lloyd Shapley in 1962 and it works, meaning an stable assignation will be found, as long as the number of men and women are equal and the preferences are static (they don’t change in each step of the game). Two interesting things of this problem are:

  1. In the worst case scenario there will be n^2 proposals before founding and stable equilibrium, therefore the algorithm order is n^2.
  2. The stable matching tends to favor the group that make the proposals.

I also found out that this methodology is actually used in the US to match medical students into their preferred hospital across the country. To do this, they use a program called “The National Resident Matching Program” (NRMP) or “The Match” that uses a similar algorithm that the one described in your example. However, in this case and given that generally there are more applicants than positions it is possible for an applicant to not match with a preferred program.

Finally, I leave you two short videos that describe each of the examples (marriage and resident matching) in a very fun and illustrative way:

Stable Marriage Problem

How the NRMP Matching Algorithm Works