Day 3 如果合作賽局的節果是全體聯盟，則該怎麼分配得到的效用呢？簡介 Shapley Value

上次我們提到了三種常見的賽局，分別是加性賽局、超加性賽局與次加性賽局。其中我們也分析了這三種賽局中的結盟傾向：

• 加性賽局：要不要合作並無太大差異，因為效用可以完美疊加。
• 超加性賽局：合作總比不合作好，所以最後容易形成全體聯盟
• 次加性賽局：單打獨鬥反而比合作好，所以不易出現聯盟。

在一個超加性賽局中，如果所有成員最終通力合作，就會形成「全體聯盟 (Grand Coalition)」。此時，我們獲得的總效用 v(N) 要如何在各玩家之間做分配？本篇要介紹一種廣受重視的分配方法：Shapley Value。

Shapley Value ：基於邊際貢獻的分配方式

我們從一個假想的超加性賽局出發：

假設有三個專業人士 A, B, C ，各自擁有不同的能力與資源。

單打獨鬥時，因為條件不具備或投入不足，無法產出任何效用：

若兩人組隊，會有一定程度的專業互補與成本分攤，所以能創造些許價值，但幅度有限：

然而，當 三位專業人士全部合作（全體聯盟）時，能夠把彼此專長完全結合，達成更大規模或更深層次的專案，產生 10 的總價值：

你可以透過窮舉法很快驗證出此合作賽局屬於超加性賽局，也就是合作比不合作好。

前面提到，當三位專業人士 A,B,C 全部合作時能創造 10 的高額價值；而兩兩合作時只能創造 3 或 4；單打獨鬥更是 0。因此，一旦合作賽局確立了「一起上」最有利，那麼該如何將這 10 的總效用分配給三人，才算「合理」與「公平」？

先來後到的問題

假設我們只看「誰最後加入使得效用增量最高」，就可能出現某些人一毛都拿不到的極端狀況。例如：

首先我們關心以下兩個效用值的話

那好像可以做出結論：因為 C 的加入，所以我們這個團隊的效用增加了 7 單位，根據「逆向的使用者付費原則」，我們應該給 C 分配 7 點的 payoff。同理，

好像可以做出結論：因為 B 的加入，所以我們這個團隊的效用增加了 3 點，而因此我們應該給 B 分配 3 點。最終可以寫出

此時 A 沒分到半毛，他於是很生氣的說「你這個按照進場順序分配根本不公平！如果要這樣算的話，那我以後都最後加入！大家以後都最後加入！」這個發言很有道理，考慮這兩個效用值

你可以做出結論：因為 A 的加入，所以這個團隊的效用增加了 6 點，所以你應該要給 A 分配 6 點的效用，而不是零點。

你發現了一個問題，這種根據「邊際貢獻」的分配方式會根據先來後到而產生非常大的不同，進而造成不公平。結論就是：僅以單一路徑或單一增量，去判斷某人「究竟貢獻多少」 往往會失真。

怎麼辦呢？Shapley 先生說了：「那就把所有先來後到的順序都考慮一遍，然後取個平均吧！」

Shapley 先生的建議：「把所有先來後到順序都考慮一遍，然後取平均」

A, B, C 三人，有六種先來後到的順序：

（這好像六個平行宇宙）

在第一個順序中： (A,B,C) 代表 A 最早來，C 最晚來

• A 的邊際貢獻：v({A}) − v(∅) = 0 − 0
• B 的邊際貢獻：v({A,B}) − v({A}) = 3 − 0 = 3
• C 的邊際貢獻：v({A,B,C}) − v({A,B}) = 10 − 3 = 7

在第二個順序中：(A, C, B)

• A 的邊際貢獻：v({A}) − v(∅) = 0 = 0
• C 的邊際貢獻：v({A,C}) − v({A}) = 3 − 0 = 3
• B 的邊際貢獻：v({A,B,C}) − v({A,C}) = 10 − 3 = 7

在第三個順序中： (B, A, C)

• B 的邊際貢獻: v({B}) - v(∅) = 0 - 0 = 0
• A 的邊際貢獻: v({A,B}) - v({B}) = 3 - 0 = 3
• C 的邊際貢獻: v({A,B,C}) - v({A,B}) = 10 - 3 = 7

