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 [email protected]