大学招生与婚姻稳定性

1、大学招生与婚姻的稳定性 大卫·盖尔、罗伊德·S.沙普利 发表于2012-10-23 01:06从开始的大学入学问题，到最后讨论婚姻配对问题，我们都抛弃了现实，进入了一个理想化的数学世界。 从开始的大学入学问题，到最后讨论婚姻配对问题，我们都抛弃了现实，进入了一个理想化的数学世界。务实的读者大概会马上问，我们有没有做一些努力，来解决现实中的问题。虽然，要回答这个问题，需要考虑许多非数学的因素，而且这种讨论在数学期刊上似乎不太适宜，我们的观点是，我们在这里介绍的观点，可能会被利用于解决某个阶段的入学问题。我们研究的问题和下面这种典型情况有关：一个大学正在对n个提出申请的学生进行

2、考核，招生的名额是q。在评估申请学生的资格之后，招生处得决定招收哪些学生。如果仅仅录取q个最具资格的学生，可能达不到令人满意的结果，因为收到录取通知的q个学生不一定都会接受录取。因此，为了使大学能够招收到q个学生，一般来说，发出的录取通知需要超过q个。解决招收多少学生以及招收哪些学生的问题，需要加入一些猜想。我们可能并不知道，一个收到录取通知的学生是否还申请了别的学校；即使知道了这一点，也无法搞清楚这个学生对自己申请的学校怎样排名，就算知道了，也难以知道其他哪些学校会愿意招收这个学生。基于种种不确定因素，学校只能期望招进的学生人数和理想的人数接近，并且学生质量能接近可达到的最优值。通常的招生程

3、序给申请的学生和学校都带来一些困扰。被要求在申请表格中按偏好列出学校排列的学生，可能会觉得如果让一个学校知道它只是自己的第三选择，会降低自己被这个学校录取的可能性。有个精心设计的方案是引入“候补申请人”名单，意思就是申请者在得知自己没有被录取的同时，也被告知当有空缺存在时可能会被录取。但是，这会导致新的问题。假设一个学生被一所大学录取，与此同时，他又被列在另一所自己更心仪的大学的“候补申请人”名单上，他是应该保险起见，接受第一个大学的录取，还是冒险一试，寄希望于自己更喜欢的学校呢？如果接受了第一个学校的录取，不告知第二个学校，等第二个学校愿意录取自己时再拒绝第一个学校，这样做道德吗？上面列出的

4、问题其实都可以避免，我们将描绘一种能令学校和学生两方都满意的分配申请者的程序，这种程序可以清除一切不确定性，并且，假定有足够的申请者，这个程序可以让每个学校分配到和给定招生名额一致的学生。分配规则假设，n个申请者将被分配到m个学校，而q是第i个学校的招生名额。每个学生剔除那些在任何情况下都不愿意去的学校，按照自己的偏好对剩下的学校进行一个排名。方便起见，假设学生和学校之间没有关系，那么，即使对于一个学生来说，某两所学校或者多所学校之间没有什么差别，他还是要按照某一顺序给学校做出排名。每个学校同样按照自己的偏好，给申请者排名，首先排除那些在任何情况下（即使这意味着招生名额不满）都不愿意接收的学生

5、。通过学校的录取名额、学生和学校各自的排列名单，我们希望能够找到某种达成统一意见的公平规则，将申请者分配到学校。照刚才的思路，简单地看，解决方案很容易浮出水面。不过，很少有人将分配和偏好联系在一起，一旦考虑这点，复杂性就增加了。举一个简单的案例，假设有两个学校A和B，两个申请者a和b。a更喜欢A学校，b更喜欢B学校，遗憾的是，A学校更喜欢b申请者，B学校更喜欢a申请者。这种情况下，没有能使各方都满意的分配方案。遇到这种情况，我们又必须做出决定。哲学上，学校是为学生而存在的，而不是反过来。将a申请者分配到A学校，b申请者分配到B学校这种做法可能是合适的。这也暗示了一个受到承认的大致规则：当其他因

6、素一样时，比起学校，学生应该被优先考虑。这个规则本身来讲没有什么作用，不过我们讲述完另一个更为明确的事情之后，再回过头来说。我们接下来要阐述的核心观点就是，无论最终是决定使用哪种分配方案，下面这个定义描述的情况，很有可能不发生。定义：如果有两个申请者a和b，分别被分配到A学校和B学校，但是b更偏好A学校，而a更偏好B学校，那么，这种分配被定义为“不稳定”。假定，刚提到的这种情况真的发生了。申请者b可以向A学校表明态度说，自己愿意转到A学校，A学校可以许诺招收申请者b，同时，让a学生转校，来维持总招收的人数在招生名额之内。A学校和b学生会考虑这么做，让分配更利于各自。如此一来，原来的分配就“不稳

