论文标题
两全其美：有权利的代理商
Best of Both Worlds: Agents with Entitlements
论文作者
论文摘要
不可分割的商品的公平划分是人工智能中的核心挑战。对于许多突出的公平标准，包括嫉妒 - 柔性（EF）或相称性（Prop），不可能存在满足这些标准的分配。这个问题的两种流行疗法是公平概念的随机或放松。及时的研究方向是将两者的优势结合在一起，通常称为两全其美（Bobw）。我们考虑具有权利的公平分裂，这允许将公平概念调整为代理商之间的异质优先事项。这是对标准公平分区模型的重要概括，在BOBW结果方面并不理解。我们的主要结果是用于添加估值和不同权利的彩票，这些款项是不含加权的嫉妒（WEF）的，以及最高的（WPROP1）的前post加权比例（WPROP1）和加权转移的嫉妒，最多是一种商品（WEF（1,1,1））。它可以在强烈的多项式时间内计算。我们表明，此结果很紧 - 前WEF与任何更强的前WEF放松都不兼容。此外，我们将BOBW的结果扩展到群体公平性，并将其结果的概括探索到具有更有表现力的估值功能的实例。
Fair division of indivisible goods is a central challenge in artificial intelligence. For many prominent fairness criteria including envy-freeness (EF) or proportionality (PROP), no allocations satisfying these criteria might exist. Two popular remedies to this problem are randomization or relaxation of fairness concepts. A timely research direction is to combine the advantages of both, commonly referred to as Best of Both Worlds (BoBW). We consider fair division with entitlements, which allows to adjust notions of fairness to heterogeneous priorities among agents. This is an important generalization to standard fair division models and is not well-understood in terms of BoBW results. Our main result is a lottery for additive valuations and different entitlements that is ex-ante weighted envy-free (WEF), as well as ex-post weighted proportional up to one good (WPROP1) and weighted transfer envy-free up to one good (WEF(1,1)). It can be computed in strongly polynomial time. We show that this result is tight - ex-ante WEF is incompatible with any stronger ex-post WEF relaxation. In addition, we extend BoBW results on group fairness to entitlements and explore generalizations of our results to instances with more expressive valuation functions.
