论文精读：Approximating Maximin Share Allocations（上）

前言

标题意味“近似最大最小份额分配”。这是2019年发表在SOSA（Symposium on Simplicity in Algorithms，算法简单性研讨会）上的一篇论文。该论文研究的是以最大最小份额（MMS）为指标的公平分配问题，给出了一种较为简单的$\frac{2}{3}$近似算法，并证明了其正确性。

原文为英文，有的概念是我自行根据意思翻译的，有可能跟别人的翻译不太一样。

问题介绍

本文研究的问题是，如何把$m$个不可分割的，且具有可加性的物品，公平地分配给$n$个人。

如何判断某个分配方案是否公平，有不同的衡量标准。比如无嫉妒（envy-freeness）和均衡原则（proportionality）。无嫉妒就是指在分配完之后，每个人都不会觉得别人得到的比自己多。均衡原则是指在分配完之后，每个人都能得到至少总价值的$\frac{1}{n}$那么多的价值。

事实上，在假定物品不可分割的前提之下，以上两种指标都太理想化了，没有算法可以做到。举反例非常容易，就是考虑把一个物品分给$n$个人的情况，怎么分都无法满足无嫉妒或均衡原则。所以我们需要提出新的衡量公平性的指标。最大最小份额（maximin share，简称MMS）就这么被提出了。

背景知识

在$n=2$时，一定存在满足MMS的分配方案。在$n\ge 3$时，存在不满足MMS的反例。当$n=3$时，存在$\frac{7}{8}$MMS近似算法；当$n=4$时，存在$\frac{4}{5}$MMS近似算法。当$n$为任意整数时，存在$\frac{2}{3}$MMS近似算法。

本文的主要贡献

提出了一种实施起来和分析起来都很简单的$\frac{2}{3}$MMS近似算法，而且不需要计算每个人的MMS值，并且严格证明了算法的正确性。

符号与定义

基本符号

我们用 M = { 1 , 2 , ⋯ , m } M=\{1,2,\cdots,m\} M={1,2,⋯,m}表示物品集，即这$m$个物品构成的集合。

我们用 N = { 1 , 2 , ⋯ , n } N=\{1,2,\cdots,n\} N={1,2,⋯,n}表示代理人集，即这$n$个人构成的集合。

我们用$v_{ij}$表示第$j$个物品对于第$i$个人的价值，即第$i$个人心目中认为的第$j$个物品的价值。

我们定义一个价值函数$v_i:2^M\to {\mathbb{R}}^{+}$，表示对于一捆物品$S\subseteq M$，在第$i$个人心目中的价值。

我们用 A = { A 1 , A 2 , ⋯ , A n } A=\{A_1,A_2,\cdots,A_n\} A={A1​,A2​,⋯,An​}表示一个分配，表示把所有物品划分为$n$份（每份分给一个人）。

A = { A = { A 1 , A 2 , ⋯ , A n } : A i ∩ A j = ϕ , ∀ i , j ; ⋃ k = 1 n A k = M } \mathcal{A} =\{A = \{A_1, A_2,\cdots, A_n\} : Ai ∩ Aj = \phi, \forall i, j; \stackrel{n}{\underset{k=1}\bigcup} A_k = M \} A={A={A1​,A2​,⋯,An​}:Ai∩Aj=ϕ,∀i,j;k=1⋃​n​Ak​=M}表示所有可行的分配的集合。

可加性

物品具有可加性，指的是在所有人心目中，多个物品的价值就等于单个物品的价值相加。也就是说不会有人认为某两件物品组合在一起之后，价值会比两个物品单个的价值相加更高。这是本文为了简化这个问题做的一个假设，在现实生活中可能不一定满足。

可加性用数学的语言描述就是：$\forall S\subseteq M,v_i(S)={\sum }_{j\in S}{v}_{ij}$

最大最小份额

前面一直反复提到这个词，现在这里详细地解释一下这个词的含义。

