论文标题
优先级代理商的公平部门
Fair Division with Prioritized Agents
论文作者
论文摘要
我们认为不可分割的项目的公平分裂问题。众所周知，可能不存在无嫉妒的分配，并且已广泛考虑了一种嫉妒柔软，嫉妒柔和的轻松版本（EF1）。在EF1分配中，代理商可能会羡慕他人分配的股票，但最多只能一项。在许多应用程序中，我们可能希望指定一部分优先代理的子集，在这些药物中需要从这些代理到其余代理，同时确保整个分配仍然是ef1，在这些应用程序中。优先的代理商可能是那些在以前的EF1分配中令人羡慕的代理商，那些属于代表性不足的群体等的代理人。我们提出了一个新的公平概念，名为Envy-Freyentes lightistife and Adistifiend Agentents“ Efprorior”，并研究存在和算法方面的问题，以计算出EFPROPRIOR的问题。通过添加估值，简单的圆形旋转算法能够计算EFIOR分配。在本文中，我们主要关注一般估值。特别是，我们提出了一种多项式时间算法，该算法输出了分配的大多数项目。当所有项目需要分配时，我们还为某些动机的特殊情况提供了多项式时间算法。
We consider the fair division problem of indivisible items. It is well-known that an envy-free allocation may not exist, and a relaxed version of envy-freeness, envy-freeness up to one item (EF1), has been widely considered. In an EF1 allocation, an agent may envy others' allocated shares, but only up to one item. In many applications, we may wish to specify a subset of prioritized agents where strict envy-freeness needs to be guaranteed from these agents to the remaining agents, while ensuring the whole allocation is still EF1. Prioritized agents may be those agents who are envious in a previous EF1 allocation, those agents who belong to underrepresented groups, etc. Motivated by this, we propose a new fairness notion named envy-freeness with prioritized agents "EFPrior", and study the existence and the algorithmic aspects for the problem of computing an EFPrior allocation. With additive valuations, the simple round-robin algorithm is able to compute an EFPrior allocation. In this paper, we mainly focus on general valuations. In particular, we present a polynomial-time algorithm that outputs an EFPrior allocation with most of the items allocated. When all the items need to be allocated, we also present polynomial-time algorithms for some well-motivated special cases.
