Pricing commodities
How should a seller price her 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 it is 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 LP rounding based technique easily extends to a different scenario, in which the buyers want to buy all the desired goods, as long as they are within budget. (C) 2009 Elsevier B.V. All rights reserved.
pricing lp rounding revenue maximization combinatorial bidding unit-demand bidders single-minded bidders approximation algorithms