簡要回顧：「排列式」的 Shapley Value
在 Day 3 與 Day 4，我們已經討論了 Shapley Value 的基礎定義，以及它所滿足的四大特徵（效率性、對稱性、沒貢獻者零收益、可加性）。
這裡先簡要回顧「排列式（Permutation）」的 Shapley Value。
令 N = {1, 2, ..., n} 為玩家（成員）的集合
特徵函數為 v 且 v(∅)=0
並假設此合作賽局為超可加賽局，且最後會形成全體聯盟
對於玩家 i ，排列式（Permutation）定義的 Shapley Value 為：
Day4 中以介紹的四大特徵
效率性：
對稱性：若玩家 i 與玩家 j 為對稱，則
沒貢獻者零收益：若 i 為沒貢獻者（無論加入何種子集合都不改變該子集合的效用），則
最後還有可加性：若 G1 與 G2 為兩個超可加遊戲且賽局最後形成全體聯盟，且 G 上的特徵函數為 G1 與 G2 的特徵函數的和，則
子集合加權式的 Shapley Value
雖然「排列式」定義很直觀，但在計算上常可使用另一種 子集合加權 的想法來簡化或理解。以下示範一個四人賽局的做法，再給出一般化公式。
四人賽局的舉例
令玩家集合為 N = {A, B, C, D}，並設定特徵函數 v 。假設此為超加性合作賽局且最後結果玩家組成全體聯盟。
我們來專注計算分配給 A 的效用該是多少，根據 Shapley Value 的精神，我們應該要把玩家 A 在所有可能的順序下的邊際效用算出來取平均。
注意到，因為要談「 A 的加入」，所以得先確定 A 原本不在該聯盟中。也就是 A 只能加入以下八種聯盟並造成邊際貢獻：
以空集合為例，邊際貢獻是
哪種排列會「觸發」A 對空集合的邊際貢獻？
答案是那些把 A 放在第一位（在空集合後面）的排列：
共有 3! = 6 種，因為一旦固定 A 為第一位，B, C, D 三人可以任意排列。
所以在「所有可能的先後順序」中， A 先進場（前面是空集合）的邊際貢獻會被算到 6 次，也就對應到上面列舉的這六種。
最後再算平均的時候，這個 A 對空集合的邊際貢獻就要算六次
好，接著來看加入 {B} 的邊際貢獻，以及「觸發排列」的個數：
當聯盟為 {B} 時，A 的邊際貢獻會是
那麼，有幾種排列能讓這個邊際貢獻被「觸發」？
答案是我們需要讓 B 在 A 的前面，然後 C 與 D 自然就會在 A 的後面：
那其實熟悉排列組合的讀者就知道，這個可以用以下乘法原理進行計數：
因此此邊際貢獻會在這兩個排列裡出現，所以在最後算平均的時候，這個 A 對 {B} 的邊際貢獻要算兩次。
以此類推，現在我們考慮玩家 A 對某不含 A 的聯盟 S 的邊際貢獻，並考慮他要被算幾次：
首先查閱特徵函數得值，得到
有幾種排列能讓這個邊際貢獻被「觸發」？答案跟上面一樣，當 S 的元素出現在 A 前面時：
根據排列組合的乘法原理，這樣的排列總共會有
於是，我們就知道 Shapley Value 應該是這樣計算：
其中前面的 1/n! 是取平均的分母。
子集合加權式 Shapley Value 之一般公式
將以上想法一般化，並重新寫可以得到：
令玩家集合為 N ，特徵函數為 v ，並假設此賽局為超加性賽局且最後形成全體聯盟。則玩家 i 的 Shapley Value 也可以由以下公式求得
這個公式就是 子集合加權式 定義的 Shapley Value。
兩者等價的數學證明
最後，我們要嚴謹地證明：「排列式」與「子集合加權式」的 Shapley Value 其實是同一件事，計算結果必然一致。
我們先前介紹了排序式的 Shapley Value 公式
P 代表 Permutation（排列）
然後上一節介紹了子集合加權式的 Shapley Value 公式
S 代表 Subset （子集合）
現在我們要說：這兩個公式算出來真的是一樣的！
（證明並不困難）
我們從排序式的 Shapley Value 出發，注意到
中的排列 sigma 會跑遍所有的排列順序。因此如果固定一個不含玩家 i 的集合 S ，則總是會有一些排列 sigma 滿足「在該排列下，i 前面的先行者等於 S」
我們於是把求和符號改寫：
對於每個在左邊被算到的排序 sigma ，令 S 為在該排列下的玩家 i 前面的先行者，則這個 sigma 就會被右邊的求和符號算到；對於每個在右邊的排序 sigma ，總是會在左邊被算到，因為左邊算了所有可能的排序 sigma。
於是我們就可以寫出
現在，被運算的
實際上與排序 sigma 無關，因此可以當作常數提出
現在我們來計算
其實他的意思就是問說有多少個排序 sigma 會滿足
這意思相當於有多少個排序 sigma 會滿足以下的先後順序
那根據乘法原理，答案是
因此
而最後可以寫出：
證明完畢
Takeaway
- 排序式的 Shapley Value 公式
- 子集合加權式的 Shapley Value 公式
- 兩種定義，可說是從不同的角度落實了 Shapley Value 的「公平分配」理念。
Reference
Branzei, Rodica, Dinko Dimitrov, and Stef Tijs. _Models in cooperative game theory_. Vol. 556. Springer Science & Business Media, 2008.
