Automated Channel Abstraction for Advertising Auctions

DSpace/Manakin Repository

Automated Channel Abstraction for Advertising Auctions

Citable link to this page


Title: Automated Channel Abstraction for Advertising Auctions
Author: Walsh, William E.; Boutilier, Craig; Sandholm, Tuomas; Shields, Rob; Nemhauser, George; Parkes, David C.

Note: Order does not necessarily reflect citation order of authors.

Citation: 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.
Full Text & Related Files:
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:
Terms of Use: This article is made available under the terms and conditions applicable to Open Access Policy Articles, as set forth at
Citable link to this page:
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search