7、定”了，这种分配可能会被学校和申请者联合推翻，以达到一种对两者都更有好处的分配。我们对一个分配方法的首个要求，是不会表现出不稳定。这立马就引出一个数学问题：是否总有可能找到一个这样的分配方案？下面我们会给出一个肯定的答案，虽然说，找到佐证的例子并不困难，不过，如有些例子所暗示的，结果看似不那么明显。假定稳定分配方案暂时存在，我们仍必须决定在诸多可能的稳定方案中，更倾向于哪种。现在，说回到刚刚我们提到的哲学原则，并给它一个确切的表达方式。定义：如果每个申请者对当前的稳定分配方案的满意度，至少跟对其他稳定分配方案的满意度一样，那么这种稳定分配可被称作“最优”。稳定分配的存在，远不能说明最优分配就存

8、在，不过，有一点很清楚，最优分配是独一无二的（假使它存在）。如果有两个最优分配，那么，至少有一个申请者，会在其中一种分配方案里，感觉比另一个分配方案里更好，因而这两个所谓最优的分配方案中，有一个说到底就不是最优的了。当我们不考虑存在与否这个问题，稳定性和最优的规则，能引导我们找到一个独特的“最好”的分配方案。稳定分配和婚姻问题在试图解决稳定分配的存在问题的过程中，我们首先想研究一个特别的案例，在这个案例中，申请者和学校的数量一致，而且每个学校的招生名额也统一。当然，这种情况，于实际的学校招生情况来说，是反常的。但是，有另一个“故事”，就可以很符合我们的设想条件。某一个社区由n个男子和n个女子组

9、成，每个人按照婚姻伴侣的标准，根据自己的偏好，给异性做出排序。我们试图找到一个令人满意的方式，能让社区里的男子和女子都找到伴侣。模拟之前我们给“不稳定分配”定义，如果在某种分配方案里，一个女子和一个男子没有结婚，但是，对彼此的喜好超过对他们各自的实际伴侣，那么，我们可以说，这种婚姻“不稳定”（这个术语在此很清晰）。问题：对于各种模式的偏好，是否可能找到一种稳定的婚姻配对？在给出答案之前，我们先看一些例子。这个矩阵的每对数字中，第一个数字表示男子对女子的排列，第二个字数表示女子对男子的排列。在这个排列矩阵中，可以发现，男子将女子A排在第一，女子B在第二，女子C在第三，而女子A将男子作为首选，作为

10、第二选择，作为第三选择等等。这个例子里，有6种可能的婚姻配对，其中，有3种配对是稳定的。其中一种达到稳定配对的方法，是让每个男子能娶到自己的最心仪对象，也就是说，男子娶女子A，男子娶女子B，男子娶女子C。你也许注意到，每个女子只能嫁给自己的第三选择，然而这种安排是稳定的配对。另一种稳定配对可能是让每个女子嫁给自己最心仪的对象，让C女子嫁给男子，A女子嫁给男子，B嫁给男子。第三种稳定配对的方案则是，让每个人和自己的第二选择结婚，让男子和B女子结婚，男子和C女子结婚，男子和A女子结婚。读者们会很容易证明其他种配对都是不稳定的。这个矩阵中画了圈的项，显示只有一种稳定的婚姻配对。注意在这种情况下，如果

11、想达到稳定性，每个人都不能够和自己的最心仪对象结婚。 例3和婚姻配对问题类似的一个问题是“室友分配问题”。比如，有偶数个男孩要被分配成一对对室友。如果分配之后，没有男孩找不到室友，并且也不会存在一个男孩比起和现有室友一起住，更愿意和别的男孩一起住的情况，那么，这种分配可以说是“稳定的”。举一个简单的例子就可以显示，存在着多种配对不稳定的情况。我们把男孩们简称为、,假设这个例子里，把列在第一位，把列在第一位，把列在第一位，而、都把排在末位。不考虑的偏好，没办法安排稳定的配对，因为，被安排跟一个宿舍的那个男孩会想要搬出去，而其他两个男孩中的一个男孩，会愿意接纳这个搬出的男孩搬进自己的宿舍。上面提到

12、的这些例子都说明，要找到解决稳定配对的方案不那么容易，不过，可以得出两个定理。定理一，总存在稳定的婚姻配对。证据。我们将通过递次求近法证明稳定婚姻配对的存在，找到一个稳定的婚姻配对。首先，让每个男子向自己最喜欢的女子求婚，每个收到不止一个求婚的女子，可以从求婚者中选出自己最喜欢的一个，并且拒绝其他求婚者。但是，这个女子并不立刻接受当下最喜欢的求婚者的求婚，而是将他作为保留人选，给下一轮求婚者中更好的人选机会。然后，进入第二个阶段，在第一轮求婚中被拒绝的男子，可以向自己的第二选择求婚。收到求婚的女子，从新的求婚者和保留的求婚者中，选出自己最喜欢的求婚者，同样，再次拒绝其他求婚者，只保留自己最喜欢

