Gale-Shapley Algorithm

user_10941457 0
Viewed 1320

I want to write a program that matches n men [0,1,2,...,n-1] to n women [0,1,2,...,n-1] according to their preferences. These preferences are represented by n x n-matrices, one for the men and one for the women. 

            [ 0 2 1 ]
  E.g. men: [ 1 0 2 ]. The rows represent each man from 0 to 2, and per row we see a man's 'top 3'.
            [ 1 2 0 ]
  In this example: man 0 prefers woman 0 over woman 2; woman 1 is both man1's and man2's most prefered partner.

Now, I want to make sure that the matchings are as ideal as possible. This can be done by using the Gale-Shapley Algorithm.

I have two questions:

  • Suppose that m0 and m1 both have w0 as their first pick. Then, we'll have to look at w0's preferences: suppose that m0 is ranked higher, then (m0,w0) is a (temporary) matching. What should I do next? Do I first match m2 to his first pick, or - since m1 is still free - do I match m1 to his second pick?

  • I've already implemented an algorithm that looks like this:

Basically, the input consists of the preference matrices of both men and women. The result should be an array like res = [2,0,1], meaning man 2 is matched to woman 0, m0 with w1 and m1 with w2.

    public int[] match(int[][] men, int[][] women) {

    int n = men.length;
    boolean[] menFree = new boolean[n];
    Arrays.fill(menFree, true);
    int[] res = new int[n];
    Arrays.fill(res, -1);
    int free = n;
    int m = 0;
    while (free > 0 && m<n) { 
        for (int i = 0; i < n; i++) {
            if(menFree[i]){
                int w = men[i][m];
                if(res[w]==-1){
                    res[w]=i;
                    menFree[i]=false;
                    free--;
                } else {
                    int c = res[w];
                    int colI = 0;
                    int colC = 0;
                    for(int j=0;j<n;j++){ 
                        if(women[w][j]==i){
                            colI = j;
                        } else if(women[w][j]==c){
                            colC = j;
                        }
                    }
                    if(colI<colC){
                        res[w]=i;
                        menFree[c]=true;
                        menFree[i]=false;
                    } else {
                        //do nothing or change column here, depending on answer to my first question.
                    }
                }
            }
        }
        m++; 
    }
    return res;
    }

As you can see I'm not sure what to do with the else-part when the position of a man's (=M's) competitor is higher then the position of M himself. Also, if it turns out that I should at that point look for M's second pick, how can I do this? There's still a possibility that I'll have to return to the first pick of the man after M.

Thanks for helping me out.

algorithm java
1 Answers

I read the wiki. And I implement myself.I think I understand it but my program is not beautiful.Just for communication.

package algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class GaleShapley {

    public static void main(String[] args) {
        int[][] men = {{1, 2, 0}, {0, 1, 2}, {2, 1, 0}};
        int[][] women = {{1, 2, 0}, {0, 1, 2}, {2, 1, 0}};
        int[] res = match(men, women);
        for (int i : res)
            System.out.println(i);
    }

    static int[] match(int[][] men, int[][] women) {
        Map<Integer, Integer> temp = new HashMap<>();
        int size = men.length;
        boolean[] menFree = new boolean[size];
        boolean[] womenFree = new boolean[size];
        Arrays.fill(menFree, true);
        Arrays.fill(womenFree, true);
        ArrayList<Integer> stillFree = new ArrayList<>();

        while (stillFree.size() + temp.size() < size) {
            for (int i = 0, j = 0; i < size; i++, j = 0) {
                if (menFree[i]) {
                    for (; j < size; j++) {
                        //if the woman is free,make them a pair
                        if (womenFree[men[i][j]]) {
                            // make woman and man i pair, the woman's index is men[i][j]
                            temp.put(men[i][j], i);
                            menFree[i] = false;
                            womenFree[men[i][j]] = false;
                            break;
                        } else {
                            // the woman is not free,check her pair is whether stable
                            int pairMan = temp.get(men[i][j]);
                            boolean stable = checkStable(pairMan, i, men[i][j], women);
                            // not stable break them and make new pair
                            if (!stable) {
                                temp.put(men[i][j], i);
                                menFree[i] = false;
                                menFree[pairMan] = true;
                                break;
                            }
                        }
                    }
                    // if man i is still free , it means that he can't find a woman
                    if (menFree[i])
                        stillFree.add(i);
                }
            }
        }
        int[] stablePair = new int[2 * temp.size()];
        int i = 0;
        for (Map.Entry<Integer, Integer> entry : temp.entrySet()) {
            stablePair[i] = entry.getValue();
            i++;
            stablePair[i] = entry.getKey();
            i++;
        }
        return stablePair;
    }

    static boolean checkStable(int pairMan, int currentMan, int woman, int[][] women) {
        // index of pairMan and currentMan
        int p = 0, c = 0;
        for (int i = 0; i < women.length; i++) {
            if (women[woman][i] == pairMan)
                p = i;
            else if (women[woman][i] == currentMan)
                c = i;
        }
        // p<c : the woman love p more than c, they are stable
        return p < c;
    }
}
user_103244940
Related