盖尔-沙普利算法(Gale-Shapley)

简称“GS算法”，也称为延迟接受算法。是盖尔和沙普利为了寻找一个稳定匹配而设计出的市场机制。

稳定婚配问题

这是GS算法主要的应用领域，假设现在有五位男士（Ａ，Ｂ，Ｃ，D，E），四位女士（ａ，ｂ，ｃ，ｄ），他们参加一档相亲节目，如何配对能保证最终的相亲结果是稳定的

稳定婚姻就是不存在两个人都认为对方比自己现在的婚配对象更好，例如A与a婚配，B与b婚配，但是A认为b比a更适合自己，b也认为A比B更适合自己，这就是一种不稳定的婚姻关系

而Gale-Shapley算法得到的最终结果一定是一组稳定的婚配关系

算法流程：

初始状态下

首先，参加婚配的男士和女士根据各自情况对异性做出排序（根据偏好程度）

所有人都完成自己的偏好列表后

开始进行邀请，由男士邀请女士，男士根据自己的偏好列表发出邀请，女士在收到邀请后会决定接收或拒绝

当自己现在没有婚配对象并且邀请人在自己考虑范围之内时这位女士会“暂时”接收邀请，当这名女士已经有暂时婚配对象时，女士会将这两名邀请人进行比较，接收其中更偏好的邀请人的邀请，拒绝另外一位的邀请

可以看到在第一轮的邀请过程中，男士A与女士b暂时达成婚配关系，男士B与女士c暂时达成婚配关系，男士D与女士d暂时达成婚配关系，而男士C与男士E的邀请都被拒绝

在第二轮的邀请中，上一轮确定婚配关系的男士会放弃邀请，上一轮邀请失败或者被拒绝的男士按照偏好表顺序继续发出邀请

在第二轮邀请过程中，C与D的邀请均失败，男士C是由于女士b更偏好A，男士E则是由于不在女士c的考虑范围之内

可见第三轮邀请仍然以两位的失败告终

第四轮邀请，男士C比男士D更被女士d偏好，所以邀请成功，男士D则被拒绝，达成的暂时婚配关系失效。而男士E则再次被拒绝，并且由于他已经邀请了自己偏好表中的所有女士，所以他被迫出局

接下来的五，六，七轮中，只有男士D不断发出邀请，但都被拒绝

最终，男士D，男士E由于邀请都被拒绝而出局，女士A由于未接收任何邀请也被迫出局。而男士A与女士b，男士B与女士c，男士C与女士d，最终确定婚配关系。

并且达成的都是稳定的婚配关系。

算法的结果

算法最终的结果是稳定匹配的婚姻关系，但不一定是匹配最大的婚姻关系，例如 A-a，B-b，C-c，D-d 可以构成四对匹配关系，但这并不是稳定的因为相较于各自现在的对象，A更偏好b，b也更偏好A。

另外算法中的结果，对于发出邀请的一方往往只能将就，而被邀请的一方往往拥有更好的选择（邀请者在与被邀请者确定暂时匹配关系后，被邀请者可以继续接收更偏好的人的邀请，并结束这段暂时匹配关系，而邀请者就只能继续匹配更不偏好的被邀请者）

算法实现

Man类，表示婚姻匹配问题中发出邀请的男士

package Gender;
import edu.princeton.cs.algs4.Queue;


/*
 * 男性类Man
 * 继承了可比类Comparable
 * 实现了婚配过程中的发出邀请
 * 以及暂时接收后被拒绝等过程
 */


public class Man implements Comparable<Man>{
    private char name;  //男性姓名
    public int[] favorNum;
    private Queue<Woman> favor;  //利用先进先出队列实现男性的偏好队列
    private boolean status;  //男性婚配状态，是否暂时拥有婚配对象
    private Woman current_Girl;  //当前婚配对象
    private boolean failed;  //通过偏好队列是否为空判断是否出局



    //构造函数
    public Man(char name_in,int numWoman){
        name=name_in;
        favorNum=new int[numWoman];
        favor= new Queue<>();  //初始化队列
        status=false;  //初始状态无婚配状态
        current_Girl=null;  //暂定女友为null
        failed=false;  //初始状态没有出局
    }

