Day 14 核仁（Nucleolus）之三：利用凸組合分析以及組合學的手法來證明核仁的唯一性
我們要證明的事情是：
假設
目標是要證明 x = y 。
大致的思路如下：
如果根據剛剛的假設，則我們知道 x 與 y 的不滿值向量 θ(x), θ(y) 都會是在字典序下最小的，於是我們就有
然後因為當 a ≥ b 且 b ≥ a 時我們有 a = b ，所以我們就想要寫下
這個叫做字典序的不對稱性（antisymmetric order），我們會在下面對這件事情做證明。
接著，我們會考慮一個凸組合
也就是一個新的效益分配向量 z ，當 α = 1 與 α = 0 時就分別等於 x 與 y 。
證明出
再透過凸組合的兩端點證明出 x = y 。
字典序的不對稱性
假設
則我們要證明 x = y。
假設 x ≠ y 。因為
所以存在一個下標 k1 使得
同時因為
所以存在一個下標 k2 使得
你會發現 k1 ≠ k2 ，而且 k1 < k2 與 k2 < k1 都會導致矛盾，因此透過反證法我們知道， x = y。
放到我們真正要證明的脈絡裡，假設
則我們知道 x 與 y 的不滿值向量 θ(x), θ(y) 都會是在字典序下最小的，於是我們就有
根據字典序的不對稱性，我們結論出：
凸組合分析
現在考慮一個 x 與 y 的凸組合
以及對應的不滿值向量
我們來證明兩個方向的不等式：
以及
由此就可以結論出
大於等於方向：直接根據構造的論證
要證明
很簡單，只要證明出 z 是屬於 Imputation set I(v)，那麼因為 θ(x), θ(y) 都會是在字典序下最小的，於是不等式就會成立。
要證明 z 屬於 I(v)，我們就要證明效率性與個體理性：
效率性：
因為 x 與 y 都在 I(v) ，都滿足效率性。
個體理性：對於每個玩家 i
因為 x 與 y 都在 I(v) ，都滿足個體理性。
至此，我們可以結論出 z 屬於 I(v) ，於是因為 θ(x), θ(y) 都會是在字典序下最小的，所以
小於等於方向：帶有組合學色彩的論證
現在要證明
但我們證明一個更強的不等式：對於所有 x, y 與 α 我們有
再根據 θ(x) = θ(y) 就可以完成原不等式的證明了。
令 L 與 R 分別代表欲證明不等式的左手邊跟右手邊
這個證明的關鍵是，當你把 L 與 R 依序寫出來
我們可以允許「一開始就看到小於」：
我們也可以允許「經過一些等號後看到小於」：
但我們不可以允許「一開始就看到大於」：
我們也不可以允許「經過一些等號後看到大於」：
所以我們的證明需要做到「當後面兩個我們不允許的狀況出現時，會導致矛盾」。
為了做這件事，我們要來證明這個不等式：
其中 θ_i(x) 代表 θ(x) 的第 i 個元素。
好，因為 z 是 x 與 y 的凸組合，所以
我們寫出 θ(z) 的不滿值向量：
注意到不滿值向量 θ(z) 是由大排到小的，所以這裡的 S1, S2, ... 是根據 z 量身定做的。
現在把注意力放到前 k 個元素的和
我們令
則
因為這是前 k 的元素，不滿值向量是由大排到小的，所以我們還可以寫出
接著我們把 z 展開
這是因為原本選好一個 T ，就要放到後面計算
但是最後一行是，你可以為
各選擇一個能達到最大值的 T 。
根據不滿值向量的定義，θ(x) 與 θ(y) 也會是由大排到小，因此你也可以寫出
以及
於是
於是我們就證明出
回到我們要證明的事情：我們不可以允許「一開始就看到大於」：
我們也不可以允許「經過一些等號後看到大於」：
所以我們的證明需要做到「當後面兩個我們不允許的狀況出現時，會導致矛盾」。
好，若 k = 1 ，不等式
會變成
就會跟
矛盾。
接著假設「經過一些等號後看到大於」：
則前面 k-1 個元素相等告訴我們
因為
相減得出
就跟
矛盾。
於是不等式
證明完畢，再因為 θ(x) = θ(y) 得到
繼續完成唯一性證明
現在我們有
以及
根據我們第一節做的不對稱性，我們結論出
沿用
其中 S1, S2, ... 是根據 z 量身定做的，因為不滿值向量的定義是由大排到小。
構造兩個向量：
也就是根據 S1, S2, ... 去計算出 x, y, 依序在這些聯盟的不滿值
當代入 α = 1 時，
然後另一方面：
於是我們就結論出
同理代入 α = 0 時，
又因為 θ(x) = θ(y) ，所以 a = b，於是根據構造
對於每一個下標 k，我們都有
也就是對於每一個聯盟 S ，我們都有
所以特別地，當 S = { i } 時，
所以
移項可以得到
因此我們做出結論
證明完畢。
Takeaway
- 字典序的反對稱性
＝
- 我們可以利用嚴格的數學證明推導出核仁的唯一性
Reference
Lecture Slide by Martin Černý
https://kam.mff.cuni.cz/~cerny/data/CG/CG3-nucleolus_handout.pdf
