Robert Krauthgamer, Aranyak Mehta and Atri Rudra

Pricing commodities, or How to sell when buyers have restricted valuations

Abstract : How should a seller price his goods in a market where each buyer prefers a single good among his desired goods, and will buy the cheapest such good, as long as its within his budget? We provide efficient algorithms that compute near-optimal prices for this problem, focusing on a commodity market, where the range of buyer budgets is small. We also show that our technique (which is based on LP-rounding) easily extends to other scenarios, in which the buyers want to buy all the desired goods, as long as they are within budget.