Approximation in Multi-dimensional Pricing
Jason Hartline
Northwestern University
Department of Electrical Engineering
and Computer Science
Abstract:
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.