Title: A Constant Factor Prophet Inequality for Subadditive Combinatorial Auctions
| Speaker: | Rian Neogi |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract: In this talk, I will go through the paper of Correa and Cristi that appeared in STOC 2023. The paper proves a O(1) prophet inequality for online combinatorial auctions with subadditive buyers.
Their techniques involve the use of what they call a Random Score Generator (RSG for short), which is a distribution over prices of the items. Each buyer 'plays' an RSG. The algorithm samples a vector of prices of the items from this RSG for each buyer as they arrive, and assigns to them the set of items for which the sampled prices are larger than prices from another independent sample from the RSGs of all the buyers. A mirroring argument is used to bound the value of the allocation computed by their algorithm, and a novel fixed point argument is used to show the existence of RSGs that guarantee a good approximation.
In contrast to the O(log log m) prophet inequality covered previously in the CO reading group, the algorithm in this paper does not run in polynomial time, and does not involve posted prices.