报告题目：Fairness Properties under Maximum Nash Social Welfare

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

报告摘要：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 the fairness, three well-adopted concepts, EFX (Envy-freeness up to any item), MMS (Maximin Share), 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 function. 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.

报告人简介：张涌，中国科学院深圳先进技术研究院研究员，博士生导师，香港大学名誉教授。中国运筹学会数学规划分会理事，中国计算机学会理论专委会委员。2007年博士毕业于复旦大学计算机系。之后在德国柏林工业大学数学系做博士后，香港大学计算机系任职高级研究员。研究方向包括算法优化、分布式计算、算法博弈论等，近年来在本领域中国际知名会议和期刊上发表文章超过100 篇。张涌研究员近年来承担了多项国家和省部级科研项目，包括国家自然科学基金，科技部国家重点研发计划，中科院重点部署项目等。

报告时间：2022年9月26日 9:00-10:00

报告地点：腾讯会议ID：531-676-867

主办单位：伟德国际1946源自英国