    //通过数组进行入队操作，获取偏好队列
    public void EntryQueue(Woman[] womanGroup){
        for (int favorGirl : favorNum) {
            favor.enqueue(womanGroup[favorGirl]);
        }
    }

    //定义Invitation方法，用于对异性发出邀请并处理
    public int Invitation(){
        //如果已有婚配，本轮放弃发送邀请
        if(status) return 0;
        //如果已出局，本轮放弃发送邀请
        if(failed) return 0;
        //正常发送邀请
        else{
            //从偏好队列中出队，获取当前最偏好的异性
            Woman Girl=favor.dequeue();
            //调用Woman的ReceiveInvitation()方法，获得邀请的结果
            boolean result=Girl.ReceiveInvitation(this);
            //如果成功邀请
            if(result){
                status=true;  //修改婚配状态
                current_Girl=Girl;  //修改暂时婚配对象
                return 1;
            }
            //如果没有成功邀请并且队列为空，说明该男性出局
            if(favor.isEmpty()) {
                failed=true;
            }
            return 1;
        }
    }


    //更改状态方法，用于女方反悔约定后修改男方的婚配状态
    public void ChangeState(){
        status=false;
        current_Girl=null;
    }


    public char name(){return name;}

    //获取婚配对象的姓名
    public char GirlName(){
        if(current_Girl!=null) return current_Girl.name();
        else{return ' ';}
    }

    //重载比较方法
    @Override
    public int compareTo(Man man) {
        if(name==man.name) return 0;
        else return -1;
    }
}

Woman类，表示婚姻匹配问题中接收邀请的女士

package Gender;

import edu.princeton.cs.algs4.StdOut;


/*
 * 女性类Woman
 * 定义了接收邀请的方法，用于处理男方发送邀请后进行的操作
 * 同样继承了可比较类用于进行比较
 * */


public class Woman implements Comparable<Woman> {
    private char name;  //姓名
    //偏好数组（由于女方不需要判断出局，同时每轮都需要挑选最优的邀请所以采用了数组的数据结构）
    private Man[] favor;
    private boolean status;  //婚配状态
    private Man current_Boy;  //暂时婚配对象

    //构造函数
    public Woman(char name_in, Man[] favor_in){
        name=name_in;
        favor=favor_in;
        status=false;
        current_Boy=null;
    }

    //接收邀请函数，用于接收男方邀请后进行决策
    public boolean ReceiveInvitation(Man man){
        /*
         * 没有婚配对象的情况下
         * 只需要在偏好数组中发现这个邀请人，就可以将他暂定为对象
         */
        if(!status){
            //遍历偏好数组
            for(Man favorMan:favor){
                //如果存在这个邀请人
                if(favorMan==man) {
                    current_Boy=man;  //修改暂定婚配对象
                    status=true;  //修改婚配状态
                    StdOut.printf("man:%c 与 woman:%c 暂时配对\n",man.name(),name);
                    return true;  //邀请成功，返回true
                }
            }
            //没有遍历到，说明对方不在这个人考虑范围内，返回false。邀请失败
            StdOut.printf("man:%c 与 woman:%c 配对失败\n",man.name(),name);
            return false;
        }


        //存在婚配对象的情况下，判断这个邀请人和当前对象的偏好顺序，择优取之
        else {
            //遍历偏好数组
            for(Man favorMan:favor){
                //先发现当前对象，说明更偏好当前对象，邀请失败
                if(favorMan==current_Boy) {
                    StdOut.printf("man:%c 与 woman:%c 配对失败, woman:%c 仍与 man:%c 配对\n", man.name(), name, name, current_Boy.name());
                    return false;
                }
                //先发现邀请对象，说明更偏好邀请对象，邀请成功
                else if(favorMan==man){
                    current_Boy.ChangeState();  //先修改原对象的状态
                    StdOut.printf("man:%c 取代 man:%c 与 woman:%c 暂时配对\n",man.name(),current_Boy.name(),name);
                    current_Boy=man;  //更改暂定对象的数据
                    //不需要修改状态，始终都是已经暂时匹配的状态
                    return true;  //返回true
                }
            }
            StdOut.printf("man:%c 与 woman:%c 配对失败, woman:%c 仍与 man:%c 配对\n",man.name(),name,name,current_Boy.name());
            return false;  //可以说不存在这种情况，因为已经有暂定对象，那必然可以遍历到至少一个对象，不会运行这两句语句
        }
    }


