文档介绍：海盗分金博弈关键词:海盗分金;利益最大化; 喂鲨鱼一、问题提出 1 假设: 5 个海盗抢得 100 枚金币后,讨论如何进行公正分配。他们商定的分配原则是: (1 )抽签确定各人的分配顺序号码( 5,4,3,2,1); (2 )由抽到 5 号签的海盗提出分配方案,然后 5 人进行表决,如果方案得到半数或半数以上的人同意,就按照他的方案进行分配,否则就将 5 号扔进大海喂鲨鱼; (3 )如果 5 号被扔进大海,则由 4 号提出分配方案,然后由剩余的 4 人进行表决, 只有当达到半数的人同意时,才会按照他的提案进行分配,否则也将被扔入大海; (4 )依此类推。 2 条件: (1 )每个海盗都是很聪明的人,都能很理智的判断得失,从而做出选择; (2 )海盗之间不会相互串谋; (3) 海盗在自己的收益最大化的前提下乐意看到其他海盗被扔入大海喂鲨鱼。( 因为其他海盗被扔入大海喂鲨鱼符合每个海盗的最大化利益。) 3 问题: 第一个海盗提出怎样的分配方案才能够使自己的收益最大化? 二、问题解法利用逆推法: (1 )假设 5、4、3 号已被扔入海中,则 2 号的方案为 0、 100 ,2 号自己支持这个方案就满足半数或半数以上的人同意的条件, 所以这个方案必定能通过; (2)3 号的方案必为 1、0、 99,1 号在这个方案能得到 1 个金币比 2 号的方案 0 个金币要好,所以 1 号会同意这个方案,不管给多少金币给 2 号, 2 号都不可能支持这个方案, 因为如果 3 号死了, 2 号会得到 100 金币,所以 1、3 号支持,超过半数,这个方案必定能通过; (3)4 号的方案必为 0、1、0、 99, 因为只要半数人同意, 方案就会通过,4 号只要给 2号1 个金币,2 号就会同意, 方案也就能通过, 而若要 1 号同意, 至少要给 1号2 个金币, 要3 号同意则要 100 个金币,都不符合利益最大化; (4)5 号的方案必为 1、0、1、0、 98 ,这个方案要至少 3 人同意才能通过,所以除 5 号自己外, 还要有 2 人同意,在4 号的方案中 1 号和 3 号一个金币也得不到, 故只要各给他们1 个金币他们就会同意, 而若要 2 号同意则需 2 个金币,要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≤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