Ad delivery planning of online display advertising

Abstract

This dissertation presents modeling and solution methods for two research problems: (1) integrated ad delivery planning for online display advertising; and (2) data-driven ad delivery planning for non-guaranteed targeted display advertising. An online publisher of display advertising sells its advertising resources through two markets — the upfront market and the spot market. In the upfront market, a publisher and each of its advertisers enter into a contract (called “guaranteed contract”), which specifies an agreed upon amount of advertising resources to be delivered over a certain period at a fixed price. On the other hand, in a spot market, the publisher auctions off excessive resources among advertisers (known as “non-guaranteed delivery”). When planning ad delivery, the publisher needs to ensure that the guaranteed contracts are fulfilled, otherwise a penalty is incurred. Furthermore, to establish and maintain a long-term relationship with advertisers, a publisher must strive to improve advertising effectiveness. However, the publisher works to maximize revenue from the spot market because revenue from the upfront market is essentially fixed. Consequently, the publisher faces a trade-off between earning a greater short-term profit from the spot market and strengthening its long-term reputation among advertisers by improving the effectiveness of the guaranteed ads in the upfront market. To address this challenge, we propose an integrated planning model. Specifically, we first derive a closed-form expression for audience reach, a critical measure of advertising effectiveness. The ad delivery planning problem is then formulated into a chance-constrained stochastic programming model. By a series of safe approximations, we transform the stochastic model into a convex programming model that is more tractable to solve. For large-scale applications that require approximate real-time solutions, we design an efficient clustering algorithm, together with an effective upper bound. Based on real data, as well as random generated data in the literature, we conduct extensive numerical experiments. Experiment results demonstrate that our method achieves ad delivery plans that can deliver the guaranteed ads in a robust manner, as well as effectively balance the short-term profit and advertising effectiveness of guaranteed ads. Non-guaranteed targeted display advertising has attained remarkable, sustainable progress in recent years, especially with the emergence and popularity of social network sites such as Facebook and Twitter, which attract many advertisers seeking viewer response (e.g., clicks on ads) with limited budgets. Advertising resources are sold by auction in real-time (e.g., the generalized second-price auction), and advertisers pay publishers according to the cost-per-click pricing model. Each time that a viewer loads a web page with an ad slot, an auction is immediately run among the ads targeting that particular viewer, with the winning ad selected for display. However, the auction based selling mechanism may lead to loss of efficiency due to sub-optimal revenue realized, especially when advertisers have budget constraints. Strategically, the auction may induce advertisers to bid below their true willingness-to-pay to exploit the periods of incomplete competition. To address this deficiency in non-guaranteed targeted display advertising, we propose a data-driven ad delivery planning approach with the objective of maximizing the total revenue for the publisher. Specifically, based on predicted ad clicks and advertisers’ bid prices and budgets, we present a novel plan for allocating advertising resources. Under the cost-per-click pricing model, the number of clicks received by each ad needs to be estimated to evaluate advertising revenue. Thus, we introduce an arbitrary-points-inflated Poisson regression model to forecast ad clicks. Based on ad clicks forecasting, we formulate the ad delivery planning problem into a nonlinear mixed integer programming model. To solve this optimization model, we propose an efficient algorithm that is capable of finding near-optimal solutions with known optimality gap bounds quickly. To verify the effectiveness of our approach, we have conducted extensive numerical experiments based on a twenty-day sampled log data provided by our collaborator, an online advertising publisher in China. Experiment results substantiate that our ad clicks forecasting model achieves acceptable accuracy. In addition, the estimated revenue obtained by our ad delivery plan often significantly exceeds actual revenue. To the best of our knowledge, this study is the first to present a data-driven approach that combines forecasting and optimization in ad delivery planning for non-guaranteed targeted display advertising.

Date of Award	2 Oct 2015
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Yanzhi David LI (Supervisor) & Kwok Fai Geoffrey TSO (Supervisor)