Escaping Cannibalization? Correlation-Robust Pricing for a Unit-Demand Buyer - Babaioff, Moshe; Feldman, Michal; Gonczarowski, Yannai A.; Lucier, Brendan; Talgam-Cohen, Inbal (The 21th ACM conference on Economics and Computation (ACM EC 2020), 2020)
A single seller wishes to sell n items to a single unit-demand buyer. We consider a robust version of this revenue-maximization pricing problem, where the seller knows the buyer’s marginal distributions of values for each item, but not the joint distribution, and wishes to maximize worst-case revenue over all possible correlation structures. We devise a computationally efficient (polynomial in the support size of the marginals) algorithm that computes the worst-case joint distribution for any choice of item prices. And yet, in sharp contrast to the additive buyer case (Carroll, 2017), we show that it is NP-hard to approximate the optimal choice of prices to within any factor better than n^[1/2]−ε. For the special case of marginal distributions that satisfy the monotone hazard rate property, we show how to guarantee a constant fraction of the optimal worst-case revenue using item pricing; this pricing equates revenue across all possible correlations and can be computed efficiently.