今天，在看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. 這篇婚戀交友推薦的文章時，里面有最大最小公平方面的內(nèi)容。特

我們經(jīng)常面臨給一組用戶劃分稀有資源的問題,他們都享有等價的權(quán)利來獲取資源,但是其中一些用戶實際上只需要比其他用戶少的資源.那么我們?nèi)绾蝸矸峙滟Y源呢?一種在實際中廣泛使用的分享技術(shù)稱作“最大最小公平分享”.直觀上,公平分享分配給每個用戶想要的可以滿足的最小需求,然后將沒有使用的資源均勻的分配給需要‘大資源’的用戶。

最大最小公平分配算法的形式化定義如下：

資源按照需求遞增的順序進行分配

與之對應(yīng)的可執(zhí)行定義：

考慮用戶集合1, …, n分別有資源需求x1, x2, …, xn.不失一般性,令資源需求滿足x1 <= x2 <= … <= xn.令服務(wù)器具有能力C.那么,我們初始把C/n資源給需求最小的用戶.這可能會超過用戶1的需求,繼續(xù)處理.該過程結(jié)束時，每個用戶得到的沒有比自己要求更多，而且，如果其需求得不到滿足，得到的資源也不會比其他用戶得到的最多的資源還少.我們之所以稱之為最大最小公平分配是因為我們最大化了資源得不到滿足的用戶最小分配的資源.

示例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.

到目前為止,我們假設(shè)所有的用戶擁有相同的權(quán)利來獲取資源.有時候我們需要給予一些用戶更大的配額.特別的,我們可能會給不同的用戶1, …, n關(guān)聯(lián)權(quán)重w1, w2, …, wn,這反映了他們間的資源配額.

我們通過定義帶權(quán)的最大最小公平分配來擴展最大最小公平分配的概念以使其包含這樣的權(quán)重:

下面的示例描述了如何實現(xiàn)?

示例2

有一四個用戶的集合,資源需求分別是4,2,10,4,權(quán)重分別是2.5,4,0.5,1,資源總能力是16,為其計算最大最小公平分配.

解決方法:第一步是標準化權(quán)重,將最小的權(quán)重設(shè)置為1.這樣權(quán)重集合更新為5,8,1,2.這樣我們就假裝需要的資源不是4份而是5+8+1+2=16份.因此將資源劃分成16份.在資源分配的每一輪,我們按照權(quán)重的比例來劃分資源,因此,在第一輪,我們計算C/n為16/16=1.在這一輪,用戶分別獲得5,8,1,2單元的資源,用戶1得到了5個資源,但是只需要4,所以多了1個資源,同樣的,用戶2多了6個資源.用戶3和用戶4拖欠了,因為他們的配額低于需求.現(xiàn)在我們有7個單元的資源可以分配給用戶3和用戶4.他們的權(quán)重分別是1和2,最小的權(quán)重是1,因此不需要對權(quán)重進行標準化.給予用戶3額外的7 × 1/3單元資源和用戶4額外的7 × 2/3單元.這會導(dǎo)致用戶4的配額達到了2 + 7 × 2/3 = 6.666,超過了需求.所以我們將額外的2.666單元給用戶3,最終獲得1 + 7/3 + 2.666 = 6單元.最終的分配是,4,2,6,4,這就是帶權(quán)的最大最小公平分配.

Reference：

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

http://www.tuicool.com/articles/VvuA3y