    public char name(){return name;}

    @Override
    public int compareTo(Woman woman) {
        if(name==woman.name) return 0;
        else return -1;
    }
}

GaleShapley类，执行算法流程的主程序类

import Gender.Man;
import Gender.Woman;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;

/*
 * 盖尔沙普利算法的实现
 * */

public class GaleShapley {

    public Man[] ManGroup;
    public Woman[] WomanGroup;
    public GaleShapley(In in1,In in2){
        CreateManGroup(in1);
        CreateWomanGroup(in2);
        InsertManFavor();
    }

    public void CreateManGroup(In in){
        int numMan=in.readInt();
        int numWoman=in.readInt();
        ManGroup=new Man[numMan];

        for(int i=0;i<numMan;i++){
            int manName=in.readInt();
            Man man=new Man((char) manName,numWoman);
            for(int j=0;j<numWoman;j++){
                int Num=in.readInt()-1;
                man.favorNum[j]=Num;
            }
            ManGroup[i]=man;
        }
    }
    public void CreateWomanGroup(In in){
        int numMan=in.readInt();
        int numWoman=in.readInt();
        WomanGroup=new Woman[numWoman];
        for(int i=0;i<numWoman;i++){
            int womanName=in.readInt();
            Man[] men=new Man[numMan];
            for(int j=0;j<numMan;j++){
                int favorNum=in.readInt()-1;
                if (favorNum<0) continue;
                Man favorMan=ManGroup[favorNum];
                men[j]=favorMan;
            }

            WomanGroup[i]=new Woman((char)womanName,men);
        }
    }
    public void InsertManFavor(){
        for(Man man:ManGroup){
            man.EntryQueue(WomanGroup);
        }
    }

    public static void main(String[] args) {

        GaleShapley GS=new GaleShapley(new In(args[0]),new In(args[1]));

        //初始化num=1
        int num=1;
        //开始循环进行邀请
        while(num!=0){
            StdOut.printf("-------------------------------------------" +
                    "\n开始一轮邀请" +
                    "\n-------------------------------------------\n");
            num=0;  //将num设为0
            //男方进行一轮邀请
            for(Man man:GS.ManGroup){
                num+=man.Invitation();  //不断将返回值加入num
            }
            //num仍然等于0说明一整轮都没有成功“发出”邀请
            //注意是发出邀请，只要女方成功接收到邀请就返回1（不需要女方一定同意邀请），否则返回0.
            //说明所有男性要么已经有暂时配对成功的对象，要么已经出局
            //这种情况就可以结束循环，打印结果了
        }
        StdOut.println("\n最终结果\n");
        for(Man man:GS.ManGroup){
            StdOut.printf("man:%c --> woman:%c\n",man.name(),man.GirlName());
        }

    }
}

运行结果

-------------------------------------------
开始一轮邀请
-------------------------------------------
man:A 与 woman:b 暂时配对
man:B 与 woman:c 暂时配对
man:C 与 woman:c 配对失败, woman:c 仍与 man:B 配对
man:D 与 woman:d 暂时配对
man:E 与 woman:d 配对失败, woman:d 仍与 man:D 配对
-------------------------------------------
开始一轮邀请
-------------------------------------------
man:C 与 woman:b 配对失败, woman:b 仍与 man:A 配对
man:E 与 woman:c 配对失败, woman:c 仍与 man:B 配对
-------------------------------------------
开始一轮邀请
-------------------------------------------
man:C 与 woman:a 配对失败
man:E 与 woman:b 配对失败, woman:b 仍与 man:A 配对
-------------------------------------------
开始一轮邀请
-------------------------------------------
man:C 取代 man:D 与 woman:d 暂时配对
man:D 与 woman:c 配对失败, woman:c 仍与 man:B 配对
man:E 与 woman:a 配对失败
-------------------------------------------
开始一轮邀请
-------------------------------------------
man:D 与 woman:b 配对失败, woman:b 仍与 man:A 配对
-------------------------------------------
开始一轮邀请
-------------------------------------------
man:D 与 woman:a 配对失败
-------------------------------------------
开始一轮邀请
-------------------------------------------

