›› 2012, Vol. 27 ›› Issue (4): 718-726.doi: 10.1007/s11390-012-1258-4

• Special Section on Theoretical Computer Science • Previous Articles     Next Articles

Pricing Loss Leaders Can be Hard

Yi Wu (吴奕)   

  1. IBM Almaden Research Center, San Jose 95120, CA, U.S.A.
  • Received:2011-02-27 Revised:2012-05-02 Online:2012-07-05 Published:2012-07-05
  • Supported by:

    This work is partially supported by the National Natural Science Foundation of China under Grant Nos. 91024028, 91024031. A preliminary version of the paper appeared in the Proceedings of ICS 2011.

Consider the problem of pricing n items under an unlimited supply with m single minded buyers, each of which is interested in at most k of the items. The goal is to price each item with profit margin p1, p2,..., pn so as to maximize the overall profit. There is an O(k)-approximation algorithm by Balcan and Blum when the price on each item must be above its margin cost; i.e., each pi > 0. We investigate the above problem when the seller is allowed to price some of the items below their margin cost. It was shown by Balcan et al. that by pricing some of the items below cost, the seller could possibly increase the maximum profit by Ω(log n) times. These items sold at low prices to stimulate other profitable sales are usually called “loss leader”. It is unclear what kind of approximation guarantees are achievable when some of the items can be priced below cost. Understanding this question is posed as an open problem by Balcan and Blum. In this paper, we give a strong negative result for the problem of pricing loss leaders. We prove that assuming the Unique Games Conjecture (UGC), there is no constant approximation algorithm for item pricing with prices below cost allowed even when each customer is interested in at most three items. Conceptually, our result indicates that although it is possible to make more money by selling some items below their margin cost, it can be computationally intractable to do so.

[1] Guruswami V, Hartline J D, Karlin A R, Kempe D, Kenyon C,McSherry F. On profit-maximizing envy-free pricing. In Proc.the 15th ACM-SIAM Symp. Discrete Algorithms, Philadelphia,PA, USA, Jan. 2005, pp.1164-1173.

[2] Briest P, Krysta P. Single-minded unlimited supply pricing onsparse instances. In Proc. the 17th ACM-SIAM Symp. DiscreteAlgorithms, New York, USA, Jan. 2006, pp.1093-1102.

[3] Balcan M F, Blum A. Approximation algorithms and onlinemechanisms for item pricing. In Proc. the 7th ACM Conferenceon Electronic Commerce, New York, USA, June 2006,pp.29-35.

[4] Demaine E K, Feige U, Hajiaghayi M, Salavatipour M R.Combination can be hard: Approximability of the unique coverageproblem. In Proc. the 17th ACM-SIAM Symp. DiscreteAlgorithms, New York, USA, Jan. 2006, pp.162-171.

[5] Khandekar R, Kimbrel T, Makarychev K, Sviridenko M.On hardness of pricing items for single-minded bidders. InAPPROX-RANDOM, Berkeley, USA, August 2009, pp.202-216.

[6] Khot S. On the power of unique 2-prover 1-round games. InProc. the 34th STOC, Montreal, Canada, May 2002, pp.767-775.

[7] Balcan M F, Blum A, Chan H, Hajiaghayi M. A theory of lossleaders:Making money by pricing below cost. In Proc. the3rd Intern. Workshop on Internet and Network Economics,San Diego, USA, Dec. 2007, pp.293-299.

[8] Khot S, Kindler G, Mossel E, O’Donnell R. Optimal inapproximabilityresults for MAX-CUT and other 2-variable CSPs?SIAM Journal on Computing, 2007, 37(1): 319-357.

[9] Raghavendra P. Approximating NP-hard problems: Efficientalgorithms and their limits [PhD Thesis]. University of Washington,2009.

[10] Mossel E. Gaussian bounds for noise correlation of functionsand tight analysis of long codes. In Proc. the 49th IEEESymp. Foundations of Comp. Sci., Philadelphia, USA, Oct.2008, pp.156-165.

[11] O’Donnell R,Wu Y, Zhou Y. Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups. In Proc. the26th IEEE Conference on Computational Complexity, SanJose, USA, June 2011, pp.23-33.

[12] Khot S, Regev O. Vertex cover might be hard to approximateto within 2??. In Proc. the 18th IEEE Conferenceon Computational Complexity, Aarhus, Denmark, July 2003,pp.379-386.
No related articles found!
Full text



[1] Wang Xuan; Lü Zhimin; Tang Yuhai; Xiang Yang;. A High Resolution Chinese Character Generator[J]. , 1986, 1(2): 1 -14 .
[2] Liu Tong; C.S.Tang;. Semantic Specification and Verification of Data Flow Diagrams[J]. , 1991, 6(1): 21 -31 .
[3] Wang Xianchang; Chen Huowang; Zhao Qinping;. On the Relationship Between TMS and Logic Programs[J]. , 1994, 9(3): 245 -251 .
[4] Gao Hong;. Transformation List for SGML Application[J]. , 1995, 10(5): 455 -462 .
[5] Lu Bo; Cai Shijie;. A Skeleton-Based Approach of Automatically Generating Some Chinese Typefaces[J]. , 1996, 11(1): 30 -38 .
[6] LI Laruan; LI Chunlin;. Studies on Algorithms for Self-Stabilizing Communication Protocols[J]. , 1999, 14(6): 606 -613 .
[7] Jie Liang and Xue-Jia Lai. Improved Collision Attack on Hash Function MD5[J]. , 2007, 22(1): 79 -87 .
[8] Xue Zhang, Jue Hong, Sang-Lu Lu, Li Xie, and Jian-Nong Cao. Scoped Bellman-Ford Geographic Routing for Large Dynamic Wireless Sensor Networks[J]. , 2008, 23(6 ): 944 -956 .
[9] Qing-Shi Gao, Xiao-Yu Gao, and Yue Hu. A New Fuzzy Set Theory Satisfying All Classical Set Formulas[J]. , 2009, 24(4): 798 -804 .
[10] Huai-Yu Wu, Chun-Hong Pan, Hong-Bin Zha, and Song-De Ma. Model Transduction for Triangle Meshes[J]. , 2010, 25(3): 583 -594 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved