Stable Marriage Problem in Java
Given N men and N women, the Stable Marriage Problem asks you to match up the men and women in such a way that there are never any two people of the same sex who would choose to be together over their current relationships. Each person has listed their preferences for each member of the other sex in order.If none of these exist, all marriages are deemed to be "stable."
The stable marriage problem is a classic problem in computer science and economics. Finding the perfect match between two sets of elements is a problem, often referred to as men and women.
The goal of the problem is to find a stable set of matches, that is, a set of matches such that no two people prefer each other over their current match. Several algorithms , such as the Gale-Shapley algorithm, have been developed to solve this problem.
In Java, the Gale-Shapley algorithm can be used to solve the stable marriage problem. The algorithm works by having each man and woman rank each other and then iterating over the set of pairs. For each pair, the man and woman compare their rankings, and the man proposes to the woman if he ranks her higher than his current match. The woman then either accepts or rejects the proposal. The algorithm continues until all pairs are stable. The "stable matching problem" requires that two sets of people, men and women, be stably matched to one another. The Gale-Shapley algorithm is an algorithm that resolves this problem. It was initially put up in 1962 by David Gale and Lloyd Shapley.The algorithm works by having each man propose to the woman he prefers, and each woman accepts the highest-ranking proposal she receives. This process continues until each man is matched to a woman and each woman is matched to a man. The matching is said to be stable if there is no pair of people who prefer each other over the people they are matched with.
Example 1
Alice and Bob are both single and looking to get married. Both have a list of potential partners, ranked in order of preference. Alice's list of preferences is Bob, Dave, Joe, and Carl; Bob's list of preferences is Alice, Joe, Dave, and Carl.
Assuming that both Alice and Bob are honest about their preferences, the stable marriage problem can be solved by having Alice and Bob go through the following steps:
- Alice proposes to Bob, who accepts.
- Dave proposes to Alice, who rejects him.
- Joe proposes to Alice, who rejects him.
- Carl proposes to Alice, who rejects him.
- Joe proposes to Bob, who rejects him.
- Dave proposes to Bob, who accepts.
As a result, Alice and Bob are now married, and Dave and Joe remain single. This is a stable marriage because no two people would benefit from switching partners since Alice and Bob prefer each other to the other two potential partners.
Example 2
Example:
John, Mary, Bob, and Jane are four individuals who need to find partners. John and Mary prefer each other over Bob and Jane, while Bob and Jane prefer each other over John and Mary.
John: Mary, Bob, Jane
Mary: John, Bob, Jane
Bob: Jane, Mary, John
Jane: Bob, Mary, John
In this case, the stable marriage problem can be solved by having John and Mary pair off while Bob and Jane pair off. This solution is stable, as neither John nor Mary would prefer Bob or Jane over each other, and neither Bob nor Jane would prefer John or Mary over each other.
Using Gale Shapley Algorithm
The goal is to cycle through every available free man as long as there are accessible free men. Every free man visits every woman on his preference list in the order they are listed. He asks each lady he approaches if she is available, and if she is, they become engaged. If the woman is not free, she can reject him or break off her engagement with the man, depending on her preference list. Therefore, a previously established engagement may be broken if a woman has a better option. The Gale-Shapley algorithm has an O time complexity (n2).
Pseudo Code
// Function to calculate Shapley value
FUNCTION ShapleyValue(players, contributions):
// Initialize the Shapley value of each player to 0
SET ShapleyValues FOR players TO 0
// Loop through all possible permutations of players
FOR EACH permutation IN players:
// Calculate the contribution to the total
// made by the players in this permutation
SET contribution TO contributions[permutation]
// Calculate the marginal contribution of each player
// in this permutation
FOR EACH player IN permutation:
SET marginalContribution TO contribution - contributions[permutation without player]
// Add the marginal contribution of each player
// to their Shapley value
FOR EACH player IN permutation:
SET ShapleyValues[player] TO ShapleyValues[player] + marginal contribution
// Divide the Shapley values of each player
// by the total number of permutations
FOR EACH player IN players:
SET ShapleyValues[player] TO ShapleyValues[player] / PERMUTATIONS(players)
RETURN SjapleyValues
Program
File Name : StableMarriage.java
// Finding the stable marriages using GaleShapley Algorithm
// importing the required packages
import java. util.*;
// Main class declaration
class StableMarriage
{
// Number of Men or Women
// static declaration of number of women or men
static int n = 4;
// wPrefersM1 function returns true if a woman 'w' prefers a man 'm1.'
static boolean wPrefersM1(int pre[][], int w,int m, int m1)
{
// Check if w prefers m over her current engagement m1
for (int j = 0; j < n; j++)
{
// If m1 comes before m in the list of w, then w prefers her current engagement
if (pre[w][j] == m1)
return true;
if (pre[w][j] == m)
return false;
}
return false;
}
// static function declaration to find the stableMarriage . Static functions does not require objects
static void stableMarriage(int pre[][])
{
// integer array to store all the partners of women w
int wPartner[] = new int[n];
boolean mFree[] = new boolean[n];
Arrays.fill(wPartner, -1);
int freeCount = n;
while (freeCount > 0)
{
// Pick the first free man
int m;
// for loop to check whether the men at index m is free or not
for (m = 0; m < n; m++)
if (mFree[m] == false)
break;
// Go to each woman one by one by m's preferences. This is M, the chosen free guy.
for (int j = 0; j < n && mFree[m] == false; j++)
{
int w = pre[m][j];
// if the partner of w is not there
if (wPartner[w - n] == -1)
{
wPartner[w - n] = m;
mFree[m] = true;
freeCount--;
}
// If w is not free
else
{
// Find current engagement of w
int m1 = wPartner[w - n];
// if the woman w prefers m1, then
if (wPrefersM1(pre, w, m, m1) == false)
{
wPartner[w - n] = m;
mFree[m] = true;
mFree[m1] = false;
}
} // Else block
}
} // main while loop block
// Printing the solution
System.out.println("Woman Man");
// for loop to print the solution
for (int j = 0; j < n; j++)
{
System.out.print(" ");
System.out.println(j + n + " " + wPartner[j]);
}
}
// Main section of the program, from where execution begins
public static void main(String[] args)
{
// static declaration of 2- D array to store all the data of women and men
int pre[][] = new int[][]{{7, 5, 6, 4},
{5, 4, 6, 7}, {4, 5, 6, 4},
{5, 5, 6, 7},
{0, 1, 2, 3},
{0, 1, 1, 3},
{0, 2, 2, 3},
{0,1,3,3}};
// calling the function to find stable marriages
stableMarriage(pre);
}
}
Output
Woman Man
4 2
5 1
6 3
7 0
Explanation
All men and women are initially unengaged or free. Each male will present the ladies on his preference list (ranked from highest to lowest), and while iterating the list for each woman, determine whether she is free and, if so, engage her. If not, it means that she has already accepted a proposal from another man. In that case, she can either dump the first man and accept the current man's offer (this will only occur if the current man is preferred over the first man on her list of preferences), or she can decide not to dump the man and let the current man try his luck with the other woman on his list.