Item pricing for revenue maximization

ABSTRACT

We consider the problem of pricing n items to maximize revenue when faced with a series of unknown buyers with complex preferences, and show that a simple pricing scheme achieves surprisingly strong guarantees.

We show that in the unlimited supply setting, a random single price achieves expected revenue within a logarithmic factor of the total social welfare for customers with general valuation functions, which may not even necessarily be monotone. This generalizes work of Guruswami et. al [18], who show a logarithmic factor for only the special cases of single-minded and unit-demand customers.

In the limited supply setting, we show that for subadditive valuations, a random single price achieves revenue within a factor of 2^{O(√(log n loglog n)} of the total social welfare, i.e., the optimal revenue the seller could hope to extract even if the seller could price each bundle differently for every buyer. This is the best approximation known for any item pricing scheme for subadditive (or even submodular) valuations, even using multiple prices. We complement this result with a lower bound showing a sequence of subadditive (in fact, XOS) buyers for which any single price has approximation ratio 2^{Ω(log1/4 n)}, thus showing that single price schemes cannot achieve a polylogarithmic ratio. This lower bound demonstrates a clear distinction between revenue maximization and social welfare maximization in this setting, for which [12,10] show that a fixed price achieves a logarithmic approximation in the case of XOS [12], and more generally subadditive [10], customers.

We also consider the multi-unit case examined by [1111] in the context of social welfare, and show that so long as no buyer requires more than a 1 -- ε fraction of the items, a random single price now does in fact achieve revenue within an O(log n) factor of the maximum social welfare.

REFERENCES

• 1: G. Aggarwal, T. Feder, R. Motwani, and A. Zhu. Algorithms for multi-product pricing. In Proceedings of the International Colloquium on Automata, Languages, and Programming, pages 72--83, 2004.
• 2: Maria-Florina Balcan , Avrim Blum, Approximation algorithms and online mechanisms for item pricing, Proceedings of the 7th ACM conference on Electronic commerce, p.29-35, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134711]
• 3: 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]
• 4: M.-F. Balcan, A. Blum, and Y. Mansour. Single price mechanisms for revenue maximization in unlimited supply combinatorial auctions. Technical Report CMU-CS-07-111, Carnegie Mellon University, February 2007.
• 5: L. Blumrosen and N. Nisan. Combinatorial auctions. In N. Nisan, T. Roughgarden, E. Tardos, and V.V. Vazirani, editors, Algorithmic Game Theory. Cambridge University Press, 2007.
• 6: P. Briest, M. Hoefer, and P. Krysta. Stackelberg network pricing games. In Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS), 2008.
• 7: 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]
• 8: Peter Cramton , Yoav Shoham , Richard Steinberg, Combinatorial Auctions, The MIT Press, 2006
• 9: 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]
• 10: S. Dobzinski. Two Randomized Mechanisms for Combinatorial Auctions. In APPROX, 2007.
• 11: Shahar Dobzinski , Noam Nisan, Mechanisms for multi-unit auctions, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250960]
• 12: Shahar Dobzinski , Noam Nisan , Michael Schapira, Truthful randomized mechanisms for combinatorial auctions, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132607]
• 13: K. Elbassioni, R. Sitters, and Y. Zhang. A Quasi-PTAS for Profit-Maximizing Pricing on Line Graphs. In ESA, 2007.
• 14: Uriel Feige, On maximizing welfare when utility functions are subadditive, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132523]
• 15: Amos Fiat , Andrew V. Goldberg , Jason D. Hartline , Anna R. Karlin, Competitive generalized auctions, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509921]
• 16: 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
• 17: A. Grigoriev, J. van Loon, R. Sitters, and M. Uetz. How to Sell a Graph: Guideliness for Graph Retailers. Meteor Research Memorandum RM/06/001, Maastricht University, 2005.
• 18: 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
• 19: J. Harltine and A. Karlin. Profit maximization in mechanism design. In N. Nisan, T. Roughgarden, E. Tardos, and V.V. Vazirani, editors, Algorithmic Game Theory. Cambridge University Press, 2007.
• 20: J. Hartline and V. Koltun. Near-Optimal Pricing in Near-Linear Time . In 9th Workshop on Algorithms and Data Structures, pages 422--431, 2005.
• 21: Noam Nisan , Tim Roughgarden , Eva Tardos , Vijay V. Vazirani, Algorithmic Game Theory, Cambridge University Press, New York, NY, 2007
• 22: Ron Lavi , Chaitanya Swamy, Truthful and Near-Optimal Mechanism Design via Linear Programming, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.595-604, October 23-25, 2005 [doi>10.1109/SFCS.2005.76]
• 23: B. Lehmann, D. Lehmann, and N. Nisan. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior, 2006.
• 24: Daniel Lehmann , Liadan Ita Oćallaghan , Yoav Shoham, Truth revelation in approximately efficient combinatorial auctions, Journal of the ACM (JACM), v.49 n.5, p.577-602, September 2002 [doi>10.1145/585265.585266]
• 25: R. Myerson. Optimal Auction Design. Mathematics of Opperations Research, 6:58--73, 1981.
• 26: N. Nisan. Introduction to mechanism design (for computer scientists). In N. Nisan, T. Roughgarden, E. Tardos, and V.V. Vazirani, editors, Algorithmic Game Theory. Cambridge University Press, 2007.
• 27: W. Vickery. Counterspeculation, Auctions and Competitve Sealed Tenders. Journal of Finanace, 1961.

INDEX TERMS

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

General Terms:
Algorithms, Economics, Theory

Keywords:
approximation algorithms, combinatorial auctions