Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Interesting seminar this Friday

Huy Tuan Pham huypham at
Mon Mar 15 14:45:07 PDT 2021

Hi everyone,

The Faculty Area of Research Seminar in the Math Department this Friday
(03/19) may be of interest to some of you.


*Title:* *Combinatorial optimization, submodular functions, and Nash social

*Speaker: Jan Vondrak*

*Abstract:* 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.


The seminar runs from 11:30AM-12:30PM PST this Friday (03/19). This is the
Zoom link for the event.

Join from PC, Mac, Linux, iOS or Android:

    Password: 986571

Best wishes,

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list