Pricing Loss Leaders Can be Hard

作     者：吴奕 

作者机构：IBM Almaden Research Center 

出 版 物：《Journal of Computer Science & Technology》 (计算机科学技术学报（英文版）)

年 卷 期：2012年第27卷第4期

页      面：718-726页

核心收录：

学科分类：120202[管理学-企业管理（含：财务管理、市场营销、人力资源管理）] 12[管理学] 1202[管理学-工商管理] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：supported by the National Natural Science Foundation of China under Grant Nos. 91024028  91024031 

主　　题：complexity theory game theory approximation algorithm Unique Games Conjecture 

摘      要：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 /2（logn） 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.