每周一题3: 室友 or 女友？

相似文件 换一批

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

大家好，这里是“每周一题”第3期，往期题目/讨论请见这里：
第一期题目
第一期讨论
第二期题目
第二期讨论
下面是本期活动：


参与方式：


1. 本次活动答题截止时间为：2013年8月3日23:59:59，之后将进行锁贴处理，请在截止时间前提交自己的答案。
2. 本贴将设置“回复仅作者可见”，在答题期内大家无法看到其他版友的答案（但可修改自己的答案）。活动截止时将取消作者可见，公布大家提交的答案。
3. 请大家独立思考并提交答案，请勿在答案公布前在版内开贴讨论。
4. 参考答案将于2013年8月4日放出，同时发放奖励。
5. 本贴禁水。每人只回复一楼（回复后可编辑、修改），无关回复（并非答题的回复）一律删除。

（由于本期题目小问较多，认真答题者奖励翻倍（请认真给出至少前两问的"你的“答案，并不要求是”正确答案“））

奖励规则：

有效回复（给出答案＋简要陈述理由）                      +3论坛币（翻倍后为+6）

精彩回复（观点有启发）                                  额外+7论坛币（翻倍后为+14）

每周最佳答案                                                 额外+20论坛币（翻倍后为+40）

注：每人各项奖励最多只能获得一次。

注2: 未避免争议，本人对答案的评判保留最终解释权。

————————————————————————————————————————————————————————
本周题目：


这期的主题是一个匹配问题，最终目的是寻找“全局”稳定的均衡状态。


首先，给出问题：


问题1: 给定4位单身男生a, b, c, d, 以及4位单身女生A, B, C, D。他们对对方都有一个偏好排序（1>2>3>4), 可用如下矩阵表示：





以女生A（左边矩阵A列）为例，从A列可以看出，她对4个男生的偏好为a>b>d>c。
以男生b（右边矩阵b行）为例，从b行可以看出，他对4个女生的偏好为B>A>C>D。


下面定义稳定的匹配：


每个男生和女生都选择好了自己的伴侣（男女搭配），如果没有任何两人（一男一女）能够“一拍即合”（她俩的情况都得以改善），那么这个匹配是稳定的。


以下面的匹配为例：
A-a
B-b
C-c
D-d


从这个匹配中，我们可以看到a在A心目中排第一位，而A在a心目中是最后一位的。


这个匹配是不稳定的：


男生a可以和女生D双宿双飞，此时a的配偶从A变到了D（对a（右矩阵a行）来说，D(3)>A(4)），D的配偶从d变到了a（对D（左矩阵D列）来说, a(2)>d(4)）。所以男生a有动机和女生D“一拍即合”，抛弃原来的伴侣。（注意，被抛弃的两人不必要变得更好，他们是被抛弃的！）

那么，聪明的你能找出一个“稳定”的匹配么？请给出你的思路/方法。




问题2: 下面考虑“换室友”问题，4个男生a b c d对其他男生都有一个偏好排序，如下面矩阵所示：



对a来说，b>c>d
对b来说，c>d>a
对c来说，a>b>d
对d来说，c>a>b

a,b,c,d 四人将分成两对、成为室友，那么是否存在稳定的室友匹配呢？（“稳定”的定义也是，没有两人能“一拍即合”，通过抛弃原来的室友获得情况改善）
例：一种分寝室方式是：a-b    c-d

问题3: 上面两种问题有什么区别与联系？
HINT: 问题1类型（男女匹配）一定存在稳定匹配，而问题2类型（室友匹配）不一定存在稳定匹配，请探究其原因。

————————————————————————————————————————————————————————
最后插播

征稿启示：

如果您在生活中遇到什么博弈相关的问题、或者浏览到相关方面的的奇闻轶事，欢迎投稿每周趣题，一经采用将获得最高50论坛币的丰厚奖励噢。

征稿要求：

0. 趣题尽量要有“趣”，贴近生活，有启发性为佳。

