Combinatorial optimization, submodular functions, and Nash social welfare

I will talk about 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 "valuation functions" 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 valuation functions, 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 main new result is that one can find an allocation within a constant factor of the optimal Nash social welfare, whenever the valuation functions are submodular.

This is joint work with Wenzheng Li.