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

Almost envy-free allocations of unweighted items

作　　者：张智杰 应东昊 张家琳[1,2] 孙晓明 Zhijie ZHANG;Donghao YING;Jialin ZHANG;Xiaoming SUN(Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100080,China;University of Chinese Academy of Sciences,Beijing 100080,China;Industrial Engineering and Operations Research Department,University of California,Berkeley,Berkeley 94704,USA)

机构地区：[1]中国科学院计算技术研究所,北京100080 [2]中国科学院大学,北京100080 [3]Industrial Engineering and Operations Research Department,University of California,Berkeley,Berkeley 94704,USA

出　　处：《中国科学：信息科学》2022年第6期935-946,共12页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:61832003,61872334);中国科学院战略性先导科技专项A类(批准号:XDA27000000)资助项目。

摘　　要：公平分配研究如何把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.

关 键 词：公平分配 无忌妒性 不可分物品 奖品 苦差 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]