海盗分金博弈

1、- -海盗分金博弈关键词 ：海盗分金；利益最大化；喂鲨鱼一、问题提出1 假设：5 个海盗抢得100 枚金币后，讨论如何进行公正分配。他们商定的分配原则是：（ 1）抽签确定各人的分配顺序号码（5， 4， 3， 2， 1） ；（ 2）由抽到5 号签的海盗提出分配方案，然后5 人进行表决，如果方案得到半数或半数以上的人同意，就按照他的方案进行分配，否则就将5 号扔进大海喂鲨鱼；（ 3）如果5 号被扔进大海，则由4 号提出分配方案，然后由剩余的4 人进行表决，只有当达到半数的人同意时，才会按照他的提案进行分配，否则也将被扔入大海；（ 4）依此类推。2 条件：（ 1）每个海盗都是很聪明的人，都能很理智的

2、判断得失，从而做出选择；（ 2）海盗之间不会相互串谋；（ 3） 海盗在自己的收益最大化的前提下乐意看到其他海盗被扔入大海喂鲨鱼。（因为其他海盗被扔入大海喂鲨鱼符合每个海盗的最大化利益。）3 问题：第一个海盗提出怎样的分配方案才能够使自己的收益最大化？二、问题解法利用逆推法：（ 1）假设 5、 4、 3 号已被扔入海中，则2 号的方案为0、 100， 2 号自己支持这个方案就满足半数或半数以上的人同意的条件，所以这个方案必定能通过；3 号的方案必为1、 0、 99， 1 号在这个方案能得到1 个金币比2 号的方案0 个金币要好，所以1 号会同意这个方案，不管给多少金币给2 号， 2 号都不可能支

3、持这个方案，因为如果3 号死了，2 号会得到100 金币，所以1、 3 号支持，超过半数，这个方案必定能通过；4 号只要给4 号的方案必为0、 1、 0、 99，因为只要半数人同意，方案就会通过，2 号 1 个金币，2 号就会同意，方案也就能通过，而若要1 号同意，至少要给1 号 2 个金币，要 3 号同意则要100 个金币，都不符合利益最大化；5 号的方案必为1、 0、 1 、 0、 98，这个方案要至少3 人同意才能通过，所以除5号自己外，还要有 2 人同意，在 4 号的方案中1 号和 3 号一个金币也得不到，故只要各给他们 1 个金币他们就会同意，而若要 2 号同意则需2 个金币，要 4

4、 号同意则需100 金币， 根据利益最大化要求，给1 号和 3 号各 1 个金币，而给2 号和 4 号 0 个金币。故答案是：1 、 0、 1、 0、 98。三、问题扩展现在假设是N 个海盗分M 个金币，其他条件不变，则 N 号海盗应该提出怎样的分配方案？（ 1）当2 N 2M+2 时，从上述解法推知，2k 号的海盗分给号码是小于2k 的偶数号的海盗 1 个金币，自己拿剩余的M-k+1 个金币，其他人0 个，显然这里k=1,2,3, ,M+1;2k+1 号的海盗分给号码是小于2k+1 的奇数的海盗1 个金币，自己拿剩余的M-k 个金币，其他人0 个，显然这里k=1,2,3, ,M 。所以就有2

5、 N 2M+2 时，N=2k （k=1,2,3, ,M+1）， N 号海盗提出的方案应为（0,1,0,1, , 0, M-k+1 ） ；N=2k+1 （k=1,2,3, ,M）， N 号海盗提出的方案应为（1,0,1,0, , 1,0, M-k） 。（ 2）当N 2M+2 时，就会发现金币不够分，再用上面的方法就不行了。N=2M+3 时，需要M+2 个人同意才满足半数或半数以上的人同意的条件，前2M+2 个人中号码是奇数的海盗有M+1 个，现在只有M 个金币，故只有分到金币的M 个人会同意，再加上他自己，共有M+1 个人同意，少于半数，所以他会被扔进大海里喂鲨鱼；N=2M+4 时，需要M+2

