New Models and Mechanisms for the Planning and Allocation of Online Advertising

Motivated by recent trends in online advertising, most of this dissertation is devoted to the introduction, modeling, and the design of efficient allocation techniques for a new form of online advertising contract, which we refer to as Reach and Frequency (R&F) contract. In the first chapter, we consider a type of R&F contract which allows online advertisers to specify the number of unique individuals that should see their ad (reach), and the minimum number of times each individual should be exposed (frequency) for him/her to be counted as reached. We develop an optimization framework that provides minimal under-delivery and proper spread of each campaign over its targeted demographics. As well, we introduce a pattern-based delivery mechanism which allows us to integrate a variety of new features into a website's ad allocation optimization problem, e.g., allowing publishers to implement any desired pacing of ads over time at the user level or control the number of competing brands seen by each individual. Numerical tests, conducted on real industry data obtained from Yahoo, show that our solution algorithm produces high-quality solutions and has promising run-time and scalability. Several extensions of the model are presented, e.g., to account for multiple ad positions on the webpage, or randomness in the website visitors' arrival process. In the second chapter, we consider different variants of R&F contracts in which the advertiser specifies frequency using a probability distribution that details what fraction of users should see the ad how many times. We propose two Markov chain models for serving ads, namely when frequencies are counted over a fixed timespan or on a rolling basis. We then investigate how each Markov chain performs in maintaining the desired frequency distribution of an online ad campaign. In each case, we characterize the feasibility criteria, and show that the publisher's impression assignment rule can be obtained very efficiently in linear time in the length of the frequency distribution specified by the advertiser.In the final chapter, we present a new online competitive algorithm for delivering online guaranteed targeted display advertising which, under certain conditions, outperforms the best known algorithm of its type