状态机：如何构建稳定的婚姻( 四 ) _状态

2.2结婚后婚姻是稳定的：
我们可以证明匹配完成后不存在可能有暧昧关系的两个人。假设匹配完成后Jen和Brad两个人不是配偶，那么根据Brad的名单会有以下两种情况：
Case 1: Brad名单上已经没有Jen了，即他向Jen示爱过并被拒绝了。由上面的不变量P，Jen一定有一个比Brad更加喜欢候选人并和他结了婚，所以Jen不会被Brad吸引，即他们不会有暧昧关系。
Case 2: Jen还在Brad的名单上，由于Brad是按照好感顺序去示爱的，如果最后Jen还在他的名单上，Jen又没有和他结婚，那么Brad一定和一个他更有好感的女人结了婚，所以Brad不会在意Jen的“勾引”，也就不会和她有暧昧关系。
由于Brad和Jen的选择是随机的，所以匹配后任何人之间不会产生暧昧关系，即婚姻一定是稳定的。
这个方法对男人有利还是女人有利？
你可能觉得女人具有选择权——她们每天都能选择一个更好的配偶，男人只能被拒绝——只能选择越来越差的配偶，但实际上在该算法中女人是很弱势的一方！我们前面只证明了婚姻匹配方法得出来的匹配的正确性，事实上，稳定的匹配方法可能不止一种，例如，如果我们还是利用婚姻匹配算法，将匹配时的男女属性换一下就可能得到不同的结果（还是稳定的）。
称一个人对于另一个人是“可行配偶”如果在某一个的稳定匹配中他们可以成为夫妻。下面证明上面算法的状态机具有一个不变量Q：对于女人w和男人m，如果w被m从名单中划掉了，那么w对于m不可能是“可行配偶” 。
反证法，假设某个时候Alice要被Bob从名单中划去因为Alice选择了另一位叫Frank的男性，如果Alice和Bob成为了配偶，那么Frank也就只能划掉Alice选择更“差”的一位女性，而Alice也就只能跟着不那么喜欢的Bob，所以Frank和Alice之间就可能发生暧昧关系，因此Alice和Bob不可能是可行配偶。
称在一个人所有的”可行配偶“中Ta最喜欢的那一个为”最理想配偶“，最不理想的那一个为”最不理想配偶“ 。下面证明如果使用上面的婚姻匹配算法，男人们总会娶到”最理想老婆“，而女人们总会娶到”最不理想老公“ 。
证明：如果Bob利用上面的算法和Alice结了婚，那么之前在名单中Alice之上的女性都被Bob划掉了，由不变性Q，被划掉的女性都不是”可行配偶“，而Alice又是划掉操作后最排行最高的女性，所以Alice是Bob的”最理想配偶“ 。另一方面，如果Alice对她的丈夫好感度低于对Bob的，那么Bob一定取了一位不是”最理想配偶“的人，这样Alice和Bob就可能发展暧昧关系，所以Bob一定是Alice的”最不理想配偶，证毕。
婚姻匹配算法的实际应用：
在50年代的时候，美国启动了一项名为国家公民匹配（，NRMP）的计划，该计划主要是为了解决从学校毕业的学医学生和医院之间的匹配关系——尽量使学生和医院都满意，在该计划中就大量使用到了婚姻匹配算法，即医院和学生分别充当男人和女人。其发明人获得了2012年的诺贝尔经济学奖。大量的交友网站使用到了该算法（当然男人不会向女人去示爱，都是计算机完成的）。《 for》的作者之一Tom 创立了互联网接口公司, 他们将婚姻匹配算法用到了服务器和用户的资源调配之中（CDN）。其中网络请求（客户）作为女人，网站服务器作为男人；网络请求对服务器的“好感度”取决于延迟和丢包率，网站服务器对于网络请求的“好感度” 取决于连接带宽和主机代管商的成本。
参考：
for