Revenue optimization in internet advertising auctions

Abstract

In economic theory, an auction refers to any mechanism or sets of trading rules for exchange. In the aspect of computer science, auction is an algorithm to process the input, (including items and agents' bids)to output(including allocation and pricing). Recently, with the progress of human civilization, auctions have also been used extensively to stock exchange, spectrum allocation, cloud services resources scheduling, as well as internet ads selling. Internet advertising, includes the search ads and the contextual (or banner) ads. Search ads places keyword based text advertising and link alongside search results. Contextual ads is a form of targeted advertising for advertisements appearing on websites. Internet ads are generating billions of dollars every year. Google earned more than 30 billion dollars from their search ads and 10 billion dollars from contextual ads within the year 2012, which make up the majority of their total revenue. Internet advertising is the primary factor in the successful commercialization of search engines [13,41] and numerous websites, online advertising is the true business of the Internet. The whole industry keeps 20% growth year to year, and it is expected to be a 100 billion dollars industry in the year 2014. With the rapid growth of the internet ads, the trade mode of the ads selling was evoluted from negotiated prices to cost-per-click auction, from frist price auctions to second price auctions. Most search engines use the weighted Generalized Second Price auction (wGSP) to sell their keyword ads nowadays, as well as the contextual and banner ads in other websites. Ads auction actually becomes an industy standard, thus, designing and optimizing these auctions are naturally important problems for both efficiency and profit. Those problems were widely discussed in academy and industry in recent years. In the first part of this thesis, we show how to calculate and implement the revenue optimal reserve price of the wGSP mechanism in realistic settings. Unlike reserve prices in standard single-item auctions, we find that optimal reserve prices in wGSP auctions are discriminatory, even when advertisers bid on the same keyword. The optimal reserve price results can be extended to support CPA/CPC/CPM1 hybrid auctions. Our simulations indicate that setting a proper reserve price will transfer some bidder utility (payoff) to auctioneer utility, resulting in higher revenue for the search engine. We also describe a practical methodology to implement optimal reserve prices in production systems. In the second part of the thesis, we focus on a subproblem in reserve pricing - estimation of the bids distribution from the truncated samples, and further calculate the optimal reserve price in an iterative setting. We propose to use maximum likelihood estimate (MLE) to solve the problem, and we prove that it is an unbiased method for distribution estimation. Moreover, we further simulate the iterative optimal reserve price calculating and updating process based on the estimated distribution. The experimental results are interpreted in terms of the robustness of MLE to truncated sample size and initial reserve price (truncated value), and the convergence of subsequent optimal reserve price in the iterative updating process is also discussed. We conclude that MLE is reliable enough to be applied in real world optimal reserve pricing in keyword auctions, and these simple method give near-optimal revenue guarantee in a very robust manner. In the third part of the thesis, we refer to the optimal pricing problem for a model of the rich media advertisement market, as well as other related applications. In this market, there are multiple buyers (advertisers), and items (slots) that are arranged in a line such as a banner on a website. Each buyer desires a particular number of consecutive slots and has a per-unit-quality value vi (dependent on the ad only) while each slot j has a quality qj (dependent on the position only such as click-through rate in position auctions). Hence, the valuation of the buyer i for item j is vi cot qj. We want to decide the allocations and the prices in order to maximize the total revenue of the market maker. A key difference with the traditional position auction is the advertiser's requirement of a fixed number of consecutive slots. Consecutive slots may be needed for a large size rich media ads. We study three major pricing mechanisms, the Bayesian pricing model, the maximum revenue market equilibrium model and an envy-free solution model. Under the Bayesian model, we design a polynomial time computable truthful mechanism which is optimum in revenue. For the market equilibrium paradigm, we find a polynomial time algorithm to obtain the maximum revenue market equilibrium solution. In envy-free settings, an optimal solution is presented when the buyers have the same demand for the number of consecutive slots. We conduct a simulation that compares the revenues from the above schemes and gives convincing results.

Date of Award	15 Jul 2014
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Qing LI (Supervisor) & Xiaotie DENG (Supervisor)