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_ e (e-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 5.7. In other words, Theta(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 2.2 log k + t Theta(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.
We study the simultaneous optimization of efficiency and revenue in pay-per-click keyword auctions in a Bayesian setting. Our main result is that the efficient keyword auction yields near-optimal revenue even under modest competition. In the process, we build on classical results in auction theory to prove that increasing the number of bidders by the number of slots outweighs the benefit of employing the optimal reserve price. Abstract We study the performance of the English auction under different assumptions about the seller's degree of “Bayesian sophistication.” We define the effectiveness of an auction as the ratio between the expected revenue it generates for the seller and the expected valuation of the object to the bidder with the highest valuation (total surplus). We identify tight lower bounds on the effectiveness of the English auction for general private-values environments, and for private-values environments where bidders' valuations are non-negatively correlated. For example, when the seller faces 12 bidders who the seller believes have non-negatively correlated valuations whose expectations are at least as high as 60 of the maximal possible valuation, an English auction with no reserve price generates an expected price that is more than 80 of the value of the object to the bidder with the highest valuation.