Day 13 核仁（Nucleolus）之二：使用數學分析（俗稱高等微積分）證明存在性

在前一篇文章（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.