最大最小份额（maximin share），简称MMS。你的最大最小份额就是你来分配物品，并且最后挑，能保证自己得到的最大价值。这个概念其实是从切蛋糕问题中引申过来的。你来切蛋糕，为了让你能够更加公平地分配，于是让你最后挑。你最后挑，很可能就是最小的那块给了你，所以你要让最小的蛋糕最大。

用${\mu }_i$表示第$i$个人的MMS，那么${\mu }_i=\underset{A\in \mathcal{A}}{\max }\underset{A_k\in A}{\min }{v}_i(A_k)$
计算每个人的MMS是一个NP-hard问题，但是我们有近似算法。

MMS分配

我们称一个分配$A$为MMS分配，如果每一个人$i$都认为自己得到的一捆物品$A_i$的价值大于等于自己的MMS，即$\forall i,v_i(A_i)\ge {\mu }_i$。

我们称一个分配$A$为$\alpha$近似MMS分配（简称$\alpha$-MMS分配），如果$\forall i,v_i(A_i)\ge \alpha {\mu }_i$。此处，$\alpha \in (0,1)$。

正文

命题1（MMS的放缩不变性）

命题内容

MMS具有放缩不变性。假设 A = { A 1 , A 2 , ⋯ , A n } A=\{A_1,A_2,\cdots,A_n\} A={A1​,A2​,⋯,An​}是实例$I=(N,M,V)$的一个$\alpha$-MMS分配。$\forall i\in N,c\in {\mathbb{R}}^{+}$，如果创造一个新的实例$I^{\prime }=(N,M,V^{\prime })$，将价值放缩为$c$倍，即$v_{ij}^{\prime }=c{v}_{ij},\forall j\in M$，那么A仍然是$(N,M,V^{\prime })$的$\alpha$-MMS分配。

命题证明

假设${\mu }_i$和${\mu }_i^{\prime }$分别是第$i$个人在实例$I$和$I^{\prime }$中的MMS。$\forall S\subseteq M,v_i^{\prime }(S)=c{v}_i(S)$，于是有${\mu }_i^{\prime }=c{\mu }_i$。假设 A = { A 1 , A 2 , ⋯ , A n } A=\{A_1,A_2,\cdots,A_n\} A={A1​,A2​,⋯,An​}是第$i$个人得到MMS${\mu }_i$时所采用的分配方案，那么 $v_i^{\prime }(A_k)=c{v}_i(A_k)\ge c\alpha {\mu }_i=\alpha {\mu }_i^{\prime },\forall k$。证毕。

命题理解

该命题说明了MMS这个定义的某种性质。命题的意思是把某一个人对于物品的价值同时变成$c$倍，不会影响到别人，也不会影响整个方案的公平性。在MMS的定义下，每个人其实是具有高度独立性的，就是说，在你眼中这些物品的价值如何，根本不会影响到我的MMS，所以MMS是完全不考虑价值最大化的，只关注公平。而在一个人眼中，这些物品的价值其实本质上只是一个相对关系，没有绝对的数值，只有相对的大小。这消除了数值规模在不同数量级上的比较一捆物品相对价值的问题。

命题2（标准化赋值）

命题内容

对于实例$I=(N,M,V)$如果第$i$个人的价值函数满足$v_i(M)=\sum _{j\in M}{v}_{ij}=|N|$，那么${\mu }_i\le 1$。

命题证明

反证。假设$v_i(M)=|N|$，但是${\mu }_i>1$。假设 A = { A 1 , A 2 , ⋯ , A n } A=\{A_1,A_2,\cdots,A_n\} A={A1​,A2​,⋯,An​}是第$i$个人得到MMS${\mu }_i$时所采用的分配方案，由${\mu }_i$的定义可知，$v_i(A_k)\ge {\mu }_i,\forall A_k\in A$，于是有$|N|=v_i(M)={\sum }_k{v}_i(A_k)\ge |N|{\mu }_i>|N|$，矛盾！

