问题：﻿恋爱中有哪些博弈？ 刚上完博弈论，老师在课堂上提出了这样一个问题：恋爱中有哪些博弈？作为男方/女方该如何决策才能达到两者最优？ 相关问题:到底为什么有钱，长得帅，长得高，和…
话题：﻿恋爱、恋爱心理
回答：﻿目前排名最高的@尼克余的算法表述有问题。本回答主要内容同恋爱中有哪些博弈？-瞻彼淇奥的回答。以下内容搬运自Roth&Sotomayor“TWO-SIDEDMATCHING:AGAME-THEORETICMODELANDANALYSIS”Chapter2，主要内容就是DeferredAcceptanceAlgorithm（以下所有举例均以男方视角入手，大部分情况下都同样适用于女方视角）一、婚姻市场在婚姻市场上有m个男人，n个女人，每个男人对于所有女人有一个排序，反之亦然。NOTE1：@尼克余的假定是，每个男人会选择任何一个女人，每个女人会选择任何一个男人。但在标准模型中，男人的偏好中，除了所有女人之外，还有他自己；所有排在自己之后的女人都被视为unacceptable（换句话说，宁愿单身也不愿意接受这些女人）；反之亦然。另外，标准模型讨论了偏好是否strict的问题。strict的意思是，对于任何两个女人，男人总是喜欢一个胜过另一个，不会出现觉得两个女人一样好的情况；反之，认为有些女人一样好的情况称为“indifference”二、matchingmatching，或者说一个配对，就是将婚姻市场上的一部分男人和女人一对一配对(one-to-onematching)，然后剩下一部分男人和女人保持单身（见NOTE1）；标准模型中用了一个函数μ(x)，表示配偶。μ(x)满足以下三条要求：男人的配偶不是自己（单身）就是女人；女人的配偶不是自己（单身）就是男人；每个人的配偶的配偶都是本身。但是，matching有很多种，比如说每个人都保持单身，这也是一个matching，但是这样的matching几乎是不可能发生的，所以我们要对matching再加一些限制，称为stablematching。stablematching指的是满足以下两个要求的matching：1.individualrationality，个体理性，每个人不会接受unacceptable的配偶。2.pairwisestability,配对稳定，不会同时有一男一女喜欢对方胜过自己的配偶。（此时称这一男一女block了这个matchingμ(x)）一般来说，第一条是很容易满足的，比如说每个人都保持单身，就是individualrationality的。但是第二条就不一定了，而且在现实世界中很有可能就发生这样的事（NTR）了。那么问题就来了，怎么来找到stablematching呢？NOTE2:在这里，作者首先就指出，对于寻找stablematching的过程，存在两种不同的解释：其一，婚姻市场上，男女双方不断地更换伴侣（按照某种规则），然后最终达到stable的状态；其二，有一个婚姻中介，它收集了男女双方的偏好信息，给双方提供了一个最终的清单，保证这个清单是stable的。实际上，即使我们按照Gale&Shapley提出的算法找到了一种stablematching，我们也不需要真的按照这个过程走（像第一种解释那样），而完全有可能是按照第二种解释那样，直接给出了一个stablematching，并且各方遵循了这个决定。三、寻找stablematchingNOTE3：首先说一句题外话，其实婚姻市场是一个非常特别的市场，它有这样两个性质：（1）它把所有市场中的人分成了两边，互相进行选择（2）它是一对一的这两个性质保证了一点，就是stablematching的存在性。Gale&Shapley提供了另外三种情况：（1）市场上只有一类人（室友选择问题，所有人是同一类的）（2）市场上有三类人（家庭配对，父亲、母亲和孩子）（3）市场是一对多的（劳动力市场，一个公司招募多个工人）；在这三种情况中，都不一定存在stablematching回到正题，怎么寻找stablematching呢？一个比较直接的想法是，首先大家自由配对，选择自己能够accept的对象，比如所有人单身（避免了IndividualRationality的问题），这时候的matching可能还是不满足pairwisestability，那好，我们在所有block了这个matching的男女中，找一对出来，让他们俩成了（有三种可能，本来各自有配偶的，那就另两个成了；有一个单身的，那被抛弃的就单身了；都是单身的，那就成了，没问题），得到一个新的matching，然后不断重复这个过程。这个想法有什么问题吗？有，Knuth就找到了这样一个例子，如果选择这个blocking的一对男女选的特别不巧的话，还真有可能进入一个死循环。但是好在有另一个定理证明了，如果block这个matching的男女不止一对，那么我就随机选一对，只要每种选择的概率都严格大于0，那么在足够长的时间过后，几乎一定能够跳出死循环找到一个stablematching。但是，这种办法太折腾了，一个运气不好就麻烦了，而且从现实问题的框架来看，婚姻市场中的男男女女的数量不知道要多少，这个算法太麻烦了。那么有没有更好的算法呢？那就是Gale&Shapley提出的算法（实际上，他们是以定理的形式给出的，算法本身是作为证明的存在）具体的相互propose的过程（假定男人求婚）第一轮，每个男人向排名最高的女人propose；每个女人拒绝掉所有unacceptable的男人，在剩下的propose中，选择在自己的偏好中排名最高的男人，keepengaged，并且拒绝掉所有其它男人。之后的每一轮，每个没有被keepengaged的男人，向排名最高的没有拒绝过自己的女人propose；每个女人仍然是拒绝掉所有unacceptable的男人，然后在剩下的propose以及keepengaged的那个男人中，选择偏好中排名最高的男人，并且拒绝掉所有其它男人。每个男人一直propose，直到被keepengaged或者所有acceptable的女人都拒绝了他。如果没有男人propose了，算法结束（这个过程可以保证是有限的），此时所有女人和其keepengaged的男人结婚，剩下的人保持单身。接下来，就要讨论stablematching的好坏问题了。Gale和Shapley进一步证明了，如果由男性求婚，得到的stablematching是M-optimal的，反之，如果由女性求婚，得到的stablematching是W-optimal的。（前提条件是偏好是strict的）让我们先往前回一点，先定义对于双方来说stablematching的好坏。我们用（>m）来表示对男方来说的“优于”，假设我们现在有两个stablematching，分别称为μ和μ’，μ>mμ'的意思就是每个男人在μ中的配偶至少和μ'中一样好，且至少有一个男人在μ中的配偶比μ'要好。（对女性来说就是>w啦）然后我们就会突然得到一个神奇的结论，如果两个stablematchingμ>mμ'，那么一定有μ'>wμ。也就是说，男人认为好的配对，女人一定认为是不好的。反之也成立。（这个定理来自Kunth）这个定理最牛逼的地方在于，它有一个非常直截了当的推论：一个M-optimal的stablematching（由男性求婚给出）中，每个男性都匹配上了他在所有的stablematching中可以匹配到的最好的女性（或者他只能匹配到自身），每个女性则匹配上了她可以匹配到的最差的男性（或者自身）；反之亦然。NOTE4:更加神奇的是，即使我们拿在手里的是两个不能比较的stablematching（也就是有些男人喜欢μ，有些男人喜欢μ'），那么我们可以让每个男人在μ和μ'里的两个配偶中选一个更好的，每个女人在μ和μ'里的两个配偶中选一个更差的，然后：（1）一定能得到新的配对（也就是不会出现两个男的选同一个女的或者两个女的选同一个男的或者男的选了女的女的却没有选男的）（2）新的配对也是stable的（3）新的配对对男性来说比μ和μ'都要好。（实际上，这意味着所有的μ构成了一个代数，称为lattice，它有一些很好的性质，这里不再展开。）这里贴一张图说明lattice：每个点表示一种stablematching，左边自上之下是>m的关系，右边是>w的关系。NOTE5:最后说一句主动不主动的问题，算法的要求是，自始至终只有一方propose，否则该算法不能顺利进行（如果轮流propose，在一定程度上就相当于寻找blocking并且凑成一对，也即Knuth给出过反例的那个算法）。所以，妹子们主动不主动和这个算法其实没有关系，真正有关系的在于偏好啊，你不主动一点男神一直把你放在忽略的人里面（也就是unacceptable的人里面）那你就一点机会都没有了啊！