Given N men and N women, where each person has ranked all members of the opposite sex in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are “stable” (Source Wiki).
It is always possible to form stable marriages from lists of preferences (See references for proof). Following is Gale–Shapley algorithm to find a stable matching:
The idea is to iterate through all free men while there is any free man available. Every free man goes to all women in his preference list according to the order. For every woman he goes to, he checks if the woman is free, if yes, they both become engaged. If the woman is not free, then the woman chooses either says no to him or dumps her current engagement according to her preference list. So an engagement done once can be broken if a woman gets better option.
http://prismoskills.appspot.com/lessons/Algorithms/Chapter_14_-_Marriage_problem.jsp
While there are bachelor men remaining, do the following:
Allow a man to propose to a woman.
If that woman has not accepted any proposal yet, she will accept the proposal.
If that woman has already accepted a proposal, she will break that if the new proposal is higher in her preference list.
If woman breaks her current alliance, the corresponding man will return to the pool of bachelors and have some wine.
When the pool of free men is over, everybody has been assigned a stable spouse.
And they live happily ever after.
public static void main(String[] args)
{
// Preference order for 3 men
int men[][] = {
{0,1,2},
{0,1,2},
{0,1,2}
};
// Preference order for 3 women
int women[][] = {
{1,0,2},
{1,2,0},
{0,1,2}
};
// Add all available men to a HashSet, so its easy to lookup remaining bachelors
Set<Integer> availableMen = new HashSet <Integer> ();
for (int i=0; i<men.length; i++)
availableMen.add(i);
// Store alliance of a women in a HashMap.
// Null value means no alliance.
Map<Integer, Integer> availableWomen = new HashMap <Integer, Integer> ();
for (int i=0; i<women.length; i++)
availableWomen.put(i, null);
// Loop till there are bachelor men available
int size = availableMen.size();
while (size > 0)
{
int currentBachelor = availableMen.iterator().next();
System.out.println ("\nMan " + currentBachelor + " arrives:");
for (int w : men[currentBachelor]) // loop through preferences of this man
{
Integer fiance = availableWomen.get(w);
if (fiance == null) // this woman is not yet engaged
{
availableWomen.put(w, currentBachelor);
availableMen.remove(currentBachelor);
System.out.println ("Man " + currentBachelor + " engaged to woman " + w);
break;
}
else // this woman is currently engaged
{
int prefForFiance = -1;
int prefForCurrentBachelor = -1;
for (int k=0; k<women[w].length; k++)
{
if (women[w][k] == fiance) // find preference order for current fiance
prefForFiance = k;
if (women[w][k] == currentBachelor) // find preference order for current proposer
prefForCurrentBachelor = k;
}
if (prefForCurrentBachelor < prefForFiance) // nextBachelor has higher preference by this woman
{
availableWomen.put (w, currentBachelor); // accept current bachelor
availableMen.remove(currentBachelor);
availableMen.add(fiance); // return previous fiance to bachelors' pool
System.out.println ("Man " + fiance + " is dumped by woman " + w);
System.out.println ("Man " + currentBachelor + " engaged to woman " + w);
break;
}
}
}
size = availableMen.size();
}
// Print out the alliances
System.out.println();
Iterator<Entry<Integer, Integer>> itr = availableWomen.entrySet().iterator();
while (itr.hasNext())
{
Entry<Integer, Integer> entry = itr.next();
System.out.println ("Man " + entry.getValue() + " married to woman " + entry.getKey());
}
}
Read full article from Stable Marriage Problem | GeeksforGeeks
It is always possible to form stable marriages from lists of preferences (See references for proof). Following is Gale–Shapley algorithm to find a stable matching:
The idea is to iterate through all free men while there is any free man available. Every free man goes to all women in his preference list according to the order. For every woman he goes to, he checks if the woman is free, if yes, they both become engaged. If the woman is not free, then the woman chooses either says no to him or dumps her current engagement according to her preference list. So an engagement done once can be broken if a woman gets better option.
Initialize all men and women to free
while there exist a free man m who still has a woman w to propose to
{
w = m's highest ranked such woman to whom he has not yet proposed
if w is free
(m, w) become engaged
else some pair (m', w) already exists
if w prefers m to m'
(m, w) become engaged
m' becomes free
else
(m', w) remain engaged
}
// Prints stable matching for N boys and N girls. Boys are numbered as 0 to// N-1. Girls are numbereed as N to 2N-1.void stableMarriage(int prefer[2*N][N]){ // Stores partner of women. This is our output array that // stores paing information. The value of wPartner[i] // indicates the partner assigned to woman N+i. Note that // the woman numbers between N and 2*N-1. The value -1 // indicates that (N+i)'th woman is free int wPartner[N]; // An array to store availability of men. If mFree[i] is // false, then man 'i' is free, otherwise engaged. bool mFree[N]; // Initialize all men and women as free memset(wPartner, -1, sizeof(wPartner)); memset(mFree, false, sizeof(mFree)); int freeCount = N; // While there are free men while (freeCount > 0) { // Pick the first free man (we could pick any) int m; for (m = 0; m < N; m++) if (mFree[m] == false) break; // One by one go to all women according to m's preferences. // Here m is the picked free man for (int i = 0; i < N && mFree[m] == false; i++) { int w = prefer[m][i]; // The woman of preference is free, w and m become // partners (Note that the partnership maybe changed // later). So we can say they are engaged not married if (wPartner[w-N] == -1) { wPartner[w-N] = m; mFree[m] = true; freeCount--; } else // If w is not free { // Find current engagement of w int m1 = wPartner[w-N]; // If w prefers m over her current engagement m1, // then break the engagement between w and m1 and // engage m with w. if (wPrefersM1OverM(prefer, w, m, m1) == false) { wPartner[w-N] = m; mFree[m] = true; mFree[m1] = false; } } // End of Else } // End of the for loop that goes to all women in m's list } // End of main while loop // Print the solution cout << "Woman Man" << endl; for (int i = 0; i < N; i++) cout << " " << i+N << "\t" << wPartner[i] << endl;}// This function returns true if woman 'w' prefers man 'm1' over man 'm'bool wPrefersM1OverM(int prefer[2*N][N], int w, int m, int m1){ // Check if w prefers m over her current engagment m1 for (int i = 0; i < N; i++) { // If m1 comes before m in lisr of w, then w prefers her // cirrent engagement, don't do anything if (prefer[w][i] == m1) return true; // If m cmes before m1 in w's list, then free her current // engagement and engage her with m if (prefer[w][i] == m) return false; }}While there are bachelor men remaining, do the following:
Allow a man to propose to a woman.
If that woman has not accepted any proposal yet, she will accept the proposal.
If that woman has already accepted a proposal, she will break that if the new proposal is higher in her preference list.
If woman breaks her current alliance, the corresponding man will return to the pool of bachelors and have some wine.
When the pool of free men is over, everybody has been assigned a stable spouse.
And they live happily ever after.
public static void main(String[] args)
{
// Preference order for 3 men
int men[][] = {
{0,1,2},
{0,1,2},
{0,1,2}
};
// Preference order for 3 women
int women[][] = {
{1,0,2},
{1,2,0},
{0,1,2}
};
// Add all available men to a HashSet, so its easy to lookup remaining bachelors
Set<Integer> availableMen = new HashSet <Integer> ();
for (int i=0; i<men.length; i++)
availableMen.add(i);
// Store alliance of a women in a HashMap.
// Null value means no alliance.
Map<Integer, Integer> availableWomen = new HashMap <Integer, Integer> ();
for (int i=0; i<women.length; i++)
availableWomen.put(i, null);
// Loop till there are bachelor men available
int size = availableMen.size();
while (size > 0)
{
int currentBachelor = availableMen.iterator().next();
System.out.println ("\nMan " + currentBachelor + " arrives:");
for (int w : men[currentBachelor]) // loop through preferences of this man
{
Integer fiance = availableWomen.get(w);
if (fiance == null) // this woman is not yet engaged
{
availableWomen.put(w, currentBachelor);
availableMen.remove(currentBachelor);
System.out.println ("Man " + currentBachelor + " engaged to woman " + w);
break;
}
else // this woman is currently engaged
{
int prefForFiance = -1;
int prefForCurrentBachelor = -1;
for (int k=0; k<women[w].length; k++)
{
if (women[w][k] == fiance) // find preference order for current fiance
prefForFiance = k;
if (women[w][k] == currentBachelor) // find preference order for current proposer
prefForCurrentBachelor = k;
}
if (prefForCurrentBachelor < prefForFiance) // nextBachelor has higher preference by this woman
{
availableWomen.put (w, currentBachelor); // accept current bachelor
availableMen.remove(currentBachelor);
availableMen.add(fiance); // return previous fiance to bachelors' pool
System.out.println ("Man " + fiance + " is dumped by woman " + w);
System.out.println ("Man " + currentBachelor + " engaged to woman " + w);
break;
}
}
}
size = availableMen.size();
}
// Print out the alliances
System.out.println();
Iterator<Entry<Integer, Integer>> itr = availableWomen.entrySet().iterator();
while (itr.hasNext())
{
Entry<Integer, Integer> entry = itr.next();
System.out.println ("Man " + entry.getValue() + " married to woman " + entry.getKey());
}
}
Note that this problem does not consider the unhappiness of people who did not get the spouses of their choice.
Maybe there were people who absolutely hated each other and would not sustain a marriage if married.
If that were the case, then the above problem would need to have weights associated with each preference.
Something like:
For such a case, following algorithm might work:
Maybe there were people who absolutely hated each other and would not sustain a marriage if married.
If that were the case, then the above problem would need to have weights associated with each preference.
Something like:
// Preference order for 3 men, along with weights for their preferences
int men[][][2] = {
{ {0,90} ,{1,50} ,{2,20} },
{ {0,80} ,{1,60} ,{2,40} },
{ {0,60} ,{1,50} ,{2,40} }
};
// Preference order for 3 women, along with weights for their preferences
int women[][][2] = {
{ {1,30} ,{0,20} ,{2,10} },
{ {1,90} ,{2,50} ,{0,10} },
{ {0,70} ,{1,50} ,{2,30} }
};
For such a case, following algorithm might work:
- While there are bachelor men remaining, do the following:
- Allow a man to propose to a woman.
- If that woman has not accepted any proposal yet, she will accept the proposal.
- If that woman has already accepted a proposal, she will break that if
the new proposal is higher in her preference list.- the sum of older relationship's preferences is lower than that of new relationship.
- If woman breaks her current alliance, the corresponding man will return to the pool of bachelors and have some wine.
- When the pool of free men is over, everybody has been assigned a stable spouse.
Read full article from Stable Marriage Problem | GeeksforGeeks
