Pricing heterogeneous products to heterogeneous customers who buy sequentially

Abstract This paper considers optimal pricing in a system with limited substitutable resources, such as certain goods or services. Prices for the different resources have to be set and then customers with heterogeneous preferences show up sequentially. Customers, of n types, select an item from the m available resources, depending on their valuations of the resources and the prices. The goal is to analyze this optimization problem, characterize a set of candidates to optimal solutions and provide methods for solving it. We prove that this problem is NP-hard to approximate within a factor O (n^1-) O (n 1 - ε) for any fixed >0 ε > 0. Another important contribution is to prove that, the space of prices (which in principle is a continuous domain in {R}ᵐ R m), can be reduced to a finite set of vectors of cardinality m^m-2nᵐ2ᵐ m m - 2 n m 2 m. For a deterministic version of the problem, where the customer types are known to the firm, we provide a mathematical program that chooses the best set of prices. We report extensive computational results showing the usefulness of our exact approach to solve medium size problems with up to 200 customers and different assortments of products and customer types. We then show how to approximate the stochastic model by a small number of solutions of deterministic scenarios solved using a mixed-integer linear program.