Day 11 加權投票賽局，與Banzhaf 類似的 Sharpley-Shubik 指數
Shapley–Shubik 指數 是專門用在分析「加權投票賽局」的經典方法。它的核心在於：若我們把所有玩家以各種順序排列，看看誰最常在「剛好跨過門檻」時出手，就能知道誰真正掌握了翻轉勝負的關鍵力量。
概念介紹
若所有玩家會「依序」加入某個聯盟，每種加入順序都具有相同的機會出現，那麼在各種排列順序中，「第一個使當前聯盟的票數達標」的那位玩家，就扮演了關鍵一票 (pivotal player)。藉由統計某玩家在所有排列裡成為關鍵一票的頻率，便能量化該玩家「影響決策成敗」的實際能力。
注意這裡是「各種『排列順序』中，第一個使當前聯盟的票數達標」
但是因為我們在「加權投票賽局」的設定，所以要計算「玩家扮演關鍵一票」就相當於計算形成 grand coalition 時的 Shapley Value 。因為玩家扮演關鍵一票時，會產生一點的邊際貢獻，其餘狀況則沒有邊際貢獻。
實例計算
讓我們用一個簡單例子說明：假設有四位玩家，權重分別是 A = 4, B = 3, C = 2,，總計 9 票，門檻 q = 6。
我們來計算三個玩家的 Shapley-Shubik value，需要考慮所有順序
1. (A, B, C)
第一次達到 6 以上是在第 2 步，關鍵：B
2. (A, C, B)
第一次達到 6 以上是在第 2 步，關鍵：C
3. (B, A, C)
關鍵：A
4. (B, C, A)
關鍵：A
5. (C, A, B)
關鍵：A
6. (C, B, A)
關鍵：A
因此可以算得
我們也計算這場賽局的 Banzhaf 指數：
- w(A) = 4。檢視所有 S⊆{B,C}：
- {B,C} 有 4 個子集：
- ∅ → sum = 0，0 + 4 = 4 (<6) → 不夠
- {B} → sum = 3，3 + 4 = 7 (≥6) → A 是關鍵
- {C} → sum = 2，2 + 4 = 6 (≥6) → A 是關鍵
- {B,C} → sum = 5，5 + 4 = 9 (≥6) → A 是關鍵
- A 能把 #2,3,4 這三個子集合翻盤
- A 的原始 Banzhaf 計數 = 3。
- 使用同樣的步驟得出 B 的原始 Banzhaf 計數 = 1
- 使用同樣的步驟得出 C 的原始 Banzhaf 計數 = 1
在正規化後，得到
主要差異及共通處
- 共同目標：Banzhaf 指數跟 Shapley–Shubik 一樣，都是用在衡量「加權投票賽局」裡玩家影響力的經典方法。
- 計算出發點不同
- Banzhaf：假設「所有可能的聯盟（子集合）等機率」出現，統計玩家加入後能把該聯盟從「不贏」變「贏」的次數。
- Shapley–Shubik：假設「所有玩家出場的排列順序等機率」，看誰在「第一次跨過門檻」時成為那張關鍵票。
Takeaway
- Shapley-Shubik 指數與 Banzhaf 計算的中心思想非常相似：計算翻盤次數
- Shapley-Shubik 指數與 Banzhaf 指數的不同之處在於：前者考慮了所有排列順序，而後者僅考慮了各種子集合可能
Reference
Chalkiadakis, Georgios, Edith Elkind, and Michael Wooldridge. _Computational aspects of cooperative game theory_. Morgan & Claypool Publishers, 2011.a
