The Problem
The Stable Marriage Problem is a fairly well known matching algorithm. The premise is that a group of men and an equally numbered group of women both rank their preferred matches. The solution is to create matches between all men and women. Those matches are stable when there are no matches in which both the man and woman could be better off with someone else. Not exactly the most romantic proposition, but it is pretty darn efficient as we will see.
The Matching Process
To start, the group of men rank their preferred matches, and, conversely, the group of women each rank their preferred matches.
There are certain qualifiers in this matching process. For this example, the man proposes to the woman, but the woman’s preferences may influence her decision to accept or reject that proposal. If the roles were reversed, it is possible we would see different results.
Round One
- Adam’s first preference is Cindy.
- Adam proposes to Cindy.
- Cindy is single, so she accepts Adam’s proposal.
Round Two
- Blake’s first preference is Betty.
- Blake proposes to Betty.
- Betty is single, so she accepts Blake’s proposal.
Round Three
- Carl’s first preference is Cindy.
- Cindy, however, is matched with Adam.
- Cindy prefers Adam to Carl, so she rejects Carl’s proposal in order to stay with Adam.
- Carl moves on to his next preference, Betty.
- Betty is matched with Blake.
- It is Carl’s lucky day (and Blake’s unlucky day). Betty prefers Carl to Blake, so she breaks up with Blake to accept Carl’s proposal.
We remove the match between Blake and Betty and create a new match between Carl and Betty.
At this point, we have two matches (Adam + Cindy, Carl + Betty). Blake and Allie remain unmatched, so we can start the process over again, this time only for those men who are still unmatched.
- Blake tries again.
- Blake’s first preference was Betty, but she broke up with him to get with Carl, so forget her.
- Blake’s next preference is Allie. Allie is still available, so she accepts Blake’s proposal.
And they all lived happily ever after.
Implemented in Business Rules
If we want to implement a similar matching process using business rules we can do so with the following entity model in irAuthor:
The business rules are straightforward from there. Of course we need rules to iterate through the collection of men and other rules for determining whether someone is matched or not. I won’t get into those here because they are self-explanatory. The rule I want to focus on is the logic for determining if the woman will accept or reject a proposal as seen here:
The example above is an implementation in its simplest form because (a) there is an equal number of men and women and (b) the rankings have already been done by the men and women ahead of time. The business rules just need to find the stable matches. Complexity creeps in when there are unequal numbers and/or no rankings exist at the start of the process.
Gale-Shapley
A better example that demonstrates the complexity is how hospitals select residents. A resident makes a list of their preferred hospitals they want to work at. The difference here is that the number of hospitals does not equal the number of residents. There are fewer hospitals to residents and each hospital may only accept a specific number of residents during the application process. The residents may get prioritized based on whether they’ve already done a residency at a given hospital, their med school grades, references from doctors, and possibly even geography. Add to that the possibility that each hospital may have their own guidelines for how to prioritize. A sample rule framework may look like the following:
This matching model is a derivation of the Stable Marriage known as Gale-Shapley. It is here where we find the benefits of business rules. Having the ability to create and manage distinct prioritization and selection rules inside the matching process gives the administrators of that process more insight and control over its implementation.
