前言：本帖可视为【毒酒滴冻鸭】兄的那贴【三人不吃亏分酒】的补充和拓展。首先贴上原帖地址： http://tieba.baidu.com/f?kz=762526555


我想大家在思考三人不吃亏分配问题同时，或许也尝试过思考如何解决多人不吃亏分配问题。当人数为2人时，分的人后拿是个既不错又简单明了的解法，普通人也很容易想到。而当人数为3人时，Selfridge–Conway discrete procedure（基本类似于原帖标准答案）给出了完美的解答，不过我们也可以看出，问题的复杂度已经上升了一个等级。而当人数>3时（即使为4），问题的复杂度将再次上升一个等级（分割次数可能无限增大）。以下将介绍Brams-Taylor procedure如何解决多人不吃亏平均分配问题。


声明：以下理论虽然不是本人原创（废话，要是能写出这些东西我也不再这混了），不过也是本人辛辛苦苦花了1个多小时翻译完的（由于没找到中文版本，只能自己汉化了，而且边翻还要边理解，累），希望转贴的请标注一下，珍惜别人劳动成果。
N人的不吃亏分蛋糕法(以4人为例)
                                              translated by dama

      Step 1：player 2把蛋糕分成4等份（在他看来是均等的），分别分给自己和其他人各一份。
      Step 2：询问除了player 2外每个玩家是否提出异议。（player A有异议当且仅当他认为其他某玩家所得到的一份比他大）
      Step 3：如果没人有异议，则每人得到step 1中分得的一份，结束。
      Step 4：否则，我们随便选择一个有异议的玩家，假设是player 1。Player 1指出其他玩家中他认为比他大的一份，记为A。player 1自己的一份记为B。
      说明：一旦我们有了A和B，则把其他两块混合，之后我们会用到。记住现在player 1认为A>B，player 2认为A=B。
       Step 5：player 1现在要确定一个正整数r>=10（r满足如下条件：如果把A任意分成r份，即使把player 1认为的最小的7份去掉，player 1还是认为A>=B）。
      说明：确定r的简单方法为：最小的7份必然不会比总共r份的平均大小的7倍大，所以player 1只需简单确定一个足够大的r使得7μ(A)/r<μ(A)-μ(B)，这里μ是player 1的价值观。
      Step 6：player 2把A分成r等份，同样把B分成r等份。
      Step 7：player 1从B中选择最小的3份，记为Z1，Z2，Z3。然后他可以从以下动作中2选1：从A中选择最大的3份（如果他认为这3份均严格大于Z1，Z2，Z3），并把它们按照他们3个中最小的一个来修剪（切除多余部分）；或者把A中最大的一份分为3等份。无论如何，记新的3份为Y1,Y2,Y3。
      说明：现在player 1认为Y1,Y2,Y3大小相等，并且均严格大于Z1，Z2，Z3（注意即使player 1选择了第二个方案结果也是如此）。Player 2认为Z1，Z2，Z3大小相等，并且每个均不小于Y1,Y2,Y3。
      Step 8：player 3观察这6份，选择他认为第一大的一份和第二大的一份，按照第二大的大小修剪，制造出他认为并列最大的2份。
      Step 9：按照player 4，3，2，1的顺序从现在的6份中各自选择自己认为最大或最大之一的一份，player 3必须选择他修剪过的一份（如果可能的话），player 2必须选择Z1，Z2，Z3中的一份，player 1必须选择Y1,Y2,Y3中的一份。
      说明：于是我们得到集合{X1，X2，X3，X4，L1}，之中{X1，X2，X3，X4}为4人自认为不吃亏的所得，L1为剩下的蛋糕总量。另外，player 1认为自己的X1严格大于player 2的X2，我们把其差值记为ε。
      Step 10：player 1确定一个正整数s，s满足[4μ(L1)/5]^s<ε，μ为player 1的价值观。
      说明：s决定了所有玩家将需要重复step 11-14的次数。其等价于将step 11-14重复到当player 1认为剩下的蛋糕总量比他与player 2的蛋糕的差值还要小的时候。注意如果规则改为当player 1认为剩下的蛋糕总量比他与player 2的蛋糕的差值还要小的时候喊停，一个盲目的player 1可能会使此步骤无限进行。
      Step 11：player 1把L1分成5等份。
      Step 12：player 2从这5份中选择最大3份，按照3份中最小一份进行修剪，制造出他认为并列最大的3份。
      Step 13：player 3从现有5份中选择最大的2份，按照2份中最小一份进行修剪，制造出他认为并列最大的2份。
      Step 14：按照player 4，3，2，1的顺序从现在的5份中各自选择自己认为最大或最大之一的一份，player 3，2选择的一份必须是自己修剪过（如果可能的话）。
      Step 15：重复step 11-14 s-1次，每一次的L1为上一次剩余的蛋糕总量。
      说明：我们得到集合{X1’，X2’，X3’，X4’，L2}，其中{X1’，X2’，X3’，X4’ }为4人自认为不吃亏的所得，L2为剩下的蛋糕总量。由于player 1认为X1’大于X2’+L2，我们可以说Player 1对于player 2有绝对优势。我们把这种绝对优势集合记为IA，把Player 1对于player 2有绝对优势记为（1，2）∈IA。
      Step 16：player 2把L2分为12等份。
      Step 17：每个玩家可以宣称自己是A型（当其认为所有12份大小相等），或是D型（当其认为所有12份大小有差别）。Player 2显然是A型的。
      Step 18：如果D×A∈IA，则我们只需把这12份平分给所有A型的玩家。若如此，则结束。
      Step 19：否则，我们选择一对不符合D×A∈IA玩家（i，j），然后回归step 4，并把player i当作player 1，player j当作player 2，L2作为待分的蛋糕。
      Step 20：重复step 5-18。
      说明：每一次我们完成step 15的时候，集合IA则增加了一对元素。注意由于D×A∈{1，2，3，4}×{1，2，3，4}，且IA∈{1，2，3，4}×{1，2，3，4}，我们最多在重复16次后必然得到D×A∈IA。所以，我们认为这其中的某一次step 18必然能得到每个人都自认为不吃亏的分配结果。