ICS 2011

Welcome to ICS2011

Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, 101-111, 978-7-302-24517-9
Tsinghua University Press

Pricing Loss Leaders can be Hard Authors : Yi Wu [Download PDF]

Abstract:
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 [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 paper, we give a strong negative result for the problem of pricing loss leaders. We prove that assuming the Unique Games Conjecture (UGC) [Kho02], there is no constant approximation algorithm for item pricing with prices below cost allowed even when each customer is interested in at most 3 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.

Preview: