Day 9 加權投票賽局與最小獲勝聯盟
作者按：前幾日已經用了太多集合論數學，決定暫時轉換到一些有有趣實例的主題。
投票賽局與加權投票賽局
先想像一個最簡單的投票場景：假設所有參與者的票數相同、投票權力相同，只要多數通過就能決定某項提案或政策。在這種情境下，我們考量的重點通常是：哪些人會投贊成票？哪些人會投反對票？以及要如何湊足「過半票數」。這樣的分析雖然簡單，但在真實世界裡，很多重要決策並不是「一人一票」。
舉例來說，在公司股東會上，每位股東持有的股份比例（股權）往往不同，因此他們在投票時擁有的影響力也不同。類似的狀況還可見於政治領域，例如議會席次比例不同的各黨派，或國際組織裡依據會員國人口／經濟規模等而分配投票權。這些「擁有不同權重的投票人」所組成的系統，便是所謂的「加權投票賽局（Weighted Voting Game）」。
換句話說，投票賽局聚焦在「如何在一群投票者之間進行投票決策」，而加權投票賽局則更進一步，允許每個玩家擁有「權重（weight）」，用來量化玩家投票過程中的影響力。只要有一群玩家組成的聯盟其權重總和達到指定的門檻，就能通過提案、分配資源或實現某個目標。這樣的框架讓我們能在理論上分析並預測：哪些玩家處於關鍵地位？哪些聯盟會最有可能達成共識？以及決策通過後，如何衡量各方的貢獻與收益分配。
接下來，我們就用股東會投票作為例子，來看看加權投票賽局的基本樣貌。
以股東會投票作為舉例
假設有一間公司，主要有三位持股不同的股東，情況如下：
- 股東 A：持股 50%
- 股東 B：持股 30%
- 股東 C：持股 20%
假設公司的決策規定是「只要有超過 50% 的股權支持，就能通過某項提案」。因此，我們可以看到：
- 若 A 單獨一人就已佔 50%，只要規定允許「大於等於 50%」即可通過，那麼 A 就能獨自決定；如果必須「大於 50%」，則要和 B 或 C 其中一位合作才行。
- 若 B 和 C 聯手，合計 30% + 20% = 50%，同樣能達到（或剛好達到）決策門檻。
- 若只有 B 或只有 C，任何一方都無法獨力通過提案。
透過這個例子可以體會，不同股東對投票結果的影響力並不相同，而他們之間如何結盟、是否能達到門檻，往往就決定了最終結果。
正式定義：加權投票賽局
給定一組玩家
以及對應的權重向量
這代表每個玩家所擁有的投票權重。
以及一個門檻（quota）
並將此賽局的特徵函數定義為
意思是當某聯盟的權重總和超過 q 時，便能發動投票所要表決的事項（通常就是通過議案），賦予效用 v(C) = 1。否則就什麼都無法完成，賦予效用 v(C) = 0。
從定義的角度看上面的舉例
玩家集合為三個股東：
對應的權重為
若規定只要「大於等於 50%」即可通過提案，便是設定
若規定是要「大於 50%」即可通過提案，便是設定
從這個形式化定義出發，能考慮以下問題：
- 哪些聯盟（子集合）可以成功通過提案？
- 哪些玩家在談判中會是關鍵？
- 是否存在只要再少一位成員就無法過關的「剛好贏」聯盟？（這就帶出了「最小獲勝聯盟」的概念）
接下來，我們進一步探討在加權投票賽局中常被關注的「最小獲勝聯盟」，並連結到為何在現實世界裡，人們傾向組成這類型的聯盟。
最小獲勝聯盟
在加權投票賽局中，一個聯盟 C ⊆ N 若能贏得投票（也就是該聯盟的權重總和 w(C) 大於 q），我們就稱它為「獲勝聯盟（winning coalition）」。然而，最小獲勝聯盟（minimal winning coalition） 有更嚴格的條件：
一個聯盟 C 若為「獲勝聯盟」，且對於聯盟中的任何玩家 i ∈ C，只要把他從聯盟中移除，剩下的聯盟 C - {i} 就無法達到贏的標準 q，那麼我們稱 C 為「最小獲勝聯盟」。
換言之，最小獲勝聯盟是一個「剛剛好能過門檻」的聯盟：沒有任何多餘的成員可以被排除，而仍保持勝利。以下用前面股東會範例來說明：
- 門檻 q = 50 的情況
- 聯盟 {A} 的權重為 50%，若規定「大於等於 50% 即可通過」，則它本身是獲勝聯盟，而且移除任何玩家也不會獲勝（因為聯盟就沒了），所以 {A} 是最小獲勝聯盟。
- 聯盟 {B,C} 的總權重是 30% + 20% = 50%，同樣能過門檻。若移除 B，只剩 C 的 20%；若移除 C，只剩 B 的 30%；都無法達到 50%，因此 {B,C} 也是最小獲勝聯盟。
- 聯盟 {A,B} 雖然權重和是 80%，也能贏，但它不是「最小」的，因為若移除 B，剩下 {A} 仍然是 50%，一樣贏得投票。所以 {A,B} 並非「最小獲勝聯盟」。
- 若門檻 q = 51 時
- {A} 的 50% 不足以通過提案，所以它不再是獲勝聯盟，更不是最小獲勝聯盟。
- {A,B} 的 80% 以及 {A,C} 的 70% 都能通過提案；不過因為去掉 B 或 C 後仍有 50%，不達 51%，就變成「去掉任何一位就不夠」，因此，它們都會是最小獲勝聯盟。
為何現實中常見「最小獲勝聯盟」？
在政治與商業世界裡，通常大家不會主動想要拉入「過多」的成員共同決策。原因包括：
- 分配利益：勝利聯盟若能獲得某種收益（如內閣席位、股份分紅等），成員越少，每個人的可分得量越多。
- 談判成本：成員越多，協調、談判以及意見整合的成本就越高，有時反而導致決策拖延或失敗。
- 穩定性：如果聯盟中有成員不是「關鍵」，該成員可能隨時被踢出或被忽略，反而容易引發聯盟內部分歧；相較之下，「最小獲勝聯盟」每位成員都不可或缺，會比較傾向互相支持、維持合作。
因此，在研究加權投票賽局時，「最小獲勝聯盟」是一個重要的分析焦點，可以用來解釋許多現實中的投票與決策行為，也可進一步延伸到「關鍵玩家」、「權力指數」或「收益分配」等議題。
Takeaway
加權投票賽局（weighted voting game）： 將不同大小的投票權力以「權重」形式表示，並用「門檻」來判定能否通過提案。
獲勝聯盟（winning coalition）： 任何聯盟只要其成員權重總和達到（或超過）門檻，就能成為獲勝聯盟。
最小獲勝聯盟（minimal winning coalition）： 在獲勝聯盟中，若移除任何成員後就無法達到門檻，則稱此聯盟為最小獲勝聯盟。它反映了「剛好過門檻」的合作狀態。
Reference
Chalkiadakis, Georgios, Edith Elkind, and Michael Wooldridge. _Computational aspects of cooperative game theory_. Morgan & Claypool Publishers, 2011.
