Approximation Algorithms and Online Mechanisms for Item Pricing

We present approximation and online algorithms for problems of pricing a collection of items for sale so as to maximize the seller's revenue in an unlimited supply setting. We also improve the approximation of Guruswami et al. (2005) for the "highway problem" in which all desired subsets are intervals on a line, from O(log m + log n) to O(log n), where m is the number of bidders and n is the number of items. Our approximation algorithms can be fed into the generic reduction of Balcan et al. (2005) to yield an incentive-compatible auction with nearly the same performance guarantees so long as the number of bidders is sufficiently large. In addition, we show how our algorithms can be combined with results of Blum and Hartline (2005) and Kalai and Vempala (2003) to achieve good performance in the online setting, where customers arrive one at a time and each must be presented a set of item prices based only on knowledge of the customers seen so far.