Approximation algorithms and online mechanisms for item pricing

ABSTRACT

We present approximation and online algorithms for a number of problems of pricing items for sale so as to maximize seller's revenue in an unlimited supply setting. Our first result is an O(k)-approximation algorithm for pricing items to single-minded bidders who each want at most k items. This improves over recent independent work of Briest and Krysta [5] who achieve an O(k²) bound. For the case k = 2, where we obtain a 4-approximation, this can be viewed as the following graph vertex pricing problem: given a (multi) graph G with valuations w_e on the edges, find prices p_i ≥ 0 for the vertices to maximize Σ (p_i + p_j). {e=(i,j):w_e ≥ p_i + p_j.We also improve the approximation of Guruswami et al. [11] from O(log m + log n) to O(log n), where m is the number of bidders and n is the number of items, for the "highway problem" in which all desired subsets are intervals on a line.Our approximation algorithms can be fed into the generic reduction of Balcan et al. [2] 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 [3], Blum et al. [4], and Kalai and Vempala [13] 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.

REFERENCES

• 1: Baruch Awerbuch , Robert D. Kleinberg, Adaptive routing with end-to-end feedback: distributed learning and geometric approaches, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007367]
• 2: Maria-Florina Balcan , Avrim Blum, Mechanism Design via Machine Learning, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.605-614, October 23-25, 2005 [doi>10.1109/SFCS.2005.50]
• 3: Avrim Blum , Jason D. Hartline, Near-optimal online auctions, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 4: Avrim Blum , Vijay Kumar , Atri Rudra , Felix Wu, Online learning in online auctions, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 5: Patrick Briest , Piotr Krysta, Single-minded unlimited supply pricing on sparse instances, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1093-1102, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109678]
• 6: Varsha Dani , Thomas P. Hayes, Robbing the bandit: less regret in online geometric optimization against an adaptive adversary, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.937-943, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109660]
• 7: Erik D. Demaine , Mohammad Taghi Hajiaghayi , Uriel Feige , Mohammad R. Salavatipour, Combination can be hard: approximability of the unique coverage problem, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.162-171, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109577]
• 8: Guy Even , Oded Goldreich , Michael Luby , Noam Nisan , Boban Veličković, Efficient approximation of product distributions, Random Structures & Algorithms, v.13 n.1, p.1-16, Aug. 1998 [doi>10.1002/(SICI)1098-2418(199808)13:1<1::AID-RSA1>3.0.CO;2-W]
• 9: A. Goldberg, J. Hartline, A. Karlin, M. Saks, and A. Wright. Competitive auctions. Games and Economic Behavior. (To appear). An earlier version available as InterTrust Technical Report STAR-TR-99.09.01.
• 10: Andrew V. Goldberg , Jason D. Hartline , Andrew Wright, Competitive auctions and digital goods, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.735-744, January 07-09, 2001, Washington, D.C., United States
• 11: Venkatesan Guruswami , Jason D. Hartline , Anna R. Karlin , David Kempe , Claire Kenyon , Frank McSherry, On profit-maximizing envy-free pricing, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 12: J. Hartline and V. Koltun. Near-Optimal Pricing in Near-Linear Time . In 9th Workshop on Algorithms and Data Structures, pages 422--431, 2005.
• 13: Adam Kalai , Santosh Vempala, Efficient algorithms for online decision problems, Journal of Computer and System Sciences, v.71 n.3, p.291-307, October 2005 [doi>10.1016/j.jcss.2004.10.016]
• 14: Michael Luby , Avi Wigderson, Pairwise Independence and Derandomization, University of California at Berkeley, Berkeley, CA, 1995
• 15: H. B. McMahan and A. Blum. Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary. In Proceedings of 17th Conference on Computational Learning Theory, pages 109--123, 2004.
• 16: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Economics, Theory

Keywords:
approximation algorithms, combinatorial auctions, online optimization, single minded, unlimited supply