稳定匹配问题 (1) - Gale & Shapley

稳定匹配

---

在1962年Gale和Shapley发表了一篇论文: College Admissions and the Stability of Marriage，首次提出了婚姻匹配问题(维基百科), 使婚姻和大学招生成为稳定匹配的典型例子.

什么是稳定匹配

---

以婚姻匹配为例, 假设在当前匹配结果中存在两对(m1, w1)和(m2, w2), 在喜好排名中, m1更喜欢w2, m2也更喜欢w1, 这时我们可以称当前匹配是不稳定的.

如何实现稳定匹配呢 ?

---

要找到一种稳定匹配, 可使用Gale-Shapley提出的算法( 用反证法证明其有效性 ), 但有个前提是让男生主动求婚, 主要过程如下:

function stableMatching {
    Initialize all m ∈ M and w ∈ W to free
    while ∃ free man m who still has a woman w to propose to {
       w = first woman on m’s list to whom m 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' becomes free
           (m, w) become engaged
         else
           (m', w) remain engaged
    }
}

算法实现

---

Person.java, 用来表示male或female.

public class Person {

    public static final Integer SINGLE = -1;

    private Integer id;
    private String name;
    private Integer nextAskId = 0;
    // 当前伴侣id
    private Integer currentPartnerId = SINGLE;
    // 伴侣id在心中的排名
    private Map<Integer, Integer> partnerIdToRank = new LinkedHashMap<Integer, Integer>();

    public Person addRank(Integer personId, Integer rank) {
        this.partnerIdToRank.put(personId, rank);
        return this;
    }

    public Integer getRankOf(Integer partnerId) {
        Integer rank = this.partnerIdToRank.get(partnerId);
        return rank == null ? Integer.MAX_VALUE : rank;
    }

    //======================================================================

    public Integer getId() {
        return id;
    }

    public Person setId(Integer id) {
        this.id = id;
        return this;
    }

    public String getName() {
        return name;
    }

    public Person setName(String name) {
        this.name = name;
        return this;
    }

    public Integer getNextPerfectId() {
        return nextAskId;
    }

    public Person setNextAskId(Integer nextAskId) {
        this.nextAskId = nextAskId;
        return this;
    }

    public Integer getCurrentPartnerId() {
        return currentPartnerId;
    }

    public Person setCurrentPartnerId(Integer currentPartnerId) {
        this.currentPartnerId = currentPartnerId;
        return this;
    }

}

GaleShapley.java, 主要是算法过程:

public class GaleShapley {

    public static void main(String[] args) {
        List<Person> males = new LinkedList<Person>();
        males.add(new Person().setId(0).setName("Mr.A").addRank(1, 1).addRank(2, 2).addRank(0, 3));
        males.add(new Person().setId(1).setName("Mr.B").addRank(1, 1).addRank(0, 2));
        males.add(new Person().setId(2).setName("Mr.C").addRank(0, 1).addRank(1, 2));
        males.add(new Person().setId(3).setName("Mr.D").addRank(3, 1).addRank(1, 2));

        List<Person> females = new LinkedList<Person>();
        females.add(new Person().setId(0).setName("Miss.A").addRank(1, 1).addRank(2, 2));
        females.add(new Person().setId(1).setName("Miss.B").addRank(0, 1).addRank(1, 2).addRank(2, 3));
        females.add(new Person().setId(2).setName("Miss.C").addRank(3, 1).addRank(1, 2));
        females.add(new Person().setId(3).setName("Miss.D").addRank(1, 1).addRank(2, 2));

        new GaleShapley().stableMatch(males, females);
    }

    public void stableMatch(List<Person> males, List<Person> females) {
        if (males == null || females == null) {
            return;
        }
        if (males.size() != females.size()) {
            return;
        }
        Person freeMale = getFreeMale(males);
        while (freeMale != null) {
            Integer femaleId = freeMale.getNextPerfectId();
            Person female = females.get(femaleId);
            if (isSingle(female)) {
                // 还是单身
                freeMale.setCurrentPartnerId(female.getId());
                female.setCurrentPartnerId(freeMale.getId());

            } else {
                // 选择更好的
                Integer curMaleId = female.getCurrentPartnerId();
                Integer curMalePartnerRank = female.getRankOf(curMaleId);
                Integer freeMaleRank = female.getRankOf(freeMale.getId());
                if (freeMaleRank < curMalePartnerRank) {
                    males.get(curMaleId).setCurrentPartnerId(Person.SINGLE);
                    freeMale.setCurrentPartnerId(female.getId());
                    female.setCurrentPartnerId(freeMale.getId());
                }
            }
            freeMale.setNextAskId(freeMale.getNextPerfectId() + 1);
            // 继续为 freeMale 找对象
            freeMale = getFreeMale(males);
        }

        print(males, females);
    }

    private static void print(List<Person> males, List<Person> females) {
        males.forEach(m -> {
            Person female = females.get(m.getCurrentPartnerId());
            if (female != null) {
                System.out.println(m.getName() + "  <-->  " + female.getName());
            } else {
                System.out.println(m.getName() + "  still  SINGLE");

            }
        });
    }

    private static Person getFreeMale(List<Person> males) {
        for (Person male : males) {
            if (isSingle(male)) {
                return male;
            }
        }
        return null;
    }

    private static boolean isSingle(Person p) {
        return Person.SINGLE.equals(p.getCurrentPartnerId());
    }
}

执行main()中的用例, 得出结果:

Mr.A  <-->  Miss.B
Mr.B  <-->  Miss.A
Mr.C  <-->  Miss.D
Mr.D  <-->  Miss.C

有多少稳定匹配结果

---

上面讨论的前提是男士主动求婚, 而且是先有一个队伍顺序, 如果改变一下这些条件, Gale-Shapley算法可能得到的是另外一种稳定匹配结果.
那么, 如何获得所有的稳定匹配结果呢 ?

使用穷举法

我们需要对每个male进行穷举, 覆盖所有的male求婚顺序, 这样的问题用递归很方便.

public void allStableMatch(Integer maleId, List<Person> males, List<Person> females) {
    if (maleId.intValue()  == males.size()) {
        if (isStableMatch(males, females)) {
            print(males, females);
        }
        return;
    }
    Person male = males.get(maleId);
    // 试所有女的favor舞伴
    male.getPartnerIdToRank().entrySet().forEach((favor) -> {
        Person female = females.get(favor.getKey());
        if (isSingle(female) && female.like(maleId)) {
            male.setCurrentPartnerId(female.getId());
            female.setCurrentPartnerId(male.getId());
            allStableMatch(maleId + 1, males, females);
            male.setCurrentPartnerId(Person.SINGLE);
            female.setCurrentPartnerId(Person.SINGLE);
        }
    });
}

测试用例 :

public static void main(String[] args) {
    List<Person> males = new LinkedList<Person>();
    males.add(new Person().setId(0).setName("Mr.A").addRank(0).addRank(2).addRank(1));
    males.add(new Person().setId(1).setName("Mr.B").addRank(1).addRank(2).addRank(0));
    males.add(new Person().setId(2).setName("Mr.C").addRank(0).addRank(1).addRank(2));

    List<Person> females = new LinkedList<Person>();
    females.add(new Person().setId(0).setName("Miss.A").addRank(2).addRank(0).addRank(1));
    females.add(new Person().setId(1).setName("Miss.B").addRank(0).addRank(2).addRank(1));
    females.add(new Person().setId(2).setName("Miss.C").addRank(1).addRank(0).addRank(2));

    new GaleShapleyAllCompose().allStableMatch(0, males, females);
}

最终可以找出两个匹配结果, 如下:

Mr.A  <-->  Miss.C
Mr.B  <-->  Miss.B
Mr.C  <-->  Miss.A


Mr.A  <-->  Miss.B
Mr.B  <-->  Miss.C
Mr.C  <-->  Miss.A

二分图和匈牙利算法

其实这个问题还可以用二部图和匈牙利算法来处理, 详细内容请看下一篇博客.

参考

---

College Admissions and the Stability of Marriage
https://en.wikipedia.org/wiki/Stable_marriage_problem