Efficient Advert Assignment

Frank Kelly (), Peter Key () and Neil Walton ()
Additional contact information
Frank Kelly: Statistical Laboratory, University of Cambridge, Cambridge CB3 0WB, UK
Peter Key: Microsoft Research, Cambridge CB1 2FB, UK
Neil Walton: University of Manchester, Manchester M13 9PL, UK

Operations Research, 2016, vol. 64, issue 4, 822-837

Abstract: 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 (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2016.1519 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:64:y:2016:i:4:p:822-837

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().