6、个人同意才满足半数或半数以上的人同意的条件，前2M+2 个人中号码是奇数的海盗有M+1 个，现在只有M 个金币，故只有分到金币的M 个人会同意，2M+3 号也一定会同意（不同意的话，就轮到他做决策，他一定会被扔进大海里喂鲨鱼），再加上他自己，共有 M+2 个人同意，刚好半数，他的方案是（ 1,0,1,0, , 1,0,0,0,1, , 1,0, 1,0,0,0） ，即给从前M+1 个号码是奇数的海盗中任取M 个给 1 个金币，其他人给0 个；N=2M+5 时， 需要 M+3 个人同意才满足半数或半数以上的人同意的条件，只要给 2M+4号方案中得益是0 的人 1 个金币， 他们就会同意（当然也可

7、以给得1 个金币的人多于1 个金币，但这不符合利益最大化条件），还有就是不能确定前2M+2 个人中号码是奇数的海盗中哪一个得0 个金币，故这一个也应该剔除，所以应该从前2M+2 个人中号码是偶数的海盗（ M+1 个） ， 2M+3 ， 2M+4 号海盗中（即2M+4 号方案中得益一定是0 的人，共M+3 个）任选 M 个给 1 个金币，其他得0 个，加上自己共M+1 个同意，故2M+5 号海盗会被扔进大海里喂鲨鱼；N=2M+6 时， 需要 M+3 个人同意才满足半数或半数以上的人同意的条件，只要给 2M+4 TOC o 1-5 h z 号方案中得益一定是0 的人 1 个金币，他们就会同意，所以

8、应该从M+3 个海盗中任选M 个给 1 个金币，其他得0 个， 2M+5 号一定会同意，加上自己共M+2 个同意，故2M+6 号海盗也会被扔进大海里喂鲨鱼；N=2M+7 时， 需要 M+4 个人同意才满足半数或半数以上的人同意的条件，只要给 2M+4号方案中得益一定是0 的人 1 个金币，他们就会同意，所以应该从M+3 个海盗中任选M 个给 1 个金币，其他得 0 个， 2M+5、 2M+6 号一定会同意，加上自己共M+3 个同意， 故 2M+7号海盗还是会被扔进大海里喂鲨鱼；N=2M+8 时， 需要 M+4 个人同意才满足半数或半数以上的人同意的条件，只要给 2M+4号方案中得益一定是0 的

9、人 1 个金币，他们就会同意，所以应该从M+3 个海盗中任选M 个给 1 个金币，其他得0 个， 2M+5、 2M+6、 2M+7 号一定会同意，加上自己共M+4 个同意，刚好半数，他的方案是从前2M+2 个人中号码是偶数的海盗(M+1 个) ， 2M+3 ， 2M+4 号海盗中(即2M+4 号方案中得益一定是0 的人，共M+3 个)任选M 个给 1 个金币，其他得0个；依次类推，可以得到：N=2M+2 k( k=2,3,4, )时，需要M+2 k-1 个人同意才满足半数或半数以上的人同意的条件，只要给2M+2 k-1 号方案中得益一定是0 的人 1 个金币，他们就会同意，所以应该从M+2k-

10、1-1 个海盗中任选M 个给 1 个金币， 其他得 0个， 2M+2k-1+1 、 2M+2k-1+2、 、2M+2k-1号一定会同意，加上自己共M+2 k-1 个同意，刚好半数，他的方案是从前2M+2 个人中号码是奇数或偶数( k 是偶数时这里是奇数，k 是奇数时这里是偶数)的海盗， 2M+3， 2M+4， ，2M+2 k-1 号海盗中(共M+2 k-1-1 个)任选M 个给 1 个金币，其他给0 个；N 2M+2 k( k=2,3,4, )时，他一定会被扔进大海里喂鲨鱼。偶数(k是偶数时这里是奇数，k是奇数时这里是偶数)的海盗，2M+3 ， 2M+4 ， ， 2M+2 k-1 号海盗中(共

11、M+2 k-1-1 个)任选M个给 1个金币，其他给0个。从前 M+1 个号码是奇数的海盗中任取M 个给 1 个金币，其他人给 0个。综上，我们可以得到：当 2 N 2M+2 时，N=2k (k=1,2,3, ,M+1)， N 号海盗提出的方案应为(0,1,0,1, , 0, M-k+1 ) ；N=2k+1 (k=1,2,3, ,M)， N 号海盗提出的方案应为(1,0,1,0, , 1,0, M-k) ；当 N 2M+2 时，N=2M+2 k( k=2,3,4, ) N 号海盗提出的方案应为从前2M+2 个人中号码是奇数或偶数( k 是偶数时这里是奇数，k 是奇数时这里是偶数)的海盗，2M+

