大家好，这里是“每周一题”第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: 对本活动有任何建议、意见，欢迎随时联系！
扫码加好友，拉您进群
全部版块
我的主页
收藏
