Automated Channel Abstraction for Advertising Auctions

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.