最终结果

man:A --> woman:b
man:B --> woman:c
man:C --> woman:d
man:D --> woman: 
man:E --> woman:

可以看到最终运行结果与我们预估过程一致

---

高考录取机制下的Gale-Shapley算法

现行高考录取机制-顺序志愿

这里以顺序志愿为例，即第一志愿优先的录取机制。考生在填报志愿时，分为第一志愿，第二志愿等多个志愿。这些志愿之间的关系不是平行的，而是顺序投递

即第一轮，先进行第一志愿的投递，各个学校在收到志愿后根据招生人数N和考生分数统计前N位考生，并直接录取。N位以后的考生不予录取。如果报考人数没有达到招生人数，则投递志愿的考生均被录取，剩余名额在第二轮继续招收

第二轮，进行第二志愿的投递，所有第一轮未被录取的考生的第二志愿投递到对应高校，如果高校招生人数已满，则该考生第二志愿仍被拒绝。如果人数未满会按照剩余人数结合报考考生的分数继续择优录取

以此类推，直至所有志愿都投递完后，若仍有考生未被高校录取，则该考生落榜。

顺序志愿录取机制弊端

将高考录取填报演变为一场寻找分数最优策略的博弈，导致考生忽视了个人理想对于报考决定的因素

假设有三个考生 (i1, i2, i3) 和两所学校 (c1, c2) , c0表示不上学。每个学校的招生名额qc=1, 考生的成绩和真实偏好如下:

假设考生都真实的按照偏好申报志愿，根据顺序志愿的录取机制

• 第一轮i1被c1录取，i2由于分数低于i1而被退录，i3则成功被c2录取
• 第二轮i2由于c2已经达到规定录取人数而被退录，虽然他的成绩优于i3
• 录取结束，i2落榜

最终录取结果：

可以看到最终结果是不公平的，i2分数高于i3并且也偏好c2，但却被退录。说明顺序志愿的高考录取机制是不公平的机制，会造成“高分低就”的情况发生

由于真实申报个人偏好有被退录的风险，这就给了i2申报虚假偏好的动机和理由，当其他人申报真实志愿时，i2操纵自己的志愿填报了”c2-c1-c0″,这时的录取结果就变成了

可以验证，这种志愿填报方式是一个纳什均衡

在这个简单的高考博弈中,所有的纯策略纳什均衡为志愿组合：

其中i3的志愿ci1-ci2-ci3是 (c1, c2, c0) 的一个任意排列。所有这些纳什均衡的结果都是

---

传统的顺序录取方式将高考录取志愿填报从一个考察学生偏好并进行选拔的过程变为了一场几十万人共同参与的博弈，如何避免这种情况，并能保证每个考生和高校之间实现最佳匹配。这就应用到了上文所谈到了Gale-Shapley算法。

典型的Gale-Shapley算法对应的被邀请人只能同时接收一名邀请人的暂时匹配请求，但对于高考录取问题，一个高校面对的是数百上千名考生，我们就需要重新定义整个算法流程，达到算法与录取过程的匹配，这就是Gale-Shapley学生最优机制。

Gale-Shapley学生最优机制

算法流程

第一轮，录取过程开始，学生志愿按照偏好顺序开始投递，各个学校在收到所有志愿后按照分数进行排序，如果人数未达到录取名额则全部暂时录取，如果超出录取名额N，则仅录取前N名考生，后续考生予以退录处理

第二轮，在第一轮中未被录取或被退录的考生继续按照偏好顺序投递志愿，高校在收到所有志愿后，与第一轮中暂时录取的考生合并共同排名，录取前N名考生，如果未达到N名，则全部录取

……

由于考生和高校都是有限的，所以志愿投递的过程也一定是有限的，当全部考生都被录取或落榜时，志愿投递结束。

Gale-Shapley算法优势：

• Gale-Shapley学生最优机制是抗操纵的
• Gale-Shapley学生最优机制帕累托优于任何公平机制。
• 在高考招生问题中,Gale-Shapley学生最优机制是唯一满足个人理性、公平、没有浪费和抗操纵的学生录取机制。
• 唯一的尊重学生考分进步, 并且满足个人理性,没有浪费和公平的学生录取机制是Gale-Shapley 学生最优机制。

