Abstract

Abstract:
We consider the problem of designing auctions with worst case revenueguarantees for sponsored search. This problem differs from previouswork because of ad dependent clickthrough rates which lead to {emtwo} natural posted-price benchmarks. In one benchmark, the winningadvertisers are charged the same price per click, and in the other,the product of the price per click and the advertiser clickability(which can be thought of as the probability an advertisement isclicked if it has been seen) is the same for all winningadvertisers. We adapt the random sampling auction fromcite{JasonSoda} to the sponsored search setting and improve theanalysis from~cite{me}, to show a high competitive ratio for twotruthful auctions, each with respect to one of the two describedbenchmarks.However, the two posted price benchmarks (and therefore the revenueguarantees from the corresponding random sampling auctions) can eachbe larger than the other; further, which is the larger cannot bedetermined without knowing the private values of the advertisers. Wedesign a new auction, that incorporates these two random samplingauctions, with the following property: the auction has a Nashequilibrium; and emph{every} equilibrium has revenue at least thelarger of the revenues raised by running each of the two auctionsindividually (assuming bidders bid truthfully when doing so is autility maximizing strategy). Finally, we perform simulations whichindicate that the revenue from our auction outperforms that from theVCG auction in less competitive markets.


Download:

Paper 1.pdf
ACM COPYRIGHT NOTICE. Copyright © 2012 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept., ACM, Inc., fax +1 (212) 869-0481, or permissions@acm.org.