• Time：Tuesday, Aug.16, 13:30--14:30

• Tencent Meeting ID：853-8759-9058；PW：123456

1. 主讲人介绍

Biaoshuai Tao is an assistant 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.

2. 讲座介绍

Title:

On the Complexity of Maximizing Social Welfare within Fair Allocations of Indivisible Goods

Abstract:

Fair division is a classical topic studied in various disciplines and captures many real applications. One important issue in fair division is to cope with (economic) efficiency and fairness. A natural question along this direction that receives considerable attention is: How to obtain the most efficient allocations among all the fair allocations? We study the complexity of maximizing social welfare within envy-free up to one item (EF1) allocations of indivisible goods for both normalized and unnormalized valuations. With two agents, we show a fully polynomial time approximation scheme (FPTAS) and complement this positive result with the NP-hardness result where the latter resolves an open problem raised by the previous work. Further, when the number of agents n is a constant, we provide a bi-criteria algorithm that finds the optimal social welfare while relaxing EF1 by a factor arbitrarily close to 1. We complement this by providing several strong inapproximability results if EF1 is not allowed to relax. In particular, we demonstrate that the inapproximability becomes stronger as n increases. Last, we consider the case with general number of agents. In this case, we give a variant of the round-robin algorithm with an approximation ratio of

This is a joint work with Xiaolin Bu, Zihao Li, Shengxin Liu, and Jiaxin Song.