论文标题
计算帕累托最佳和几乎不嫉妒的不可分割的商品分配
Computing Pareto-Optimal and Almost Envy-Free Allocations of Indivisible Goods
论文作者
论文摘要
我们研究了一套不可分割的商品的公平有效分配给具有累加估值的代理商的不可分割的商品的问题，该问题是使用嫉妒性的公平性观念（EF1），最高可比性（EF1），最高可（EQ1）与帕累托（Pareto）与帕累托（Pareto）相结合（PO）。存在一种伪多项式时间算法来计算EF1+PO分配和非结构性证明，表明存在EF1和EF1和分数的分配偏瘫（FPO），这是比PO更强大的概念。我们提出了一种伪多项式时间算法来计算EF1+FPO分配，从而改善了较早的结果。我们的技术还使我们能够证明EQ1+FPO分配始终存在时，当值是正时，并且可以在伪单式时间中计算出来。 我们还考虑了$ k $ - yar的类别，其中$ k $是一个常数，即每个代理商最多具有$ k $的商品值。对于这种情况，我们表明可以在强烈多项式时间内计算EF1+FPO分配。当所有值均为正时，我们表明可以在强烈的多项式时间内计算此类实例的EQ1+FPO分配。接下来，我们考虑代理数量恒定的实例，并表明可以在多项式时间内计算EF1+PO（同样，EQ1+PO）分配。这些结果显着扩展了多项式时间的可计算性，超出了已知的二进制或相同估值案例。 我们还设计了一种多项式时间算法，该算法计算NASH福利最大化分配时，当经常有许多具有许多不同值的代理时，货物的分配。最后，在复杂性方面，我们表明计算EF1+FPO分配的问题在于复杂性类PL。
We study the problem of fair and efficient allocation of a set of indivisible goods to agents with additive valuations using the popular fairness notions of envy-freeness up to one good (EF1) and equitability up to one good (EQ1) in conjunction with Pareto-optimality (PO). There exists a pseudo-polynomial time algorithm to compute an EF1+PO allocation and a non-constructive proof of the existence of allocations that are both EF1 and fractionally Pareto-optimal (fPO), which is a stronger notion than PO. We present a pseudo-polynomial time algorithm to compute an EF1+fPO allocation, thereby improving the earlier results. Our techniques also enable us to show that an EQ1+fPO allocation always exists when the values are positive and that it can be computed in pseudo-polynomial time. We also consider the class of $k$-ary instances where $k$ is a constant, i.e., each agent has at most $k$ different values for the goods. For such instances, we show that an EF1+fPO allocation can be computed in strongly polynomial time. When all values are positive, we show that an EQ1+fPO allocation for such instances can be computed in strongly polynomial time. Next, we consider instances where the number of agents is constant and show that an EF1+PO (likewise, an EQ1+PO) allocation can be computed in polynomial time. These results significantly extend the polynomial-time computability beyond the known cases of binary or identical valuations. We also design a polynomial-time algorithm that computes a Nash welfare maximizing allocation when there are constantly many agents with constant many different values for the goods. Finally, on the complexity side, we show that the problem of computing an EF1+fPO allocation lies in the complexity class PLS.
