Repository logo
 

Efficient advert assignment

Accepted version
Peer-reviewed

Type

Article

Change log

Authors

Key, P 
Walton, N 

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.

Description

Keywords

sponsored search, VCG mechanism, decomposition, auction, social welfare optimization

Journal Title

Operations Research

Conference Name

Journal ISSN

0030-364X
1526-5463

Volume Title

64

Publisher

Informs
Sponsorship
The research of Neil Walton was funded by the VENI research programme, which is financed by the Netherlands Organisation for Scientific Research (NWO).