分数公平系列独裁机制

• 先把所有考生按分数从高到低排序, 然后从高分到低分一次一个依次录取。
• 第一个考生从所有招生学校中, 选择他最偏好的学校, 被选学校的招生名额减少一个;
• 如果一个学校用完招生名额, 就停止招生;如果没有考生可接受的学校, 他选择不上学。
• 然后考虑下一个学生。一般来说, 第k个考生从在他选择时仍招生的所有学校中选择他最偏好的学校, 被选学校的招生名额相应地减少一个, 如果学校用完招生名额, 就停止招生;如果没有可接受的学校, 他选择不上学;然后考虑下一个学生。
• 这样一直下去, 直到所有的考生都被考虑或者所有的学校的招生名额用完, 招生停止, 剩下的考生落榜。

“平行院校志愿”机制就是我们上面描述的系列独裁机制。“平行院校志愿”机制也等价于Gale-Shapley学生最优机制。

代码实现：

学生类，表示所有投递志愿的考生

package Identity;
import edu.princeton.cs.algs4.Queue;

//学生类

public class Student implements Comparable<Student>{
    public char name;  //学生姓名
    public int[] favorNum;  //利用学校序号进行入队操作
    public Queue<School> favor;  //偏好队列
    public boolean status;  //录取状况，是否暂时被录取
    public School currentSchool;  //暂时录取院校
    public int score;  //考试分数
    public int numInGroup;  //在数组中序号

    //构造函数
    public Student(char name_in,int SchoolNum,int MyScore,int num){
        name=name_in;
        favorNum=new int[SchoolNum];
        favor= new Queue<>();
        status=false;
        currentSchool=null;
        score=MyScore;
        numInGroup=num;
    }
    //利用学校数组进行入队操作
    public void EntryQueue(School[] SchoolGroop){
        for (int favorSchool : favorNum) {
            favor.enqueue(SchoolGroop[favorSchool]);
        }
    }
    //用于被退录后进行状态的修改
    public void ChangeState(){
        status=false;
        currentSchool=null;
    }
    //获取暂时录取的院校名称
    public char SchoolName(){
        if(currentSchool!=null) return currentSchool.name;
        else{return ' ';}
    }

    //比较方法
    @Override
    public int compareTo(Student stu) {
        return Integer.compare(score, stu.score);
    }
}

高校类，表示接收志愿的高校

package Identity;

import edu.princeton.cs.algs4.Merge;

//学校类School

public class School implements Comparable<School> {
    public char name;  //学校名称
    public int Contains;  //学校预录取人数
    public int currentStuNum;  //当前录取人数
    public Student[] currentStus;  //当前预录取名单
    public int currentLowerScore;  //当前学校录取的最低分数

    //构造函数
    public School(char name_in,int contains){
        name=name_in;
        Contains=contains;
        currentStuNum=0;
        currentStus=new Student[contains];
        //初始化数组各项
        for(int i=0;i<Contains;i++){
            currentStus[i]=new Student((char)0,0,0,0);
        }
        currentLowerScore=0;
    }
    //获取当前录取最小的分数
    public int getCurrentLowerScore(){
        Merge.sort(currentStus);  //对当前名单内录取人员进行排序
        if(currentStuNum<Contains) return 0;  //未录满情况下返回0，表示只要申请的学生就能暂时录取
        else return currentStus[0].score;  //录满情况下数组第一位表示最小录取分数
    }
    //重载比方法
    @Override
    public int compareTo(School school) {
        if(name==school.name) return 0;
        else return -1;
    }
}

Gale-Shapley类，表示实现Gale-Shapley学生最优机制的类

import Identity.School;
import Identity.Student;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;

//盖尔沙普利算法

public class GaleShapleyStu {
    public Student[] StuGroup;  //所有学生组成的数组
    public School[] SchoolGroop;  //所有学校构成的数组

    //构造函数
    public GaleShapleyStu(In in1, In in2){
        CreateStuGroup(in1);
        CreateSchoolGroup(in2);
        InsertStuFavor();
    }


