之前我们讨论的一直是学生可以操纵最后的结果，但实际上学校也仍然有一定的自主权，虽然priority是由政府决定的，但是学校可以假装自己没有那么多位置，反而能获得更好的学生。肯定会有同学表示：这怎么可能呢？多了一个位置，就好比是扩大了你的决策集，应该总是better off的呀？但是请注意，现在我们面临的机制设计问题，本质上还是博弈论问题，这是一个动态的决策，很多时候减少自己的选择是能够帮助玩家取得更好的结果的。
我们先简单地考虑一个例子，有两个学校A和B以及两个学生1和2，学校A有两个位置，学校B只有一个位置，学校A更喜欢学生2，学校B更喜欢学生1，但是学生1更喜欢学校A，学生2更喜欢学校B。
假定我们按照由学校向学生“求婚”的DA算法来进行择校过程，学校B选了学生1，学校A两个都选了，此时两个学生都会去学校A。但是学校B还没招满，于是它又去招揽学生2，学生2就乖乖地去学校B了，学校A只留下了自己的次选学生。
归根结底，学校A做错的不就是好死不死地在第一轮把学校B喜欢的学生给抢走了嘛，那么如果学校A假装自己就只要一个学生会怎么样呢？学校A在第一轮就不会要学生1了，学生1留在学校B，学生2留在学生A，对学校来说皆大欢喜（对学生来说自然是worse off咯）。
聪明的同学可能已经发现了，如果是由学生向学校“求婚”呢？这时候，不论学校A是不是假装减少一个位置，终归是学生1去学校A，学生2去学校B，这种情况我们就称为“不可通过容量操纵的(Non-manipulable via capacities)”。
首先开始更系统性研究这个问题的paper是Sönmez(1997，JET) “Manipulation via Capacities in Two-sided Matching Markets”。他告诉我们，当学校和学生（在论文中是医院和实习生，一个道理咯）至少有两所和三名时，所有的稳定匹配规则都是有可能通过容量操纵的（所谓有可能，指的是存在特定的偏好和配额，使得其中至少有一个学校减少自己的配额能够得到更好的结果）。
啊，我是不是没有讲什么叫稳定匹配规则？其实上面提到的由学校向学生“求婚”的DA算法（因为得到的是对学校（文中是医院）最优的结果，称之为HOSM，即Hospital Optimal Stable Matching）或是学生由学校“求婚”的DA算法（IOSM，即Intern Optimal Stable Matching），都属于稳定匹配规则，它们保证了对于任意的偏好R和配额q，都能给出一个稳定匹配。实际上，稳定匹配规则并不关心中间的过程（分成几轮啊，谁向谁求婚啊，拒绝或是不拒绝谁啊），而是一个黑箱，输入任意一个（R，q）的组合，给出一个匹配μ对于（R,q）都是稳定的，就算做一个稳定匹配规则。也就是说，我完全可以制定这样一个稳定匹配规则：如果学生1认为学校A是accpetable的，那么就给出HOSM的稳定匹配，否则给出IOSM的稳定匹配。
简单的情况下，比如当只有一个学校的时候，它一定会用完自己的配额，所以不会主动减少容量；当只有一个学生的时候，他会选择自己最喜欢的学校，学校减少配额是没有意义的，要么就是那个学生本来就不选你，要么就是那个学生选了你，你把名额从大于一的任意数减少到一，结果也不会变，如果再减少到零连唯一的这个学生都没有了。当有两个学校和两个学生的时候，可以证明IOSM是无法通过容量操纵的。（咦突然发现作者没有证明如果有两个学生和多于两个学校的情况……不过好像这时候显然IOSM也是无法通过容量操纵的……）
那么至少有两所学校和三名学生的时候会发生什么呢？其实只需要一个反例，这个反例是这样的：
先看恰好有两所学校和三名学生的情况，这时候的偏好和priority分别是
（注意这里学校的priority是用集合的形式给出的，这是正式的写法。如果写成之前的1 2 3，无法看出学校会更喜欢{1}还是{2,3}）
PA: {1,2,3} {1,2} {1,3} {1} {2,3} {2} {3}
PB: {1,2,3} {2,3} {1,3} {3} {1,2} {2} {1}
R1: B A
R2: A B
R3: A B
当两个学校的配额容量都是2的时候，稳定匹配只有一个，那就是(A 2,3)(B 1)
当两个学校的配额容量都是1的时候，稳定匹配也只有一个，那就是(A 1)(B 3)
（同学们可以拿出纸笔自己验算一下~）
但如果学校A的配额容量是2，而学校B的配额容量是1的时候，稳定匹配会有两个，其中一个是(A 2,3)(B 1)，另一个是(A 1,2)(B 3)
这时候让我们来构造稳定匹配规则吧，我们只需要考虑在这三种不同配额的情景下，分别给出哪一种稳定匹配就可以了，显然前两种情景已经不用选了，关键看第三种情景：
如果选(A 2,3)(B 1)，这时候把第三种情景作为初始情况，学校A把自己的配额从2减少到1变回第二种情景，对它来说{1}比{2,3}更好。
如果选(A 1,2)(B 3)，这时候把第一种情景作为初始情况，学校B把自己的配额从2减少到1变为第三种情景，对它来说{3}比{1}更好。
所以无论我们在第三种情景下怎么选，总存在一组(R,q)，使得其中有一个学校减少配额能够得到更优的结果。
还没完，因为我们要证明的是“至少”两所学校和三名学生，那么我们在已经有两所学校和三名学生的基础上，加上更多的学生和更多的学校，这些新增的学生不愿意去任何一所学校，而新增的学校不愿意招收任何一名学生，显然在所有的稳定匹配中，这些学生和学校都保持“单身”，不影响结论成立。
当然，这种举反例的方式有点无赖，而且基本上不可能普遍适用。但无论如何，这篇paper开辟了一个新的领域，也说明了这个问题值得得到重视（毕竟这个结论是“几乎都能被操纵”）。后续阅读推荐Ehlers(2010) “Manipulations via Capacities Revisited”，进一步归纳和总结了一些性质和结论。
顺带提一句，如果我们抛弃稳定性而只考虑帕累托最优和防止通过容量操纵的话，其实有一种很简单粗暴的匹配规则：首先把学校编个号，然后学校1先过来挑，挑到配额全部用完或者所有acceptable的学生都挑完为止，然后学校2来挑，然后学校3……对于每个学校来说，减少配额是没有意义的，假设这个学校的配额是p，在这个机制中挑了q个学生(p>q)，如果把配额减少到q,q+1,q+2,…,p-1，结果不变，还是挑q个学生，如果把配额减少到q-1,q-2,…,1,0，那连q个学生都挑不满，而前面的学校又不会因为你减少了配额给你留一点更好的学生，结果只会更糟。这个规则也有一个名字，叫作Serial Dictatorship（中文大致叫“序贯独裁”吧）。
（2015.06.19 @ 微信公众号 @ 《第三讲：More on College Admission 择校问题补遗（三）》）
