IEOR PhD student and Paul Grigas’s advisee Alfonso Lobos has won the best student paper award at the 2018 Knowledge Discovery and Data Mining (KDD) conference in London for his paper “Optimal Bidding, Allocation and Budget Spending for a Demand Side Platform Under Many Auction Types.” Lobos’s paper won at the 2018 AdKDD & TargetAd workshop that focused on the evolution of computational advertising, large-scale and novel ad targeting, and how the deployment of real systems to target users work in online advertising.
Abstract: We develop a novel optimization model to maximize the profit of a Demand-Side Platform (DSP) while ensuring that the budget utilization preferences of the DSP’s advertiser clients are adequately met. Our model is highly flexible and can be applied in a Real-Time Bidding environment (RTB) with arbitrary auction types, e.g., both first and second price auctions. Our proposed formulation leads to a non-convex optimization problem due to the joint optimization over both impression allocation and bid price decisions. Using Fenchel duality theory, we construct a dual problem that is convex and can be solved efficiently to obtain feasible bidding prices and allocation variables that can be deployed in a RTB setting. With a few minimal additional assumptions on the properties of the auctions, we demonstrate theoretically that our computationally efficient procedure based on convex optimization principles is guaranteed to deliver a globally optimal solution. We conduct experiments using data from a real DSP to validate our theoretical findings and to demonstrate that our method successfully trades off between DSP profitability and budget utilization in a simulated online environment.
In Feyman Terms (or more user-friendly introduction):
The goal of Online Advertising is to target the right user, at the right time, with the right content/offer. In online advertisement these opportunities occur whenever a user downloads an app, opens a webpage, plays a video, etc. which account for approximately 200 billion events per day. These events are sold in Ad-exchanges in which companies called Demand -Side Platforms (DSPs) participate. For each event a real time auction is held and in less than 100ms the event has been sold to some DSP and an ad have started to be shown to the user. A DSP usually manage marketing campaigns of hundreds or thousands of different advertisers. Our work optimizes how a DSP should bid in these real time auctions and, whenever an auction is won, how to select an ad to be shown from one of the DSP advertiser clients. We extend previous works in this area by taking into account that different Ad-exchanges may use different auction types, which is an important extension as today first and second price auctions are being used by Ad-exchanges in similar amounts. The methodology developed in the paper also offer flexibility on how the budget of the a DSP advertiser’s clients should be spent, and we prove that our methodology is optimal under several settings.
The full paper can be downloaded here. This is joint work with Paul Grigas, Zheng Wen (Adobe Research), Kuang-chih Lee (Alibaba).