【论文评述】On Approximately Fair Allocations of Indivisible Goods

发表于 分类于

文献：On Approximately Fair Allocations of Indivisible Goods

这篇文章应该算是不可分割物品公平分配的奠基作，

这篇blog暂时只谈这篇文章的第一个结果。

问题

设为玩家，为物品。

设，则表示在获得时的收益。当时，，即单调性。我们暂时不假设商品收益有可加性。

把分成份，我们就得到一个分配。也即，

，，。

如果是对的某个子集进行划分，就称为“部分分配”（partial allocation）。

在公平分配领域，最经典的“公平”概念就是无嫉妒性，envy-free，它表示

。

我们用

表示具体的嫉妒量。

用

表示一个分配产生的最大嫉妒。

我们通常的目标就是找到一个合适的让

，也叫envy-free。

然而，对于不可分割物品的情形，完全的envy-free是不可能的（比方说只有一个商品，两个玩家）。所以我们使用envy-free up to one good的概念（在这篇文章出现时还没有专门的概念描述它）。

我们将可能出现的最大的边际效益记为

，也即“一个商品能带来的最大嫉妒”。

envy-free up to one good 即

。

在分析allocation的envy时，我们通常会使用envy graph：令个玩家为个node，如果嫉妒，那就连一条指向的有向边。

引理

在给出 envy-free up to one good 的算法前，我们首先给出一个重要的引理，该引理表明，如果一个分配的 envy-graph 是有环的（注意这个环是有向环），那么必然可以通过消解这些环来降低该分配的最大嫉妒（）。

怎么消解环呢？只需要像TTC算法（不含钱的房屋轮换）那样，把环里的物品按环的反方向倒转一次。很明显的是，原来分配的一组组物品并没有变，只是把它们给了更需要的人。所以可以很容易发现，每个人都变得更满意，且不会对他人产生更大的嫉妒（因为物品分割并没有变）。如果转一次没把环消掉，那就接着转。直到图里没有环了，我们的引理的能力就耗尽了。

引理的严格表述如下。

引理：

对于任意envy-graph为的部分分配，总存在一个envy-graph为的部分分配，满足

  • 无环

证明是构造性的，就是上面提到的转动物品的流程。

算法

上面的引理只是给出了一个构造“极小值”的办法，但这个极小值并不一定是envy-free up to one good的，怎么进一步利用它呢？

用归纳法：

首先，把第一个物品随意分配给某个玩家，此时显然有；

假设前个物品已经被分配且满足，我们考虑如何分配第个物品。

我们先构造出前个物品分配的envy-graph，利用引理，把它改造为无环图（注意这个改造完的分配的envy只会更好不会更差）。此时，由于是无环的，我们必然可以找到一个入度为零的node 。我们把第个物品分配给它即可。由于的入度为，说明在之前是不被任何玩家嫉妒的。那么现在他多拿到一个物品，至多让他人产生一个物品价值的嫉妒。因此仍保持。

该算法的时间复杂度为。原因是，找到一个环并消解它需要的时间，而每轮分配一个物品后，图里至多新增条边，总共轮，因此最多需要消环次，所以时间复杂度为。

待续…