命题理解

这个命题跟上一个命题要连起来看，既然价值函数可以放缩，那肯定要放缩到一个有意义的值上。标准化赋值让每个人的价值函数之和都是$|N|$，从而利用好了MMS的定义，在不新增任何假设的情况下，进一步化简了题目。

命题3

命题内容

假设$I=(N,M,V)$是一个实例，${\mu }_i$代表第$i(i\in N)$个人的MMS。如果我们移除一个人$k\in N$，并且移除一个物品$j\in M$，那么所有人的MMS在剩余实例 I ′ = ( N \ { k } , M \ { j } , V ) I'=(N\backslash \{k\},M\backslash \{j\},V) I′=(N\{k},M\{j},V)中不会变小，即${\mu }_i^{\prime }\ge {\mu }_i$。

命题证明

在剩余实例中，我们在剩下的人中任意挑选一个人$i$，对其进行考虑。假设 A = { A 1 , A 2 , ⋯ , A n } A=\{A_1,A_2,\cdots,A_n\} A={A1​,A2​,⋯,An​}是第$i$个人在原始实例$I$中得到MMS${\mu }_i$时所采用的分配方案。根据MMS的定义，$\forall A_l\in A,v_i(A_l)\ge {\mu }_i$。不妨假设$A_l$就是那个包含物品$j$的集合，在剩余实例中，把 A l \ { j } A_l\backslash \{j\} Al​\{j}任意分配到其它的一捆物品中，形成新的分配方案 A ^ = { A ^ 1 , A ^ 2 , ⋯ , A ^ n − 1 } \widehat{A}=\{\widehat{A}_1,\widehat{A}_2,\cdots,\widehat{A}_{n-1}\} A ={A 1​,A 2​,⋯,A n−1​}。很显然，新的分配方案$\hat{A}$是一个可行方案，且$\forall {\hat{A}}_l\in \hat{A},v_i({\hat{A}}_l)\ge {\mu }_i$。因此，${\mu }_i^{\prime }\ge {\mu }_i$。

命题理解

减少一个人和一件物品，不会使得其他人的MMS减少。那么，减少$x$个人和$x$个物件，也不会使得其他人的MMS减少。这就是我们的推论4。

推论4

命题内容

假设$L\subset N,S\subset M$，${\mu }_i$代表实例$I=(N,M,V)$中的第$i$个人的MMS。如果$|L|=|S|$，那么在剩余实例$I^{\prime }=(N\backslash L,M\backslash S,V)$中的MMS${\mu }_i^{\prime }$不会变小，即${\mu }_i^{\prime }\ge {\mu }_i$。

命题证明

命题3的自然推论。

逐袋填充算法

这里介绍一个朴素的贪心算法——逐袋填充算法（bag filling algorithm）。假设我们在寻找一个$\alpha$-MMS算法。该算法描述如下：我们每次任意选择一个物品放入袋子$S$中，直到有人$k$认为袋子中物品的总价值大于等于$\alpha {\mu }_k$，即$v_k(S)\ge \alpha {\mu }_k$。如果有多个人这么认为，那就随机挑一个人。我们把袋子$S$分给第$k$个人，并把$S$和$k$分别从实例中移除。然后重复执行上述分配过程。该算法在分配低价值的物品上非常有效。

当然，该算法的成立也需要一些条件。命题5就是在给出一些条件（物品都是低价值物品）的情况下证明该算法的正确性。

命题5（逐袋填充算法的成立条件）

命题内容

假设所有人的价值函数已经如命题2中那样被标准化，并且没有人认为任何一个物品的价值大于$\delta ,0<\delta <\frac{1}{2}$，即$v_{ij}\le \delta ,\forall j\in M,\forall i\in N$，那么“逐袋填充算法”给出了一个$(1-\delta )$MMS分配算法。

命题证明

