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.