让大家久等啦，今天我们接着讲择校机制~
四、波士顿机制的性质
对于每一种机制的考量主要分为三个方面，效率(efficiency)，稳定性(stability)，和是否存在使学生谎报偏好的激励(strategy-proofness)。
所谓效率，就是学生是否得到了可能获得的最好的学校。在DA算法中，我们证明了，如果由学生主动“求婚”，能够得到最好的学校，但这里的“最好”指的是在所有稳定匹配中最好的学校。如果我们考虑不稳定匹配，实际上可能存在帕累托更优的不稳定匹配，每个学生至少和在最好的稳定匹配中的处境一样好，且至少有一个人匹配到了比稳定匹配中更喜欢的学校，而这正是BM的情况。实际上，BM给出了一个帕累托最优，但是不一定稳定的匹配。
考虑下面这样一个例子，有六个学生16，四个学校ad，学校ab各有两个招生名额，cd各有一个招生名额。
学生对于学校的偏好是
R1:a 后略
R2:a 后略
R3:a b 后略
R4:c 后略
R5:c a b d 后略
R6:c a b d 后略
学校对于学生的priority是
a: 6 1 2 3 后略
b: 5 6 3 后略
c: 4 5 6 后略
d: 5 6 后略
根据BM，得到的匹配是
a: 1和2
b: 3和5
c: 4
d: 6
匹配的最优性是显而易见的，因为每一轮BM都把每个学生匹配到了当前最好的学校，对于任何一个学生来说，他比BM所匹配的学校更喜欢的那些学校在任何匹配中都不可能招收他。而这个匹配的不稳定性在上面这个例子也展现出来了，学校a喜欢学生6胜过学生1和学生2，而学生6喜欢学校a胜过学校d，说明上面的这个匹配不是稳定匹配。
观察一下学生6的偏好，可以发现他在第一轮选择了自己最喜欢但是却并不是那么喜欢自己的学校c，这是一个严重的失误，因为同时本来最喜欢他的学校a已经招满了学生，即使他试图在第二轮挽回（选择了学校a），仍然一再错失机会，最后只得到了排在最后的学校d；这就是“一旦拒收，一落千丈”和“浪费首选位置”的真实体现。
在这里，又不得不提到最后一个考量标准，即strategy-proofness。在单边市场中，学校的priority是不能更改的，但学生仍然可以不按照自己真实的意愿来报告自己对学校的偏好。当学生面对BM时，确实存在谎报偏好使得自己能够进入更好学校的可能，仍以上面这个例子为例，如果学生6意识到自己可能被学校c拒绝并最终不得不进入学校d，那么他完全可以谎报自己喜欢a胜过喜欢c，这样在第一轮他就把学生2挤走，成功进入了学校a，尽管他没能进入最想进入的学校c，但是仍然比进入学校d要更好。
综上所述，BM虽然能够给出帕累托优的匹配，但是这个匹配是不稳定的，而且学生有谎报自己偏好以进入更好学校的可能。
五、BM与DA的联系
不过拍脑袋一想，不对啊，既然你可以改自己的志愿，我也可以改嘛。因此，在BM真正开始分配之前，也就是学生们填报志愿的时候，就已经开始了一场没有硝烟的战争，学生们都会调整自己的志愿，使得自己能够上到更符合自己偏好的学校，这就构成了一场新的博弈。在这场博弈中，每个学生都是参与者，他们的策略就是不同的志愿填报顺序，最终的结果(outcome)就是根据每个人填报的志愿进行BM分配所得到的学校，相应的支付(payoff)就是是否获得自己更偏好的学校。
在这个博弈中，存在一系列的纳什均衡，而神奇的是，这些纳什均衡的结果恰好就是所有的稳定匹配，这个命题的证明可以在这里稍微表述一下：
首先要证明所有的纳什均衡结果都是稳定匹配，这是显然的，如果存在纳什均衡的结果是不稳定匹配，那么也就意味着有学校S想要学生s来踢掉别人或者填补空位，学生s也想要学校S而非现在匹配的学校，那么学生s只需要把学校S提到自己志愿的第一位就可以了；换句话说，学生s有进一步改变自己志愿的激励，不满足纳什均衡的要求。
其次要证明所有的稳定匹配都是纳什均衡的结果，这就更显然了，只要每个人都把自己在这个稳定匹配中匹配到的学校填在第一位，第一轮百分之百全部录取；任何人单方面的背离都不能使他更好，因为其他人把所有别的坑都填满了，他要么最后还是回去填了自己的坑，要么就没学上。
根据集合的性质，如果集合A和集合B互相包含，那么这两个集合相等，因此所有的纳什均衡结果就是所有的稳定匹配。
这告诉我们什么呢？如果将学生在BM下选择不同的志愿视为一场博弈的话，非常神奇的是，这个博弈的所有纳什均衡结果恰好是所有稳定匹配，而我们又知道，在所有稳定匹配中，学生的最优解可以由学生主动“求婚”的DA算法来得出，因此，一切又回归到DA算法，将学校招生视为双边市场，考虑学生主动“求婚”的DA算法，得到的解满足stable（稳定），student-optimal（在所有稳定匹配中对于学生来说最优）以及strategy-proof（学生没有激励去伪造自己的真实意愿，可以证明，此处略去）。
顺便说句题外话，其实在某种特殊的情况下，BM和DA一定会给出同样的结果，那就是如果所有学生对于学校的排序都是一样的，同时学校对于所有学生的排序都是一样的，这时候最好的学校招最好的学生，差一点的学校招差一点的学生，最差的学校招最差的学生，依此类推。我们常常诟病的“一考定终生”就是这样的情况，学校对于学生只有单一的衡量标准，也就是分数，如果学生对于学校本来就划分了三六九等，恰好就满足了这样的条件。当然，这种条件的出现是比较少见的，像目前中国的高考算是比较接近的例子，但高考的录取机制又不完全是BM或者DA，这个就留到下一讲吧。
（2015.06.02 @ 微信公众号 @ 《第二讲：College Admission 择校问题（下）》）
