Automated Channel Abstraction for Advertising Auctions

View/ Open
Author
Walsh, William E.
Boutilier, Craig
Sandholm, Tuomas
Shields, Rob
Nemhauser, George
Metadata
Show full item recordCitation
Walsh, William E., Craig Boutilier, Tuomas Sandholm, Rob Shields, George Nemhauser, and David C. Parkes. 2009. Automated channel abstraction for advertising auctions. In the Fifth Workshop on Ad Auctions, 2009. Proceedings of the Tenth ACM Conference on Electronic Commerce : July 6-10, 2009, Stanford, California.Abstract
The use of auction mechanisms like the GSP in online advertising can lead to loss of both efficiency and revenue when advertisers have rich preferences: even simple forms of expressiveness like budget constraints can lead to suboptimal outcomes. This has led to the recognition of the value of (sequential and/or stochastic) optimization in ad allocation. Unfortunately, natural formulations of such optimization problems fall prey to channel explosion. Specifically, available ad inventory must be partitioned into subsets, or channels, of indistinguishable supply, each channel containing inventory that is interchangeable from the perspective of each active advertiser. The number of such channels grows exponentially in the number of features of interest. We propose a means for automatically abstracting these channels, grouping together channels so that irrelevant distinctions are ignored. Our approach, based on LP/MIP column and constraint generation, dramatically reduces the number of distinct channels over which ads are allocated, thus rendering optimization computationally feasible at practical scales. Our algorithms also allow revenue/efficiency to be sacrificed in a principled fashion by ignoring potentially relevant distinctions, but retaining the most important distinctions, ignoring only those that have low impact on solution quality. This allows tradeoffs to be made between tractability and solution quality. Numerical experiments demonstrate the computational practicality of our approach as well as the quality of the abstractions generated.Other Sources
http://www.eecs.harvard.edu/econcs/pubs/walsh09.pdfTerms of Use
This article is made available under the terms and conditions applicable to Open Access Policy Articles, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#OAPCitable link to this page
http://nrs.harvard.edu/urn-3:HUL.InstRepos:3996849
Collections
- FAS Scholarly Articles [18172]
Contact administrator regarding this item (to report mistakes or request changes)