800论坛币悬赏博弈最优值问题

10# hblzy 合作就不存在分配问题，因为你的条件中没有合作的比例。只存在合作与不合作，以及多少是合作，多少是不合作？多少是和什么人合作的问题。而这些问题，这个线性规划应该是能够说明的。
我不明白你为什么认为这个线性规划还不能说明你的问题？

hblzy 发表于 2010-1-23 09:48
这个线性规划我想过做过，答案明显不对，因为没有涉及合作后怎么分配的变量，而手工做的53/21
就是不知道是不是最小值。用线性规划来解好像要把分配比例从0----1全部模拟出来，看谁最小值最小，这个比例才整体最优。我从没接触过这种，优化中的最优，搞得头都有点痛了，但文章中涉及这样一个问题，又绕不过去，呵呵。
     
    尽管没有解决问题，谢谢你的热心帮助，你发个100出售帖我来买

请告诉我，你做出来的答案，我们分析一下！
我不认为我的这个线性规划是对的，但我暂时还没有找到问题所在，希望能和楼主好好探讨探讨！

另，这个规划不宜是0-1规划，最好是线性规划。0-1规划一个解比较困难，第二可能限制了获得最优解的可能性！

可以用博弈方法或数学方法，数学方法如下：
我是首先判断三人合作优于其他形式，设其中一位所得到的分配比例最大，（所得比例为一变量），他先出局，得到剩余二人所分的产品数量和三人合作所需的时间，（都含参数）而两人合作又优于单干，合作时可以找到一个固定的最优比例，又有一人出局，最后一人单干直至满足消费，得到一个含分配比例为参数的表达式，再在约束范围里求极值。
   就是有点麻烦，但是能解出来。
    合作与不合作的判断用是同样时间内单干与合作按比例分配得到的产出大小来判断，是帕累托条件下的自愿选择。所以约束较多。

转坛友wellwell提供的答案：
设：将具体的数字表示为甲乙丙三人合作博弈的特征函数：v(1),v(2),v(3),v(12),v(13),v(23),v(123).——v(ij)表示i,j两人合作的单位生产数量。显然这个博弈是超可加的。现在每个人均想得到a个单位，问如何合作，如何分配合作所得使得总生产时间最短。
（1）：如果核心非空，即0.5[v(12)+v(13)+v(23)]>=v(123)
i：如果（v(123)/3，v(123)/3，v(123)/3）在核心内最好了，就是前一个帖子说的，1：1：1的比例生产3a个单位，然后平分；
ii：如果（v(123)/3，v(123)/3，v(123)/3）不在核心内，在核心内选择使得min[x,y,z]/max[x,y,z]最大的分配（x0, y0, z0）我们不妨设z0最大
三人合作生产a*(x0+y0+z0)/z0个，按比例(x0, y0, z0）分配，此时丙得到a个，退出。甲得到a*x0/z0,乙得到a*y0/z0
此时甲还需要a-a*x0/z0,记为b;乙还需要a-a*y0/z0,记为c 注意到2人合作博弈的核心总是非空的，如果（v(12)b/(b+c), v(12)c/(b+c)）在核心中，最好了。甲乙合作生产b+c个，按照比例b:c分配，结束；如果（v(12)b/(b+c), v(12)c/(b+c)）不在核心中，在核心中选择最接近比例b:c的分配——对于2人博弈，只需要考查
(v(1), v(12)-v(1))与(v(12)-v(2), v(2))这两个分配就可以了。不妨设是v(1)： v(12)-v(1)=b'：c与b:c比较接近。二人合作生产b'+c个(若b'<b)或b(b'+c)/b'个(若b'>b)，按照比例b'：c分配。此时甲(b'>b)或乙(b'<b)满足，剩余一人独自生产不足部分。
（2）：如果博弈没有核心。我们考虑两两合作的情形。用文字描述太困难。解释一下变了直接上方程。ti——i单干时间；tij——ij合作时间。因为核心空，所以无法实现三人合作。单干时无所谓比例，我们设x,y,z分别为在联盟12，13，23中第一个人分配的比例,对应的，第二个人的分配比例为1-x,1-y,1-z.我们有如下线性规划
min u=t1+t2+t3+t12+t13+t23
约束于
t1*v(1)+x*t12*v(12)+y*t13*v(13)=a
t2*v(2)+(1-x)*t12*v(12)+z*t23*v(23)=a
t3*v(3)+(1-y)*t13*v(13)+(1-z)*t23*v(23)=a
(x*v(12), (1-x)v(12))属于2人博弈的核心，即在(v(1), v(12)-v(1))与(v(12)-v(2), v(2))之间
(y*v(13), (1-y)v(13))同上
(z*v(23), (1-z)v(23))同上
所有变量>=0

和我自己的方法大同小异， 先判断再定分配比例，直到圈子退化为一。
      最后对时间加总得到答案
不过我的判断方法不一样，我的是：
    i为总个体数目，ei为个体i单干效率，ei1,i2为个体i1，i2之间合作效率，(i1<=i,i2<=i).  ei1,i2,i3为三个个体之间的合作效率，以此类推直到ei1,i2......,ii全部合作的效率。
   

     合作圈子大小的判定，必要条件：所有的eA + e(非A)>=ei1,i2.....ii,（j=1...i),A为全集的任意一个子集，再加上：
max[(ei1,i2...ii)/i .(ei1,...i(i-1))/(i-1),......(ei1,i2)/2, ei)]=ei1,i2...ii)/i 时，存在全员合作。否则，i退化为i-1,一直这样操作，直到出现满足这个不等式的情况，设退化m次，出现满足这个不等式，则最大的合作人数为i-m.

   分配方法是一样的，第一步判断，确定是平均分配还是非平均分配，若是非平均分配，再确定最大分配比例和首先出局的个体，退化后继续这样步骤，直到人数为1为止。