时间：2024年9月23日14:00-15:30

地点：立德楼1826报告厅

报告题目：The Incentive Guarantees Behind Nash Welfare in Divisible Resources Allocation

报告摘要：We study the problem of allocating divisible resources among n agents, hopefully in a fair and efficient manner. With the presence of strategic agents, additional incentive guarantees are also necessary, and the problem of designing fair and efficient mechanisms becomes much less tractable. While the maximum Nash welfare (MNW) mechanism has been proven to be prominent by providing desirable fairness and efficiency guarantees as well as other intuitive properties, no incentive property is known for it.

We show a surprising result that, when agents have piecewise constant value density functions, the incentive ratio of the MNW mechanism is 2 for cake cutting, where the incentive ratio of a mechanism is defined as the ratio between the largest possible utility that an agent can gain by manipulation and his utility in honest behavior. Remarkably, this result holds even without the free disposal assumption, which is hard to get rid of in the design of truthful cake cutting mechanisms. We also show that the MNW mechanism is group strategyproof when agents have piecewise uniform value density functions.

Moreover, we show that, for cake cutting, the Partial Allocation (PA) mechanism proposed by Cole et al., which is truthful and 1/e-MNW for homogeneous divisible items, has an incentive ratio between [e^{1/e}, e] and when randomization is allowed, can be turned to be truthful in expectation. Given two alternatives for a trade-off between incentive ratio and Nash welfare provided by the MNW and PA mechanisms, we establish an interpolation between them for both cake cutting and homogeneous divisible items.

Finally, we study the existence of fair mechanisms with a low incentive ratio in the connected pieces setting. We show that any envy-free cake cutting mechanism with the connected pieces constraint has an incentive ratio of at least Ω(n).

This is a joint work with Xiaohui Bei, Jiajun Wu, and Mingwei Yang.

主讲人：陶表帅  上海交通大学副教授

主讲人简介：Biaoshuai Tao is a (tenure-track) associate professor at John Hopcroft Center for Computer Science at Shanghai Jiao Tong University since 2020. In 2020, he received his Ph.D. degree in computer science at the University of Michigan, Ann Arbor. His research interests mainly include the interdisciplinary area between theoretical computer science and economics, including social network analyses, resource allocation problems, and algorithmic game theory. Before joining the University of Michigan, Biaoshuai was employed as a project officer at Nanyang Technological University in Singapore from 2012 to 2015, and he received the B.S. degree in mathematical science with a minor in computing from Nanyang Technological University in 2012.

Webpage: https://jhc.sjtu.edu.cn/~bstao/