Efficiency of (revenue-)optimal mechanisms

ABSTRACT

We compare the expected efficiency of revenue maximizing (or optimal) mechanisms with that of efficiency maximizing ones. We show that the efficiency of the revenue maximizing mechanism for selling a single item with (k + log_eovere-1 k + 1) bidders is at least as much as the efficiency of the efficiency-maximizing mechanism with k bidders, when bidder valuations are drawn i.i.d. from a Monotone Hazard Rate distribution. Surprisingly, we also show that this bound is tight within a small additive constant of 4.7. In other words, Θ(log k) extra bidders suffice for the revenue-maximizing mechanism to match the efficiency of the efficiency-maximizing mechanism, while o(log k) do not. This is in contrast to the result of Bulow and Klemperer comparing the revenue of the two mechanisms, where only one extra bidder suffices. More precisely, they show that the revenue of the efficiency-maximizing mechanism with k + 1 bidders is no less than the revenue of the revenue-maximizing mechanism with k bidders.

We extend our result for the case of selling t identical items and show that Θ(log k) + t Θ(log log k) extra bidders suffice for the revenue-maximizing mechanism to match the efficiency of the efficiency-maximizing mechanism.

In order to prove our results, we do a classification of Monotone Hazard Rate (MHR) distributions and identify a family of MHR distributions, such that for each class in our classification, there is a member of this family that is pointwise lower than every distribution in that class. This lets us prove interesting structural theorems about distributions with Monotone Hazard Rate.

REFERENCES

• 1: J. Bulow and P. Klemperer. Auctions Versus Negotiations. AMERICAN ECONOMIC REVIEW. 86:180--194, 1996.
• 2: E. Clarke. Multipart pricing of public goods. Public Choice. 11(1):17--33, 1971.
• 3: T. Groves. Incentives in teams. Econometrica. 41(4):617--631, 1973.
• 4: Anton Likhodedov , Tuomas Sandholm, Auction mechanism for optimally trading off revenue and efficiency, Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779964]
• 5: R. Myerson. Optimal Auction Design. MATH. OPER. RES. 6(1):58--73, 1981.
• 6: Z. Neeman. The effectiveness of English auctions. Games and Economic Behavior. 43(2):214--238, 2003.
• 7: T. Roughgarden and M. Sundararaj. Is efficiency expensive. In Third Workshop on Sponsored Search Auctions, 2007.
• 8: W. Vickrey. Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance. 16(1):8--37, 1961.
• 9: R. Zhan. Optimality and Efficiency in Auctions Design: A Survey.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.m MISCELLANEOUS

General Terms:
Design, Economics, Theory

Keywords:
auction design, efficiency, optimal auctions, vcg