We investigate non-parametric unit-demand pricing problems, in which the goal is to find revenue maximizing prices for a set of products based on consumer profiles obtained, e.g., from an e-Commerce website. A consumer profile consists of a number of non-zero budgets and a ranking of all the products the consumer is interested in. 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, max-buying, and rank-buying models.
For the min-buying and general rank-buying models the best known approximation ratio is logarithmic in the number of consumer profiles and, previously, the problem was only known to be APX-hard. We obtain the first (near) tight lower bound showing that the problem is not approximable within some polylogarithmic factor, unless NP = DTIME(n^(log log n)). Going to slightly stronger (but still reasonable) complexity theoretic assumptions we prove inapproximability also in terms of the number of non-zero budgets per consumer and the number of products. Surprisingly, these hardness results hold even if a price ladder constraint, i.e., a predefined total order on the prices of all products, is given.
This changes if we require that in the rank-buying model consumers' budgets are consistent with their rankings, i.e., that higher ranked products must be assigned a non-smaller budget. Assuming a price ladder a PTAS is known for both the rank-buying (with consistent budgets) and max-buying models. We prove that this is best possible, as both problems are strongly NP-hard, thereby resolving a previously open problem.
Previous results indicate that in the max-buying model the situation becomes more involved when we assume limited product supply. We show that this is in fact not the case if no price ladder constraint exists. More precisely, we prove that the problem is polynomially solvable for unit-supply, becomes APX-hard if maximum supply is increased to 2 and allows a 2-approximation in general. It turns out that techniques used here extend also to proving a bound of 2 on the price of anarchy of a closely related pricing game.
