Stable Marriage Problem In C++

In the realm of combinatorial mathematics and computer science, the Stable Marriage Problem stands out as a renowned conundrum. It revolves around forming a solid match between two distinct sets of entities, like males and females, each with their unique preferences for the members of the opposite group. A match is deemed stable when there are no pairs of elements that would both rather be paired with each other instead of their current partners. The solution to this problem often involves employing algorithms such as the Gale-Shapley algorithm.

Algorithm:

One widely used approach to solving the Stable Marriage Problem is the Gale-Shapley algorithm, created by David Gale and Lloyd Shapley.

Following are the steps in the algorithm:

• ✅ Every single man proposes to the woman he likes best out of those he hasn't yet.
• ✅ Each woman carefully weighs the offers she has received before tentatively accepting the one from her favourite male.
• ✅ When a woman rejects him, the male moves on to his next favourite woman and proposes.
• ✅ As long as no man is rejected or has used up all of his alternatives, the procedure is repeated.

Properties:

A stable matching is consistently found through the Gale-Shapley algorithm, ensuring its guaranteed conclusion.

At every step, the situation yields a consistent outcome since when a man makes a proposal to a woman and she declines, it signifies her preference for him over her current partner (if she is in a relationship).

Program:

Let's consider an instance to illustrate the stable marriage problem using C++.

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
// Function to perform the Stable Marriage algorithm
void stableMarriage(const vector<vector<int>>& menPrefs, const vector<vector<int>>& womenPrefs)
{
 int n = menPrefs.size(); 
 // Number of men and women
 // Initialize arrays to store current matches
 vector<int> menMatches(n, -1); 
 // -1 represents no match
 vector<int> womenMatches(n, -1);
 // Initialize arrays to keep track of men's and women's proposals
 vector<int> menProposals(n, 0);
 vector<vector<int>> womenProposals(n, vector<int>(n, 0));
 // Create maps to store preferences for faster access
 vector<map<int, int>> womenRankings(n);
 for (int i = 0; i < n; ++i)
 {
 for (int j = 0; j < n; ++j)
 {
 womenRankings[i][womenPrefs[i][j]] = j;
 }
 }
 // While there are unmarried men
 int unmarriedCount = n;
 while (unmarriedCount > 0)
 {
 int man;
 for (man = 0; man < n; ++man) 
 {
 if (menMatches[man] == -1) 
 {
 break;
 }
 }
 // Find the first woman on the man's list that he has not proposed to
 int woman;
 for (int i = 0; i < n && menMatches[man] == -1; ++i) 
 {
 woman = menPrefs[man][i];
 if (!womenProposals[woman][man])
 {
 womenProposals[woman][man] = 1;
 menProposals[man]++;
 if (womenMatches[woman] == -1)
 {
 menMatches[man] = woman;
 womenMatches[woman] = man;
 unmarriedCount--;
 }
 else
 {
 if (womenRankings[woman][man] < womenRankings[woman][womenMatches[woman]])
 {
 int prevMan = womenMatches[woman];
 menMatches[prevMan] = -1;
 menMatches[man] = woman;
 womenMatches[woman] = man;
 }
 }
 }
 }
 }
 // Print the stable matches
 cout << "Stable Matches:" << endl;
 for (int i = 0; i < n; ++i) {
 cout << "Man " << i << " matches with Woman " << menMatches[i] << endl;
 }
}
int main()
{
 int n;
 // Number of men and women
 cout << "Enter the number of men and women: ";
 cin >> n;
 vector<vector<int>> menPrefs(n, vector<int>(n));
 vector<vector<int>> womenPrefs(n, vector<int>(n));
 cout << "Enter men's preferences (0-based indexing):" << endl;
 for (int i = 0; i < n; ++i)
 {
 cout << "Preferences for Man " << i << ": ";
 for (int j = 0; j < n; ++j) 
 {
 cin >> menPrefs[i][j];
 }
 }
 cout << "Enter women's preferences (0-based indexing):" << endl;
 for (int i = 0; i < n; ++i)
 {
 cout << "Preferences for Woman " << i << ": ";
 for (int j = 0; j < n; ++j) 
 {
 cin >> womenPrefs[i][j];
 }
 }
 stableMarriage(menPrefs, womenPrefs);
 return 0;
}

Output:

Enter the number of men and women: 3
Enter men's preferences (0-based indexing):
Preferences for Man 0: 1 0 2
Preferences for Man 1: 2 1 0
Preferences for Man 2: 0 2 1
Enter women's preferences (0-based indexing):
Preferences for Woman 0: 1 0 2
Preferences for Woman 1: 2 1 0
Preferences for Woman 2: 0 2 1
Stable Matches:
Man 0 matches with Woman 1
Man 1 matches with Woman 2
Man 2 matches with Woman 0

• ✅ First, men's and women's numbers are entered into the program.
• ✅ After that, the preferences of every man and woman are factored into the system. The preferences are entered as a list of indices with values indicating the priority to which they should be given.
• ✅ Stable matches between men and women are found using the Gale-Shapley algorithm, which is implemented by the stableMarriage function.
• ✅ Up until every man is matched, the algorithm iterates: It identifies the first woman on each single man's list who hasn't received a marriage proposal. A match develops between them if the woman is single. Even though the woman is already matched, if she finds her current mate to be less appealing than the previous one, she swaps partners. Until every man is matched, the algorithm keeps running. The stable matches between men and women are printed by the program at the end.
• ✅ It identifies the first woman on each single man's list who hasn't received a marriage proposal.
• ✅ A match develops between them if the woman is single.
• ✅ Even though the woman is already matched, if she finds her current mate to be less appealing than the previous one, she swaps partners.
• ✅ Until every man is matched, the algorithm keeps running.
• ✅ The stable matches between men and women are printed by the program at the end.