无权重物品的几乎无忌妒分配

Almost envy-free allocations of unweighted items

公平分配研究如何把m个不可分的物品公平地分配给n个玩家.每个玩家关于物品有一个可加的估值函数.物品是无权重的,如果他们的取值范围为{1,0,-1}.非负估值的物品称为奖品,非正估值的物品称为苦差.本文考虑寻找无权重物品的分配,并满足“相差任意物品下是无忌妒的”(envy-free up to any item,EFX0).EFX;是本领域内最受关注的公平性度量.一般可加估值函数下的EFX;分配的存在性仍然是开放的.本文提出寻找无权重物品的EFX;分配的多项式时间算法.为了达到这个目的,本文分别提出了寻找无权重奖品和无权重苦差的EFX;分配的算法.然后,通过将二者小心地结合起来,本文得到了最终的算法.本文的结果完整刻画了无权重情况下寻找EFX;分配的解决方案.

Fair allocation studies how to fairly allocate m indivisible items among n agents.Each agent has an additive valuation function over items,which are unweighted if their values are in{1,0,-1}.Those items with non-negative values are called goods,and those with non-positive values are called chores.We consider the problem of finding an allocation of unweighted items which is envy-free up to any item(EFX0).EFX0 is one of the most concerned fairness notions in the literature.It remains open whether EFX0 allocations always exist even under additive valuation functions.In this paper,we present polynomial-time algorithms for finding an EFX0 allocation of unweighted items.To achieve this,we present algorithms for finding EFX0 allocations of unweighted goods and unweighted chores separately,which are then carefully merged to deliver the final algorithms.As a result,we provide a complete solution for finding EFX0 allocations in the unweighted scenario.