Tata Institute of Fundamental Research
Approximating the Nash Social Welfare with Subadditive Valuations
STCS Seminar
Speaker:
Umang Bhaskar
Organiser:
Rahul Vaze
Date:
Friday, 17 Jul 2020, 14:00 to 15:00
Venue:
(Scan to add to calendar)
Abstract:
Abstract: How should one divide $m$ goods between $n$ agents, given the utility each agent has when allocated a subset of goods? Allocations which maximize the Nash Social Welfare --- the product of agent utilities for their allocation --- are known to possess a number of natural and agreeable properties. Unfortunately, maximizing the Nash Social Welfare is known to be APX-hard, even when agent utility functions are additive over the set of goods.
We present an algorithm that for the general case of subadditive utility functions for the agents, obtains an $O(n)$-approximation to the optimal Nash Social Welfare, given value oracle access to the utility functions. This improves upon a previous $O(n log n)$ algorithm for submodular utilities (SODA '20). Our approximation ratio is tight for subadditive utilities and for value oracle access.
This is joint work with Siddharth Barman, Anand Krishna, and Ranjani Sundaram.
| Speaker: | Umang Bhaskar |
| Organiser: | Rahul Vaze |
| Date: | Friday, 17 Jul 2020, 14:00 to 15:00 |
| Venue: |
(Scan to add to calendar)
Abstract:
Abstract: How should one divide $m$ goods between $n$ agents, given the utility each agent has when allocated a subset of goods? Allocations which maximize the Nash Social Welfare --- the product of agent utilities for their allocation --- are known to possess a number of natural and agreeable properties. Unfortunately, maximizing the Nash Social Welfare is known to be APX-hard, even when agent utility functions are additive over the set of goods.
We present an algorithm that for the general case of subadditive utility functions for the agents, obtains an $O(n)$-approximation to the optimal Nash Social Welfare, given value oracle access to the utility functions. This improves upon a previous $O(n log n)$ algorithm for submodular utilities (SODA '20). Our approximation ratio is tight for subadditive utilities and for value oracle access.
This is joint work with Siddharth Barman, Anand Krishna, and Ranjani Sundaram.
We present an algorithm that for the general case of subadditive utility functions for the agents, obtains an $O(n)$-approximation to the optimal Nash Social Welfare, given value oracle access to the utility functions. This improves upon a previous $O(n log n)$ algorithm for submodular utilities (SODA '20). Our approximation ratio is tight for subadditive utilities and for value oracle access.
This is joint work with Siddharth Barman, Anand Krishna, and Ranjani Sundaram.