Day 7 探究凸性賽局（Convex Games）：邊際貢獻遞增如何保證核心不為空
更多賽局的核心 Core
回顧核心 Core 的定義
假設賽局 N = {1, 2, ..., n} 是超可加且最後形成全體聯盟
考慮一個效益分配向量 payoff vector
若此效益分配向量滿足以下兩件事
1. 效率性原則
2. 對於所有的（次）聯盟 S ⊆ N, 要滿足
則我們說此效益分配向量是屬於 Core ，或者說滿足穩定性。
我們今天來看兩個例子，看看他們 Core 的結構
沒有核心的賽局
假設 N = {1, 2, 3}
因為大聯盟收益大於任意雙人聯盟，所以此賽局有可能最後結果為全體聯盟，在這個狀況下我們想要找到一個穩定的效益分配向量。
如同上篇文章所提及，這可以被寫成一個線性規劃問題
假設欲求的效益分配向量為
效率性條件要求
穩定性條件要求
單人聯盟：
雙人聯盟：
將全部條件整理後可以得到
但是注意到，根據最後三條不等式的加總，我們得到
也就是
約分得到
可是此線性系統的第一條（效率性要求）告訴我們
矛盾！
因此我們知道在核心裡面的 x 所需要滿足的系統
是無解的，結論出這個賽局沒有穩定分配的方式，核心 Core 是空的
一些觀察：
三人結盟雖然比兩人結盟多得一點的效益，但這額外的一點不足以同時不常所有可能的雙人聯盟。如果任意兩人的組合都能拿到 4，為了避免他們私下結盟分走 4，你必須讓該兩人在大聯盟中的總分配不低於 4。可是總財富只有 5，三組（1,2）、（2,3）、（1,3）都要給到 4，算起來就要求至少 6 點，無法達成。
核心是否存在的關鍵是 v(N) 要足夠大（夠有利）到可以「堵住」所有小聯盟的潛在收益。不然就會像這個例子一樣，雖然大聯盟可以產生更高的效益，卻無法找到穩定非配方案。
核心很多的賽局
假設 N = {1, 2, 3}
一樣我們來用線性規劃解出核心 Core
效率性條件要求
穩定性條件要求
單人聯盟：
雙人聯盟：
將全部條件整理後可以得到
我們將 x3 做代換，然後用 sagemath 來畫圖
我們的不等式系統變成
化簡後得到
因此我們在 sage 的命令行介面輸入以下指令
var('x1 x2')
# 列出所有不等式
ineqs = [
x1 >= 2,
x1 <= 4,
x2 >= 2,
x2 <= 4,
x1 + x2 >= 5,
x1 + x2 <= 7
]
# 使用 region_plot 繪出同時滿足這些不等式的區域
p = region_plot(
ineqs, # 不等式列表
(x1, 0, 6), # x1 繪圖範圍
(x2, 0, 6), # x2 繪圖範圍
incol='lightblue', # 填充顏色
bordercol='blue', # 邊界顏色
alpha=0.5 # 透明度
)
# 加上一些標記、座標軸名稱
p += text("Feasible Core", (3, 5), color='black', fontsize=12)
p.axes_labels(['x1','x2'])
p.show()
於是可以得到
藍色區域裡面的每一點都是滿足穩定性跟效率性的解，這個賽局的 Core 有無限多個效益分配向量。
凸性賽局（Convex Game）
在前面的兩個範例中，我們看到了「核心（Core）可能是空的」以及「核心可能是一整塊（具有體積）的多面體」。如果站在實務應用的角度，我們多半希望核心能夠存在、而且越大越好，因為那代表有多種方式能滿足穩定性，不會讓玩家們分裂。
這就引出凸性賽局（Convex Game）的概念：在某些情境下，賽局的特徵函數能保證邊際貢獻（marginal contribution）呈現一種「遞增」的特性，使得全體聯盟更有機會產生「足以安撫每個次聯盟」的總收益。換言之，當賽局「越凸」，核心就越容易存在
直覺解釋
所謂凸性，可用「邊際貢獻遞增」來理解：
- 一位玩家加入較大規模的聯盟時，不會產生比加入較小聯盟更低的收益增量，甚至可能更高。換句話說，聯盟規模越大，新成員的貢獻並不被稀釋，反而能帶來更多整合效益。
- 因為大聯盟能創造更充裕的總收益，它更有能力把這些收益分配到各個成員，於是更容易符合「對每個次聯盟都不虧」的穩定條件。下面我們就會證明說，凸賽局必定會有非空的核心 Core
數學定義
對任意 T ⊆ S ⊆ N 以及任何不在 S 裡的玩家 i
也就是說，當玩家 i 加入較大的聯盟 S 所帶來的邊際貢獻，不會小於他加入較小聯盟 T 時的貢獻
讀者如果有閱讀過相關的課本，應該比較容易看到另一種使用超模（supermodular）的定義：對於任意的聯盟 C 與 D
這兩種定義是等價的；第一種關注「玩家對大小不同聯盟的邊際貢獻」，第二種關注「兩個聯盟的合併與交集」。兩者都是凸性的核心概念，在合作賽局中隨處可見。我們會在隔天用複雜的數學來證明兩者等價。
凸性賽局必定會有穩定的分配（核心非空）
我們現在來證明，如果一個賽局是凸的，則必定可以找到核心裡面的效益分配向量，也就是找得到一個穩定的分配方式。
要證明這件事呢，我們只要找出一個穩定分配的方式就可以了，而這件事也不難，我們隨便使用一個排序
然後用邊際貢獻的方式來分配效益
以此類推
而這些 x_i 就會是一個符合穩定性的效益分配向量。
首先，他有滿足效率性
穩定性就比較難證明：
令 S 為一個 N 下的聯盟，裡頭有 s 個玩家，我們可以把它寫成
因為他一定有出現在上面的 sigma 排序裡面。
所以我們要來關心在 S 裡的成員所分配到的效益是否大於等於 v(S)。
好的，根據上面的分配方式，這些成員會得到
這可以寫為
除此之外我們注意到
所以根據凸賽局的定義，我們可以寫出
於是我們知道
於是我們知道
因此滿足穩定性條件，證明完畢
Takeaway
- 核心在一般遊戲中可能是空的，也可能是一個多面體。
- 「大聯盟收益是否足以補償各種次聯盟」是核心存在與否的關鍵。
- 凸性遊戲（Convex Game）因為「邊際貢獻遞增」，能保證核心一定非空。
- 建構邊際貢獻向量是凸性遊戲核心非空的經典證明方法。
Reference
Chalkiadakis, Georgios, Edith Elkind, and Michael Wooldridge. _Computational aspects of cooperative game theory_. Morgan & Claypool Publishers, 2011.