13、的求婚者。接下来，以同样的方式继续。在第二阶段被拒绝的求婚者，向自己的次一个选择求婚，女子仍然只从保留的求婚者和新的求婚者中选出最喜欢的人，拒绝掉其他人。最终（实际上，最多经过n2-2n+2个阶段），每个女子都会收到一个求婚，因为只要有一个女子还没有被求婚，就存在拒绝和新一轮求婚，不过，因为没有男子能够对同一个女子提出超出一次求婚，每个女子总会在适当的时候得到一个求婚。当每个女子都收到求婚时，“求婚”行动就结束了。这时，每个女子都要接受自己保留的那个求婚者。我们相信这种婚姻配对是稳定的。比如，约翰和玛丽没有能结婚，而约翰喜欢玛丽胜过自己的妻子。那么，约翰肯定在过去某个时刻向玛丽求过婚，而玛丽当

14、时因为更喜欢别人拒绝了约翰。很明显，玛丽肯定喜欢自己的丈夫胜过约翰。也就不存在婚姻的不稳定。读者可能自娱自乐一下，把这个例证的程序应用到解决例1和例2上。稳定配对，也不一定非得要求有一样数量的男子和女子。假设有b个男子，g个女子，如果bg，当每个男子要么被某个女子作为了保留人选，要么被所有女子拒绝了的时候，这个过程结束。这两种情况下的婚姻配对都是稳定的。显然，存在一个完全对称的程序，即如果女子向男子求婚，也会达成稳定的婚姻配对。然而，如果男子求婚，配对的结果对男子来说最好，如果女子求婚，配对的结果会对女子来说最好。只有当存在唯一的稳定婚姻配对时，两种程序的分配结果才会一样。稳定分配和入学问题将

15、“延迟接受”的程序延伸到大学入学问题。方便起见，假定如果一个学校在任何情况下都不愿意招收某个学生，这个学生甚至不被允许申请这个学校。在这个前提下，我们来理解下面的程序：首先，所有的学生都向自己的首选学校提出申请。一个有q个招生名额的学校，将排在前面的q个学生放进自己的候补名单，而拒绝其他申请者。如果给这个学校提出申请的学生人数不满q人，这个学校将所有申请者都列入候补名单。被这个学校拒绝的申请者，向自己的第二选择学校提出申请，再次，每个学校都从新的申请者和自己的候补名单中选出q个申请者，将这些学生建立一个新的候补名单，同样，拒绝掉其他申请者。当每个申请者要么在某个候补名单上，要么被所有自己愿意去

16、又被允许申请的学校拒绝时，这个程序就结束了。这个时候，每个学校都接受各自候补名单上的所有申请者，稳定分配也就达成了。证实这种分配是稳定的，类似于证明根据这种方法进行的婚姻配对是稳定的，就留待读者自己验证吧。最优解现在，我们要说明，刚提到的“延迟接受”程序不仅可以让申请分配达到稳定，而且可以达到最优。也即定理二.每个申请者，至少觉得，经由延迟接受程序安排的分配带来的好处，跟其他稳定分配一样。证据。如果有一种稳定分配把某个学生分配到某个学校，我们就把这个学校称作对这个学生而言是“可能的”。这个证据要运用归纳法。假设，到程序中的某一个节点为止，没有申请学生被“可能的”学校拒绝。在这个节点上，假定学校

17、A接到了满足招生名额的q个更具资格的申请者，因而拒绝了申请者。我们必须表明学校A对于申请者而言，是“不可能”的。我们现在知道在A学校候补名单上的q个申请者，都喜欢A学校胜过其他学校，除了那些之前拒绝过他们因而对他们而言“不可能”（假设）的学校。设想一个分配方案，把申请者送到A学校，把A学校候补名单上的申请者中的某一个送到其他可能接受他的学校。这样的话， 就要去到另一个他觉得不如A学校的学校。这种分配是不稳定的，因为A学校很可能颠覆这种安排，换一种更利于双方的安排。所以说，这种设想的分配方案不稳定，A学校对于申请者而言，是“不可能”的。就此得出的结论是，我们的程序里，学校只是拒绝那些在任何稳定分

18、配方案中都不会被录取的学生，因而，我们程序所得出的分配结果是最佳的。我们顺带也注意到，尽管在这个案例里面，不会遇到婚姻配对时的对称问题。然而，也可以反转入学模式，来达到唯一的“入学最优”分配。这种反转的方法有点像联谊会的“高峰周”，首先，每个学校竞标自己最中意的那些学生，一直到自己的招生名额满了，然后，被竞标的学生保留最具吸引力的学校，拒绝掉其他学校，等等。结论阅读至此的读者无疑会注意到我们讨论的特点。为了对我们的问题进行数学分析，我们进行了所需的特定假设，从开始的大学入学问题，到最后讨论婚姻配对问题，我们都抛弃了现实，进入了一个理想化的数学世界。务实的读者大概会马上问，我们有没有做一些努力，来解决现实中的问题。虽然，要回答这个问题，需要考虑许多非数学的因素，而且这种讨论在数学期刊上似乎不太适宜，我们的观点是，我们在这里介绍的观点，可能会被利用于解决某个阶段的入学问题。最后，我们注意一下前文分析的另一个方面，这可能对数学老师而言比较有趣。那就是，在我们的论述里，有大把的例子来反驳非数学家对数学的