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 個子集：

1. 1. 1. ∅ → sum = 0，0 + 4 = 4 (<6) → 不夠
      2. {B} → sum = 3，3 + 4 = 7 (≥6) → A 是關鍵
      3. {C} → sum = 2，2 + 4 = 6 (≥6) → A 是關鍵
      4. {B,C} → sum = 5，5 + 4 = 9 (≥6) → A 是關鍵

• • A 能把 #2,3,4 這三個子集合翻盤
  • A 的原始 Banzhaf 計數 = 3。
• 使用同樣的步驟得出 B 的原始 Banzhaf 計數 = 1
• 使用同樣的步驟得出 C 的原始 Banzhaf 計數 = 1

在正規化後，得到

主要差異及共通處

1. 共同目標：Banzhaf 指數跟 Shapley–Shubik 一樣，都是用在衡量「加權投票賽局」裡玩家影響力的經典方法。
2. 計算出發點不同

• • 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