Stable matching examples

Next week I will present a paper about public school choice based on the mechanism design approach. A mechanism design approach for the matching between schools and students have a long history. As a background information, an introduction for the one of the earliest studies, Gale and Sharpley (1962) is given here.

We first look what’s called College Admission Problem. A set of applicants is to be assigned among a set of colleges. Each applicant ranks the college in the order of his/her preference. Similarly each college ranks the student in order of preference. We want to find the assignment that is stable and optimal:

* An  assignment of applicants to colleges will be called unstable if there are two students X and Y assigned to college A and B, although student X prefers college B to A and student Y prefers college A to B.

* A stable assignment is called optimal if every applicant is at least as well off under it as under any other stable assignment.

To solve the problem, deferred-acceptance procedure is introduced. First, all student apply to their first choice college. A college puts preferred student in the waitlist, and rejects the rest. Then rejected applicants apply again, but this time to their second choice. And then the college compares all the student among new applicants and those in the waitlist, and rejects the rest. This procedure terminates when every applicant is either on a waitlist or has been rejected by every single college he/she applied. This deferred-acceptance procedure is proven to achieve the stable, optimal matching  between students and colleges.

Another (and possibly more interesting) well-known matching market is Marriage Problem. Think of a community with n boys and n girls. To use deferred acceptance procedure, let each boy propose to his favorite girl. Each girl who receives more than one proposal rejects all but her favorite from among those who have proposed to her. However, she does not accept him yet, but keep him on a string to allow for the possibility that someone better may come along later (!).

It’s time for the second round. Those boys who were rejected from the girl last time now proposes to their second favorite girl. Each girl receiving multiple proposals compares all proposers (including the boy on a string..!) and rejects all but the favorite boy. The procedure continues until all girls gets her proposal, and then finally each girl truly accept the boy on her string.

Now this community has n stable, optimally married couples.

Soovin

Reference: Gale D. and Shapley L.S., College Admissions and the Stability of Marriage, The American Mathematical Monthly (1962).

 

Advertisements

6 thoughts on “Stable matching examples

  1. This is so cool. I was just talking with a friend who was applying to several grad schools, and she explained how the process was automated to match her to a school based on her ranking of the school and the school’s ranking of her. I was thinking about how that sounded like a great OR problem, so I’m looking forward to learning more during your presentation.

    Liked by 1 person

    1. Unfortunately, although this study has initiated from the problem they named “College Admission”, I don’t think it is being used directly in college applications in practice. Bit it is gaining more and more popularity in elementary school choices.

      Like

  2. This is not unlike what we do when we decide to admit students. We can only make a limited number of offers, and we want to know if students “like us back.” It sounds juvenile, but these kinds of issues pop up in situations where you have limited resources.

    Liked by 1 person

    1. I agree. As I understand grad schools have more.. sophisticated procedures for admissions. This mechanism is now more popular in other practical situations, like labor market clearinghouses and elementary school choices.

      Like

  3. This is a really interesting problem! I like the marriage example; it’s easy to visualize how the process works (although we can be glad this isn’t actually how marriage works!). How would this system handle ties in preferences (e.g., girl A would be equally happy to marry either boy X or boy Y and they both propose to her)? Is it just a random choice between the tied options? I’m also interested in what would happen in a case where a girl is so unpopular that no boy ever proposes to her until the very last round, where only one boy and one girl remain and have to get married by default. I’m going to guess that it’s safe to assume this would never cause an unstable system, but intuitively it seems like it could?

    Liked by 1 person

    1. I’m really happy to see your question on tie handling, cause that’s what I’ll cover in the presentation. In the above example, I implicitly assumed that boys and girls have ‘strict’ preferences over each other, just for simplicity of explanation. But it is also possible and probably more realistic that the preference is not strict and the girl can’t tell which boy she loves more. In that case, we need some tie-breaking rule additionally, which is often just a random lottery as you guessed. And fortunately, adding the correct tie-breaking rule does not ruin the good properties of the mechanism.

      The situation of having an unpopular girl(and a boy) is also very likely to happen. Yes, they will be matched at the very last round since they have no other choice, and it is likely that their marriage is not very satisfactory and stable… However, from the point of view of a system designer, that’s still called ‘stable’, since doing so is ‘fairer’ than making them marry others.

      Liked by 1 person

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s