Buying cheap is expensive: Hardness of non-parametric multi-product pricing

We investigate non-parametric unit-demand pricing problems, in which we want to find revenue maximizing prices for products ℘ based on a set of consumer profiles C. A consumer profile consists of a number of non-zero budgets for different products and possibly an additional product ranking. Once prices are fixed, each consumer chooses to buy one of the products she can afford based on some predefined selection rule. We distinguish between the min-buying, maxbuying, and rank-buying models. For the min-buying model we show that it is not approximable within O(log^ϵ|C|) for some constant ϵ > 0, unless NP ⊆ DTIME(n^{O(log log} n)), thereby closing the gap between the known algorithmic results and previous lower bounds. We also prove inapproximability within O(ℓ^ϵ), ℓ being an upper bound on the number of non-zero budgets per consumer, and O(|℘|^ϵ) under slightly stronger assumptions and provide matching upper bounds. Surprisingly, these hardness results hold even if a price ladder constraint, i.e., a predefined order on the prices of all products, is given. For the max-buying model a PTAS exists if a price ladder is given. We give a matching lower bound by proving strong NP-hardness. Assuming limited product supply, we analyze a generic local search algorithm and prove that it is 2-approximate. Finally, we discuss implications for the rankbuying model.