匹配理论(Matching Theory)讨论了许多非常生活化的经济学，让你充分意识到，经济学本质上解决的是稀缺资源如何分配的问题，而不仅仅是GDP、收入、消费等等这些一听就像要钻进“钱”眼里的名词。在本讲中，我们首先介绍婚姻市场（也可以叫恋爱市场）中的匹配模型，参考书目是Roth & Sotomayor(1992)“TWO-SIDEDMATCHING:A GAME-THEORETIC MODEL AND ANALYSIS”。
婚姻市场
首先，婚姻市场是一个双边市场，分为男生和女生。由对称性，以下的讨论我们都站在男生的视角，但同样的结论对于女生也是成立的。
每个男生对于所有女生有一个偏好（就是对女生有一个排序），反之女生对于所有男生也有一个偏好。不过，在男生的偏好中，除了所有女生之外，还包括他自己；所有排在自己之后的女生都被视为unacceptable（换句话说，宁愿单身也不愿意接受这些女生），反之女生也是如此。
为了方便起见，我们一般默认偏好是严格(strict)的，也就是说，对于任何两个女生，男生总是喜欢一个胜过另一个，不会出现觉得两个女生一样好(indifference)的情况。这个要求对于我们后面介绍的Deferred Acceptance算法其实没有影响，但是对于其它一些重要结论则是必要的条件。
匹配
一个匹配(matching)，就是将婚姻市场上的一部分男生和女生配对，然后让剩下的男生和女生保持单身，我们用函数μ(·)来表示这个匹配，μ(x)就是x的配偶。μ(x)满足以下三条要求：1. 男人的配偶不是自己（单身）就是女人；
2. 女人的配偶不是自己（单身）就是男人；
3. 每个人的配偶的配偶都是本身。（不考虑同性恋和一夫多妻/一妻多夫）
但是，匹配有很多种，比如说每个人都保持单身，这也是一个可行的匹配，但是这样的匹配几乎是不可能维持的（因为单身狗也有春天……）。那些可以维持的匹配，一定存在一些特殊的特点，我们把这些匹配称为稳定匹配(stable matching)。具体来说，稳定匹配指的是满足以下两个要求的匹配：
- Individual Rationality（简称IR，大致可以翻译为“个体理性”），每个人不会接受unacceptable的配偶。
- Pairwise Stability（大致可以翻译为“配对稳定”），不会同时有一男一女喜欢对方胜过自己的配偶。（如果有的话，我们称这一男一女为blocking pair，他们阻碍(block)了这个匹配μ）
一般来说，第一条是很容易满足的，比如说每个人都保持单身，就是满足IR的匹配。但是第二条就不一定了，而且在现实世界中很有可能就发生这样的事（NTR）了。那么问题来了，挖掘机技术到底哪家强？啊不对，怎么找到稳定匹配呢？
在进入下一部分之前，首先来解释一下稳定匹配的意义，或者说，为什么我们要找出稳定匹配。实际上，对于寻找稳定匹配的过程，存在两种不同的解释，或者说就是两种不同的市场：其一称为”Decentralized Market”，就是把一堆男生女生扔进市场，然后他们就开始不断地追人甩人，最后他们达到了某种稳定的状态，这种状态就是稳定匹配；其二称为”Centralized Market”，就是现在开了一家T大婚姻介绍所，所有T大的单身狗把自己的信息提交过去，然后男生给女生排个序，女生给男生排个序，然后T大婚介所根据双方的偏好信息，排好一套匹配，然后告诉男生“你命中注定的女神就是XXX”，告诉女生“你命中注定的男神就是XXX”，如果双方皆大欢喜，不存在NTR的可能，那么也是稳定匹配。下面介绍的Deferred Acceptance算法，看起来好像是按照前一种市场进行的，但实际上我们可以假定已经收集到了所有的男女生信息，然后让计算机模拟一下流程，得到了最终的稳定匹配，然后咱们的婚介所就可以关张了（当这个问题是静态时，这样的婚介所开一次就可以关门了……）。
寻找稳定匹配
知乎上有一句经典名言：不问有没有就问为什么都是耍流氓（以及其它变种……）所以在找稳定匹配之前，一定先要问一句有没有。如果有同学表示这他喵的不是显然的么，那就让我们（等会儿）用一个实际例子来糊他一脸~
实际上，婚姻市场这样一个双边市场是非常特别的，它有这样两个性质：
- 它把所有市场中的人分成了两边，互相进行选择；
- 它是一对一的；
这两个性质为什么特殊呢？因为如果不符合，那就可能没有稳定匹配；具体来说，如果市场上只有一类人（室友选择问题），或者有三类人（家庭配对，有父亲、母亲和孩子）或者市场上是一对多的（劳动力市场，一个公司招好几个工人，而且工人之间有协同效应），都能够找到反例。比如以下这个例子来自Gale & Shapley，是室友选择问题提供的一个不存在稳定匹配的反例。
有4个同学a,b,c,d分在两个寝室，每个寝室有两个人，每个同学对另外三个人各自有一个偏好（当然，这时候就不允许保持“单身”啦）。
- P(a)=b,c,d（a最希望和b分在一个寝室，然后是c，最差是d，以下同理）
- P(b)=c,a,d
- P(c)=a,b,d
- P(d)=arbitrary（d同学显然是最不受欢迎的室友= =）
4个人分在两个寝室，一共就只有三种分法
- μ1={(a b)(c d)} 不行，因为b和c希望和对方住一块儿均胜过自己的室友；
- μ2={(a c)(b d)} 也不行，这回闹别扭的是a和b；
- μ3={(a d)(b c)} 还是不行，这回闹别扭的是c和a；
于是这个室友选择问题就没有稳定匹配了。
那双边市场有没有稳定匹配呢？有。为什么呢？我们往下看。
假定我们先接受了这一事实，然后开始尝试找稳定匹配。一个比较直接的想法是，首先大家自由配对，选择自己能够接受的配偶，比如说先让所有人单身（避免了Individual Rationality的问题），这时候的匹配基本上不可能是稳定的，不满足Pairwise Stability嘛。那好，我们在所有阻碍了这个匹配的男女（还记得阻碍(block)的定义吗？不记得的向上翻）中，找一对出来，让他们俩成了，然后让他们原本的配偶（如果有的话）变成单身，就得到一个新的匹配，比原来那个稍微稳定了一点吧？然后就不断重复这个过程就行啦~
所以这个想法对吗？也不对也对。说不对，是因为Knuth找到了这样一个例子，如果选择这对（狗）男女选得特别不巧的话，还真有可能进入一个死循环。说对，是因为Roth 和 Vande Vate 给出了一个定理说，对任何一个匹配来说，一般不会只有一对男女阻碍了这个匹配成为稳定匹配，如果我在所有的匹配中随机地选一对，把他们解决掉，然后在新的匹配中随机地选一堆，然后解决掉，不断重复下去，只要每种选择的概率都是正的（都有可能被选上），那么最终这个过程以概率1达到一个稳定匹配，这篇论文“Random Paths to Stability”(Roth & Vande Vate, 1990)短小精悍，证明也很巧妙，不妨一读。
但是，这种办法实在太折腾了，而且听起来太靠运气了，有没有不那么麻烦的算法呢？那就是Gale & Shapley在1962年提出的著名的Deferred Acceptance Algorithm，简称DA算法，翻译过来叫作延迟接受算法，简单地说，就是（假定男生主动求婚）允许一个女生在接受某个男生之后，如果碰到更心仪的男生可以把前一个给甩了。
接下来就是揭露真相的时刻啦，为什么我们说双边市场有稳定匹配呢？因为Gale 和 Shapley 说，只要按照我们这个DA算法走一遍，得到的一定是稳定匹配，所以稳定匹配就一定存在。换句话说，他们就是通过用DA算法构造出一个稳定匹配，证明了双边市场上稳定匹配的存在性。
然后我们来看一看这个具体的流程（假定男生主动求婚）；
- 第一轮，每个男生向自己的偏好中排名最高的女生求婚；每个女生拒绝掉所有unacceptable的求婚者，然后在剩下的求婚者中，选择在自己的偏好中排名最高的男生，然后和他订婚(keep engaged)，并且拒绝掉其他人。
- 之后的每一轮，每个还没有名草有主的男生，向自己的偏好中排名最高的没有拒绝过自己的女生求婚；每个女生仍然是拒绝掉所有unacceptable的求婚者，然后在剩下的求婚者以及上一轮订婚的那个男生中，选择在自己的偏好中排名最高的男生，和他订婚（渣女！哼！），并且拒绝掉其他人。
- 依此类推，每一轮那些没有被接受的男生都会向下一顺位的女生求婚，直到被订婚或者所有acceptable的女生都拒绝了他。
- 如果没有男生求婚了，算法结束（这个过程可以保证是有限的），此时所有已经订婚了的男生和女生结婚，剩下的人保持单身。
可以证明，这个时候给出的匹配一定是稳定的。否则假定男生m和女生w打算私奔，那么m一定喜欢w胜过目前的配偶μ(m)，根据算法的流程，m一定在和μ(m)配对前向w求过婚并被拒绝了，那这意味着w遇到了一个比m更好的男生m’，而w目前的配偶μ(w)至少和m’一样好，所以μ(w)比m更好，那么女生w就不应该愿意和男生m私奔，矛盾。
稳定匹配的好坏
实际上，稳定匹配自然不是只有DA算法给出的这一个（或者说两个，男生主动和女生主动各自得到一个可能不同的稳定匹配），那么这些稳定匹配各自是有好有坏的。Gale 和 Shapley进一步证明，如果偏好是严格(strict)的，那么由男生主动求婚得到的这个稳定匹配对男生来说是最好的，称之为M-optimal；反之，由女生主动求婚得到的稳定匹配就是W-optimal的。
让我们先往前回一点，先定义一下对于双方来说什么是好的匹配，什么是不好的匹配。我们用”>m”（m应该是下标）来表示对男生来说的“优于”，假设我们现在有两个匹配μ和ν，μ >m ν的意思就是每个男生在μ中的配偶至少和ν中一样好，且至少有一个男生在μ中的配偶比ν要好；相对应的，女生也有这样的一个比较关系“>w”。（不是”>w<”谢谢）
牛逼轰轰的Knuth又一次站了出来，他告诉我们，如果两个稳定匹配μ和ν满足 μ >m ν，那么一定有ν >w μ。也就是说，男生认为更好的配对，女生一定认为更不好，反之亦然。这个定理最牛逼的地方在于，它有一个非常直截了当的推论：
由男生主动求婚得到的M-optimal的稳定匹配中，每个男生都匹配上了他在所有的稳定匹配中可以匹配到的最好的女生（当然如果他在所有稳定匹配中都只能单身就……），每个女生则匹配上了她可以匹配到的最差的男生（或者始终保持单身……）；反之，由女生主动求婚得到的W-optimal的稳定匹配中，每个男生匹配上了最差的女生，每个女生则匹配上了最好的男生。
更加神奇的是，即使我们拿在手里的是两个不能比较的稳定匹配（也就是有些男生更喜欢μ，有些男生喜欢ν），那么我们可以让每个男生在μ和ν的两个配偶中选一个更好的，每个女生在μ和ν里的两个配偶中选一个更差的，然后：
- 一定能得到新的匹配（也就是不会出现两个男生选同一个女生，或者两个女生选同一个男生，或者某男生选了某女生，该女生却没有选该男生）；
- 新的匹配也是稳定匹配；
- 新的匹配对每个男生来说比μ和ν都要好。
数学上，这意味着所有的稳定匹配μ构成了一个代数，称为lattice，它有一些很好的性质，这里就不再展开。
最后给各位男生女生一句忠告，由于算法要求自始至终只有一方propose，所以主动不主动和算法流程的关系不大，但真正有关系的在于偏好啊，你不主动一点男神/女神一直把你放在unacceptable的人里面那你就一点机会都没有了啊！
（2015.05.19 @ 微信公众号 @ 《第一讲：Marriage Market 婚姻市场》）
