ARC Colloquium - Wenzheng Li

Title: Constant factor approximation algorithms for Nash social welfare maximization 

Abstract: Consider the problem of allocating m indivisible items to n agents, where each agent has a valuation function. The Nash social welfare problem is to find an allocation that maximizes the geometric mean of the agents' valuations. This objective can be seen as a balance between fairness and efficiency. In this talk, I will show you various methods to get constant factor approximation algorithms for this problem with different class of valuations, from the basic additive functions to submodular or even subadditive.