Brams S J, Kilgour D M, Klamler C. The undercut procedure: an algorithm for the envy-free division of indivisible items[J]. Social Choice and Welfare, 2012, 39(2-3): 615-631.
离散资源，无嫉妒划分
概要
- 两位参与者 \(A\) 和 \(B\)，分割一整个物品集 \(X\)；
- 二者的偏好均是 \(X\) 幂集 \(\mathcal{X}\) 上的全序；
- 文中提出UP算法，必定能得到一个 \(X\) 的无嫉妒划分：
- 无嫉妒的定义：每个人都觉得自己的比对方的好；
- 即使 \(A\) 和 \(B\) 的偏好完全相同也可以得到；
- 基本思路：Undercut：
- 一人提出proposal，另一人undercut。
基础知识
记号：
- \(i\) 的单物品偏好用 \(P_i\) 表示，每个 \(P_i\) 都是
严格、完全的； - \(i\) 的偏好用 \(\succeq_i\) 表示；
- \(S\) 的补集用 \(-S\) 表示。
相关定义：
Def 1. \(\mathcal{X}\) 上的偏好 \(\succeq\) 称为是合理（responsive）的，若 \(\forall S\in\mathcal{X}\) 和 \(\forall x\in X\)，\(y\in X\backslash S\)，总有：
- \(S\succ S\backslash \{x\}\cup\{y\}\iff x~P~y\)；
- \(S\backslash \{x\}\cup\{y\}\succ S\iff y~P~x\)；
- \(S\succ S\backslash\{x\}\)。（单调性，monotonic）
Def 2. 令 \(S,T\subseteq X\)，\(S\neq T\)，令 \(P\) 是 \(X\) 上的一个严格的序。如果：
- 存在一个单射 \(\sigma_{T,S}: T\backslash S\to S\backslash T\)，s.t. \(\forall x\in T\backslash S, \sigma_{T,S}(x)~P~x\)；
则称 \(T\) 依次劣于（ordinally less）\(S\)，记作 \(T\leqslant_{OL} S\)。
- 简言之，\(S\leqslant _{OL}T\) 的意思就是存在 \(S\to T\) 的一个映射，按照这种对应，\(S\) 中的每个物品都不如 \(T\) 中的对应物品。（是 \(S\) 比 \(T\) 差了很多的意思）
Def 3. 参与者 \(i\) 认为 \(S\subseteq X\) 是至少值50% 的，如果 \(S\succeq_i -S\)。
Def 4. 集合 \(S\subseteq X\) 对 \(i\) 来说是一个minimal bundle，如果：
- \(S\succeq_i -S\)；
- \(\forall T\leqslant _{OL} S\)，总有 \(-T\succeq_i T\)。
Def 5. \(\forall S\subseteq X\)，划分 \((S,-S)\) 是无嫉妒的，如果：
- \(S\succeq_A -S\)；
- \(-S\succeq_B S\)。
Def 6. 一个无嫉妒划分 \((S,-S)\) 称为是平凡（trivial）的，如果：
- \(S\sim_A -S\)；
- \(S\sim_B -S\)。
UP：Undercut Procedure
UP算法的步骤
- 初始物品堆为 \(X\)，\(A\) 和 \(B\) 分别取当前物品堆中选取各自当前最喜欢的物品 \(x_A\) 和 \(x_B\)：
- 若 \(x_A\neq x_B\)：将 \(x_A\) 分配给 \(A\)，\(x_B\) 分配给 \(B\)；
- 若 \(x_A=x_B\)：将该物品放入待定区，记为 \(I_c\subseteq X\)；
- 继续执行 1，直到所有物品都被标记为 \(A\)，\(B\) 或 \(I_c\)；
- 考察 \(I_c\)：
- 若 \(I_c\) 为空，则分配结束…（这应该是
废话显然的）； - 若 \(I_c\) 非空，记参与者 \(i\)（\(i=A,B\)）在 \(I_c\) 中的minimal bundle集合为 \(MB_i\)，\(i\) 将 \(MB_i\) （私密地）提交给裁判；
- 若 \(I_c\) 为空，则分配结束…（这应该是
- 若 \(MB_A\neq MB_B\)，则 \(i\) 将 \(i\) 将 \(MB_i\) 中的偏好顺序提交给裁判。
- 任取一名选手（例如是 \(A\)）；
- 取 \(MB_A\) 中排名最高的集合，记为 \(T\)：
- 若 \(T\notin MB_B\)，则称其为一个proposal，此时称 \(A\) 为一个proposer；
- 若 \(T\in MB_B\)，则转而考虑 \(MB_B\) 中排名最高的集合，判断其是否属于 MB_A$…反复进行；
- 由于 \(MB_A\neq MB_B\)，故反复进行上述步骤一定能得到一个 \(MB_A\) 中的排第一，但 \(MB_B\) 中不排第一 或者 \(MB_B\) 中的排第一，但 \(MB_A\) 中不排第一 的集合，将其作为proposal。
- 若 \(MB_A=MB_B\)：
- 若 \(\exists i\)，\(\exists S\in MB_i\)，s.t. \(-S\in MB_i\)，则此时将 \(S\) 做为 proposal，\(i\) 为proposer；
- 若 \(\forall i\)，\(\not\exists S\in MB_i\)，s.t. \(-S\in MB_i\)，则此时随意选择一个minimal bundle \(S\) 做为 proposal；
- 假设 \(S\) 是proposal，\(A\) 是proposer，则 \(B\) 的undercut操作为：
- （Accepting）若 \(-S\) 对于 \(B\) 是至少价值 50% 的，则 \(B\) 可以同意 \(I_c\) 的划分 \((S,-S)\)；
- （Undercutting）在所有比 \(S\) ordinally less的集合中，取 \(B\) 最喜欢的集合 \(T\)，重新提出划分 \((-T,T)\)；
- 最终得到一个划分 \((F,-F)\)，将 \(F\) 分配给 \(A\)，\(-F\) 分配给 \(B\)。
关于UP的讨论
Th 1. 存在一个非平凡的无嫉妒划分，当且仅当 \(MB_A\neq MB_B\)。并且该情形下，UP给出的是一个无嫉妒划分。
Proof. \(\Leftarrow\)：假设存在一个无嫉妒划分 \((S,-S)\)，则必定存在一个参与者更喜欢 \(S\)（不妨设为 \(A\)），即 \(S\succ_A -S\)。 - 若 \(S\notin MB_B\)，则 \(MB_A\neq MB_B\)，\(\Rightarrow\) 得证； - 若 \(S\in MB_B\)，则 \(S\succeq_B -S\)，结合 \((S,-S)\) 是一个无嫉妒划分，应有 \(-S\succeq_B S\)，因此 \(S\sim_B -S\)。现取 \(T\subset X\)，s.t. 对 \(B\) 而言有 \(T\leqslant_{OL} -S\)（同时亦有 \(S\leqslant_{OL} -T\)），则若 \(\succeq_B\) 是
合理的，应有 \(-T\succ_B T\)，因此 \(-S\) 是 \(B\) 的minimal bundle。即 \(-S\in MB_B\)，但 \(-S\) 显然不在 \(MB_A\) 中，因此 \(MB_B\neq MB_A\)。\(\Rightarrow\)：若存在 \(S\)，s.t. \(S\in MB_A\) 但 \(S\notin MB_B\)，则有且仅有以下两种互斥的情形：
- \(S\succ_B -S\)，此时存在一个 \(T\leqslant_{OL} S\)，s.t. \(T\succeq _B -T\)，即 \(T\) 对 \(B\) 来说
至少价值50%；- \(-S\succ_B T\)。
由于以上两种情况是互斥的，因此有且仅有一个发生。然而，在以上两种中的每一种情况下，\(B\) 都得到了
至少价值50%的集合。同时，\(A\) 也得到了至少价值50%的集合：
- 若 \(B\) 接受了 \(A\) 的proposal，则 \(A\) 得到了
至少价值50%的集合；- 若 \(B\) undercut了\(A\) 的proposal，则\(B\) 的每一种undercut操作都会使得 \(A\) 得到
价值至少50%的集合。因此，此时一定能得到一个无嫉妒划分。
Cor 1. 在待定区的划分中，一个参与者（例如是 \(A\)）的 maximin 策略是给出自己所有的minimal bundle。若 \(MB_A\neq MB_B\)，则 \(A\) 的收益不会低于 50%，如果他的proposal是一个自己的minimal bundle。但若存在未提交的minimal bundle，或是提交了非minimal bundle 的集合，则可能导致他的收益低于 50%。
Def 7. 称 \(\mathcal{X}\) 上的偏好 \(\succeq\) 满足扩展单调性，如果：
- \(\forall S,T\in\mathcal{X}\)，所有单物品偏好 \(P\)，以及所有 \(x,y\in X\backslash(S\cup T)\)，总有： \[\begin{cases} S\succeq T \\ x~P~y \end{cases}\Rightarrow S\cup\{x\}\succ T\cup\{y\}.\]
Prop 1. 假设参与者的偏好都是
合理且扩展单调的，给定待定区的一个无嫉妒划分，则UP给出的整体划分是无嫉妒的。
Proof. 这个命题基本上一听就是个废话。
两个参与者偏好完全相同的情形
- \(A\) 和 \(B\) 在 \(I_c\) 上的单物偏好相同，均为 \(1~P~2~P\cdots P~c\)；
- 记 \(I_c=\{1,2,\cdots,c\}\)。
Def 8. 集合 \(S\subseteq I_c\) 称为是可行的，如果存在一个
合理的偏好 \(\succeq\)，s.t. \(S\succ -S\)。
Th 2. 令 \(S\subseteq I_c\)，且 \(S\neq\varnothing\)。则 \(S\) 是
可行的，当且仅当存在 \(k\leqslant c\)，s.t. \(|I_k\cap S|> \frac{k}{2}\)。Proof. 这个定理的样子类似于 “Computing a small agreeable set of indivisible items” 一文中的 Prop 1，证明也比较显然。
Cor 2. 对 \(\forall c\)，\(\{1\}\) 和 \(\forall S\)，s.t. \(1\in S\) 都是
可行的。
Cor 3. 假设 \(S\subseteq I_c\) 且 \(1\notin S\)。若 \(S\) 是
可行的，则 \((S,-S)\) 和 \((-S,S)\) 都可能是无嫉妒的划分。
- 以上两个推论都很容易理解和证明…不再赘述。
除此之外，还有一个很有意思的结论：
- 用 \(f(c)\) 表示待定区包含 \(c\) 个物品时，\(I_c\) 的无嫉妒划分方案数，则有： \[f(c)=\begin{cases} 2^{c-1}-\binom{c}{(c-1)/2}, & 2\not| ~c \\ 2^{c-1}-\binom{c}{c/2},& 2~|~c \end{cases}\]
待定区大小的估计
- 用 \(n\) 表示物品数量，参与者 \(A\) 的偏好为 \(1P_A 2P_A\cdots P_A n\)，且该偏好是严格的；
记 \(c(n)\) 为待定区中物品个数的期望。
- 若 \(n=1\)，显然物品 \(1\) 会被丢入待定区，因此 \(c(1)=1\)；
- 若 \(n=2\)，则 \(B\) 的可能偏好有两种，每种情况的概率为 \(1/2\)，因此 \(c(2)=\frac{1}{2}\cdot 0+\frac{1}{2}\cdot 2=1\)。
- 若 \(n\geqslant 3\)，则：
- \(B\) 最喜欢物品 \(1\) 的概率为 \(\frac{1}{n}\)，此时 \(1\) 会被置入待定区，随后进入 \(c(n-1)\) 情形；
- \(B\) 最喜欢的不是 \(1\) 的概率为 \(\frac{n-1}{n}\)，此时 \(1\) 会被送给 \(A\)，\(B\) 也会得到他最喜欢的物品，随后进入 \(c(n-2)\) 情形。
综上所述，在 \(n\geqslant 3\) 时，有： \[c(n)=\frac{1}{n}[1+c(n-1)]+\frac{n-1}{n}c(n-2).\]
Lemma 1. 若 \(c(n-1)=c(n-2)=x\)，则 \(c(n)=c(n+1)=x+\frac{1}{n}\)。
Proof. 这个证明是不是过于简单了…
Th 3. 若 \(k\geqslant 1\)，则 \[c(2k+1)=c(2k+2)=1+\frac{1}{3}+\frac{1}{5}+\cdots+\frac{1}{2k+1}.\]
Proof. 这个证明也很简单（
- Th 3 表明，\(c(n)\) 是发散的。