Improved Prophet Inequalities for Combinatorial Welfare Maximization with (Approximately) Subadditive Agents

Algorithms Seminar
Speaker Name
Hanrui Zhang
Date and Time
Talk will be virtual on Zoom

We study a stochastic optimization problem called prophet inequalities, where a principal allocates items to agents arriving online, given only statistical knowledge about how much each agent values the items.  We give a framework for designing prophet inequalities for combinatorial welfare maximization.  Instantiated with different parameters, our framework implies (1) an $O(\log m / \log \log m)$-competitive prophet inequality for subadditive agents, improving over the $O(\log m)$ upper bound via item pricing, (2) an $O(D \log m / \log \log m)$-competitive prophet inequality for $D$-approximately subadditive agents, where $D \in \{1, \dots, m - 1\}$ measures the maximum number of items that complement each other, and (3) as a byproduct, an $O(1)$-competitive prophet inequality for submodular or fractionally subadditive (a.k.a.\ XOS) agents, matching the optimal ratio asymptotically.  Our framework is computationally efficient given sample access to the prior and demand queries.

Short Biography

Hanrui is a fourth-year PhD student in Computer Science at Duke University, advised by Vincent Conitzer.  His research interests lie in the area of Economics and Computation -- the study of problems with economic motivations that can be approached using techniques from computer science.  His recent work focuses on learning and decision making in complex environments, in the presence of strategic behavior, under uncertainty of the future, with rich preferences and limited means of interaction.