讲完婚姻市场之后，我们接下来讲Matching Theory的另一个重要应用，就是College Admission，择校问题。
择校问题的市场上还是有两边，一边是学生，一边是学校，不同于婚姻市场，学生仍然只能选择一所学校，学校却可以选择多于一个学生，这是一个一对多双边市场。
实际上，像择校问题这样一对多的市场，是比婚姻市场这样一对一的市场更加普遍的一种情况，可以认为后者就是前者的一个特例；Gale和Shapley第一篇关于DA算法的论文讨论的两个例子，就是择校问题和婚姻市场。
一、一对多双边市场
实际上，只需将在一对一双边市场上的延迟接受算法稍作修改，就能够得到一对多双边市场上的延迟接受算法，这些修改大致包括如下几项：
(1)在婚姻市场上，男生对于所有女生进行排序，女生对于所有男生进行排序，这是非常直观的；在学校招生时，学生只能去一所学校，所以学生对于学校的排序也是很容易理解的；但是，学校对于学生的排序就有两种不同的情况：一种是，学生与学生之间是相互独立的，学校对于单个的学生建立偏好（也称为responsive或者separable preference）；另一种是，学生与学生之间是有关联的，学校招生的时候对于学生的组合建立偏好。（严格地说，前者是后者的一种特例，对于responsive preference，同样可以把这个偏好写成学生的组合上的偏好）
举例来说，如果一共有3个学生1,2,3，那么前一种情况就是，学校觉得1比2好，2比3好，或是3比2好，2比1好，这是建立在“单个的学生”上的偏好；另一种情况是，学校觉得同时招1和2最好，其次是1和2和3，再次是2和3，再次是1和2，等等，这是建立在“学生的组合”上的偏好。后一种情况在什么时候会发生呢？举个例子，T大每年都要参加帝都高校长绳比赛，长绳需要12名队员，选拔长绳队员的时候，并不是从各个院队里一个一个选拔出来（“单个的学生”的偏好），而是选拔了最好的一个院队（“学生的组合”的偏好），因为这些学生已经经过长期的磨合和练习，把他们组合在一起将会有协同效应，换上别的院跳得好的同学，反而有可能拖后腿。
后一种情况，正如上一讲所说的，存在反例说明可能并不存在稳定匹配。然而，对于前一种情况，稳定匹配总是存在的，原因在下面进一步阐述。
(2)引入配额(quota)的概念，即学校的招生名额，这是很自然的，一个学校能够招收的学生数量总是有限的。
(3)由于配额的存在，对于稳定匹配的要求也发生了变化：
IR: 学生不会选择unacceptable的学校，学校不会选择unacceptable的学生；
Pairwise Stability: 不存在如下情况：
(i) 学校S有空位，且学生s对于学校S是acceptable的，且对于学生s来说，学校S比目前的情况（没有学上或是被另一学校S’录取）更好；
(ii) 学校S没有空位，但在录取的学生中有一名学生s’，对于学校S来说，学生s比学生s’更好，且对于学生s来说，学校S比目前的情况更好。
回到上面这个问题，为什么当学校对于学生的偏好是建立在“单个的学生”上时稳定匹配总是存在的呢？在一对一双边市场上，稳定匹配的存在性是由DA算法构造出来的，因为构造出来的这个匹配是稳定的，所以稳定匹配存在。而对于一对多双边市场，我们不需要再按照证明一对一双边市场上那样完全走一遍，实际上，当学校的偏好建立在“单个的学生”上时，我们完全可以这样做：
学校A有三个名额，那么我就把学校A拆成学校A1、A2、A3，分别只有一个名额，它们对于学生的偏好和学校A是一样的，而学生认为学校A1、A2和A3是一样好的；对其它学校也是一样处理。DA算法并不要求偏好是严格(strict)的（这个要求对于稳定匹配的存在性或者说DA算法并没有影响，只影响了最后的稳定匹配是否构成Lattice），这样一拆，相当于构造了一个一对一双边市场，新市场上的稳定匹配存在（由DA算法给出），则原市场上的稳定匹配只需要将A1、A2、A3重新合并回学校A即可。
二、单边市场
实际上，对于学校招生，还有另外一种模型，即单边市场模型。在单边市场中其实还是存在两边，但是一边是人，另一边是物品(object)，由于我们只关注人的行为，而被分配的物品是没有“行为”的，所以称为“单边”。
最基本的单边市场是房屋市场，每个人对于房屋都有自己的偏好，房屋自己不会挑人，随便谁住都可以；但是，当我们考虑学校招生这样一个单边市场模型时，学校对于学生肯定不是随便挑的，每个学校也会有自己的“偏好”，但是这个“偏好”不是通常意义上的preference，而被称为priority，两者在形式上是一致的，但是内涵大不相同。
不同于人的偏好是自己决定的，学校的priority是受到限制的，一般来说，首先由政府制定一系列的规则，然后根据这套规则，每个学校就自动产生一套priority。举个栗子，政府规定，学校优先招纳距离学校近的学生，在距离差不多的情况下，招纳学分绩更高的学生，在学分绩也相同的情况下，优先招纳女生，这样一来政府完全可以不需要学校参与决定priority，在这个priority中也完全没有体现出学校自己的意愿，相应地，当我们考虑此时市场的效率(efficiency)时，我们就不需要将priority考虑进来，而只考虑学生这边是否进入自己心仪的学校。
由于priority取代了学校的preference，对于稳定匹配的第二条要求就有了一个新的名词，叫作respecting priority，基本上等价于双边市场中的pairwise stability。
三、波士顿机制(BostonMechanism)
在DA算法之前，有一个模型在美国学校招生中非常流行，这个模型称为波士顿机制(Boston Mechanism)，因为其最先在波士顿试水并推广而得名。如果没有猜错的话，纽约在2003年之前使用的就是BM或者BM的变种，因为相关报道中有两句话非常符合BM的实际情况：
“所以有些目标高远、填报了多家热门学校的学生，一旦被写在第一栏的学校拒收，就会在选校表中一落千丈。”
（这是BM机制中常有的，参见下面的例子中的学生6）
“家长们担心如果选错了，他们的孩子会‘浪费’至关重要的首选位置。”
（这句话虽然写在新机制DA运作之后，但表达的是BM的流毒，即浪费首选位置的想法，同样参见下面的例子中的学生6）
首先来简要介绍一下什么是BM，从流程上来说，它类似于由学生主动向学校“求婚”的DA算法，但差了这么一句话：
在BM中，如果学生s被学校S录取，那么之后不会被替换掉；而在DA算法中，如果后面出现更好的学生，学校S会踢掉学生s。
简单地说，DA对于BM最重要也是最神奇的改进只在于：允许“见异思迁”。
咱们先中途下课，下次课的时候，我们将继续介绍波士顿机制的性质，以及它和我们的老朋友延迟接受算法之间的种种爱恨（划掉）纠葛。
（2015.05.29 @ 微信公众号 @ 《第二讲：College Admission 择校问题（上）》）
