BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1070
DTSTAMP:20230914T125949Z
SUMMARY:Approximating the Nash Social Welfare with Subadditive Valuations
DESCRIPTION:Speaker: Umang Bhaskar\n\nAbstract: \nAbstract: How should o
ne divide $m$ goods between $n$ agents\, given the utility each agent has
when allocated a subset of goods? Allocations which maximize the Nash Soci
al Welfare --- the product of agent utilities for their allocation --- are
known to possess a number of natural and agreeable properties. Unfortunat
ely\, maximizing the Nash Social Welfare is known to be APX-hard\, even wh
en agent utility functions are additive over the set of goods.\nWe present
an algorithm that for the general case of subadditive utility functions f
or the agents\, obtains an $O(n)$-approximation to the optimal Nash Social
Welfare\, given value oracle access to the utility functions. This improv
es upon a previous $O(n log n)$ algorithm for submodular utilities (SODA '
20). Our approximation ratio is tight for subadditive utilities and for va
lue oracle access.\nThis is joint work with Siddharth Barman\, Anand Krish
na\, and Ranjani Sundaram.\n
URL:https://www.tcs.tifr.res.in/web/events/1070
DTSTART;TZID=Asia/Kolkata:20200717T140000
DTEND;TZID=Asia/Kolkata:20200717T150000
END:VEVENT
END:VCALENDAR