Stable Marriage Problem

◷ Reading Time: 6 minutes

The Stable Marriage Problem is the problem of finding stable matches between two equally sized sets of people with their preferences for partners in the other list. The two sets could be represented like this:

Here 1 represents the most desired match, while 4 represents the least desired. The goal is to create a list of matches so that no one would have a better possible match. For more on this take a look at Stable Marriage Problem.

This project was inspired by the June-2024 DMC Challenge and for the project input we will be using the input data from there.

Running the Sample

1. Open the DRD Main.xml

2. Click on Logic Run Template.

3. Select the template: Test from DMC Challenge – 5 Men and 5 Women

This template will use these sets:

But the input will provide them as just given matrices, and supply a list of names to associate the positions with after calculations have been done. This is what the actual input looks like:

{
"MensNames":["Adam","Bob","Charlie","Dave","Edgar"],
"WomensNames":["Alice","Barbara","Claire","Doris","Elsie"],
"MenPreferencesInput":[[5,1,2,4,3],[4,1,3,2,5],[5,3,2,4,1],[1,5,4,3,2],[4,3,2,1,5]],
"WomenPreferencesInput":[[1,2,4,3,5],[3,5,1,2,4],[5,4,2,1,3],[1,4,3,2,5],[4,2,3,5,1]]
}

4. Click Debug

5. Click Next Step to go step by step. When it asks to open a document for the Tentative Engagements node, for now, select “No” to avoid going through many iterations of loops.

6. You will see the output under Parameters window. Expant FinalMatchList to see all matches

Stable Marriage Problem – Process Steps

The process of the this project consists of these main steps:

1. Outer while loop that ends when all matches are found and no recent changes have been made
2. Inner loop that iterates through the set of women
3. For each woman, iterate through the set of men
4. If a man is found who would be better matched with current woman, add their match to a temporary list

Project Description

The Stable Marriage Problem project contains the following files:

DRD (Decision Requirement Diagram)

• Main.xml: Shows the flow between the two main nodes, Tentative Engagements and Create Final List

Flow

• Tentative Engagements.xml: Has one outer loop to loop until all matches are found and there have been no recent changes. Within it is a node that sets the noChanges flag to true, this transitions to the nested loop that iterates through the women set. Within the nested loop is a node called Proposal that is linked to Proposal.xml
• Proposal.xml: This flow loops through all men and finds the best current match for the given women

Natural Language

• AssociateNames.xml: This creates a final list that associates all given names with each matrix

The Design

Main.xml has two nodes, with a knowledge source reference to the Gale-Shapley Algorithm which was used to solve this problem. The Tentative Engagements node has an event to set the TotalMatches parameter to the length of the list. This will be used within the Tentative Engagements.xml document.

Tentative Engagement.xml contains all logic for solving the problem and is done with three loops, two within the document and then the third in the proposal document. The loops are nested like this:

– Loop Until All Matches are Found
– Loop Through All Women
– Loop Through All Men (within Proposal.xml)

Proposal.xml has a series of checks to see if the current selected man is a better match than who the current woman is matched with. It has four conditional statements:

• Is woman already matched?
• Does she prefer her current match over this one?
• Is this man already matched?
• If he is already matched, does he prefer his current match?

AssociateNames.xml is natural langauge that simply maps all names to their matrix positions.

when AssignNames
then
  Man = MensNames[MatchList[MatchIndex][0]];
  Woman = WomensNames[MatchList[MatchIndex][1]];
  FinalMatchList|add([Man,Woman]);
  MatchIndex += 1;
  MatchListCheck;
end
when MatchListCheck
  MatchIndex < (MatchList|length())
then
  AssignNames
end

Download the Stable Marriage Problem project

Use the attachment at the end of the page to download the sample project.