Title: “Maximizing the Nash Social Welfare”
Speaker: Dr. Vasilis Gatzelis (Assistant Professor at Drexel University)
Abstract: This talk will provide a brief survey of recent results on the fair and efficient allocation of resources among multiple heterogeneous agents. Each agent is characterized by a utility function that measures the agent’s value for the set of resources allocated to him, and our goal is to divide the resources among the agents aiming to maximize the Nash social welfare: the geometric mean of the agents’ utilities. The Nash social welfare objective has been studied for more than half a century, and it is known to provide a highly desired balance between fairness and efficiency. Maximizing this objective is known to be computationally intractable when the resources being allocated are indivisible, but we provide algorithms with constant factor approximation guarantees. For the case of divisible resources, we focus on problem instances where the agents’ preferences are not known to the designer: we study the extent to which the agents may wish to lie about their preferences, and we propose mechanisms that incentivize the agents to be truthful in reporting their preferences, while at the same time optimizing the Nash social welfare objective.
The results are drawn from the following papers:
“Convex Program Duality, Fisher Markets, and Nash Social Welfare”, with R. Cole et al. at EC 2017
“Nash Social Welfare Approximation for Strategic Agents” with S. Branzei and R. Mehta at EC 2017
“Approximating the Nash Social Welfare with Indivisible Items” with R. Cole at STOC 2015
“Mechanism Design for Fair Division” with R. Cole and G. Goel at EC 2013