2020/03/12 by Moshe Babaioff, Babaioff, Moshe, Michal Feldman +7 · 1 citation
Business, Management and Accounting · Decision Sciences · #Supply Chain and Inventory Management #Consumer Market Behavior and Pricing #Auction Theory and Applications
paper · pdf · doi:10.48550/arxiv.2003.05913
We consider a robust version of the revenue maximization problem, where a\nsingle seller wishes to sell n items to a single unit-demand buyer. In this\nrobust version, the seller knows the buyer's marginal value distribution for\neach item separately, but not the joint distribution, and prices the items to\nmaximize revenue in the worst case over all compatible correlation structures.\nWe devise a computationally efficient (polynomial in the support size of the\nmarginals) algorithm that computes the worst-case joint distribution for any\nchoice of item prices. And yet, in sharp contrast to the additive buyer case\n(Carroll, 2017), we show that it is NP-hard to approximate the optimal choice\nof prices to within any factor better than n1/2-\ε. For the special\ncase of marginal distributions that satisfy the monotone hazard rate property,\nwe show how to guarantee a constant fraction of the optimal worst-case revenue\nusing item pricing; this pricing equates revenue across all possible\ncorrelations and can be computed efficiently.\n