*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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
