Approximation in Multi-dimensional Pricing



Jason Hartline
Northwestern University
Department of Electrical Engineering and Computer Science

Monday  October 20, 2008
4:15 PM, 498 Uris Hall



There are concise characterizations of optimal mechanisms and monopoly pricings in single-dimensional cases (e.g., Myerson (1981)). In multi-dimensional (e.g., multi-product) settings there are no such characterizations. In many simple, relevant settings optimal and even near-optimal item-pricings are computationally intractable. We consider item-pricing for a unit-demand consumer with values for each item drawn independently, perhaps not identically, from a known distribution. We draw a close analogy between this revenue maximization problem and Myerson's single item auction problem. We show that considering the problem in virtual valuation space instead of valuation space simplifies the problem of approximating the optimal item-pricing. Indeed, with a constant virtual price for each item a seller can approximate the revenue of the optimal item-pricing. We prove an approximation factor of three.