CASOPIS REPUBLICKE AGENCIJE ZA TELEKOMUNIKACIJE

Ana Radovanovic,Google, Inc.

anaradovanovic@google.com

ABSTRACT

The goal of this paper is to present basics of the Internet advertising today.

Keywords: sponsored search, display advertising, ad exchange, auction

1. INTRODUCTION

There are two basic types of advertising on the Internet: sponsored search and display advertising. In the case of sponsored search advertising, search engines display advertisements along side the search results in response to user queries. Ads that get displayed are a result of an auction among advertisers who want their ads to be shown for specific keywords appearing within a search query. On the other hand, display advertising is graphical advertising on the World Wide Web (WWW) that appears next to content on Web pages, Instant Messaging (IM) applications, email, etc. Recently, companies like Microsoft, Yahoo and Google have been trying to get a significant share in the display market that has lots of room to grow even though display ads have been around for more than a decade, first as pop-up and banner ads, and now as ads of different sizes that mix images, text, audio, video and animation. In this paper we present key research challenges that have been part of mechanisms integrated in the process of selling and serving of both types of advertising. In the end, we include a discussion on an emerging way to sell and buy display ads on the Internet via ad exchanges.

2. SPONSORED SEARCH ADVERTISING

In this section, we describe the current systems for sponsored search advertising and introduce some of the research challenges. The overall game involves three parties - advertisers, search engine and search users. The mechanism behind bidding and pricing in these games uses techniques from three mathematical areas: mechanism design, optimization and statistical estimation.

Figure 1. Sponsored search advertising on Google search page.

Sponsored search provides targeted advertising on search queries and has been a major advertising medium in the past year, attracting large numbers of advertisers and users. The result of a user posing a query on a search page incorporates both search results together with advertisements that are placed into positions, usually arranged linearly down the page, top to bottom. Most commonly, the assignment of ads to positions is determined by an auction among all advertisers who placed a bid on a keyword that matches the query. The user might click on one or more of the ads, in which case (in the pay-per-click model) the advertiser receiving the click pays the search engine a price determined by the auction. Each player in the game has incentives to participate.

Advertisers' goal is to place their advertisements. Some advertisers want to develop their brand, some seek to make sales, and yet others advertise for defensive purposes on specific keywords central to their business. Some have budget constraints, while others are willing to spend as much as it takes to achieve their goal. Some seek to obtain many clicks and eyeballs, yet others attempt to optimize their return on investment. So, in general, advertisers are of varied types.

The auctioneer in the game is a search engine. Search engines have to balance many needs, including maintaining useful search results, as well as enhancing advertisements, which should improve search experience. They need to make sure the advertisers get their needs fulfilled, and, at the same time, ensure that the market the advertisers participate in is efficient and conducive to business.

Finally, search users use search engines for information and pointers. They also use it to discover shopping opportunities, good deals, and new products. There are millions of users with different goals and behavior patterns with respect to advertisements.

The three parties mentioned above induce a fairly sophisticated dynamics. Even though economic and game theory provide a well-developed framework for understanding the auction design, the community has had to generalize such methods and apply them carefully to understand the currently popular Internet auctions. While there has been recent work on understanding models of user behavior in the search context, including setting search queries and clicking on search responses, little is known about user behavior on advertisements, and crucially, these affect the value of the slots and, therefore, goods that are sold in an auction.

The basic auction behind sponsored search auction occurs when a user submits a query to the search engine. The resulting page includes Web search results, and independently, a set of text ads, arranged linearly top to bottom. Each advertiser i has previously submitted a bid b_i stating their value for a click, tying their bid to a specific keyword, i.e.

The auction is held in real-time among advertisers whose keywords match that user’s query. The result of the auction is the list of advertisements on the right. So, after selecting the set of eligible (matching) ads, running the auction involves the search engine determining (a) the ordering of bidders and (b) pricing.

The most natural ordering is to sort ads by decreasing bid, but that approach would not take into account the quality of ads and their suitability to users. Therefore, most commonly, bidders (advertisers) are sorted in the descending order of (), where

