老唐笔记
我们经常面临给一组用户划分稀有资源的问题。他们都享有等价的权利来获取资源，但是其中一些用户实际上只需要比其他用户少的资源。那么我们如何来分配资源呢？一种在实际中广泛使用的分享技术称作“最大最小公平分享”。直观上，公平分享分配给每个用户想要的可以满足的最小需求，然后将没有使用的资源均匀的分配给需要‘大资源’的用户。
1. max-min fairness (MMF)
最大最小公平分配算法的形式化定义如下：
- 资源按照需求递增的顺序进行分配
- 不存在用户得到的资源超过自己的需求
- 未得到满足的用户等价的分享资源
与之对应的可执行定义：
考虑用户集合 1， …， n，分别有资源需求 x1，x2，…，xn。不失一般性，令资源需求满足 x1 <= x2 <= … <= xn。令服务器具有能力 C。那么，我们初始把 C/n 资源给需求最小的用户，这可能会超过用户 1 的需求，继续处理。该过程结束时，每个用户得到的没有比自己要求更多，而且，如果其需求得不到满足，得到的资源也不会比其他用户得到的最多的资源还少。我们之所以称之为最大最小公平分配是因为我们最大化了资源得不到满足的用户最小分配的资源。
示例1
有一四个用户的集合，资源需求分别是 2，2.6，4，5，其资源总能力为 10，为其计算最大最小公平分配。
解决方法：我们通过几轮的计算来计算最大最小公平分配。第一轮，我们暂时将资源划分成 4 个大小为 2.5 的。由于这超过了用户 1 的需求，这使得剩了 0.5 个均匀的分配给剩下的 3 个人资源，给予他们每个 2.66。这又超过了用户 2 的需求，所以我们拥有额外的 0.066… 来分配给剩下的两个用户，给予每个用户 2.5 + 0.66 … + 0.033… = 2.7。因此公平分配是：用户 1 得到 2，用户 2 得到 2.6，用户 3 和用户 4 每个都得到 2.7。
2. max-min weighted fairness
到目前为止，我们假设所有的用户拥有相同的权利来获取资源。有时候我们需要给予一些用户更大的配额。特别的，我们可能会给不同的用户 1, …, n 关联权重 w1, w2, …, wn，这反映了他们间的资源配额。
我们通过定义带权的最大最小公平分配来扩展最大最小公平分配的概念以使其包含这样的权重：
- 资源按照需求递增的顺序进行分配，通过权重来标准化
- 不存在用户得到的资源超过自己的需求
- 未得到满足的用户按照权重分享资源
下面的示例描述了如何实现。
示例2
有一四个用户的集合，资源需求分别是 4，2，10，4，权重分别是 2.5，4，0.5，1，资源总能力是 16，为其计算最大最小公平分配。
解决方法：第一步是标准化权重，将最小的权重设置为 1。这样权重集合更新为 5，8，1，2。这样我们就假装需要的资源不是 4 份而是 5 + 8 + 1 + 2 = 16 份。因此将资源划分成 16 份。在资源分配的每一轮，我们按照权重的比例来划分资源，因此，在第一轮，我们计算 C/n 为 16/16 = 1。在这一轮，用户分别获得 5，8，1，2 单元的资源，用户 1 得到了 5 个资源，但是只需要 4，所以多了 1 个资源，同样的，用户 2 多了 6 个资源。用户 3 和用户 4 拖欠了，因为他们的配额低于需求。现在我们有 7 个单元的资源可以分配给用户 3 和用户 4。他们的权重分别是 1 和 2，最小的权重是 1，因此不需要对权重进行标准化。给予用户 3 额外的 7 × 1/3 单元资源和用户 4 额外的 7 × 2/3 单元。这会导致用户 4 的配额达到了 2 + 7 × 2/3 = 6.666，超过了需求。所以我们将额外的 2.666 单元给用户 3，最终获得 1 + 7/3 + 2.666 = 6 单元。最终的分配是 4，2，6，4，这就是带权的最大最小公平分配。
参考文献
- http://www.cnblogs.com/549294286/p/3935408.html
- http://www.caip.rutgers.edu/~marsic/Teaching/CCN/minmax-fairsh.html
