理論來歷
有這樣一個故事。
約克和湯姆結對旅遊。約克和湯姆準備吃午餐。約克帶了3塊餅,湯姆帶了5塊餅。這時,有一個路人路過,路人餓了。約克和湯姆邀請他一起吃飯。路人接受了邀請。約克、湯姆和路人將8塊餅全部吃完。吃完飯後,路人感謝他們的午餐,給了他們8個金幣。路人繼續趕路。
約克和湯姆為這8個金幣的分配展開了爭執。湯姆說:“我帶了5塊餅,理應我得5個金幣,你得3個金幣。”約克不同意:“既然我們在一起吃這8塊餅,理應平分這8個金幣。” 約克堅持認為每人各4塊金幣。為此,約克找到公正的夏普里。
夏普里說:“孩子,湯姆給你3個金幣,因為你們是朋友,你應該接受它;如果你要公正的話,那么我告訴你,公正的分法是,你應當得到1個金幣,而你的朋友湯姆應當得到7個金幣。”
約克不理解。
夏普里說:“是這樣的,孩子。你們3人吃了8塊餅,其中,你帶了3塊餅,湯姆帶了5塊,一共是8塊餅。你吃了其中的1/3,即8/3塊,路人吃了你帶的餅中的3-8/3=1/3;你的朋友湯姆也吃了8/3,路人吃了他帶的餅中的5-8/3=7/3。這樣,路人所吃的8/3塊餅中,有你的1/3,湯姆的7/3。路人所吃的餅中,屬於湯姆的是屬於你的的7倍。因此,對於這8個金幣,公平的分法是:你得1個金幣,湯姆得7個金幣。你看有沒有道理?”
約克聽了夏普里的分析,認為有道理,愉快地接受了1個金幣,而讓湯姆得到7個金幣。
在這個故事中,我們看到,夏普里所提出的對金幣的“公平的”分法,遵循的原則是:所得與自己的貢獻相等。
這就是夏普里值的意思。
數理概念
考慮這樣一個合作博弈:a、b、c 投票決定如何分配100萬,他們分別擁有50%、40%、10%的權力,規則規定,當超過50%的票認可了某種方案時才能通過。那么如何分配才是合理的呢? 按票力分配,a 50萬、b 40萬、c10萬;c向a提出:a70萬、b0、c30萬,b向a提出:a80萬、b20萬、c0……
權力指數:每個決策者在決策時的權力體現在他在形成的獲勝聯盟中的“關鍵加入者”的個數,這個“關鍵加入者”的個數就被稱為權利指數。
夏普里值( Shapley value):在各種可能的聯盟次序下,參與者對聯盟的邊際貢獻之和除以各種可能的聯盟組合。
次序 abc acb bac bca cab cba 關鍵加入者 b c a a a a
由此計算出a,b,c的夏普里值分別為4/6,1/6,1/6 所以a,b,c應分別獲得100萬的2/3,1/6,1/6 。
具體算法
N={a,b,c}
V(s)= 1, if s∈{{ab},{ac},{abc}} (因為必須超過50%的權利才能通過,50%也不能通過)
0, if s∈{空集,{a},{b},{c},{bc}}
可能排列 | a | b | c |
abc | 0 (v(a)-v(空集)) | 1(v(ab)-v(a)) | 0(v(abc)-v(ab) |
acb | 0(v(a)-v(空集)) | 0(v(abc)-v(ac)) | 1(v(ac)-v(a)) |
bac | 1(v(ab)-v(b)) | 0(v(b)-v(空集)) | 0(v(abc)-v(ab)) |
bca | 1(v(abc)-v(bc)) | 0(v(b)-v(空集)) | 0(v(bc)-v(b)) |
cab | 1(v(ac)-v(c)) | 0(v(abc)-v(ac)) | 0(v(c)-v(空集)) |
cba | 1(v(abc)-v(bc)) | 0(v(bc)-v(c)) | 0(v(c)-v(空集)) |
總共得票數 | 4 | 1 | 1 |
求平均值 | 4/6 | 1/6 | 1/6 |
計算公式
φi(n,v)={∑R〔vi(s)-v-1(s)〕}/n!
其中,R是n個參與人的排列,R有n!個,s為R中的一個排列,vi(s)為包括參與人i及在他之前的參與人集合組成的聯盟的支付值,v-1(s)為在他之前的參與人(不包括i)集合的聯盟的支付值。通過上述定義,我們可以看到:(1)vi(s)-v-i(s)是一種排列下,參與人i的邊際貢獻;
(2)參與人的夏普里值為他對聯盟的邊際貢獻之和除以各種可能的聯盟組合,因此φi(n,v)≤V;
(3)所有的參與人的夏普里值之和為v;
(4)夏普里值φii(n,v)為期望貢獻;
(5)夏普里值得到的前提是各博弈聯盟形成的可能性是均等的。