Day 4 Shapley Value 四大特徵：效率、對稱性、沒貢獻的玩家零收益與可加性
回顧 Shapley value
令 N = {1,2,…,n} 為玩家集合，v 為特徵函數（v(∅) = 0），假設此合作賽局為超加性賽局且結果的聯盟結構為全體聯盟。Shapley Value 是利用「所有可能的進場順序」之下，每位玩家對整體的邊際貢獻平均值來計算。具體步驟如下：
定義一個排列表示玩家進場順序：
總共會有 n! 種不同的進場順序（排列）。
再給定了一個進場順序 (a_1, a_2,..., a_n) 下，成員 i 的邊際貢獻是這樣計算的：
於是成員 i 在此順序下的邊際貢獻就是
接著，我們就對每個先後順序都計算成員 i 在該順序下的邊際貢獻，取平均即可
其中的求和符號要讓 sigma 跑遍所有可能的先後順序，因為成員有 n 為，所以總共有 n! 個邊際貢獻需要計算。此 phi_i (G) 即為成員 i 的 Shapley value。
對每個成員 i 都計算其 Shapley value 就可以得到在全體聯盟下，最後的效益分配向量：
效率 Efficiency
意義：Shapley value 滿足
代表整個博弈的總價值 v(N) 會被完整地分配給所有玩家，沒有浪費或剩餘。
證明
我們要證明對任一合作賽局 G（滿足 v(∅) = 0），有
根據定義，此等式可寫為
令某個排列為
注意到以下事實
原因是，等式左右邊都是把所有玩家在該排列下的所有邊際貢獻都加起來，只是一個按照順序加起來，另一個根據排列順序 a1, a2, ..., an 加起來。
我們還可以繼續往下寫：
於是回到原式，可以寫出
因為最後的求和符號會跑遍一共 n! 個排列順序。
證明完畢。
對稱性 Symmetry
對稱性：若對於任何不包含玩家 i 與 j 的聯盟 C⊆N，皆有
則稱玩家 i 與 j 在此博弈中「對稱」。也就是說，不論在哪個子集合 C 裡，將 i 加入或將 j 加入，其貢獻都一模一樣。
對於兩個對稱的玩家 i 與 j ，Shapley value 必定會分配給他們一樣的效益
證明
（非常複雜）
首先我們要證明的東西是，當 i 與 j 為對稱時，
我們就採用相減等於零的證明方法
注意到我們可以把排列分為兩類
於是上面的算式就可以寫為
意思是第一個求和符號跑遍所有 i 在 j 之前的排列，而第二個求和符號跑遍所有 j 在 i 之前的排列。
注意到對於每個 i 在 j 之前的排列
我們都可以對應到一個 j 在 i 之前的排列
也就是把 i 與 j 互換，其他排序保持不動。
我們來計算以下的值：
第一個括號的計算為：（藍色為要加上的效用，紅色為要減去的效用）
即
類似地，第二個括號要計算
即
好先注意到
以及
再來根據玩家 i 與 玩家 j 的對稱性，我們知道
因為上上一條告訴我們
最後了加油！我們需要證明
與
效用一樣，很簡單，兩者分別可寫成
其中 C 為不包含玩家 i 與 j 的聯盟，於是再次根據對稱性
到此為止，紅色（加法）與藍色（減法）的效用一對一對互相抵銷了。
我們得出結論
所以我們要證明的算式
（對於第一個求和符號中的每個排列，你都可以在第二個求和符號中找到一個對應的，也就是把 i 與 j 對調的排列，兩者做剛剛上面的計算會等於零）
證明完畢
沒貢獻的玩家不可得到收益 Dummy Player gets nothing
沒貢獻的玩家：若對於任何不包含 i 的聯盟 C⊆N，都有
則稱玩家 i 為 Dummy Player （沒貢獻的玩家）。
Shapley value 必定不會分配給 Dummy Player 任何效益
證明
對於任一排列（進場順序），玩家 i 的邊際貢獻定義為
由於 i 是 Dummy Player，對於任何不包含 i 聯盟 S（特別是 S=S_sigma (i) ），有
因此，對每個排列sigma 都有
最後我們可以計算 Shapley Value
證明完畢
可加性 Additivity
假設在同一個群體 N 上，有兩個不同的超加性賽局 G1, G2 分別有特徵函數 v 與 w ，並假設這些特徵函數下最後都會行程全體聯盟（也就很自然計算出 Shapley Value）。現在定義一個新賽局 G 有特徵函數
其實就是對每個聯盟 S 有特徵函數值
首先，因為 G1 與 G2 都是超加性，所以 G 也會是超加性，而其結果也會是全體聯盟。（證明在下面）
而如果要計算新賽局的 Shapley Value ，我們可以直接把原本 G1 與 G2 中的 Shapley Value 直接相加得到：
這就是 Shapley Value 的「可加性」
證明
首先讓我們證明「因為 G1 與 G2 都是超加性，所以 G 也會是超加性」
假設 S 與 T 為兩個不相交的聯盟，因為 G1 與 G2 都是超加性，所以
將兩個不等式相加，得到：
因此
證明完畢
其次讓我們證明可加性
根據 Shapley Value 的定義，對於賽局 G
而其中
因此
證明完畢
Takeaway
- 效率（Efficiency）：
證明了所有玩家的 Shapley Value 總和恰好等於大聯盟 v(N)v(N) 的總價值，確保博弈中產生的全部價值都被分配，沒有浪費或剩餘。
- 對稱性 (Symmetry)：
如果兩位玩家在不包含他們的任何聯盟中所帶來的額外效用相同，那麼他們的邊際貢獻在所有排列下都是相同的，最終的 Shapley Value 也相等，這反映了公平性。
- 沒貢獻的玩家 (Dummy Player gets nothing)：
當某位玩家無論在哪個聯盟中加入都不會增加額外價值時，其邊際貢獻均為零，因此 Shapley Value 為 0，保證了「沒貢獻的玩家不分配收益」的原則。
- 可加性 (Additivity)：
如果將兩個賽局的特徵函數 v 和 w 加總為新賽局 u = v + w，則新賽局中玩家的 Shapley Value 正好等於原來兩個賽局中該玩家的 Shapley Value 的和。這意味著，面對多個賽局或不同收益來源時，分配結果能保持一致且易於合併分析。
Reference
Branzei, Rodica, Dinko Dimitrov, and Stef Tijs. _Models in cooperative game theory_. Vol. 556. Springer Science & Business Media, 2008.
Chalkiadakis, Georgios, Edith Elkind, and Michael Wooldridge. _Computational aspects of cooperative game theory_. Morgan & Claypool Publishers, 2011.
