“Simple versus Optimal Mechanisms,” J. Hartline & T. Roughgarden (2009)

It is well known that when a single-item is auctioned to users with private values drawn from independent distributions with suitably small tails, the Vickrey-Clarke-Groves mechanism with an appropriate reserve price for each bidder is revenue-optimal. Also, Bulow and Klemperer showed that, even better than using a reserve price, the recruitment of one additional bidder will raise revenue even more. This result is fantastic because it shows that a fairly simple mechanism is revenue-optimal. How well does this “simple mechanism is best” result generalize? For instance, what if the mechanism designer only knows that bidders for a single item have private values drawn from some suitably regular distributions, but does not know exactly what those distributions are? Or what if bidders are in a multi-good environment with independently (not necessarily i.d.) distributed private values, and the auctioneer simply makes a take-it-or-leave-it offer to each agent equal to the expected monopoly-optimal price? It turns out that in both those cases, the “simple mechanism” is roughly optimal (in the computer science sense, that is – “roughly” may mean off by 75% in the worst case, but it is linearly bounded). The value of this paper is in its method for showing when mechanisms are approximately optimal.

http://www-cs.stanford.edu/~tim/papers/bk.pdf

Advertisement