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

作者：张智杰; 应东昊; 张家琳; 孙晓明

来源：中国科学:信息科学 , 2022, 52(06): 935-946.

• 公平分配
• 无忌妒性
• 不可分物品
• 奖品
• 苦差

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

• 单位
  中国科学院大学; 中国科学院计算技术研究所