Day 8 凸性賽局：邊際貢獻遞增 與 超模（Supermodular）定義的等價性
給讀者的溫馨提醒
如果你在閱讀過程中感到略微吃力，請別灰心，因為今天我確實用數學用得比前幾日還兇，我自己在研究的過程中也是費心費力。
如果你只是想知道大意，可以先跳過詳細證明，把握下列要點：
如同做昨天所說：
- 「邊際貢獻遞增」和「超模（supermodular）」這兩種凸性賽局定義，其實是一體兩面，證明的細節雖然繁瑣，但最後結論是它們是等價的。
- 一旦賽局具備這樣的「凸性」，就能保證核心（Core）不為空。大聯盟的總收益夠大，可以維持合作穩定。
若你對細節特別有興趣，歡迎往下翻看完整數學證明。
若你想省略繁複的證明步驟，不妨把這篇當作「參考資料」，等日後真要和別人辯論「超模與邊際貢獻遞增到底是不是同一回事」時再翻出來。
接下來的文章我也會盡量往實務應用的方式去做，千萬別被今天嚇到了（雖然我覺得過去幾篇也有些地方數學用很兇）。
凸性賽局：回顧
我們在昨天的文章中採用了以下的「邊際貢獻遞增」定義
對任何玩家 i 與任何兩個聯盟 T ⊂ S ⊂ N（其中 i 不屬於 S），都有
換言之，玩家 i 加入規模較大的聯盟 S 所帶來的邊際貢獻，不會比加入規模較小的聯盟 T 來得低。
我們運用了這個性質證明了，凸性賽局必定會有滿足穩定性又滿足效率性的效益分配向量，也就是核心 Core 。
但我們同時也提及了，凸性賽局也可以用超模（super modular）的方式來定義：若對於任意的聯盟 C 與 D
則稱此賽局是「凸性賽局」。
今天我們就只做一件事，就是要搞清楚這個等價關係！
證明
我們要證明兩個定義等價，那也就是說要證明一個「雙箭頭」：
- 假設滿足超模，則邊際效益遞增
- 假設邊際貢獻遞增，則滿足超模
超模 => 邊際效益遞增
假設我們有：對於任意的聯盟 C 與 D
要證明：對任何玩家 i 與任何兩個聯盟 T ⊂ S ⊂ N（其中 i 不屬於 S），都有
我們首先可以對目標進行一些移項得到
證明此式成立的話，就可以移項回去並證明完畢。
注意看這個式子其實跟超模的不等式很像，我們嘗試性的令
這樣右側就會變成
跟超模的條件完全一樣
同時注意到，因為 T ⊂ S ，我們有
以及
但是因為 i 不在 S 裡面，以及 T ⊂ S ，於是
於是 (*) 就可以寫成
而這個式子因為有超模的條件所以本來就成立，於是證明完畢。
邊際效益遞增 => 超模
（這個部分就比較複雜）
假設我們有：對任何玩家 i 與任何兩個聯盟 T ⊂ S ⊂ N（其中 i 不屬於 S），都有
要證明：對於任意的聯盟 C 與 D
首先，令集合
我們要對這個集合的大小進行數學歸納法。
當 | Dif | = 1 時，可說是 D 有一個點 { i } 是跟 C 不重複的，我們就可以用邊際效益遞增來證明超模
首先注意到
且 i 不在 C 裡面。則根據邊際效益遞增
注意到
因此從 (**) 式可以得到
移項就可以得到超模的條件
好，我們證明完 | Dif | = 1 的狀況。因為我們要用數學歸納法來論證，所以我們假設這個定理到 | Dif | = k - 1 都是對的，然後要證明當 | Dif | = k 時，此定理成立，這樣就可以完成證明了。
假設
但是我們也考慮
以及
則因為
所以根據歸納法假設，我們知道
現在注意到
因此根據邊際效益遞增，我們知道
整理一下可以得到
注意到
因此上面這個不等式可以改寫為
但是根據我們的歸納法假設，我們還知道（上面有寫）
兩個不等式相加後馬上就可以得到
最後再注意到
因為多出來的那個 i_k 根本也不在 C 裡。
於是最後就得到了
證明完畢。
Takeaway
「邊際貢獻遞增」和「超模（supermodular）」這兩種凸性賽局定義為等價定義，本文進行詳細的數學論證
Reference
Chalkiadakis, Georgios, Edith Elkind, and Michael Wooldridge. _Computational aspects of cooperative game theory_. Morgan & Claypool Publishers, 2011.
