Computer Science Department
School of Computer Science, Carnegie Mellon University


Single Price Mechanisms for Revenue Maximization in
Unlimited Supply Combinatorial Auctions

Maria-Florina Balcan, Avrim Blum, Yishay Mansour*

February 2007


Keywords: Mechanism design, profit maximization, unlimited supply, combinatorial auctions

In this paper we generalize a result of Guruswami et. al., showing that in unlimited-supply combinatorial auctions, a surprisingly simple mechanism that offers the same price for each item achieves revenue within a logarithmic factor of the total social welfare for bidders with general valuation functions (not just single-minded or unit-demand bidders as in [7]). We also extend this to the limited-supply setting for the special case of bidders with additive valuations. These are both settings for which Likhodedov and Sandholm provide logarithmic approximations but via much more complex bundle-pricing mechanisms.

10 pages

*School of Computer Science, Tel-Aviv University

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by