12、3， 2M+4，2M+2号海盗中(共M+2 k-1-1 个)任选M 个给 1 个金币，其他给0 个；N 2M+2 k( k=2,3,4, )时，他一定会被扔进大海里喂鲨鱼。四、问题变式方案“得到半数或半数以上的人同意”改为“得到多于半数的人同意”，其他不变。利用逆推法：0，0，98)或98)( 1)假设 5、 4、 3 号已被扔入海中，则2 号一定会被扔进大海里喂鲨鱼；3 号的方案为(0,0,100,0,0) ，若 3 号被扔进大海里喂鲨鱼，则2 号也会被扔进大海里喂鲨鱼，所以无论如何，2 号一定会同意；4 号的方案为(1,1, 0,98,0) ，因为必须要有3个人同意才行，故4号还需要争取2

13、个人同意，结合3 号的方案得出这样的结果；5 号的方案为(2,0, 1,0,97)或(0,2 ,1,0,97) ， 5 号还需要争取2 个人同意，结合4号的方案，可以给 3 号一个金币而得到3 号的支持，还需要一个名额，争取到 1 号或 2 号都需要 2 个金币，而争取到4 号要 99 个金币，故只需给1 号或 2 号 2 个金币就行。故得出答案是：( 2,0, 1,0,97)或(0,2 ,1,0,97) 。五、变式扩展现在假设是N 个海盗分M 个金币，其他条件同变式，则 N 号海盗应该提出怎样的分配方案？若干个海盗分100 个金币的分配方案海盗方案1234567891011121314300

14、100411098521097622109572210958222109392221093102222109111222210911222222108913222221089142222221087注：阴影部分表示从n 个任选 (n+1)/2 个2，其他为0( 1)当M=2k(k=3,4,5, )时，N M+1 ，方案为前N-3 个任取 N/2-1 个给 2 个金币，第N-2 个给 1 个金币，第N-1 个给 0 个金币，自己得M-2N/2+1 个金币；N=M ，方案为前M-3 个中任取M/2-1 个给 2 个金币，第M-2 个给 1 个金币，第M-1个得 0 个，自己得1 个金币；N=M+1

15、 ， 方案为前M-2 个海盗和M 号海盗中任取M/2-1 个给 2 个金币，第 M-1 个给 1个金币，自己得1 个金币；N=M+2 ， M+2 号海盗要想获得其他人的支持都需要付2 个金币，M 个金币最多只能获得 M/2 个人的支持，加上自己共M/2+1 个同意，刚好是总数的一半，所以M+2 号会被扔进大海里喂鲨鱼；N=M+3 ，同 M+2 号的思考方式，再加上M+2 号会无条件支持，共M/2+2 个同意，刚 TOC o 1-5 h z 好超过总数的一半，所以M+3 方案为从前M+1 个海盗中任取M/2 个给 2 个金币，第M+2个给 0 个金币，自己得0 个金币；N=M+4 ，给 M+2、

16、 M+3 号海盗各1 个金币，从前M+1 个海盗中任取M/2-1 个给 2 个金币，共M/2+2 个同意，所以M+4 号会被扔进大海里喂鲨鱼；N=M+5 ，给M+2、M+3 号海盗各1 个金币，从前M+1 个海盗中任取M/2-1 个给2 个金币，自己得0 个， M+4 号会无条件支持，共M/2+3 个同意，超过总数的一半；N=M+6 ，给M+4、M+5 号海盗各1 个金币，从前M+3 个海盗中任取M/2-1 个给2 个金币，自己得0 个，共 M/2+2 个同意，不到总数的一半，所以M+6 号会被扔进大海里喂鲨鱼；N=M+7 ，给 M+4、 M+5 号海盗各1 个金币，从前M+3 个海盗中任取M