is what is called the Click-Through-Rate (CTR) of advertiser i, i.e., the probability that a user will click on the ad, given that the user looks at it. (The CTR is usually measured by the search engine.) This is the ordering currently in use by search engines like Yahoo! and Google.

Making bidders pay what they bid would lead to well-known race conditions (see [1]). Instead, the most common method is to use a “generalized second price” (GSP) auction. Say the positions are numbered 1, 2, … starting at the top and going down, and the bidder at position i has bid b_i. In GSP, the price for a click for the advertiser in position i is determined by the advertisement below it and is given by , which is the minimum they would have needed to bid to attain their position.

Figure 2. Key parameters of the sponsored search ad campaign.

For an academic treatment of the sponsored search auctions, an interested reader is referred to ([1], [2], [3]). Common questions in this context include asking whether there is a pure-strategy Nash equilibrium of this game, as well as the analysis of the economic efficiency and revenue of such equilibria. Economic efficiency is defined as the total advertiser value generated by the assignment, and is also referred to as the social welfare. Therefore, in the context of sponsored search, the social welfare is equal to the sum of the individual advertisers’ values. By a pure-strategy Nash equilibrium we mean that no single bidder can change their bid and increase their utility.

One of the most desirable properties of a mechanism is to be truthful, which is also referred to as being incentive compatible. This property says that each bidder’s best strategy, regardless of the actions of other bidders, is to simply report the true value. Truthfulness immediately implies the existence of a pure-strategy Nash equilibrium (where every bidder reports value per click). As a result, it is simple to compute economic efficiency, since the assignment (and, thus, the efficiency) is simply a function of the values. GSP auction is not truthful. However, there is a pricing scheme that is truthful, which is based on an application of the famous Vickrey-Clarke-Groves (VCG) mechanism ([4], [5], [6]). Even though the GSP auction is NOT truthful, it has a well-understood pure-strategy Nash equilibrium.

3. PRACTICAL ASPECTS

There are elements that make sponsored search a very complex environment and that make modeling assumptions very often intractable.

·Each sponsored auction is conducted for a particular search engine user with a potentially unique query. There are perhaps millions of such queries every day. However, advertisers must submit bids on keywords and cannot adjust those bids on a per-query basis. The degree to which the keyword matches a particular query determines not only whether the advertiser will participate in the auction, but also can factor into the click-through rate that is used for ranking.

·Many advertisers have operating budgets or spending targets, and simply want to maximize their value given the constraints of that budget. This budget can be reported to the search engine, which can then employ techniques to use the budget efficiently.

·Reserve prices represent the minimum price that an advertiser can pay for a click. Sometimes these reserve prices can be specific to a particular bidder. Reserve prices are useful for controlling quality on the search results page and also have implications for revenue.

·The “separable” assumption implies that an advertiser’s click probability depends only on the properties and position of her own ad. This ignores the other ads on the search results page, which certainly affect the user experience, and therefore the click probability of this advertiser.

