能不能形象的介紹一下 shapley 值法？

shapley值法

---

OMG，之前寫的不知為何莫名其妙的沒了，就簡略的寫算了

--------------------------------------------------------------------------------------------------

首先coalitional game with transferable utility的定義，表示為。對於參與者的集合，它的每個子集在這個博弈中的新名字是coalition，TU game的核心是賦予每個coalition一個金額，使得只要這個coalition包含的所有成員一致同意（形成這個coalition而不是加入其它的coalition，以及這個金額的分配方案），成員就可以獲得事前約定的金額。可以簡潔的表示為：

Shapley value指的是對一個人合作博弈, 對於每一個player，她應期望得到的支付，根據一系列公理：

1. efficiency: 首先應把pie做到最大，再考慮分配的問題。也就是：
2. Symmetry and null player property: 每個player的是完全由他們的對各個coalition的marginal contribution決定的。所以如果兩個人對各個coalition的marginal contribution總是相等，則我們有的。另一方面，如果一個人對各個coalition（包括）的marginal contribution都等於零，則。
3. 在所有的人合作博弈在實數域上構成的向量空間上，是一個線性函數。任取兩個合作博弈，和和實數我們有，對於任意：

令以邊際貢獻做解滿足除了symmetry外的所有條件，也就給所有參與者的編號一個permutation，我們就可能得到另一組解，所以只要把所有的permutation看成等可能的，重新定義期望為Shapley value就可以在保證原有條件滿足的基礎擁有symmetry。

但Shapley value的優良性質不止於此，它還是這個所有的人合作博弈在實數域上構成的向量空間上的唯一滿足以上公理的解。

還是利用向量空間的知識，我們其實只要證明Shapley value作為一個linear function在這個向量空間的某一組基上是唯一滿足上面公理的解就好。這麼一組基就是simple games。每一個coalition，，對應一個simple game，我們要求simple game的只能等於0，除了。這是一組基因為它們線性無關外，個數還正好等於向量空間的維數。

對於simple game，唯一symmetry和efficiency的解只有

而這正是Shapley value。

---

沙普利值（Shapley value），通過考慮各個代理（agent）做出的貢獻，來公平地分配合作收益。代理i的沙普利值是i對於一個合作項目所期望的貢獻量的平均值。

這裡有必要介紹一些背景。

一個合作項目C=&是由一些代理（Ag={1,2...,n}, n2），和每個代理在這個合作項目中所做的貢獻量的特徵方程v(C)=k（）表示。

下面我們結合一個事例來形象的介紹一下沙普利值是如何公平分配收益的。

今天加班，一個程序C=500行代碼需要編寫，今天產品經理找了三個程序猿來完成，按照完成量發獎金：

v({1})=100,v({2})=125,v({3})=50,

解釋：1號屌絲程序猿獨立能寫100行，2號大神程序猿獨立能寫125行，3號美女程序猿能寫50行。

v({1,2})=270,v({2,3})=350,v({1,3})=375,

解釋：1,2號合作能寫270行，2,3號合作能寫350行，1,3號合作能寫375行。

（你可以腦補：美女都是催化劑，屌絲都是潛力股）

v({1,2,3})=500

解釋：3個人共同能完成500行。

那麼合作過程將會有6種（|Ag|！）可能發生的情況需要考慮：

A. 1號程序猿邀請2號程序猿加入他組成S聯盟，1,2號邀請3號加入共同編寫。

B. 1號邀請3號加入成為S小組，2號加入S小組

C. 2號邀請1號加入成為S小組，3號加入S小組

D. 2號邀請3號加入成為S小組，1號加入S小組

E. 3號邀請1號加入成為S小組，2號加入S小組

F. 3號邀請2號加入成為S小組，1號加入S小組

那麼根據沙普利值法，合理分配，是否公平主要考察邊際貢獻。

沙普利法定義i加入組織S的邊際貢獻（marginal contribution）：

那麼，上述事例的邊際貢獻可表示為下表：

可能性 加入順序 1號的邊際貢獻 2號的邊際貢獻 3號的邊際貢獻

（Acknowledge: Dr. Ka Lok Man from XJTLU）

而代理i的沙普利值可由上述的邊際貢獻表示：

1號代理的沙普利值為：

2號代理的沙普利值為：

3號代理的沙普利值為：

總和為v({1,2,3})=500

那麼，1號屌絲程序猿應該獲得的獎金為總獎金的32.3%

2號大神程序猿應該獲得的獎金為總獎金的32.3%

3號美女程序猿應該獲得的獎金為總獎金的35.3%以上。

---

Shapley Value思路很牛逼，寫個例子你就明白了

A,B,C三位好友看完話劇準備拼車回家，拼車總價18元。如果不拼車A回家需要6元、B需要11元、C需要15元。

C說：咱們每人出6塊吧

A表示不服：我自己回家打車就6塊，拼車還6塊，憑啥？

由於A極力反對，這個車沒拼成。

A說要不咱們商量下吧，怎麼拼車最公平，要不這樣。第一段咱們平分、第二段B和C平分、第三段C自己掏錢了吧。

B和C笑了，我們為你繞道了，繞道這部分居然沒有定價？那不行！不拼。

B說：聽我出一套最公平的方案吧，想像A打車回家途中遇到B和C，當然也有可能先遇到C再遇到B，可能出現的組合如下：

補充信息：

A-C家直線價格是11元。

第5種情況B支付2元是怎麼算的：（11+6）-15 = 2

每一種情況出現的幾率是平等的，計算後

平均計算後A需支付2.83、B是5.33、C是9.83

B說完後大家都服了。

---

推薦閱讀：