Day 12 核仁（Nucleolus）之一：如果注定沒有「穩定解」，我們只好「最小化最大不滿」
在以前的文章中，我們談到「核心 (Core)」是合作賽局中最具直覺性的穩定解：只要有一個分配落在核心裡，那便代表「任何次聯盟都不會想脫離大聯盟自行合作」。然而，有些賽局的核心根本是空的，也就是說，無法找到一個能同時滿足所有人、不會導致部分成員分崩離析的分配方案。這時，我們要如何退而求其次，至少讓「抱怨」降到最低？這便引出了 核仁 (Nucleolus) 的概念。
回顧之前沒有核心 Core 的賽局
假設 N = {1, 2, 3}，且特徵函數設定為：
如果你嘗試要找到核心 x = (x1, x2, x3) ，你會做到
加起來得到
但是效率性條件要求
於是矛盾，這個賽局的核心為空。
退而求其次：最小化「不滿值 (excess)」
既然無法同時滿足所有聯盟，那就改用「最小化所有聯盟的最大不滿」的思路：
我們對任何聯盟 S ⊆ N 定義
如果 e(S, x) > 0 ，代表
也就是「聯盟 S 在大聯盟分得的份額 不足 他們自行合作就可得到的 v(S)」，因此會感到「不滿」；越大代表越嚴重。
當核心存在時，對所有 S ⊆ N 都能達到
也就是沒有任何次聯盟真的覺得被虧待。但當核心為空，就無法做到「所有子聯盟不滿都 ≤ 0」，勢必有人會不開心。那能否把「最嚴重的抱怨」壓到最低？
最小化最大不滿與字典序最小化
最小化最大不滿
我們可以先考慮「此分配下，所有聯盟不滿值中的最大值」
這可以理解成：
- 找出所有聯盟對於分配 x 的「不滿」e(S, x)。
- 把最「抱怨」最嚴重的那個值（最大不滿）想辦法壓到最小。（透過嘗試不同的分配向量）
這第一步會給我們一個「盡可能讓最嚴重抱怨減輕」的候選解。然而，有時候可能有不只一組分配都能達到同樣的「最大不滿」水準；此時，如何在「多重平手」中進一步選出唯一解呢？
字典序最小化 (Lexicographic minimization)
除了最小化最大不滿外，還要依序比較第二大不滿、第三大不滿…，依「字典序」做多層級的最小化。
概念：把 e(S, x) 按「由大到小」排列成一串序列：
步驟：
- 先找能讓 e_1（最大不滿）最小化的所有可行分配；
- 在前一步的可行解裡，再讓 e_2（第二大的不滿）最小化；
- 依此類推，確保每一層級的不滿都被壓低到最小化。
最終，經過這樣「層層篩選」後，就會鎖定某個分配，這個分配就是「核仁（Nucleolus）」。
- 直覺解釋：即使把最大不滿壓低了，仍可能有多種分配同時達到該目標。核仁會進一步確保「次大不滿、第三大不滿…」都盡可能低，找出對整體抱怨程度最均衡、且最大抱怨最小的解。
- 在核心為空時，核仁就成了我們能參考的主要分配概念：它雖然無法達到完全穩定，但至少能保證「所有人（或所有聯盟）的抱怨都被公平地壓縮到一個最低、可接受的水準」。
線性規劃法尋找核仁
用「最大不滿值 z」來描述問題：
我們想要找出一個分配 x = (x1, x2, x3)，讓所有聯盟的「不滿值」e(S, x) 不要超過某個數 z，並盡可能將 z 壓到最小：
受限制於（subject to）
以及效率性條件
用「兩人聯盟」的條件推導：
注意到兩人聯盟的約束：
將三個兩人聯盟的不等式加總，可以得到
因此得到
表示要讓所有兩人聯盟不滿值皆不超過 z，就得有
現在我們檢查 z = 2/3 是不是一個可行解，也就是有沒有對應能配合到的 x1, x2, x3：
由上一段我們知道
相加之後得到
但是因為效率性條件有 x1 + x2 + x3 = 5 ，所以以上三個不等式的等號都成立
因此解得
因此 z = 2/3 是一個可行解，而這個向量就會是本賽局的核仁（Nucleolus）。
Takeaway
核心為空 (Empty Core)：當無法同時滿足所有次聯盟需求，核心即為空。
不滿值 (Excess)：
正值代表該聯盟「不滿」。
最小化最大不滿 (Min–Max)：先把「最大抱怨」壓到最低，再考慮其他次大不滿。
核仁 (Nucleolus)：在核心為空時，「最小化最大不滿」的解便是核仁；它能在無法穩定的情況下，提供相對「抱怨最均衡」的分配。
Reference
Chalkiadakis, Georgios, Edith Elkind, and Michael Wooldridge. _Computational aspects of cooperative game theory_. Morgan & Claypool Publishers, 2011.a
