Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Efficient Advert Assignment

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 and highly decomposed 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 advertisement 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 which 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. This decomposition is implemented in an adversarial setting. Exploiting the information asymmetry between the platform and advertiser, we describe a simple mechanism which incentivizes truthful bidding and 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 aggregate utility. Finally, we describe several extensions which illustrate the flexibility and tractability of our framework.(This is joint work with Frank Kelly, Uni. of Cambridge, and Peter Key, Microsoft Research)

Type of Seminar:
Optimization and Applications Seminar
Prof. Neil Walton
Korteweg-de Vries Institute for Mathematics, University of Amsterdam
Oct 20, 2014   16:30

HG G 19.1
Contact Person:

Prof. John Lygeros
File Download:

Request a copy of this publication.
Biographical Sketch:
Neil Walton is a faculty member in the Korteweg de Vries Institute for Mathematics at the University of Amsterdam. He obtained his Ba ('05), MMath ('06), and PhD ('10) in mathematics from the University of Cambridge. His research concerns stochastic networks and, in particular, optimizations that can be used to understand and control congestion. Recently, he has been interested in auction theory and computational economics due to spells spent at Microsoft Research. He received the best paper award at this year's ACM Sigmetrics conference and his work is currently funded by an NWO Veni fellowship.