公平分配收入的算法

Question

我正在寻找一种算法（最好是抽象的或非常清晰的 Py​​thon 或 PHP 代码），该算法允许基于以下约束在短期和长期内公平分配收入：

1. 每个传入金额将是一个整数。
2. 每个分配也将是一个整数。
3. 分配中的每个人都将获得以固定分数表示的收入分成。这些分数当然可以归入一个公分母（想象一下分母为 100 的整数百分比）。所有分子之和等于分母（百分比为 100）
4. 为了在短期内保持公平，人们i必须收到floor(revenue*cut[i])或ceil(revenue*cut[i])。编辑：让我强调ceil(revenue*cut[i])不一定等于1+floor(revenue*cut[i])，这是某些算法失败的地方，包括提出的算法（请参阅我对安德烈答案的评论）。
5. 为了保持长期公平，随着付款的累积，实际收到的削减必须尽可能接近理论削减，最好始终低于 1 个单位。特别是，如果总收入是公分数分母的倍数，那么每个人都应该收到相应倍数的分子。
6. [编辑]忘记补充一点，每次分配的总金额当然必须与收到的传入金额相加。

为了清楚起见，这里有一个示例。假设有三个人要分配收入，其中一个必须获得31%，另一个必须获得21%，第三个必须获得100-31-21=48%。

现在想象一下有80个币的收入。第一个人应该收到 或floor(80*31/100)硬币ceil(80*31/100)，第二个人应该收到 或floor(80*21/100)，ceil(80*21/100)第三个人应该收到floor(80*48/100)或ceil(80*48/100)。

现在想象一下有 120 个币的新收入。每个人都应该再次获得相应削减的下限或上限，但由于总收入 (200) 是分母 (100) 的倍数，因此每个人现在都应该有自己的确切削减：第一个人应该有 62 个硬币，第二个人应该有42个硬币，第三个人应该有96个硬币。

我想我已经为两个人的情况找到了一个算法来分配收入。情况如下（35% 和 65%）：

set TotalRevenue to 0
set TotalPaid[0] to 0
{ TotalPaid[1] is implied and not necessary for the algorithm }
set Cut[0] to 35
{ Cut[1] is implied and not necessary for the algorithm }
set Denominator to 100
each time a payment is received:
   let Revenue be the amount received this time
   set TotalRevenue = TotalRevenue + Revenue
   set tmp = floor(TotalRevenue*Cut[0]/Denominator)
   pay person 0 the amount of tmp - TotalPaid[0]
   set TotalPaid[0] = tmp
   pay person 1 the amount of TotalRevenue - TotalPaid[0]

我认为这个简单的算法满足了我的所有限制，但我还没有找到将其扩展到两个以上的人而不违反至少一个的方法。任何人都可以找出多人的扩展（或者证明它是不可能的）吗？

Answer 1

我认为这有效：

• 跟踪 a totalReceived，即已进入系统的总金额。
• 当钱添加到系统中时，将其添加到totalReceived。
• 放person[i].newTotal = floor(totalReceived * cut[i])。 编辑：这里有错误；感谢评论者。 这分配了一些钱。跟踪有多少，以了解还剩下多少“新钱”。需要明确的是，我们正在跟踪总金额中剩余的金额，并且直观地我们在每一步中重新分配全部金额，尽管实际上没有人的资金在一步与下一步之间出现下降。
• 您需要知道如何分配剩余的整数金额：应该少于numPeople剩余的金额。对于i从0到 的范围leftOverMoney - 1，增加person[i].newTotal1。实际上，我们给第一批人的每个人一美元leftOverMoney。
• 要计算一个人在此步骤中“收到”的金额，请计算person[i].newTotal - person[i].total。
• 要清理/完成，请设置person[i].total = person[i].newTotal。