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.
Versions