12.00 hrs.
On the hardness of pricing Loss Leaders
Preyas Popat
New York University, U.S.A.
12-01-12

---

Abstract

We consider variants of the following problem: a seller has unlimited copies of n items, which he needs to price to maximise revenue. There are customers interested in (say) pairs of items. Each customer has a budget. The customer will buy both items he is interested in at their quoted prices if the combined price is below hisbudget and nothing otherwise. We allow prices for individual items to be negative (Loss Leaders).

We show that assuming the Unique games conjecture (UGC) the problem above cannot be approximated to any constant factor. During the talk we will also review a known reduction from UGC to Max 2 Lin.

Joint work with Yi Wu.