Computer Science Department
School of Computer Science, Carnegie Mellon University
Single Price Mechanisms for Revenue Maximization in
Maria-Florina Balcan, Avrim Blum, Yishay Mansour*
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 ). 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.
*School of Computer Science, Tel-Aviv University