破产问题
目录
我们从2000年前古巴比伦犹太法典《塔木德》(Talmud) 中描述的一个案例为出发点，介绍一种资源分配的策略。从合作博弈论的角度来理解，这种分配策略是 Nucleolus 分配。本文参考 Robert J. Aumann 和 Michael Maschler 1。
争大衣问题
《塔木德》2 源于公元前 2 世纪至公元 5 世纪间，记录了犹太教的律法、条例和传统。其内容分三部分，分别是密西拿(Mishnah) – 口传律法，革马拉(Gemara) – 口传律法注释，米德拉什(Midrash) – 圣经注释。
密西拿中描述了如下的案例:
- 争大衣问题 (The Contested Garment)
两个人共同拥有一件大衣。第一个人说大衣完全属于他；第二个人说大衣的一半属于自己。那么应该给第一个人 3/4，另一个人1/4。
如果按比例分配，应该给第一个人2/3，另一个人1/3。我们想一想，上面的分配逻辑是怎样的?
为方面描述, 我们引入如下的记号。
- $E$ – 总资产
- $d_i$ – 第$i$个人声明的资产，$i=1, 2$
- $x_i$ – 给第$i$个人实际分配的资产，$i=1, 2$
它的分配思想是: 没有争议的给对方，有争议的部分平均分。
记 $\theta_+ = \max(\theta, 0)$。注意到 $(E-d_1)_+$ 是第一个人对第二个人无争议的部分；$(E-d_2)_+$是第二个人对第一个人无争议的部分。因此，双方有争议的部分为 $$ E - (E-d_1)_+ - (E-d_2)_+$$
这样一来，上面的分配逻辑可以描述称如下原则。
CG 原则 (Contested Garment Principle)
$$ \begin{aligned} & x_1 = \frac{E-(E-d_1)_+ - (E-d_2)_+}{2} + (E-d_2)_+\\ & x_2 = \frac{E-(E-d_1)_+ - (E-d_2)_+}{2} + (E-d_1)_+ \end{aligned} $$
破产问题
如何把争大衣的分配策略扩展到任意多个人的情形?
- 破产问题 (The Bankruptcy Problem)
用二元组 $\langle E, d\rangle$ 描述一个破产问题的实例，其中 $E$ 代表某个破产银行的总资产，$d=(d_1, d_2,\ldots, d_n)$ 代表银行对 $n$ 个机构(或个人)的欠款。设 $d_1\leq d_2\leq \ldots \leq d_n$ 且 $0\leq E\leq \sum_{i=1}^n d_i$。应该如何把资产 $E$ “公平地"分配给 $n$ 个机构。
在这个问题中，我们注意到总资产一定不能满足所有人的需求。换句话说，总资产可能不够分。因此，分配时应该尽量保证"公平性"，但是公平性并不好定义。常见的分配方式是按比例分，但是这样做可能不公平，因为权重越大的人分到的资产越多，反之则越少。 上面描述的 CG 原则，从另外的角度给出了一种分配，它的公平性体现在同时考虑了损失和收益(参考下文)。
例 考虑3个人 $d_1=100$，$d_2=200$，$d_3=300$。$E$ 分别为 100, 200, 300 时，“密西拿“ 规定的分配如下表所示。
| E | $x_1$ ($d_1=100$) | $x_2$ ($d_2=200$) | $x_3$ ($d_3=300$) |
|---|---|---|---|
| 100 | 33 + 1/3 | 33 + 1/3 | 33 + 1/3 |
| 200 | 50 | 75 | 75 |
| 300 | 50 | 100 | 150 |
通过观察，我们发现：
- $E=100$ 时是 平均分配。
- $E=200$ 时看起来挺神秘的。
- $E=300$ 时是 按比例分配。
接下来我们考虑，如何把 CG 原则扩展到 $n$ 人情形，或者说如何解释上面的分配策略?
一致性分配
考虑一个分配结果 $x=(x_1, x_2, \ldots, x_n)$，对任意两个机构 $i$, $j$ ($i\neq j$)，如果按照 CG 原则对 $i$ 和 $j$ 分配总资产 $(x_i+x_j)$，它们得到的资产仍然为 $x_i$ 和 $x_j$，那么我们称 $x$ 是 一致的(Consistent)。
容易验证上面例子的分配符合一致性。
下面我们介绍一致性分配的性质 (证明忽略)。
破产问题的一致性分配是 唯一的.
破产问题的一致性分配是 自洽的 (self-consistent)。即，考虑破产问题的任意子问题，它的机构集合为$S\subseteq {1,2,\ldots,n}$，总资产为 $\sum_{i\in S}x_i$。那么重新按照一致性分配，$S$ 中的机构分配到的资产仍然为 $x_i$，其中$i\in S$。
破产问题存在唯一的 自对偶的 (self-dual) 一致性分配。为描述简单起见，我们忽略自对偶的定义 (详细定义请参考1)，仅解释其意义。令 $D=\sum_{i=1}^n d_i$ 为破产银行对所有机构的总欠款。所以我们可以把这个问题从两个方面理解：
a. 如何把总资产 $E$ 公平地分配给 $n$ 个机构?
b. 如何把总损失 $D-E$ 公平地分配给 $n$ 个机构?
如果分配策略是自对偶，那么按照上述两种情况分配最终得到的资产是相同的。
对任意的集合$S\subseteq N = \set{1, 2, \ldots, n}$，定义效用函数 $$v(S) = \left(E-\sum_{i\in N\backslash S}d_i\right)_+$$ 该问题可以被描述成合作博弈(Cooperative Game)。那么自对偶的一致性分配是 Nucleolus3。
接下来考虑如何计算自对偶的一致性分配。
计算方式
我们先介绍一个简单的分配策略。
CEA (Constraint Equal Award)
考虑破产问题 $\langle E, d\rangle$。设 $d_1\leq d_2\leq \ldots\leq d_n$。首先给第一个机构分配，原则是在不超过 $d_1$ 的前提下对当前的总资产平均分，即 $x_1= \min(E/n, d_1)$。之后机构 1 离开，剩下总资产 $E-x_1$，总机构数为 $n-1$。依此类推，我们可以完成对所有机构的分配，最终得到 $x_1,x_2,\ldots, x_n$ 作为 $n$ 个机构分配到的资产。
为方便描述，我们用 $\text{CEA}(E,d) = (x_1, x_2, \ldots, x_n)$ 表示分配结果。令 $D=\sum_{i=1}^n d_i$。 用 $x$ 代表分配结果。
下面是计算方式:
- 如果 $E\leq D/2$，那么 $x=\text{CEA}(E, d/2)$。
- 如果 $E>D/2$，先计算 $y=\text{CEA}(D-E, d/2)$ (先分配损失)，然后令 $x=d-y$。
容易验证上一节例子中的分配结果就是按照本节中的计算方式得到的。
总结
破产问题本质上是一个资源分配问题，而 CG 分配原则考虑了某种意义上的公平性。可以证明，按照上一节描述的方式计算的结果不仅是唯一的一致性分配，而且是自对偶的。即，它分配资产和分配损失的策略是相同的。此外，与按比例分配相比，CG 分配更多地照顾到了低权重的个体。在实际中，我们应该根据具体的业务场景选择合适的分配策略。