1. 鼓励原创，可以是课后习题的延伸、拓展，也可以是网络上、学习中读到的文章、遇到的启发性的问题。

2. 带有比较成熟的参考答案，或者相关reference。

注：没有成熟答案的问题也欢迎来本版发贴交流！

注2：投稿请通过私信的方式联系我，谢谢！

注3: 对本活动有任何建议、意见，欢迎随时联系！

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：每周一题 Reference erence refer 20论坛币 参考答案 答题

2012年的诺贝尔经济学奖授给了夏普利(L. S. Shapley)和罗斯(A. E. Roth)，表彰他们在稳定配对和市场设计方面的理论和实践并重的贡献。
这个稳定配对大意是说，不存在两个人他们都更中意于彼此，胜过他们当前的配对者。换句话说，你的配偶就是你的最爱。
稳定的定义是没有一对夫妻相互认为自己与其他人的组合会比现在的组合更好。
换言之，如果丈夫认为某个其他女性要比现在的妻子好，这个女性也不会选择他，因为她更偏爱她现在的丈夫。那个男人只是单相思而已。
因为如果婚姻市场上有数量大致相当的适婚男女，男的知晓所有女的信息，女的也一样。然后男的对女的有一个排序，女的也对男的进行排序。接下来一方发起求婚，另一方对照自己的偏好排序表，如果是最爱的就接受，不是的就拒绝。
假设结婚比单身好，在完全信息、交易费用为零和配对时间不限的情况下，最终萝卜青菜各有所爱，每个人总能找到自己的伴侣，并且这种配对是稳定的，即没有人想分手，不会出现出轨的现象。
为什么呢？
让我们假设有X男和Y女发生了婚外情，X与原来的M女离婚，这说明X更偏好Y，这违反了预设的偏好排序。每个人都是按照自己的偏好排序来求婚的，所以如果是稳定配对，就不存在出轨现象。
延迟接受算法：
1. 每个男的向他最喜爱的女的求婚
2. 每个女的记录下所有向她求婚的人
3. 留下自己的最爱，回绝其他求婚者
4. 被回绝的男生降格以求进入下一轮
5. 回到2，直至女生嫁完为止
让我们看看用这理论设计的求偶规则，怎么造就个没人想偷腥，小三也撬不进的稳定婚姻。
假设有N男配N女，男女每人都有自个儿的心仪异性爱慕顺序表，跟速配节目里一样，求婚阿妹不成求二妞，嫁不成张三嫁李四，对于这么通情达理面对现实的男女，月老划下规则如下：
首先给每个男的向最心仪的女人表白机会。这时侯女的不外乎两种情况：一是无人问津，那她就靠边等下轮；二是有了爱慕者，那就别犹豫立马约会去，如果不止一个，当然约最帅的压马路，其他的都给闭门羹。吃了闭门羹的回家洗洗，第二轮再拿朵玫瑰向他No.2的女人求爱，剩女被追时照前例办理；
有主的若又见到玫瑰花，如果更喜欢这新来的，就把正约会的给蹬了，改约新欢。还没战果的剩男包括踢出门的，回家洗洗，再来第三轮追求，追他爱慕顺序表里的下一个；……
如此几轮下去每个男的都配上个女的了。
不难看到这个匹配是稳定的。求婚中，人至贱则无敌。这里人人都把这诀窍发挥到极致，就没有什么可遗憾的了。因为每个男的，献媚过更爱慕的，结果都没成，现在身边的女友比上不足比下有余，人家也不嫌弃，就认命吧，单相思是没有意义的。
每个女的得到的是所有向她求婚人中最喜欢的那一个，虽然可能还有更好的梦中情人，可是望断秋水都没来，那也是在梦里，也该知足了。所以这样匹配的婚姻，男的没胃口去偷腥，女的也当不成小三，谁都不想再改变了，很稳定。答案：aD，bA，cB，dC

1、男女搭配问题
    稳定匹配为：a—D
                      b—A
                      c—B
                      d—C