Algorithms & Randomness Center (ARC)
Jan Vondrak (Stanford)
Monday, March 29, 2021
Virtual via Bluejeans - 11:00 am
Title: Combinatorial allocation, submodular functions, and Nash social welfare
Abstract: I will discuss the problem of allocating indivisible goods to agents in order to optimize a certain welfare objective. Various objectives can be considered, the most natural being the summation of valuations of the participating agents. The "Nash social welfare" is an alternative objective which goes back to John Nash's work in the 1950s; it is the geometric average rather than a sum of valuations, which has several desirable properties such as balancing total welfare with fairness. On the technical side, it presents a significantly different problem, with connections to areas such as matching theory, computation of the permanent, and stable polynomials.
Our new result is a constant-factor approximation for Nash social welfare, whenever the valuation functions are submodular.
(Joint work with Wenzheng Li.)
----------------------------------
Videos of recent talks are available at: http://arc.gatech.edu/node/121
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