    //创建学生数组
    public void CreateStuGroup(In in){
        int StuNum=in.readInt();
        int SchoolNum=in.readInt();
        StuGroup=new Student[StuNum];

        for(int i=0;i<StuNum;i++){
            int StuName=in.readInt();
            int MyScore=in.readInt();
            Student stu=new Student((char) StuName,SchoolNum,MyScore,i);
            for(int j=0;j<SchoolNum;j++){
                int Num=in.readInt()-1;
                stu.favorNum[j]=Num;
            }
            StuGroup[i]=stu;
        }
    }

    //创建学校数组
    public void CreateSchoolGroup(In in){
        int stuNum=in.readInt();
        int SchoolNum=in.readInt();
        SchoolGroop=new School[SchoolNum];
        for(int i=0;i<SchoolNum;i++){
            int SchoolName=in.readInt();
            int Contains=in.readInt();
            SchoolGroop[i]=new School((char)SchoolName,Contains);
        }
    }

    //为每个学生写入偏好队列
    public void InsertStuFavor(){
        for(Student stu:StuGroup){
            stu.EntryQueue(SchoolGroop);
        }
    }



    //定义根据盖尔沙普利算法的申请方法
    public void Invitation(Student stu){
        School sch=stu.favor.dequeue();  //学生当前偏好度最高的院校
        sch.currentLowerScore=sch.getCurrentLowerScore();  //获取当前学院最低录取分数
        //未录满情况下
        if(sch.currentStuNum<sch.Contains){
            for(int i=0;i<sch.currentStus.length;i++){
                if(sch.currentStus[i].name==0){
                    //修改学校部分的数据

                    sch.currentStus[i]=(stu);
                    sch.currentLowerScore=sch.getCurrentLowerScore();
                    sch.currentStuNum++;
                    //修改学生部分的数据
                    StuGroup[stu.numInGroup].status=true;
                    StuGroup[stu.numInGroup].currentSchool=sch;
                    StdOut.printf("学生:%c(%d)被学校:%c暂时录取，学校剩余名额%d(%d)\n",stu.name,stu.score,sch.name,sch.Contains-sch.currentStuNum,sch.currentLowerScore);
                    return;
                }
            }
        }
        //院校录满情况下
        else {
            //分数低于当前最低录取分数的情况下直接被拒绝
            if(stu.score<sch.currentLowerScore){
                StdOut.printf("学生:%c(%d)被学校:%c拒绝，学校剩余名额%d(%d)\n",stu.name,stu.score,sch.name,sch.Contains-sch.currentStuNum,sch.currentLowerScore);
            }
            //分数高于当前最低录取分数，可以暂时录取
            else{
                //删除录取名单中分数最低的学生，并修改这名学生状态
                Student leastStu=sch.currentStus[0];

                StuGroup[leastStu.numInGroup].ChangeState();
                //修改学校部分数据
                sch.currentStus[0]=(stu);
                sch.currentLowerScore=sch.getCurrentLowerScore();
                //修改学生部分数据
                StuGroup[stu.numInGroup].status=true;
                StuGroup[stu.numInGroup].currentSchool=sch;
                StdOut.printf("学生:%c(%d)被学校:%c暂时录取，学生:%c(%d)被退录，学校剩余名额%d(%d)\n",stu.name,stu.score,sch.name,leastStu.name,leastStu.score,sch.Contains-sch.currentStuNum,sch.currentLowerScore);
            }
        }
    }



    public static void main(String[] args) {

        GaleShapleyStu GS=new GaleShapleyStu(new In(args[0]),new In(args[1]));

        //初始化num=1
        int num=0;
        //开始循环进行申请
        while(num!=GS.StuGroup.length){
            StdOut.printf("-------------------------------------------\n开始一轮邀请\n-------------------------------------------\n");
            num=0;  //将num设为0

            for(Student stu:GS.StuGroup){
                //有暂时录取学校或者出局不再进行本轮循环
                if(stu.favor.isEmpty()||stu.currentSchool!=null){
                    num++;
                }
                //进行循环
                else {
                    GS.Invitation(stu);
                }
            }
        }
        for(Student stu:GS.StuGroup){
            StdOut.printf("Stu:%c(%d) --> School:%c\n",stu.name,stu.score,stu.SchoolName());
        }

    }

}