保研录取的双边匹配问题

保研夏令营是典型的双边匹配问题，学生与导师都在互相选择以至存在博弈关系，我们将保研过程抽象为这样一个初始模型：一个大学正在对n个提出申请的学生进行考核，招生的名额是q。在评估申请学生的资格之后，招生处得决定招收哪些学生。如果仅仅录取q个最具资格的学生，可能达不到令人满意的结果，因为收到录取通知的q个学生不一定都会接受录取。因此，为了使大学能够招收到q个学生，一般来说，发出的录取通知需要超过q个。解决招收多少学生以及招收哪些学生的问题，需要加入一些猜想。

我们可能并不知道，一个收到录取通知的学生是否还申请了别的学校；即使知道了这一点，也无法搞清楚这个学生对自己申请的学校怎样排名，就算知道了，也难以知道其他哪些学校会愿意招收这个学生。基于种种不确定因素，学校只能期望招进的学生人数和理想的人数接近，并且学生质量能接近可达到的最优值。

有个精心设计的方案是引入“候补申请人”名单，意思就是申请者在得知自己没有被录取的同时，也被告知当有空缺存在时可能会被录取。但是，这会导致新的问题。假设一个学生被一所大学录取，与此同时，他又被列在另一所自己更心仪的大学的“候补申请人”名单上，他是应该保险起见，接受第一个大学的录取，还是冒险一试，寄希望于自己更喜欢的学校呢？如果接受了第一个学校的录取，不告知第二个学校，等第二个学校愿意录取自己时再拒绝第一个学校，这样做道德吗？

如何建立一个有效的分配规则呢？假设，n个申请者将被分配到m个学校，而q是第i个学校的招生名额。每个学生剔除那些在任何情况下都不愿意去的学校，按照自己的偏好对剩下的学校进行一个排名。方便起见，假设学生和学校之间没有关系，那么，即使对于一个学生来说，某两所学校或者多所学校之间没有什么差别，他还是要按照某一顺序给学校做出排名。每个学校同样按照自己的偏好，给申请者排名，首先排除那些在任何情况下（即使这意味着招生名额不满）都不愿意接收的学生。通过学校的录取名额、学生和学校各自的排列名单，我们希望能够找到某种达成统一意见的公平规则，将申请者分配到学校。

举一个简单的案例，假设有两个学校A和B，两个申请者a和b。a更喜欢A学校，b更喜欢B学校，遗憾的是，A学校更喜欢b申请者，B学校更喜欢a申请者。这种情况下，没有能使各方都满意的分配方案。遇到这种情况，我们又必须做出决定。哲学上，学校是为学生而存在的，而不是反过来。将a申请者分配到A学校，b申请者分配到B学校这种做法可能是合适的。这也暗示了一个受到承认的大致规则：当其他因素一样时，比起学校，学生应该被优先考虑。这个规则本身来讲没有什么作用，不过我们讲述完另一个更为明确的事情之后，再回过头来说。

定义1：如果有两个申请者a和b，分别被分配到A学校和B学校，但是b更偏好A学校，而a更偏好B学校，那么，这种分配被定义为“不稳定”。

假定，刚提到的这种情况真的发生了。申请者b可以向A学校表明态度说，自己愿意转到A学校，A学校可以许诺招收申请者b，同时，让a学生转校，来维持总招收的人数在招生名额之内。A学校和b学生会考虑这么做，让分配更利于各自。如此一来，原来的分配就“不稳定”了，这种分配可能会被学校和申请者联合推翻，以达到一种对两者都更有好处的分配。

定义2：如果每个申请者对当前的稳定分配方案的满意度，至少跟对其他稳定分配方案的满意度一样，那么这种稳定分配可被称作“最优”。

稳定分配的存在，远不能说明最优分配就存在，不过，有一点很清楚，最优分配是独一无二的（假使它存在）。如果有两个最优分配，那么，至少有一个申请者，会在其中一种分配方案里，感觉比另一个分配方案里更好，因而这两个所谓最优的分配方案中，有一个说到底就不是最优的了。当我们不考虑存在与否这个问题，稳定性和最优的规则，能引导我们找到一个独特的“最好”的分配方案

