There are usually two different measures that auction designers attempt optimizing for: efficiency (social welfare) and auctioneer revenue. A “better” auction often improves both efficiency and revenue but in other cases these are conflicting goals. It is well known that efficiency is optimized by Vickerey Auctions while revenue is optimized by Myerson optimal auctions. I often hear cynical doubts about whether anyone optimizes efficiency rather than revenue, and specifically such disbelief regarding the big companies running ad auctions (such as my current employer, Google). As far as I can tell, reality seems to be quite the opposite: companies aim to optimize their long-term or middle-term revenue rather than the revenue of a single auction. In a competitive environment the only way of optimizing long term revenue is by gaining and maintaining market share which in turn requires providing high “added-value” i.e. optimizing efficiency.
In any case, this post points out to a paper by Gagan Aggarwal, Gagan Goel and Aranyak Mehta recently posted to the arXiv. Complementing a result of Jeremy Bulow and Paul Klemperer, they show that the difference between the two different optimization goals is not very large compared to increasing the number of bidders. The setting is the classic one of selling a single indivisible good in the private value model with a commonly known distribution over bidders’ valuations (with some mild restrictions on the distribution). The BK paper shows that the revenue of an efficiency-maximizing auction with k+1 bidder is at least as high as that of the revenue-maximizing one with k bidders. The new AGM paper shows that the efficiency of a revenue-maximizing auction with k+logk bidders is at least as high as that of an efficiency-maximizing one with k bidders (and that the logk term is necessary).
[Added on 10.6: Thanks to Tim Roughgarden for pointing out to me his closely related joint paper with Mukund Sundararajan that generalizes the BK result to an ad-auction setting, as well as provides direct revenue guarentees without increasing the number of bidders.]
Turing's Invisible Hand 
Hi Noam, I am learning about mechanism design and one definitional issue that puzzles me about social welfare maximizing mechanisms (i.e. VCG mechanisms) is that they don’t take into account the payments made by players to the mechanism. Wouldn’t it be more reasonable to say that the social welfare is equal to the sum of all valuations minus the payments made?
Papers you point to in your post all use distributional assumptions. Are such assumptions actually used in practice? How good are they?
Thanks,
navin
1. Social welfare also counts the auctioneer.
2. While I doubt that in practice people choose the optimal auction according to a theoretical analysis that follows the statistically determined real-world distribution, they do use general insights from the analysis for the general form of the auction and then optimize according to real-world feedback.
If you do not want to count the auctioneer, look for papers on “redistribution”.
Noam, I do not agree with the claims. Both the public evidence, e.g., Google setting reserve prices, and scientific theory, which you mentioned, that is the lack of competitive environment (I am not refering to Googles XX% share, but the fact that a given search query is monopolized by a single search engine) hints towards myerson type auction rather than vcg type. Indeed GSP is closer to myerson type auction.
Now your other claim is scientifically misleading. Search engine maximizes the users’ liking of the surplus, e.g., ads from faster websites are preferred, ads from relevance is preferred. This is altogether a separate issue that myerson/vcg debate.
Basically the search engine utility is (revenue + relevance). Now one can do VCG(revenue+relevance), or Myerson(revenue + relevance). The public evidence says that the mostly latter is being done.
You could prove me wrong by claiming that Google does not have reserve prices, because that is one of the main differences between myerson and vcg, in fact the only difference in case all the advertisers have to be treated equally beyond revenue+relevance.
Kamal, I figured that you’ll disagree….
Due to the large number of bidders (as well as the BK result above) it is very hard to consider the reserve prices as an attempt at maximizing revenue — there are much stronger reasons (e.g. psychological or anti-spam).
According to BK result above, a larger marketplace such as Google has even lesser reason for reserves.
If a spam site is bidding more than agtb blog, then a reserve mechanism which blocks the spam site blocks the agtb blog too. The standard method, which I believe Google uses too, is use the parameter which called Quality Factor in the ranking function.
Regarding the psychological impact, there are two kinds of reserve. One is a bidder can’t even enter bid less than X cents per click. That you can call it psychological, and ideally it is not reserve, but minimum bid. The bid you enter is then converted in to the ranking function, which takes into account parameters such as CTR and QF. Well, requiring a reserve on this ranking function is what I am talking about. Public evidence hints that there are reserves on this ranking function. It is not psychological, since people do not even know these reserves.
Again, this is a question for AGT folks to study, and those who are in Google, convince Google to change the auction in the interest of maximizing the social welfare. Especially in the presence of BK paper, not much revenue will be lost. If you beleive in the paper, you should be able to convince.
[…] link: Noam Nisan has an old post with some related links that inform the GSP vs. VCG discussion. Comments RSS […]
Very informative content. Thanks for this article friend.
Wow, that’s what I was searching for, what a data! existing here at this blog, thanks admin of this website.
Hi, Professor Nisan: I think a similar problem like the trade-off between the revenue and efficiency is the problem of the user-experience and revenue for search engine provider. Have anyone study the problem or could you recommend some papers on this topic ?
Admiring the hard work you put into your blog and detailed information you
offer. It’s nice to come across a blog every once in a while that isn’t the same outdated
rehashed material. Fantastic read! I’ve bookmarked your site and I’m including your RSS feeds to my Google account.