Stable Matching Problem Example

The Stable matching problem Example started with a question that, is that possible to design a college admission process that will be self enforcing? or a job recruiting process which is self enforcing? Stable Matching Wikipedia.

Let’s say all Juniors in University started applying for summer Internships. The summer internship process is a two way interplay between companies and students. The students create preferences based on their dream company and the company create preferences based on their required candidate. Companies make offers based on their preferences, and students pick offers.

There was a problem with this approach of recruitments. Suppose a student X has just accepted a summer job at company Y. Now company Z calls student X for their company. Student X has a greater preference for company Z then Y. So he lefts the job at company Y and leaves for Z. Company Y will now call second preference from the list who was working in another company, leaves that company and joins Y, here the Chaos begins.

stable matching problem example

What went wrong exactly? The fundamental issue was that, the process was not self-enforcing. If people are free to chose there self interests it leads to collapsing.

Stable Matching Problem Example Solution

Gale and Shephley came up with an Idea that, Given the set of preferences can we assign applicants to companies in a way that every company X and every student A who is not scheduled yet to work, must satisfy two cases,

  1. X prefers every one of its accepted applicants to A.
  2. A prefers her current situation over working for employer X.

If this holds the outcome is stable. To get the essence of this concept, it helps to make the problem as clean as possible.


Algorithms related posts visit HERE

Data Structures related posts visit HERE

Databases related posts Visit HERE

Python-related posts Visit HERE

C++ related posts Visit HERE

Data Science related posts visit HERE