Make delicious recipes!

Stable marriage problem



Puzzle: Given n men and n women and a preference order of marriage from each one of them, how to marry these 2n bachelors such that their marriages are stable.
A marriage is stable when both partners in a couple cannot find anyone else (higher in their priority list) available for marriage.
In other words, a marriage is stable when every person gets its most desired partner subject to availability.


Example: Given men m1 and m2 and women w1 and w2.
Preference order of m1 is w1,w2 and that of m2 is also w1,w2.
Preference order of w1 is m1,m2 and that of w2 is also m1,m2.

Possible marriages among the above are:
  1. m1,w1 and m2,w2
  2. m1,w2 and m2,w1

The second system of marriages is less stable than the first one because there exists a combination where both m1 and w1 can find a better spouse as per their choice.
While there is no such possibility in the first case, hence its more stable.




Solution: An algorithm to do this as follows:

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.



Java code:

import java.util.*;
import java.util.Map.Entry;

public class StableMarriageProblem {

    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());
        }
    }
}




Sample Run:

Input Output
// 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}
};

Man 0 arrives:
Man 0 engaged to woman 0

Man 1 arrives:
Man 0 is dumped by woman 0
Man 1 engaged to woman 0

Man 0 arrives:
Man 0 engaged to woman 1

Man 2 arrives:
Man 0 is dumped by woman 1
Man 2 engaged to woman 1

Man 0 arrives:
Man 0 engaged to woman 2

Man 1 married to woman 0
Man 2 married to woman 1
Man 0 married to woman 2

Reference: http://en.wikipedia.org/wiki/Stable_marriage_problem


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:
// 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.









Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal