Day 20 使用線性空間的觀點來看合作賽局
在合作賽局理論裡，將「特徵函數」視作「向量」，並把所有賽局形成的集合看作一個「向量空間」，能夠為我們提供許多強而有力的數學工具。例如，我們可以用基底來唯一地表達任意賽局，進一步在此空間進行公設、解概念的分析。今天就讓我們從這個觀點出發，導入一組重要的「齊一性賽局 (unanimity games)」並證明它們能形成整個向量空間的基底。
特徵函數是個向量
首先我們回顧「特徵函數賽局（Characteristic Function Games）」，每個這樣的賽局 (N, v) 都會有個特徵函數
於是我們就可以固定玩家集合 N ，然後考慮所有可能的特徵函數 v ，並搭配以下的定義
對於兩個特徵函數 v 與 w，定義其加法
對於特徵函數 v 與實數 c ，定義其係數乘法（係數積）
則我們檢驗並結論出這些特徵函數 v 形成一個線性空間，並且維度為
2 的 |N| 次方。
如果你固定
則維度為 2 的 |N| 次方減一。
我們會在以下的篇幅中描述一組特別的基底（Unanimity games），然後證明這些維數。
齊一性賽局（Unanimity games）
給定任意非空子集 T ⊆ N，定義 unanimity game 如下：
也就是只有當集合 S 包含整個集合 T 時，其效用才為 1，否則為 0。
例如若 N = {1, 2, 3} ， T = {1} 時，
我們宣稱以下集合為線性獨立，且可以生成此空間中的所有特徵函數
線性獨立性
假設有一組實數 a_T 滿足
我們透過數學歸納法證明所有 a_T = 0 。
首先證明當 |S| = 1 ，也就是 S = { i } 時，a_S = 0 。這很顯然，因為
而但是又
因此
現在假設當 |S| 小於等於 k - 1 時，a_S = 0 ，則考慮當 |S| = k 時
但是當
時，我們必定有 |T| 小於等於 k - 1 ，也就知道 a_T = 0 ，所以
於是因為
所以
得出 a_S = 0
根據數學歸納法，結論成立。
線性生成性
我們要證明對於任何一個賽局的特徵函數 v ，我們都可以透過
的線性組合來組合出 v
為了證明此定理，我們首先給定一個賽局的特徵函數 v ，以及另一個特徵函數 w ，但是 w 是定義做
也就是說，這個 w 其實是從 v(S) 的資訊定出來的。
現在我們宣稱並證明：對於所有聯盟 S 我們有 v(S) = w(S)
首先，根據構造
再根據構造，我們知道
以及
對於第二式，我們可以詳細解釋這個求和符號
這個符號其實是，先選擇符合條件的 T ，再選擇符合條件的 U，計算求和的被加數，最後全部加起來。如果我們交換選擇的順序，就可以得到
現在把 (1) 與 (2) 代入回去 (0)，你就可以得到
於是我們知道
而目標就是把這坨好雜亂的式子算到等於 0 。
首先注意到，兩項的第一個求和符號範圍一樣，所以可以合併成
而大括號中的第一項正好等於第二個求和符號中，把 T 用 S 帶入，因此又可以合併成
進一步提出 v(U) 可得到
現在我們集中火力處理大括號裡面的數字
我們看遍每一個可能的 T ：
假設 T = U 的話，這個分量會是
假設 T 比 U 多一個元素，這個分量會是
原因是因為那一個多的元素有 |S| - |U| 個選擇
假設 T 比 U 多兩個元素，這個分量會是
其中最後面這個符號是指二項式係數。
因此，我們這個大括號裡面的數字就等於
根據二項式定理，我們知道
於是我們的 (3) 就會等於
所以我們結論出
因此我們證明完畢。
證明了什麼？證明了給定了 v(S) 特徵函數後，透過這個特徵函數所構造出的
會等於 v(S) ，因此我們可以寫出
所以我們結論出， v(S) 可以寫成
的線性組合
Takeaway
今天的內容給出了合作賽局的「向量空間」視角，並用齊一性賽局（Unanimity games）作為基底示範了怎麼將任意特徵函數「拆解」回去。
Reference
Branzei, Rodica, Dinko Dimitrov, and Stef Tijs. _Models in cooperative game theory_. Vol. 556. Springer Science & Business Media, 2008.
