(joint work with Bill Walsh, Tuomas Sandholm, Rob Shields, George Nemhauser and David Parkes)
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 optimization in ad allocation, especially in expressive auction settings. Unfortunately, natural formulations of ad optimization fall prey to channel explosion: ad inventory is partitioned into the channels of "indistinguishable" supply, but the number of channels grows exponentially in either attributes or bidders. In this talk, we propose a means for automatically abstracting channels, grouping together channels so that only the most important channel distinctions---as measured by impact on solution quality---are maintained. We first describe novel form of LP/MIP column generation to create abstract channels. Optimization can be performed directly on the abstract channels produced; but they can also be used more "intelligently." We then discuss a constraint generation procedure that incrementally constructs an optimal "packing" of ads within these abstract channels. These techniques dramatically reduce the number of channels over which ads are allocated by sacrificing revenue/efficiency in a principled fashion, thus rendering optimization computationally feasible at practical scales. Numerical experiments demonstrate the computational practicality of our approach as well as the quality of the abstractions generated.
Craig Boutilier received his Ph.D. in Computer Science (1992) from the University of Toronto, Canada. He is Professor and Chair of the Department of Computer Science at the University of Toronto. He was previously an Associate Professor at the University of British Columbia, and is on sabbatical for 2008-09 (part time at CombineNet, Inc. and Carnegie Mellon University).
Dr. Boutilier's research interests span a wide range of topics, with a focus on decision making under uncertainty, including preference elicitation, mechanism design, game theory, Markov decision processes, and reinforcement learning. He is a Fellow of the American Association of Artificial Intelligence (AAAI) and the recipient of the Isaac Walton Killam Research Fellowship, an IBM Faculty Award and the Killam Teaching Award. He has also served in a variety of conference organization and editorial positions, and is Program Chair of the upcoming Twenty-first International Joint Conference on Artificial Intelligence (IJCAI-09).