Online Contention Resolution Schemes for Network Revenue Management and Combinatorial Auctions

In the Network Revenue Management (NRM) problem, products composed of up to L resources are sold to stochastically arriving customers. We take a randomized rounding approach to NRM, motivated by the modern tool of Online Contention Resolution Schemes (OCRS). The goal is to take a fractional solution to NRM that satisfies the resource constraints in expectation, and implement it in an online policy that satisfies the resource constraints with probability 1, while (approximately) preserving all of the sales that were prescribed by the fractional solution. In NRM problems, customer substitution induces a negative correlation between products being demanded, making it difficult to apply the standard definition of OCRS. We start by deriving a more powerful notion of "random-element" OCRS that achieves a guarantee of 1/(1+L) for NRM with customer substitution, matching a common benchmark in the literature. We show this benchmark is unbeatable for all integers L that are the power of a prime number. We then show how to beat this benchmark under three widely applied assumptions. Finally, we show that under several assumptions, it is possible to do better than offline CRS when L>= 5. Our results have corresponding implications for Online Combinatorial Auctions, in which buyers bid for bundles of up to L items, and buyers being single-minded is akin to having no substitution. Our result under the assumption that products comprise one item from each of up to L groups implies that 1/(1+L) can be beaten for Prophet Inequality on the intersection of L partition matroids, a problem of interest. In sum, our paper shows how to apply OCRS to all of these problems and establishes a surprising separation in the achievable guarantees when substitution is involved, under general resource constraints parametrized by L.