在第四個順序中：(B, C, A)

• B 的邊際貢獻: v({B}) - v(∅) = 0 - 0 = 0
• C 的邊際貢獻: v({B,C}) - v({B}) = 4 - 0 = 4
• A 的邊際貢獻: v({A,B,C}) - v({B,C}) = 10 - 4 = 6

在第五個順序中：(C, A, B)

• C 的邊際貢獻: v({C}) - v(∅) = 0 - 0 = 0
• A 的邊際貢獻: v({A,C}) - v({C}) = 3 - 0 = 3
• B 的邊際貢獻: v({A,B,C}) - v({A,C}) = 10 - 3 = 7

在第六個順序中：(C, B, A)

• C 的邊際貢獻: v({C}) - v(∅) = 0 - 0 = 0
• B 的邊際貢獻: v({B,C}) - v({C}) = 4 - 0 = 4
• A 的邊際貢獻: v({A,B,C}) - v({B,C}) = 10 - 4 = 6

接下來，針對每位玩家分別把邊際貢獻加總後除以 3! = 6：

• A 的 Shapley Value

- 在六種排列中的貢獻分別為 0,0,3,6,3,6，總和 =18，平均為 18/6=3。

• B 的 Shapley Value

- 在六種排列中的貢獻分別為 3,7,0,0,7,4，總和 =21，平均為 21/6=3.5。

• C 的 Shapley Value

- 在六種排列中的貢獻分別為7,3,7,4,0,0，總和 =21，平均為 21/6=3.5。

於是最終的效益分配向量可以寫為：

此時三人的分配和正好是 10，完全符合「全體聯盟」的效用，也符合每位玩家在各種可能加入順序中的「平均邊際貢獻」。

簡而言之，Shapley Value 解決了「單一加入順序不公平」的問題，藉由「考慮全部可能順序」再求平均，讓結果更能反映所有人各自的貢獻。

數學上的 Shapley Value 定義

假設有一個合作賽局 G = (N, v) 滿足超可加性，其中 N 中有 n 位成員，而且最後形成全體聯盟（grand coalition）。現在要把總效益 v(N) 分配給 N 中的每個成員：

如同我們剛剛看到的： Shapley Value（夏普利值） 提供了一個經典且被廣泛接受的解法。它的核心思想是：每位玩家最終得到的效用，等於他在「各種可能進場順序」中，對整體聯盟帶來的「邊際貢獻」的平均值。

我們通常會用以下符號來代表一個進場順序：

例如

分別代表「照順序進場」、「全員反過來進場」以及「某個亂序進場（就看括號裡面數字怎麼排）」。

再給定了一個進場順序 (a_1, a_2,..., a_n) 下，成員 i 的邊際貢獻是這樣計算的：

於是成員 i 在此順序下的邊際貢獻就是

接著，我們就對每個先後順序都計算成員 i 在該順序下的邊際貢獻，取平均即可

其中的求和符號要讓 sigma 跑遍所有可能的先後順序，因為成員有 n 為，所以總共有 n! 個邊際貢獻需要計算。此 phi_i (G) 即為成員 i 的 Shapley value。

針對每個成員 i 都計算其 Shapley value 就可以得到在全體聯盟下，最後的效益分配向量：

小結與預告

本文先透過排列式定義，直觀詮釋何謂「平均邊際貢獻」。在後續內容中，將會介紹另一種常見的子集合加權公式

以及說明這兩種看似不同的計算方式，為何能得到相同結果。

之後我們也會更深入地探討 Shapley Value 的一些性質（效率、對稱性、Dummy Player gets nothing 以及可加性），並理解它為何是唯一同時滿足這些條件的解。

Takeaway

• 在超加性賽局中，若全體聯盟能帶來最大效用，就必須面對「如何分配」的核心問題。
• Shapley value 的基本精神為：每位玩家最終得到的效用，等於他在「各種可能進場順序」中，對整體聯盟帶來的「邊際貢獻」的平均值。

Reference

Chalkiadakis, Georgios, Edith Elkind, and Michael Wooldridge. _Computational aspects of cooperative game theory_. Morgan & Claypool Publishers, 2011.

封面縮圖：https://www.chinatimes.com/realtimenews/20200917005156-260408?chdtv