报告题目：The Existence of EFX and PMMS Allocations under Additive Value Functions

报 告 人：张涌 研究员（中国科学院深圳先进技术研究院）

报告时间：2024年11月16日 19：30-20:30

报告地点：数学楼301

报告摘要： Fair division is an important problem in operation research, especially in the field of resource allocation. In this talk, we consider the assignment of indivisible goods between agents with additive value functions and analyze the fairness property while the Nash Social Welfare (NSW) is maximized. To measure fairness, three well-adopted concepts, EFX (Envy-freeness up to any item) and PMMS (Pairwise Maximin Share), are considered. We show that an MNW allocation also satisfies PMMS and EFX respectively if the value functions among agents are identical. This result directly leads to the existence of PMMS under identical value functions. In this setting, we give an algorithm to achieve a PMMS allocation. Moreover, we consider the budget-feasible allocation where the budget of each agent is bounded by some positive values. For the budget-feasible variant, we show that EFX can be approximated with the ratio of 1/(k∙(k-1)) if the value functions are in the range [1, k], or with the ratio of 1/4 if agents have binary value functions. Additionally, we propose an algorithm to compute an EFX allocation for binary variants under budget constraints in polynomial time.

报告人简介：张涌，中国科学院深圳先进技术研究院研究员，香港大学名誉教授。中国运筹学会理事，中国运筹学会数学规划分会常务理事，中国计算机学会理论计算机/大数据/计算经济/协同计算专委会执行委员，英国工程技术学会会士，电子电气工程师学会高级会员。2007年博士毕业于复旦大学计算机系。之后在德国柏林工业大学数学系做博士后，香港大学计算机系任职高级研究员。张涌博士的研究方向包括算法优化、分布式计算等，近年来在国际知名会议和期刊上发表文章100余 篇。张涌博士近年来主持了多项国家和省部级科研项目，包括科技部国家重点研发计划，国家自然科学基金，中科院重点部署项目等。