·A branding advertiser could be interested in her ad appearing in a high position, but not really care whether or not it gets a click (other than due to the fact that they only pay if it does). (Indeed, a recent empirical study by the Interactive Advertising Bureau and Nielsen//NetRatings concluded that higher ad positions in paid search have a significant brand awareness effect [7].)

·The private click-value model assumes that a click is worth the same to an advertiser, which is not always the case in practice. Many advertisers track whether or not a click leads to a conversion. Conversions in sponsored search is some sort of event on the linked page (e.g., a sale, a sign-up, etc.). Given this data, the advertiser can learn which keywords lead to conversions and therefore which clicks are worth more to them.

·Most work in the context of the game theory of sponsored search has assumed that the parameters CTR and position visibility are known. However, estimating these parameters is a difficult task (e.g., [8], [9]). Indeed, there is an inherent tradeoff between learning these parameters and applying them; one cannot learn that an ad has a bad CTR unless it is exposed to the user, but then it was a bad idea to show it in the first place. This “exploration/exploitation” tradeoff turns out to be related to the “multi-armed bandit” problem (see e.g. [10]).

·Both the advertisers and the search engine have incomplete knowledge of the “inventory” available to them, since they do not know which queries will arrive. Furthermore, the bidders do not know the other bids or click-through rates. This makes the advertiser’s optimization problem much more difficult (see e.g., [12], [11], [14]). From the search engine’s point of view, we can model incomplete knowledge of the future as an online algorithm (see e.g. [13], [14], [15], [16], [10], [26]).

4. THE ADVERTISER’S POINT OF VIEW: BUDGET OPTIMIZATION

Defining an advertising campaign incorporates the following: (i) determining a set of keywords related to the campaign, (ii) creating ads, (iii) setting bid for each keyword, and (iv) setting total (or daily) budget.

It is very hard to quantify the effect of an ad campaign in any medium. On the Internet, it is commonly accepted that the goal in the search-based advertising is to maximize the number of clicks. The Internet search companies are supportive towards advertisers and provide statistics about the history of click volumes and prediction about the future performance of various keywords.

Individual keywords have significantly different characteristics from each other. Selecting the {\it right} set of keywords that will target a particular population of users, with as little as possible competition from other advertisers, is a complex task.

Furthermore, there are complex interactions between keywords because a user query may match two or more keywords, since the advertiser is trying to cover all the possible keywords in some domain. In effect the advertiser ends up competing with herself.

As a result, the advertisers face a challenging optimization problem (see [11]).

Display advertising is a fast-growing, multi-billion business, which provides a premium way of advertising online (see [20], [22]). This is much more than ads in Web browsers. People are watching videos, reading newspapers, magazines, books and listening to digital music online at an ever-increasing rate. They are turning to new devices like smartphones, tablets, e-readers and video game consoles. Display advertising has a significant advantage over advertising in magazines, newspapers and TVs: (i) it provides targeting options such as demographic and behavioral targeting to laser on a specific audience, (ii) one can track the performance of the advertising campaign daily to measure metrics such as impressions, clicks and conversions. For the reasons of growth, Google has been acquiring companies to build its display business, e.g. YouTube is the host of many Google display ads, DoubleClick provides tools for advertisers and publishers to show ads, Teracent lets advertisers tailor ads on the fly, while Invite Media or DoubleClick (Google) Ad Exchange is an exchange where advertisers can bid on display ad space.

Figure 3. An example of a display ad.

Online publishers’ (e.g. YouTube, Amazon, CNN, NY Times, etc.) goal is to grow a display advertising ’pie’. As stated in the official Google blogspot (see [20]): For millions of online publishers - from the smallest blogger to the largest entertainment, news, e-commerce and the information sites - online advertising revenue is vital. When publishers can maximize their returns, everyone benefits from more vibrant online content and websites.

In order to make display advertising work better, large companies like Microsoft, Yahoo! and Google have been investing in new technologies that should help grow display advertising for all publishers by orders of magnitude (see [20], [19]). One of such examples is a DoubleClick (Google) platform, called DoubleClick for Publishers, which is an ad serving platform that maximizes the value of ad space that publishers directly sold themselves. The overall goal is to give publishers a firm control and empower them with more data, reports and controls and, therefore, help them make better decisions about ad space forecasting, segmentation, target- ing, allocation and pricing. Pricing of display ads is one of the most challenging tasks and can significantly impact publisher’s revenue (see [21], [17], [18]).

Specific dynamics in the process of sales of display ads makes the pricing problem different from the related offline and online pricing schemes. Advertisers pre-purchase a reservation package of online inventory (impressions) on content sites (publishers). In this business context, an advertiser with certain advertising goals approaches a sales representative either directly or through an ad agency, after which they start a negotiation. The result of this process is a sold package of impressions, which represents the number of times a certain ad is displayed on a Web page when users access it within the desired window of time in the future. Impression (inventory) categories differ in their properties, such as size, type (text, video, etc.), position, as well as monitored performance measures (Click Through Rate (CTR), conversion rate, etc.), which usually impact their price. Data collected from the 2009 DoubleClick (Google) User Group sessions revealed that publishers adhere to a wide spectrum of pricing practices, ranging from scientific methodologies to educated guesses. As a result, it is likely that many publishers aren’t generating as much revenue as possible from their inventory. However, by applying scientific methodologies to publishers’ pricing practice, they may be able to improve their monetization.

Figure 4. Negotiation dynamics in display advertising.

The key questions a publisher tries to address are:

• How much to price its inventory?
• How to price a new type of inventory (i.e., new type of impressions)?
• How much should sales people be allowed to discount in the process of negotiation?
• Will raising the price of inventory increase the revenue?
• When do the sales of low priced product start affecting revenue of future reservations for higher-priced products?
• What is a dynamic inventory allocation policy in the presence of diverse advertisers and inventory quality?

On the other hand, advertiser’s dilemmas are:

• Which publisher provides with the best targeting of audience that buys/clicks?
• What kind of products to purchase and how much money to spend on it?
• How should one strategize between different publishers to reach the profit goals?

Some of the questions above were addressed in [22], [23] and [24].

6. AD EXCHANGES

An emerging way of selling and buying ads on the Internet is via an exchange that brings sellers (publishers) and buyers (advertisers) together to a common marketplace. There are exchanges in the world for trading financial securities, currency, physical goods, virtual credits, and much more. Exchanges serve many purposes from bringing efficiency, to eliciting prices, generating capital, aggregating information etc. Market microstructure is the area that studies all aspects of such exchanges.

Ad exchanges are recent. RightMedia, AdECN and DoubleClick are some of the examples. Ad exchanges let ad networks and publishers transact centrally for ads. Publishers expect to get the best price from the exchange, better than from any specific ad network; in addition, publishers get liquidity. Advertisers get access to a large inventory at the exchange, and in addition, the ability to target more precisely across web pages. Finally, the exchange is a clearing house ensuring the flow of money. In many ways, these ad exchanges are modeled after financial stock exchanges. Since 2005 when RightMedia appeared, ad exchanges have become popular. In Sept 2009, RightMedia averaged 9 billion transactions a day with 100’s of thousands of buyers and sellers. Recently, DoubleClick announced their new ad exchange. It seems ad exchanges are likely to become a major platform for trading ads.

The AdX model is distinct from sponsored search. In sponsored search, a user poses a query at a search engine and gets search results together with ads arranged top to bottom. The assignment of ads to positions is by an auction among all advertisers who placed a cost-per-click (CPC) bid on a keyword that matches the query. If the user clicks on an ad, that advertiser pays the search engine the auction price. The dynamics are simpler since there is a single publisher and a one-sided marketplace of buyers. On the other hand, sponsored search aligns the incentives of advertisers and search engines with the quality of ads for the users, and hence, the publisher faces the challenge of monitoring and maintaining the quality.

Figure 5. Interactions between players within ad exchange.

Progress on research issues in the context of ad exchanges will likely impact the design and growth of not only the existing ad exchanges but also the “ecosystem” of bidders, optimizers and quantifiers around them. The key issues include:

• Game theory of adverisers: Advertisers may go to multiple networks, or choose networks strategically. What are the resulting dynamics? How does their strategic behavior affect competition within their campaigns along multiple ad paths, across advertisers, across ad networks and ultimately, across exchanges?
• Ad quality: In sponsored search, quality of an ad is correlated with click-through-rate, and so is the pricing and incentives of the advertiser. We need a similar quality metric for impressions and endogenize that in the auction to align advertiser incentives. A proposal is to generate a suitable Markov model for users that will capture even the long term impact of ad impressions.

More on the model abstraction and research challenges in the context of ad exchanges in [25].

References

[1] Edelman, B., Ostrovsky, M., Schwarz, M. (2006). Internet advertising and the generalized second price auction selling billion of dollars worth of keywords. In the Second Workshop on Sponsored Search Auctions.

[2] Aggarwal, G., Goel, A., Motwani, R. (2006). Truthful auctions for pricing search keywords. ACM Conference on Electronic Commerce (EC).

[3] Varian, H. (2007). Position auctions. International Journal of Industrial Organization 25: 1163 – 1178.

[4] Vickrey, W. (1961). Counterspeculation, auctions and competitive-scaled tenders. Finance 16: 8 – 37.

[5] Clarke, E. (1971). Multipart pricing of public goods. Public Choice 11: 17 – 33.

[6] Groves, T. (1973). Incentives in teams. Econometrica 41, 617-631.

[7] Nielsen. Interactive advertising bureau (IAB) search branding study. Commissioned by the (IAB) Search Engine Committee. http://www.iab.net/insights_research.

[8] Mahdian, M., Immorlica, N., Jain, K., Talwar, K. (2005). Click fraud resistant methods for learning click-through rates. In Workshop on Internet and Network Economics (WINE).

[9] Dominowska, E., Richardson, M., Ragno, R. (2007). Predicting clicks: estimating the click-through rates for new ads. In proceedings of WWW.

[10] Gonen, R., Pavlov, E. (2007). An adaptive sponsored search mechanism delta-gain truthful in valuation, time, and budget. In Proceedings of the Workshop on Internet Advertising and Network Economics (WINE).

[11] Feldman, J., Muthukrishnan, S., Pal, M., Stein, C. (2007). Budget optimization in search-based advertising auctions. In ACM Conference on Electronic Commerce.

[12] Borgs, C., Chayes, J., Etesami, O., Immorlica, N., Jain, K., Mahdian M. Dynamics of bid optimization in online advertisement auctions. In Proceedings of WWW.

[13] Mehta, A., Saberi, A., Vazirani, U., Vazirani, V. (2005). AdWords and generalized online matching. In FOCS.

[14] Rusmevichientong, P., Williamson, D. (2006). An adaptive algorithm for selecting profitable keywords for search-based advertising services. In Proceedings of the 7th Conference on Electronic Commerce (EC).

[15] Muthukrishnan, S., Pal, M., Svitkina, Z. (2007). Stochastic models for budget optimization in search-based advertising. In Proceedings of the Workshop on Internet and Network Economics (WINE).

[16] Mahdian, M., Nazerzadeh, H., Saberi, A. (2007). Allocating online advertisment space with unreliable estimates. In ACM Conference on Electronic Commerce (EC).

[17] Bharadwaj, V., Ma, W., Schwarz, M., Shanmugasundaram, J., Vee, E., Xie, J., Yang, J. (2010). Pricing guaranteed contracts in online display advertising. Proceedings of the 19th ACM international conference on Information and knowledge management.

[18] Break Media. (2009). Advertising age - kill or cure: How reckitt's big buy rocked online ads. http://breakmedia.break.com.

[19] Advertising, Microsoft. (2011). Display advertising. http://advertising.microsoft.com/display-advertising

[20] Blogspot, The Official Google. 2010. Online publishers: growing the display advertising pie. http://googleblog.blogspot.com/2010/08/online-publishers-growing-display.html.

[21] Fridgeirsdottir, K., Najafi-Asadolahi, S. (2011). Cost-per-click pricing for display advertising. http://phd.london.edu/snajafi.phd2005/papers/snajafi-paper2.pdf.

[22] McAfee, P., Papineni, K., Vassilvitskii, S. (2010). Maximally representative allocations for guaranteed delivery advertising campaigns. Working paper, Yahoo! Research 7(1).

[23] Heavlin, D. H., Radovanovic, A. (2012). Risk-Aware Revenue Maximization in Display Advertising. In Proceedings of WWW.

[24] Radovanovic, A., Zeevi, A. (2010). Revenue maximization in reservation-based online advertising through dynamic inventory management. In Proceedings of the 48th Allerton Conference in Communication, Control and Computing.

[25] Muthukrishnan, S. (2009). Ad exchanges: research issues. In Proceedings of the Workshop on Internet and Network Economics (WINE).

[26] Feldman, J., Muthukrishnan, S. (2008). Algorithmic methods for sponsored search advertising. http://arxiv.org/pdf/0805.1759v1.pdf.

Author

Ana Radovanović received her B.S. in Electrical Engineering from University of Belgrade in 1999. She received her Ph.D. in Electrical Engineering from Columbia University, New York, in 2004. Her thesis, for which she was advised by Prof. Predrag Jelenkovic, was titled “Nearly Optimal Cache Replacement Policies for Efficient Web Access”. In January 2005, Ana became a Research Staff Member in Stochastic Analysis group, Mathematical Sciences Department, IBM Research. After spending three years at IBM Research, Ana joined exciting and progressive Google as a Research Scientist.