Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents

摘要

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, (2) an O(Dlog⁡m/log⁡log⁡m)-competitive prophet inequality for D-approximately subadditive agents, where D∈{1,…,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, value queries and demand queries.