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 p_1, p_2, . . . , p_n so as to maximize the overall profit. There is an O (k)-approximation algorithm by [BB06] 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 in [BB06, BBCH08] 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 in [BB06].

In this work, we give a strong negative result for the problem of pricing loss leaders. We prove that it is NP-hard to get a constant approximation for the problem for even for k=3, i.e.when each buyer is interested in at most 3 items. When k=2, we show a similar hardness result assuming the Unique Games Conjecture.

This talk is based on joint work with Prepas Popat.