在前一篇文章（Day 12）中，我們已經簡介了核仁（nucleolus）的概念。本篇將更嚴謹地證明：只要合理分配空間 I(v) 非空，核仁必定存在。核心工具將是歐氏空間中著名的「極值定理（Extreme Value Theorem）」。
回顧：核仁的定義
不滿值（excess）
對於每一個效益分配向量 x ，我們會計算他對每個聯盟的「不滿值（excess）」：
我們會對每一個聯盟 S 都計算這個 e(S, x) ，因此共有 2^n - 1 個不滿值。我們將這些不滿值由大到小排序：
也就是說
為了方便，我們也指定以下符號：
序列中第一個元素的意思
序列中第二個元素的意思，以此類推
字典序（lexicographic ordering）
假設我們有兩個效益分配向量 x 與 y ，並且他們根據計算得出的不滿值排出向量：
我們說，θ(x) 在字典序下比 θ(y)
若且唯若存在一個下標 k 滿足
以及對於所有小於 k 的下標 l
最後，我們就可以寫下核仁 Nucleolus 的定義：
也就是說核仁是在字典序下，最小的 θ(x) 向量，其中 x 為所有可能的合理分向量（下節說明）
Imputation Set（合理分配集合）
為了利用效益分配向量的拓樸性質，我們需要先定義一個常用的拓樸物件：Imputation set。
這很簡單，對於一個合作賽局 (N, v) 來說，imputation set 就是收集所有滿足效率性與個體理性的效益分配向量：
效率性已經提過很多次，就是指
個體理性的意思是：對每個個體來說，參與聯盟而配得的效益不可以少於他自己單獨作業所得到的效益：
因此，對一個合作賽局 (N, v) ，他的 imputation set 會是
本篇文章的後面一段會對證明這個集合的更多拓樸性質，且會被利用在核仁存在性的證明。
我們今天的目的，就是要證明只要合理分配向量 I(v) 非空，那核仁必定也是非空。
極值定理
這個存在性證明，最主要就是要用以下的極值定理：
在歐氏空間中，若函數 f 是定義在一個緊緻 compact 集合 X 上的連續函數，則 f 可以在 X 裡達到最小值，且所有達到最小值的點 x 也是一個緊緻集合。
好我們簡單證明此定理：
1, 由於 X 是緊緻的，所以 f(X) 也是緊緻的
2, 因為 f(X) 是緊緻的，所以
也就是存在某個 x 使得
至此為止我們證明了 f 可以在 X 裡達到最小值。
3, 考慮所有達到最小值的點 x 為集合 M
4, 因為 m 是最小值，所以對定義域 X 的捕集 X - M 就是 函數 f 的開超水準集（對不起我不知道怎麼翻譯）：
5, 因為 f 是連續函數，根據連續函數的定義（開集合版本）：值域中的開集合在連續函數 f 中的原相為開集合。而注意到
且顯然 (m, ∞) 為開區間，因此 X - M 為一個開集合，再根據拓撲空間中對閉集合的定義（開集合在拓樸（子）空間中的補集為閉集合，且 X - (X - M) = M），我們知道 M 是一個閉集合。
6, 因為 M ⊆ X 而 X 是緊緻的（閉且有界），所以 M 也是有界的集合，根據上一點，我們知道 M 是閉且有界，因此 M 是緊緻的。
證明完畢。
存在性定理證明
我們要證明的定理如下：
對於任何合作賽局 (N, v) 我們有
其中
為核仁，以及
為合理分配空間（Imputation set）
直覺說明
直覺上我們應該可以想見說，因為核仁是用這個不等式
定義出來，我們可以依序比較這些 θ 序列中的元素：先比第一個元素
收集候選的 x ，然後你也發現這些 x 是在 θ 下的某種最小值，可以利用上面的極值定理，候選的 x 大概會形成一個閉集合。
再比第二個
收集候選的 x ，大概也會形成一個閉集合。以此類推，重複利用上面的極值定理。
好，萬事起頭難，第一個要證明的點就是 I(v) 是一個緊緻空間，極值定理才可以開下去。（然後極值定理就可以一直開下去）
Imputation set 的緊緻性
假設此遊戲是 N-essential ，意思就是
則 Imputation set 非空，且會是一個單純形（Simplex）並有以下極點
其中
我們的證明分兩部：第一步是證明這些點真的是極點，第二步是證明 Imputation set 裡面的任何點都是這些極點的凸組合
驗證這些候選極點都在 Imputation set 裡：
效率性條件：
個體理性條件：對於 j ≠ i ，我們有
對於 j = i ，先因為我們假設 N-essential 所以有
移項得到
注意到左手邊其實就是給定的
驗證這些候選極點真的是極點：
假設這些點都可以寫成一個凸組合
注意到第 j 個元素， j ≠ i ，我們知道
但是因為 x 和 y 都在 imputation set 裡面，都要滿足個體理性條件，所以
現在假設兩個不等式中，其中一個等號不成立，那我們必然會有
（注意到 λ ∈ (0, 1) ）
因此我們結論出
以此類推，我們知道所有 j ≠ i 的座標都有
至於 j = i 這個座標，根據效率性原則
因為 k 都不是 i ，以及上面的論證。
同理：
因此我們證明了：
若這些點可以寫成一個凸組合
則
於是結論出這些
都是極點
證明任一個在 I(v) 中的點都可以寫成這些點的凸組合：
令 x 屬於 I(v) ，是我們想要組合出的向量
訂一個新的變數：
根據個體理性條件， y_i ≥ 0。再由效率性條件得到
現在令
則這些 (y1, y2, ..., yn) 點都屬於
而集合 Y 就是一個 (n - 1) 維度的單純形，其極點是當某一分量取 α 而其他分量取 0 的點。
從這出發，我們又可以把 y_i 寫成
其中 e_i 是向量空間中的標準基底，而 λ_i ≥ 0 且滿足
根據我們 y_i 一開始的構造方法，可以得到
現在注意到當 λ_i = 1 而其他 λ_j = 0 時，這個 x 恰好是
因此我們做出結論，對於所有在 I(v) 中的 x ，我們都可以將其表示為
也就是說 I(v) 確實是由極點
做出的單純形。
在最後的最後，因為他是一個單純型，所以閉（突組合）且有界，因此是一個緊緻集。
連續函數
現在我們要證明
是 x 的連續函數。也就固定某個 x ，我們要證明對於所有 ε ，我們都可以找到一個 δ 使得若
則
首先注意到
是一個線性函數，當然也就是連續函數。
因此對於任何給定的 ε_0 我們可以找到 δ_0 使得
現在我們取足夠小的 ε_0，使得下列性質成立：
若 e(Si, x) = e(Sj, x) 則可能會發生兩個順序互換的問題，但是不要緊張，當你固定好以下的向量
也就是 x 下的不滿值的由大到小的排序，則 y 下的不滿值的由大到小的排序會有兩種狀況：
若 e(Si, y) ≥ e(Sj, y) ，則仍然還是
若 e(Si, y) < e(Sj, y) ，則變成
而後者我們仍然有
以及
因此我們結論出，對於任意給定的 ε 我們都可以找到一個 δ_0 讓
證明完畢。
真正的存在性定理
對於一個合作賽局 (N, v)
證明如下：首先若
則
是一個緊緻的集合（也就只有一個點而已）
若
則 I(v) 根本是空集合，不是本定理考慮的對象。
若
則此為一個 N-essential 賽局，根據上上段的證明，I(v) 會是一個單純形，是一個緊緻的集合。
令
則我們可以考慮在 X0 上面的函數
根據上段的證明，這個函數是連續的，所以根據極值定理：收集所有達到最小值的 x 作為集合 X1 ，而此集合仍然是緊緻的。考慮在 X1 上面的函數
再次根據上段的證明，這個函數也是連續的，因此也再次根據極值定理，可以將達到最小值的 x 寫成集合 X2。
以此類推，做到 X_{2^n-1} 時，這個 X_{2^n-1} 仍然是非空的緊緻子集，因此對於裡面的 x
都會滿足
也就是說在字典序的排序下，這個 x 滿足
於是 x 屬於核仁，核仁非空，證明完畢。
Takeaway
Imputation set：在 N-essential 情況下是非空且緊緻的多面體。
Excess 函數連續：每個 excess 都是線性函數，保證在固定順序下向量 θ(x) 連續。
迭代最小化：利用極值定理在每一步最小化 θ(x) 的座標，確保有解。
核仁存在：只要 I(v) 非空（特別是 N-essential），η(v) 必非空。
Reference
Branzei, Rodica, Dinko Dimitrov, and Stef Tijs. _Models in cooperative game theory_. Vol. 556. Springer Science & Business Media, 2008.
Chalkiadakis, Georgios, Edith Elkind, and Michael Wooldridge. _Computational aspects of cooperative game theory_. Morgan & Claypool Publishers, 2011.
