CS 789 THEORY SEMINAR [home]

Speaker:    Paat Rusmevichientong, School of Operations Research and Industrial Engineering
Date:          September 19, 2005
Title:          A Linear Programming-Based Approximation Algorithm for Multi-Product Pricing under A Discrete Choice Model of Product Differentiation

Abstract:

We study multi-product pricing under a discrete choice model of product differentiation with arbitrary distributions of consumer-product utilities and constant marginal costs of production. Motivated by the availability of consumer preference data collected through e-commerce or product recommendation web sites, our model assumes that each consumer assigns a willingness-to-pay to each product, which may differ from one product to another. So long as the price does not exceed her willingness-to-pay for the product, the consumer is entirely insensitive to price, after which she will no longer consider the product.

Assuming competitors’ prices remain constant, we wish to determine profit-maximizing prices. We show that the optimization problem is NP-complete in the strong sense and develop an approximation algorithm with a provable performance guarantee based on a linear programming relaxation and a probabilistic rounding technique. Numerical experiments on many problem instances yield encouraging computational results, showing that the profit generated by the algorithm differs from the optimal by only 7% on average.