【论文评述】Constraints in Fair Division

发表于 更新于 分类于

文献：Suksompong W. Constraints in fair division[J]. ACM SIGecom Exchanges, 2021, 19(2): 46-61.

问题

Fair Division（公平分配）问题，是一类在数学和理论计算机科学里被长久研究的问题。和名字一样，Fair Division简单地讲就是如何把资源公平地分配给多个agents。

个agents为集合，全体资源为集合。

两类资源

资源分为两类，一类是divisible的连续资源，如一段时间、一块地皮、一块蛋糕，因此这类问题也叫cake cutting问题。

另一类是indivisible的不连续资源，如一些书本、一些画作、一堆珠宝等。

对于cake cutting，cake常用这样的区间表示，第个agent在区间取得的效益记为。

对于不连续资源，一组物品记为，第个agent在物品集合上取得的效益记为。

两类资源的效益函数通常是单调的（东西越多效益越高），有时候还是可加的（比如）

在设计算法的时候，我们首先要明确我们对效益函数能做的基本询问有哪些。

对于cake cutting，有两种基本询问：

  1. 输出的值

  2. 输出最小的满足的，或者输出不存在

这被称为Robertson–Webb模型。

对于不连续资源，如果效益不具有可加性，我们使用“效益谕示模型”（谕示就是计算理论的oracle）：对于任意和，可以询问。

对“公平”的抽象

  1. Envy-freeness

    即对比了所有人获得的资源后，仍然觉得自己手上获得的资源是最好的，即无嫉妒。

  2. Proportionality

  3. Maximin share fairness

    表示集合的的全体划分，例如时，，

    为中基数为的元素组成的集合（即把集合分成份的那些划分），

    对于,

    则Maximin share fairness即

    直观地讲，就是有很多种把全部资源划分为n份的方法f1、f2…，每一个方法都有与之对应的最差的那一小份，记为。。这种公平就是说，即使我甘愿做最差的一个，我也要是最好的划分方式下最差的那个。

  4. Envy-freeness up to k goods

    这是对Envy-freeness的放松，即

连通性限制

连续资源的连通分配

直观地讲，没有连通性限制的话，很多时候分配出来的蛋糕是一粒一粒的碎屑，很可能没有实际意义。

对于连通比例分配（即符合连通要求和Proportionality公平性），我们有下面这个基本算法：

Dubins–Spanier算法：

  1. 对所有查询

  2. 找到1中查询出的最小的，把分配给

  3. 对剩下的个angents和区间重复本算法

显然，Dubins–Spanier算法在Robertson–Webb模型下需要的查询复杂度。

Even 和 Paz 在1984年的一篇论文中运用分治法把查询复杂度降低到了。

Edmonds 和 Pruhs在2011年的一篇论文中证明了该问题的复杂度下界就是，甚至去掉连通这个要求下界仍然是。

尽管连通比例分配很简单，但是连通无嫉妒分配却非常非常困难！

首先，即使没有连通要求，目前最好的无嫉妒分配算法是Aziz
和 Mackenzie在2016年提出的一个查询复杂度为的算法。这个复杂度显然非常恐怖。

对于连通无嫉妒，Stromquist 和 Su 在上世纪用拓扑学手段证明了，连通无嫉妒分配总是存在的。

然而，Stromquist 在2008年开创性地证明了：在agent数量大于等于3时，不存在一种算法，可以在有限次的查询内找到连通无嫉妒分配。

于是，理论计算机科学们转而研究无嫉妒的放松情形，主要有下面两种：

  1. δ-additive-envy-free

  2. δ-multiplicative-envy-free

2017年，Branzei 和 Nisan证明了，对于任意，都存在算法，能够在的查询复杂度内计算出一个连通ε-additive-envy-free分配。

这个算法大致是将蛋糕切成价值不超过的碎片，然后暴力搜索所有的分配并找出符合要求的分配。

尽管这个算法的查询复杂度是线性的，但整体时间复杂度仍然是指数的，对于任何常数都是如此。

那么能不能在常数有限制的情况下找到一个多项式时间算法呢？

Goldberg等人在2020年给出了一个时的多项式时间算法，查询复杂度为。

然而，Goldberg的算法在有些时候会导致一些人的分配为0，这会导致-multiplicative-envy-free。

2019年，Arunachaleswaran等人给出了一个更加复杂的多项式时间算法，这个算法不仅能做到的-additive-envy-free，而且还能同时保证-multiplicative-envy-free。

上述这些算法给出了一类研究方向：

对于具有加性效益函数的cake cutting问题，在取哪些值时，存在能够计算连通-additive或-multiplicative-envy-free分配的多项式时间算法？对于这两类放松中的任意一个，是否存在相应的polynomial-time approximation scheme（PTAS）或fully polynomial-time approximation scheme（FPTAS）？

对于3个agent的-additive-envy-free问题，邓小铁等人于2012年给出了FPTAS。

不连续资源的连通分配

对于不连续资源，常常用无向图的形式来描述资源之间的连接关系。比方说，分配办公室的时候，我们可能希望同一个课题组的办公室是相连的，而办公室间的相邻关系可以用的边来描述。而且经过许多学者的研究，当是树时，maximin-share-fairness是一个合适的公平性度量。（下面把满足该公平的分配称为maxmin分配）

2017年，Bouveret等人证明了下述定理：

对于效益函数具有单调性的不连续资源分配，如果是树，一定存在一个连通maximin分配。不仅如此，如果效益函数具有可加性，这样的分配还能在多项式时间内被找到，并且每个agent的maxmin share也可以在多项式时间内被计算出来。

基数与拟阵限制

集合限制

分割限制

预算限制

冲突限制

（编写中）