We develop a framework for the analysis of large-scale ad auctions where
adverts are assigned over a continuum of search types. For this
pay-per-click market, we provide an efficient mechanism that maximizes
social welfare. In particular, we show that the social welfare optimization
can be solved in separate optimizations conducted on the time scales
relevant to the search platform and advertisers. Here, on each search
occurrence, the platform solves an assignment problem and, on a slower time
scale, each advertiser submits a bid that matches its demand for
click-throughs with supply. Importantly, knowledge of global parameters,
such as the distribution of search terms, is not required when separating
the problem in this way. Exploiting the information asymmetry between the
platform and advertiser, we describe a simple mechanism that incentivizes
truthful bidding, has a unique Nash equilibrium that is socially optimal,
and thus implements our decomposition. Further, we consider models where
advertisers adapt their bids smoothly over time and prove convergence to
the solution that maximizes social welfare. Finally, we describe several
extensions that illustrate the flexibility and tractability of our
framework.
Keywords: sponsored search; VCG mechanism; decomposition; auction; social welfare optimization