论文标题
不可分割的商品的比例分配最高价值最低的商品
Proportional Allocation of Indivisible Goods up to the Least Valued Good on Average
论文作者
论文摘要
我们研究了将一组不可分割的商品分配给多个代理商的问题，并专注于比例，这是经典的公平概念之一。由于当商品不可分割的情况下，比例分配并不总是存在，因此在先前的工作中已经考虑了相称的概念。其中，在所有情况下，都可以达到最佳相称的概念（propm）。在本文中，我们将相称性的概念介绍到平均价值最低的概念（Propavg），这比Propm更强烈，并表明在所有情况下始终存在Propavg分配，并且可以在多项式时间内计算。所有实例的%%。我们的结果将Propavg确立为在所有情况下都可以实现的明显的非平凡公平概念。我们的证明是建设性的，并且基于一种概括剪切协议并使用递归技术的新技术。
We study the problem of fairly allocating a set of indivisible goods to multiple agents and focus on the proportionality, which is one of the classical fairness notions. Since proportional allocations do not always exist when goods are indivisible, approximate concepts of proportionality have been considered in the previous work. Among them, proportionality up to the maximin good (PROPm) has been the best approximate notion of proportionality that can be achieved for all instances. In this paper, we introduce the notion of proportionality up to the least valued good on average (PROPavg), which is a stronger notion than PROPm, and show that a PROPavg allocation always exists for all instances and can be computed in polynomial time. %% for all instances. Our results establish PROPavg as a notable non-trivial fairness notion that can be achieved for all instances. Our proof is constructive, and based on a new technique that generalizes the cut-and-choose protocol and uses a recursive technique.
