Speaker: László Végh the Mathematics Department at the London School of Economics
Time: 2023-07-14 15:20-2023-07-14 17:00
Venue: FIT 1-315 or Tencent Meeting ID: 981-127-091

Abstract:

The Nash social welfare (NSW) problem asks for an allocation of indivisible items to agents in order to maximize the geometric mean of agents’ valuations. This is a common objective for fair division, representing a balanced tradeoff between the often conflicting requirements of fairness and efficiency. The problem is NP-complete already for additive valuation functions. For any ε>0, we give a deterministic (4+ε)-approximation algorithm for the NSW under submodular valuations, improving on the previous best approximation factor of 380. Our algorithm is very simple, using a combination of matching and local search techniques.

This is joint work with Jugal Garg (UIUC), Edin Husić (IDSIA), Wenzheng Li (Stanford), and Jan Vondrák (Standford）.

Short Bio:

László Végh is a professor in the Mathematics Department at the London School of Economics. He received his Ph.D. from Eötvös University, Budapest in 2010, and was a postdoc at Georgia Tech in 2011-12. His research addresses fundamental questions in algorithms and optimization. He received the best student paper award at STOC in 2010, and jointly the best paper award in 2018. He is an associate editor at journals including Operations Research, Mathematical Programming, and Mathematics of Operations Research, and has served on the program committee for a number of conferences. His work was supported by the European Research Council. Together with Ola Svensson and Jakub Tarnawski, he is a co-recipient of a Best Paper Award at the International Congress of Basic Science for their work on the Asymmetric Traveling Salesman Problem.