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.

Authors

• Robert Krauthgamer
• Aranyak Mehta
• Atri Rudra

Keywords

• Pricing
• Revenue maximization
• Combinatorial bidding
• Unit-demand bidders
• Single-minded bidders
• Approximation algorithms
• LP rounding