Day 5 Shapley Value：排列式與子集合加權式

簡要回顧：「排列式」的 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.