Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-068 | 6th April 2006 00:00

Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing


Authors: Patrick Briest, Piotr Krysta
Publication: 29th May 2006 11:25
Downloads: 3890


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.

ISSN 1433-8092 | Imprint