Computational Aspects of Combinatorial Pricing
Patrick Briest
Cornell University, Department of Computer Science
Abstract:
We consider the problem of assigning revenue maximizing prices to a collection of goods given data about the consumers' preferences. Apart from being of interest in its own right, this problem is closely connected to the design of revenue maximizing combinatorial auctions.
In the most general scenario, a consumer's preferences are expressed by a valuation function assigning a value to every possible subset of goods. Given a fixed set of prices, a consumer purchases the set of goods maximizing his utility, i.e., the difference between his value and the sum of item prices. Our first result shows that the simple single-price algorithm achieves a logarithmic approximation guarantee for this problem.
We then turn to a very restricted class of valuation functions, in which each consumer has a single positive value for receiving one good out of a set of alternatives, and prove a complementing lower bound. More formally, we show that this uniform-budget unit-demand envy-free pricing problem is hard to approximate within semi-logarithmic ratios under an assumption about the hardness of refuting random 3CNF formulas. This is joint work with Martin Hoefer and Piotr Krysta.