上一讲给大家介绍了DA算法，不过老是给大家讲这些五十年前的内容也挺没有意思的，所以这一讲我们来讲点新东西~
在上一讲中我们提到，对于匹配其实有两种不同的解读方式，一种是Centralized Market，另一种是Decentralized Market。在Decentralized Market中，稳定匹配的含义是市场上的男男女女会不断地分分合合，直到最后不再变动为止。
但实际情况并非如此，我们会观察到，不是每个人都愿意分分合合的，有时候就算能够有机会去找更好的对象，但是因为各种成本的问题，也许就会选择继续和现在的对象在一块儿了；就比如说，有些父母虽然感情不和，但是考虑到孩子还在读书的缘故，可能就会选择不离婚，这样的新闻也是挺常见的。
这种情况，我们可以统称为离婚成本(Divorce Cost)。在一个Decentralized的婚姻市场上，有些匹配本来应该是不稳定的，但是由于存在离婚成本的缘故，原来更好的选择反而不如保持现在的对象，结果就变成“稳定”的匹配了。由于在原本的设定中，我们对偏好并没有采用赋值的形式，而是采用了排序的形式，所以我们在表示离婚成本的时候，也不能直接说它是某个值c，而是考虑对偏好进行顺序上的调整。
在最简单的情况下，假定现在市场上已经有一个禀赋的匹配μ，我们依照这个匹配来调整每个人的偏好：某个男生m匹配的对象是μ(m)，在他的偏好中，比μ(m)高一位的是女生w；在考虑离婚成本的情况下，m把μ(m)上移一位，排到了w的上面，μ(m)同时也把m上移一位。当然，如果对象本身已经是第一位，那仍然保持不变就可以了。
如果匹配μ在调整过偏好之后的市场上是稳定的，那么我们就称它为1-稳定匹配，这里的1表示我们把匹配对象上移一位。如果上移k位，那就叫k-稳定匹配。原本的稳定匹配，我们也可以称为0-稳定匹配。
举个例子，现在有三男三女，分别是a,b,c和1,2,3，他们的偏好如下所示：
Ra: 3 2 1
Rb: 1 3 2
Rc: 1 2 3
R1: a b c
R2: a c b
R3: b a c
如果不考虑离婚成本，那么唯一的稳定匹配是：(a 3)(b 1)(c 2)
如果考虑离婚成本，而市场上本来有一个禀赋的匹配μ=(a 1)(b 3)(c 2)，那么我们相应地调整偏好为
R’a: 3 1 2
R’b: 3 1 2
R’c: 2 1 3
R’1: a b c
R’2: c a b
R’3: b a c
在调整过的偏好下，μ=(a 1)(b 3)(c 2)是稳定匹配，所以它是一个1-稳定匹配。
现在，让我们换一个角度。我们之前提到，稳定匹配首先要求个体理性(Individual Rationality)，其次要求配对稳定(Pairwise Stability)，也就是说，首先匹配对象至少要和单身一样好，其次不存在一男一女，喜欢对方胜过自己的配偶。如果我们直接从这个定义上类比地去看k-稳定匹配，那么要求就应该是：首先匹配对象至多比单身差k位，其次不存在一男一女，喜欢对方胜过自己的配偶k位。
可以证明，这两种对于k-稳定匹配的定义是等价的，而由后面这种定义，我们很容易发现，随着k的增大，k-稳定匹配组成的集合是向前包含的，也就是说，1-稳定匹配中包括了所有0-稳定匹配（也就是原本意义上的稳定匹配），2-稳定匹配包含了所有1-稳定匹配，以此类推。当k充分大的时候，k-稳定匹配将会包含所有的匹配，因为所有人会把自己在当前匹配下的对象上移到第一位。
因为这样一个向前包含的缘故，如果我们只考虑一方的福利，越来越多的选择一定意味着效用边界在不断向外推进，比如上面的例子中，对于女生1、2、3来说，(a 1)(b 3)(c 2)比起(a 3)(b 1)(c 2)来说就更优。但是，如果我们要同时考虑双方的福利，仅仅通过调整偏好，我们还是没办法得到比任何稳定匹配帕累托更优的匹配，如若不然，假定有一个稳定匹配μ和一个帕累托优于μ的匹配ν（未必是稳定匹配），不妨假定ν(m)优于μ(m)，显然ν(m)在μ中的对象不是m，那么m又优于μ(ν(m))，我们就有了一对阻碍μ的blocking pair (m,ν(m))，和μ是稳定匹配矛盾。
由于在k-稳定匹配下，我们仍然有k-blocking pair的定义，即“存在一男一女，喜欢对方胜过自己的配偶k位”，所以，我们可以将Roth & Vande Vate(1990)的结论复制过来，也即从任意一个匹配出发，以正概率随机选择一个k-blocking pair解决掉，最终一定以概率1到达一个k-稳定匹配；原论文的证明也可以直接套用。
在上文中提到，对于偏好的定义，我们采用的是排序而不是赋值的形式。如果我们采用赋值的形式，也就是说，对于男生m，和女生w1匹配时，获得效用u(m,w1)，和女生w2匹配时，获得效用u(m,w2)，依此类推，这时候我们就可以用一个数c来表示离婚成本了。通过恰当地定义效用和离婚成本，我们可以模拟出排序形式下的k-稳定匹配的定义，也就是说，采用赋值的形式来表示偏好，是对于原本问题的一个推广。
我们重新定义稳定匹配如下：一方面，如果和现在的配偶离婚回到单身能够获得收益，则收益不能超过离婚成本；另一方面，不存在一男一女，通过更换配偶所得的收益能够超过离婚成本。所有我们已经得到的结论，包括单方面的效用边界拓展，或是通过随机过程达到稳定匹配，在这个情境下依然适用。
突然发现，咱们是不是还没有介绍这是哪篇论文？其实这是我自己撰写的一篇论文，大家引用的时候记得注明Xu(2015)哦最后，诚招co-author继续研究这个问题哦哈哈
（2015.05.25 @ 微信公众号 @ 《第一点五讲：Adjusted Preference 偏好调整》）
