论文标题
公平分配两种类型的琐事
Fair Allocation of Two Types of Chores
论文作者
论文摘要
我们考虑在添加估值下公平分配不可分割的家务的问题。我们假设杂务分为两种类型，在这种情况下，我们提出了几个结果。我们的第一个结果是在我们的设置中对帕累托最佳分配的新表征，以及一种多项式时间算法来计算最多一项（EF1）和帕累托最佳分配。然后，我们转向一个问题，即我们是否可以实现一个更强大的公平概念，称为任何项目（EFX）。我们提出了一种返回EFX分配的多项式时间算法。最后，我们表明，在我们的设置中，无论是否存在嫉妒的分配，都可以在多项式时间内检查。
We consider the problem of fair allocation of indivisible chores under additive valuations. We assume that the chores are divided into two types and under this scenario, we present several results. Our first result is a new characterization of Pareto optimal allocations in our setting, and a polynomial-time algorithm to compute an envy-free up to one item (EF1) and Pareto optimal allocation. We then turn to the question of whether we can achieve a stronger fairness concept called envy-free up any item (EFX). We present a polynomial-time algorithm that returns an EFX allocation. Finally, we show that for our setting, it can be checked in polynomial time whether an envy-free allocation exists or not.
