Title: A O(log log m) prophet inequality for subadditive combinatorial auctions
| Speaker: | Rian Neogi |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract:: I will present the paper "An O(log log m) prophet inequality for subadditive combinatorial auctions", by Dütting, Kesselheim, and Lucier. In the setting of online combinatorial auctions, we have a set of m items and n buyers. Buyers arrive one by one, and our goal is to irrevocably assign a set of items to each buyer as they arrive. An item can only be allocated to one buyer. Each buyer has a subadditive valuation function, which assigns a value to every possible subset of items that can be allocated to the buyer. Our goal is to maximize the social welfare of the final allocation, which is the sum of the valuations of the buyers. The paper provides a O(log log m) prophet inequality for this problem, beating the previous O(log m) barrier. This is the current best known polynomial time algorithm for this problem.