沙普利求婚算法

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

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

立即领取

感谢您参与论坛问题回答

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

+2 论坛币

沙普利求婚算法中说最多只需n^2-2n+2回就可得出稳定结果，请问是怎样算出来的？






很好的书籍，不过问问题的时候希望能把问题说清楚。
故请把2楼附件编辑到1楼，2楼我将做删除处理。
－－－－－handsome8848留

扫码加我 拉你入群

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

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

分享0 收藏1 回帖

关键词：Hands Hand Some NDS 很好的 书籍

The solution to this problem, p37

No3676671 发表于 2013-7-18 10:41
The solution to this problem, p37

很有意思的书，正在研究，稍后给出我的想法～

看完了。

首先，建议阅读p32 （书的p16）的例子，并且自己能画出这个过程，得到stable的结果。
（一共有2个preference的matrix，可以把任一个作为proposal的matrix，另一个作为decision matrix。）

其次，知道这样的equilibrim是存在的p35(section 1.8)

确保了这两点，就可以理解为什么是n(n-2)+1了：（书上的1+n(n-2)+1前面的1应该有问题）

参见P41的例子，N=4时一共排出了9轮(n-1)^2,最后一轮只是写出结果罢了。

思想是，最多经过N(n-2)次拒绝，每个人都只有两个可能性了，这时候只需要某个人再提出一次，就可以根据他是否被接受而决定他的结果，从而决定整个的结果。
形如
x           x
x  x
   x  x
      x     x
只要定下了一个x，其他x也确定了。

如果碰到
x
x  x
   x   x    x
        x
             x
这种情况（并非每一行都是两个元素），根据解的存在性，最后一个人必须是(4,4),同时整个matrix退化成3x3的轮换式。此时定下一个仍然可以确定另两个。

handsome8848 发表于 2013-7-18 14:21
看完了。

首先，建议阅读p32 （书的p16）的例子，并且自己能画出这个过程，得到stable的结果。

D. Gale and L. S. Shapley 1962.pdf (2.22 MB)

2013-7-18 20:50:32 上传

原作者也是给出n^2-2n+2

No3676671 发表于 2013-7-18 20:51
原作者也是给出n^2-2n+2

其实那个1不用太纠结的。。
要我看的话，就算法来说，最重要的是n^2部分。
具体的数字，其实是因为他有偷换概念之嫌：
他的第一个1是说“所有人都提出他们的1st”
第二部分n(n-2）说“每一次被拒绝”，最多拒绝n(n-2)次，则还剩下2n个
第三部分1是说，再提出1次，即可解决剩下的2n的问题。

所以2，3两部分的“次数”指的是Propose\reject的次数，而1的propose确实所有人（n人）都propose了自己的选择才算了1次，并且，和第二部分其实是重复计算了的。
所以第一部分的1是没有道理的

handsome8848 发表于 2013-7-19 01:12
其实那个1不用太纠结的。。
要我看的话，就算法来说，最重要的是n^2部分。
具体的数字，其实是因为他有 ...

我觉得关键是算多少个stages，不管是propose或reject。你可以看下面的例子，要5个stages,只能用n^2-2n+2，而n^2-2n+1算出来只有4个stages。

No3676671 发表于 2013-7-19 09:12
我觉得关键是算多少个stages，不管是propose或reject。你可以看下面的例子，要5个stages,只能用n^2-2n+2， ...

n^2-2n+2不是maximum step么。。。又没说所有的都要那么多～
况且确实我关心的是step（proposal/reject），而文章定义的是stage，只是定义不同，过程、思想都是一样的吧

No3676671 发表于 2013-7-19 09:12
我觉得关键是算多少个stages，不管是propose或reject。你可以看下面的例子，要5个stages,只能用n^2-2n+2， ...

而且这个例子跟我说得不矛盾吧。
我说的是(3-1)^2步后可以得到结果，他最后一行只是把结果又写了一遍呀～
可以理解为
1行 －－－排除得 2行
2行 －－－排除得3行
3行－－－排除得4行
4行－－－排除得5行

我看的是排除多少次可以得到结果，也就是(n-1)^2。他算得是一共有多少“行”，也就是1-5共5行

另一种思维方式，每一个stage只有一个男生被reject，从女生的角度来看，每一个女生最多reject(n-1)个男生，故（n-1）个女生总共reject (n-1)(n-1)次，再加上最后一次propose不用reject。所以一共有(n-1)(n-1)+1=n^2-2n+1个stages.