论文标题
关于分配连续块的公平性
On the Price of Fairness of Allocating Contiguous Blocks
论文作者
论文摘要
在这项工作中，我们重新审视了分配许多不可分割的物品的问题，这些项目位于多个代理上。可行的分配要求将每个代理分配的项目连接到线上。这些物品可以是代理商具有非负公用事业的商品，也可以是公用事业非阳性的琐事。我们的目标是了解通过执行公平的分配，即公平价格（POF），不可避免地牺牲福利的程度。我们研究平等和功利主义福利。 Suksompong的先前作品[DIPT。应用。 Math。，2019年]以及Höhne和Van Stee [Inf。 [Comput。，2021]]研究了POF，涉及嫉妒性和相称性的概念。但是，这些公平的分配几乎没有针对不可分割的项目，因此，在这项工作中，我们专注于最大值的公平性和相称性的放松，最多可令人满意。对于大多数设置，我们给出（几乎）POF的（几乎）紧密比率，所有上限都通过设计多项式时间算法证明。
In this work, we revisit the problem of fairly allocating a number of indivisible items that are located on a line to multiple agents. A feasible allocation requires that the allocated items to each agent are connected on the line. The items can be goods on which agents have non-negative utilities, or chores on which the utilities are non-positive. Our objective is to understand the extent to which welfare is inevitably sacrificed by enforcing the allocations to be fair, i.e., price of fairness (PoF). We study both egalitarian and utilitarian welfare. Previous works by Suksompong [Discret. Appl. Math., 2019] and Höhne and van Stee [Inf. Comput., 2021] have studied PoF regarding the notions of envy-freeness and proportionality. However, these fair allocations barely exist for indivisible items, and thus in this work, we focus on the relaxations of maximin share fairness and proportionality up to one item, which are guaranteed to be satisfiable. For most settings, we give (almost) tight ratios of PoF and all the upper bounds are proved by designing polynomial time algorithms.
