ICS 2011

Welcome to ICS2011
Innovations in Computer Science  ICS 2011, Tsinghua University, Beijing, China, January 79, 2011. Proceedings, 101111, 9787302245179
Tsinghua University Press 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:

Copyright 20102011, Institute for Computer Science, Tsinghua University, All Rights Reserved.