Stable Marriage Program in C++
Introduction:
In the stable marriage problem (SMP), two sets of equal size are matched so that no two individuals of the same sex would prefer to be paired with one another than with their current partners. If there are no blocking pairs between two individuals who are not matched to one another but would both prefer to be matched to one another, the matching is deemed stable.
Real-World Applications:
Numerous practical uses of the SMP exist, including:
- Student-school matching: Students can be matched with schools according to their preferences, including location, program, and financial aid.
- Hospitals and residents can be matched according to the residents' choices, including location, speciality, and work-life balance.
- Matching employees with employment: Employees may have their preferences, such as pay, location, and benefits, and taken into account when matching them with jobs.
- Buyers and sellers can be matched depending on their choices, such as cost, quality level, and delivery timing.
Simple Example:
Consider the following simple example with three men (A, B, and C) and three women (X, Y, and Z):
Men's Preferences
Man | Preference List |
A | YXZ |
B | ZYX |
C | XZY |
Women's Preferences
Woman | Preference List |
X | BAC |
Y | CBA |
Z | ACB |
For this example, a stable match might be:
(A, Y)
(B, Z)
(C, X)
As a result of the absence of blocking pairs, this matching is stable. For instance, Man A cannot prevent this matching because he has already been paired with woman Y, his top preference. Woman Y is matched to her top pick, male A, thus she cannot stop this matching.
Example:
#include <iostream>
#include <vector>
using namespace std;
struct Person {
int id;
vector preferences;
};
struct Match {
int man;
int woman;
};
vector solveSMP(vector& men, vector& women) {
// Initialize the matching.
vector matching;
for (int i = 0; i < men.size(); i++) {
matching.push_back({-1, -1});
}
// Iterate over the men, proaposing to their preferred women in order.
for (int man = 0; man < men.size(); man++) {
for (int woman : men[man].preferences) {
if (matching[woman].man == -1) {
// The woman is free, so they become engaged.
matching[woman].man = man;
matching[man].woman = woman;
break;
} else {
// The woman is not free, so she chooses whether to stay with her current partner or switch to the new partner.
int currentPartner = matching[woman].man;
vector& womanPrefs = women[woman].preferences;
// Find the index of the current partner in the woman's preferences.
int currentPartnerIdx = -1;
for (int i = 0; i < womanPrefs.size(); i++) {
if (womanPrefs[i] == currentPartner) {
currentPartnerIdx = i;
break;
}
}
// Find the index of the new man in the woman's preferences.
int newManIdx = -1;
for (int i = 0; i < womanPrefs.size(); i++) {
if (womanPrefs[i] == man) {
newManIdx = i;
break;
}
}
if (newManIdx < currentPartnerIdx) {
// The woman prefers the new partner, so they switch partners.
matching[woman].man = man;
matching[man].woman = woman;
// The previous partner becomes free.
matching[currentPartner].woman = -1;
break;
}
}
}
}
return matching;
}
int main() {
// Create the men and women.
vector men = {
{0, {1, 2}},
{1, {2, 1}},
{2, {1, 2}}
};
vector women = {
{1, {0, 2}},
{2, {0, 1}},
{3, {2, 1}}
};
// Solve the SMP and print the matching.
vector matching = solveSMP(men, women);
for (const Match& match : matching) {
cout << "Man " << match.man << " is matched with woman " << match.woman << endl;
}
return 0;
}
Output:
![Stable Marriage Program in C++](https://static.tutorialandexample.com/cpp/stable-marriage-program-in-cpp1.png)
The Stable Marriage Problem and the Gale-Shapley Algorithm:
A distributed technique called the Gale-Shapley algorithm solves the stable marriage problem by finding a stable match. It bears the names of its creators, Lloyd Shapley and David Gale.
Each man proposesproposes to his most desired woman who is not already engaged for the algorithm to function. If the woman is available, she accepts the offer and marries the man. Otherwise, she declines the offer and keeps her existing engagement (if any) to her spouse. If a woman rejects a proposal, the man asks his next favourite woman who is not already engaged to marry him.
When all of the males are either engaged or single, the algorithm comes to an end. There are no blocking couples at this time because the matching is stable.
Representing Preference Lists:
Preference lists can be modelled in a variety of ways. One popular strategy is using a 2D vector, where each row denotes a man or woman, and each column denotes a preference. For instance, the code below demonstrates how to display the preference lists for men and women in the case of a stable marriage problem.
// Preference lists for the men
std::vector<std::vector<int>> menPreferences = {{3, 5, 7, 9}, {2, 3, 8}, {5, 8}};
// Preference lists for the women
std::vector<std::vector<int>> womenPreferences = {{2, 3, 8}, {5, 8}, {1, 3, 9}};
A map with the key being the man or woman and the value being a vector of preferences is another way to represent preference lists. For instance, the code below demonstrates how to map out the men's and women's preference lists in the case of a stable marriage:
// Preference lists for the men
std::map<int, std::vector<int>> menPreferences;
menPreferences[0] = {3, 5, 7, 9};
menPreferences[1] = {2, 3, 8};
menPreferences[2] = {5, 8};
// Preference lists for the women
std::map<int, std::vector<int>> womenPreferences;
womenPreferences[0] = {2, 3, 8};
womenPreferences[1] = {5, 8};
womenPreferences[2] = {1, 3, 9};
The application's requirements will determine the appropriate technique to represent preference lists in C++. However, both of the methods mentioned above are widely used and efficient.
Preference List Examples:
A few instances of preference lists are shown below:
- The problem of a stable marriage: In this problem, there are sets of men and women, and each set has a list of people they desire to marry. Finding a match between men and women ensures that no man or woman prefers their assigned companions above the other.
- When applying for college admission, students generally have a wish list for the universities they want to attend. Colleges also maintain a list of preferred candidates for admission. The aim is to find a match between students and colleges that accommodates everyone's preferences.
- Students often have a wish list for the people they wish to live with when they participate in roommate matching. The main objective is finding a match between the students and housemates that accommodates everyone's tastes.
- Resource allocation: Each agent in resource allocation has a preference list for the resources, and there are several resources. The aim is to find a resource distribution that results in no agent favouring a different set of resources.
The Gale-Shapley Algorithm's Accuracy and Stability:
If no two members of the same sex would choose each other over their designated partners, the marriage is regarded as stable. In other words, no two persons would benefit equally from changing partners.
The Gale-Shapley algorithm ensures stability by assuring that no man and woman may prefer each other over their designated mates. It is made possible by the way the algorithm functions. Each free man proposes to the following woman on his choice list as the algorithm cycles through all free males. If the woman accepts the offer and is available, they are matched. The woman only accepts the request if she likes the man in her current match if she is not free. Otherwise, she declines the offer.
Once all of the males have been matched, the process is repeated. At the end of the algorithm, no man and woman can choose their partners over their allocated partners. If two individuals preferred one another over their assigned partners, one would have suggested to one of them earlier in the algorithm, and the two would have been matched.
An easy illustration of how the Gale-Shapley algorithm functions is given below:
Men Preferences:
Man 0: Woman 1, Woman 2
Man 1: Woman 2, Woman 1
Women Preferences:
Woman 0: Man 1, Man 0
Woman 1: Man 0, Man 1
With Man 0, the algorithm would begin. Woman 1 would accept if Man 0 proposed to her since she thinks Man 0 is better than her existing partner (no one). Therefore, Woman 2 would accept Man 1's marriage proposal because he is better than her existing match (no one).
The process would then come to an end with the following final matching:
Man 0: Woman 1
Man 1: Woman 2
No man and woman favour each other over their designated mates, making this pairing steady.
A quick and effective method for determining a stable match between two sets of components with preference lists is the Gale-Shapley algorithm. Numerous applications have been used, such as resource allocation, flatmate matching, and college admissions.