为了证明算法的正确性，我们只需要证明两个事情，一是每个人都获得了足够价值的物品，二是每轮分配之后有足够多的价值满足后面的分配。第一点在逐袋填充算法下自动满足。于是只需要证明第二点。

在命题2的定义下，我们有$v_i(M)=|N|,{\mu }_i\le 1,\forall i\in N$。我们考虑第一轮分配。假设袋子$S$中的最后一个物品是$j$，那么在把$j$装进$S$之前，袋子中的总价值在所有人眼中都是低于$1-\delta$的（因为如果超过了，那那个人直接把$S$拿走就行了），即$v_i(S\backslash j)<1-\delta ,\forall i\in N$。根据题干的假设$v_{ij}\le \delta ,\forall i\in N$，以及物品的价值具有可加性，我们有$v_i(S)=v_i(S\backslash j)+v_{ij}\le 1$。这意味着$v_i(M\backslash S)=v_i(M)-v_i(S)\ge |N|-1$。也就是说，剩下的价值足够后面的人分配了。

命题理解

作者给的证明非常简略且抽象，并且还有一些错误，跟之前详细且严谨的证明形成了鲜明的反差，我怀疑根本不是同一个人写的。以上是我根据自己的理解写的证明。

为了表示的简略，这里把 S \ { j } S\backslash\{j\} S\{j}简写成了$S\backslash j$。其实证明中有点数学归纳法的味道。如何判断剩下的物品价值是否够剩下的人分配，其实就是保证在每一轮分配之后，剩余实例$I^{\prime }=(N^{\prime },M^{\prime },V)$满足$v_i(M^{\prime })\ge |N^{\prime }|,\forall i\in N^{\prime }$，这样最后一个人也能拿到自己认为价值大于等于1的物品（大于等于1，就一定大于他的MMS）。

该命题给出了逐袋填充算法的正确性证明，也给出了其成立的条件，即$v_{ij}\le \delta ,\forall j\in M,\forall i\in N$。这个条件结合标准化赋值$v_i(M)=|N|,\forall i\in N$，其实可以推导出一个隐藏条件，就是$m\ge \frac{1}{\delta }n$。也就是要物品足够多才可以。这个条件其实挺强的，如果要用这个算法的话，就得想方设法达到这个条件。

$\frac{1}{2}$MMS算法

结合命题2,3,5，可以得出一个$\frac{1}{2}$MMS算法。先把所有人的价值函数如命题2那样标准化处理，于是${\mu }_i\le 1,\forall i\in N$。如果$\exists j\in M,\exists k\in N,v_{kj}\ge \frac{1}{2}$，那么就把物品$j$分配给第$k$个人。如果有多个$k$满足条件，那么就随机挑一个人分配。根据命题3，剩余实例$I^{\prime }=(N\backslash k,M\backslash j,V)$中的MMS${\mu }_i^{\prime }$会大于等于原来的MMS${\mu }_i$。接下来我们对剩余实例进行标准化赋值。然后重复这个过程，每次把一个物品分给一个人，然后对剩余实例进行标准化赋值，直到所有人都分配到物品，或者$v_{ij}<\frac{1}{2},\forall j\in M,\forall i\in N$。我们对剩下的物品和人使用逐袋填充算法，命题5证明了其正确性。于是我们就得到了一个$\frac{1}{2}$MMS算法。

总结

这是我第一次做论文精读。基本上把论文带着自己的理解翻译了一遍。有些地方发现深入思考还是很有意思的。

本文介绍了公平分配问题的一些基础概念，针对于MMS这个指标进行了详细地研究。到这里为止，介绍了逐袋填充算法，并在此基础上扩展成了$\frac{1}{2}$MMS算法。其实这个算法理解起来非常简单，但是严格地定义和证明并不容易，所以才需要这么多的定义和命题。本来想一篇博客写完这篇论文的，但是内容实在是太多了，于是分成了两篇来写。下一篇接着引入一些概念和命题，提出更好的近似算法。