如果有一种稳定分配把某个学生分配到某个学校，我们就把这个学校称作对这个学生而言是“可能的”。这个证据要运用归纳法。假设，到程序中的某一个节点为止，没有申请学生被“可能的”学校拒绝。在这个节点上，假定学校A接到了满足招生名额的q个更具资格的申请者，因而拒绝了申请者α。我们必须表明学校A对于申请者α而言，是“不可能”的。我们现在知道在A学校候补名单上的q个申请者，都喜欢A学校胜过其他学校，除了那些之前拒绝过他们因而对他们而言“不可能”（假设）的学校。

将“延迟接受”的程序延伸到保研夏令营入营问题，延迟接受是指合意的邀约不会立即被接受，而只是暂时保留不被拒绝，延迟接受算法可以从一对一双边市场（婚姻市场）拓展到一对多双边市场（学校招生），新的一对多时常等价于将学校拆分成入学名额给各个学校，学生对于这些拆分后的“学校”是偏好相同的一对一市场，我们假定如果一个学校在任何情况下都不会招收某个学生，这个学生甚至不被允许申请这个学校。

在这个前提下，我们来理解下面的程序：首先，所有的学生都向自己的首选学校提出申请。一个有q个招生名额的学校，将排在前面的q个学生放进自己的候补名单，而拒绝其他申请者。如果给这个学校提出申请的学生人数不满q人，这个学校将所有申请者都列入候补名单。被这个学校拒绝的申请者，向自己的第二选择学校提出申请，再次，每个学校都从新的申请者和自己的候补名单中选出q个申请者，将这些学生建立一个新的候补名单，同样，拒绝掉其他申请者。当每个申请者要么在某个候补名单上，要么被所有自己愿意去又被允许申请的学校拒绝时，这个程序就结束了。最后，学生已经按照真实的偏好顺序来排列学校，每个学校都接受各自候补名单上的所有申请者，稳定分配也就达成了。

所谓的稳定分配其实就是最终形成录取名单的状态，也可以说是一种帕累托最优状态，如果延迟接受算法没有给学生分配到某所更好的学校，绝不是算法故意让你去不成，而恰恰说明在所有的稳定分配中，都不存在让你去这所学校的可能性，无论你如何去调整自己的志愿，最终的均衡结果中同样没有让你去这所学校的可能，这样带来的失望是没有意义的，譬如你的各方面资格和能力都比较低，然而却希望通过保研进入清华北大一样，即使进不了，也怪不得高校与录取机制，只需要自己保持努力并提升自己。

上面的双边匹配理论是沙普利采用合作博弈理论和比较不同匹配的方法进行研究，确保配置的稳定性，并在匹配过程中限制变量的影响，从而保证匹配的双方不会被对方干扰，整理并调整适合的简单的核心内容供大家学习or博君一笑；整体来说，保研夏令营在原则上不存在投机取巧的成分，但是由于目前的入营资格考核仅在于提交材料，存在一定程度的信息不对成，我们可以在真实与真诚的前提下适当包装自己，毕竟理论只是理想化的假设及证明，现实世界是多个维度的相互碰撞，先将夏令营机会拿到手中仅是我们走出的第一步，没走出这一步之前，这一步非常重要且艰难；走出这一步以后，这一步就不再重要，我们还有更重要且更紧急的事要做！

参考文献：

[1]D. Gale & L. S. Shapley(1962)College Admissions and the Stability of Marriage,The American Mathematical Monthly

[2]Aaron L. Bodoh-Creed. 2020. Optimizing for Distributional Goals in School Choice Problems.Management Science.

[3]. Jay Sethuraman, Chung-Piaw Teo, Liwen Qian. 2006. Many-to-One Stable Matching: Geometry andFairness.Mathematics of Operations Research