最大最小公平算法

不念不忘少年蓝@ 2022-07-12 14:23 197阅读 0赞

今天，在看Tu K, Ribeiro B, Jensen D, et al. Online dating recommendations: matching markets and learning preferences\[C\]//Proceedings of the 23rd International Conference on World Wide Web. ACM, 2014: 787-792.  
这篇婚恋交友推荐的文章时，里面有最大最小公平方面的内容。特转载一下内容。  
转载内容来自：[http://www.cnblogs.com/549294286/p/3935408.html][http_www.cnblogs.com_549294286_p_3935408.html]

我们经常面临给一组用户划分稀有资源的问题,他们都享有等价的权利来获取资源,但是其中一些用户实际上只需要比其他用户少的资源.那么我们如何来分配资源呢?一种在实际中广泛使用的分享技术称作“最大最小公平分享”.直观上,公平分享分配给每个用户想要的可以满足的最小需求,然后将没有使用的资源均匀的分配给需要‘大资源’的用户。

*  最大最小公平分配算法的形式化定义如下：
 *  资源按照需求递增的顺序进行分配
 *  不存在用户得到的资源超过自己的需求
 *  未得到满足的用户等价的分享资源

与之对应的可执行定义：

考虑用户集合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.

到目前为止,我们假设所有的用户拥有相同的权利来获取资源.有时候我们需要给予一些用户更大的配额.特别的,我们可能会给不同的用户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,这就是带权的最大最小公平分配.

Reference：

[http://www.caip.rutgers.edu/~marsic/Teaching/CCN/minmax-fairsh.html][http_www.caip.rutgers.edu_marsic_Teaching_CCN_minmax-fairsh.html]

[http://www.tuicool.com/articles/VvuA3y][http_www.tuicool.com_articles_VvuA3y]

[http_www.cnblogs.com_549294286_p_3935408.html]: http://www.cnblogs.com/549294286/p/3935408.html
[http_www.caip.rutgers.edu_marsic_Teaching_CCN_minmax-fairsh.html]: http://www.caip.rutgers.edu/~marsic/Teaching/CCN/minmax-fairsh.html
[http_www.tuicool.com_articles_VvuA3y]: http://www.tuicool.com/articles/VvuA3y