17、/2-1 个给 2 个金币，自己得0 个， M+6 号会无条件支持，共M/2+3 个同意，不到总数的一半，所以M+7号会被扔进大海里喂鲨鱼；N=M+8 ，给 M+4、 M+5 号海盗各1 个金币，从前M+3 个海盗中任取M/2-1 个给 2 个金币，自己得0 个， M+6、 M+7 号会无条件支持，共M/2+4 个同意，不到总数的一半，所以 M+8 号会被扔进大海里喂鲨鱼；N=M+9 ，给 M+4、 M+5 号海盗各1 个金币，从前M+3 个海盗中任取M/2-1 个给 2 个金币，自己得0个， M+6、 M+7、 M+8 号会无条件支持，共M/2+5 个同意，超过总数的一半；（ 2）当M=2k

18、+1（k=2,3,4, ）时， TOC o 1-5 h z N M+2，方案为前N-3 个任取 N/2-1 个给 2 个金币，第N-2 个给 1 个金币，第N-1个给 0 个金币，自己得M-2N/2+1 个金币；N=M+1 ，方案为前M-2 个中任取M/2-1 个给 2 个金币，第M-1 个给 1 个金币，第M个得 0 个，自己得0 个金币；N=M+2 ，给 M 、 M+1 号 1 个金币，M+2 号海盗要想获得其他人的支持都需要付2 个金币， M 剩余 M-2 个金币最多只能获得（M-1 ） /2-1 个人的支持，加上自己共（M-1 ） /2+2个人同意，超过半数，方案为前M-1 个任取（M

19、-1 ） /2-1 个给 2 个金币，M、 M+1 号 1 个金币，自己得1 个金币；N=M+3 ， M+3 号海盗要想获得其他人的支持都需要付2 个金币，M 个金币最多只能获得（ M-1 ） /2 个人的支持，加上自己共（M-1 ） /2+1 个人同意，不足半数，所以M+3 号会被扔进大海里喂鲨鱼；N=M+4 ， M+3 会无条件支持，M+4 号海盗要想获得其他人的支持都需要付2 个金币，M 个金币最多只能获得（M-1 ） /2 个人的支持，加上自己共（M-1 ） /2+2 个人同意，不足半数，所以M+3 号会被扔进大海里喂鲨鱼；N=M+5 ， M+3 、 M+4 会无条件支持，M+5 号海

20、盗要想获得其他人的支持都需要付2 个金币， M 个金币最多只能获得（M-1 ） /2 个人的支持，加上自己共（M-1 ） /2+3 个人同意，超过半数，分配方案是前M+2 个任取（M-1 ） /2-1 个给 2 个金币，M+3 、 M+4 号 0 个金币，自己得 1 个金币；N=M+6 ，分给 M+3 、 M+4 号 1 个金币就能得到他们的支持，而要想获得其他人的支持都需要付2 个金币， 剩余 M-2 个金币最多只能获得（ M-1 ） /2-1 个人的支持，加上自己共（ M-1 ）/2+2 个人同意，不足半数，所以M+6 号会被扔进大海里喂鲨鱼；N=M+7 ， M+6 会无条件支持，分给M+

21、3 、 M+4 号 1 个金币就能得到他们的支持，而要想获得其他人的支持都需要付2个金币，剩余M-2 个金币最多只能获得（M-1 ） /2-1 个人的支持，加上自己共（M-1 ） /2+3 个人同意，不足半数，所以M+7 号会被扔进大海里喂鲨鱼；N=M+8 ， M+6 、M+7 会无条件支持，分给M+3、 M+4 号 1 个金币就能得到他们的支持， 而要想获得其他人的支持都需要付2 个金币， 剩余 M-2 个金币最多只能获得（ M-1 ） /2-1个人的支持，加上自己共（M-1 ） /2+4 个人同意，不足半数，所以M+8 号会被扔进大海里喂鲨鱼；N=M+9 ， M+6 、M+7 、 M+8 会无条件支持，分给M+3