Share with your friends


Analytics Magazine

Online Analytics: Sponsored search advertising

May/June 2012

How statistical and optimization methods help advertisers manage their Internet campaigns more efficiently.

Patrick Quinn, Michel Gamache and Sandrine ParozBy (left to right) Patrick Quinn, Michel Gamache and Sandrine Paroz

As the number of worldwide Internet users grows constantly, advertisers seeking to promote their products and services are turning more and more frequently toward search engine marketing. Major search engines offer various publicity channels in which advertisers can display several types of ads. These ads can be found in the form of texts, banners or even videos. Depending on the type of ad, advertisers will either be charged as a function of the number of times their ad is shown or the number of times it is clicked.

In 2009, the sum of revenues generated by the four major search engines exceeded 37 billion dollars; Google, Yahoo, Baidu and Bing put up annual revenues of $23.7 billion, $6.5 billion, $4.4 billion and $3.1 billion, respectively [1], [2], [3], [5]. Most of the revenue was produced by advertiser Web marketing campaigns. For instance, Google claims that 99 percent of its total revenues in 2007 and 97 percent of its total revenues in 2008 were a result of advertisers paying to use its publicity networks [4].

One of the search engines’ most lucrative publicity channels is the sponsored search network, where advertiser text ads are shown on the result pages of user search queries (i.e. when users enter keywords in the search box). For each possible query, advertisers compete in auctions to determine the order in which the ads will be presented. Figure 1 shows an example of 10 ads that have been obtained while entering the query “cars for sale” in Google. The ad positions are numbered sequentially, from the top (position 1) to the bottom of the list (position 10).

Figure 1: Example of positioning for 10 different text ads on a search results page.
Figure 1: Example of positioning for 10 different text ads on a search results page.

Studies have shown that higher positions (near the top of the list) obtain more visibility and significantly higher amounts of clicks than lower positions (near the bottom of the list). Therefore, the auction mechanism’s goal is to assign a position to all of the advertisers competing for a specific query, based on the amount they are willing to pay for each click (this amount is called a bid). Search engines use sophisticated ranking algorithms that take into account advertisers’ bids as well as their text ad and Web site relevance to determine how the ads should be placed in the list. More specifically, advertiser bids are weighted by a relevance score determined by the search engine. Then, the weighted bid values are sorted in decreasing order. Once the ranking is established, the exact amount the advertisers must pay for each click is calculated using the generalized second-price algorithm; basically, the cost per click (CPC) of the advertisers corresponds to the minimal value allowing them to remain higher than the nearest competitor below them in the ranking.

Consequently, clicks, CPC and bids are all generally decreasing when expressed as a function of position. Figure 2 shows, as an example, the graphs that are obtained by plotting total clicks, average CPC and bids for each daily average position value of a given keyword (ad stats are aggregated daily for each keyword). This example illustrates the tradeoff advertisers are faced with while managing their campaigns; they must find a balance between obtaining a high amount of clicks at a high cost per click and a low amount of clicks at a low cost per click. Finding a keyword’s optimal bid value is not always easy; if the bid is too high, the campaign may become unprofitable, and if the bid value is too low, the campaign will not generate enough volume.

Figure 2: Number of clicks, average CPC and bid as a function of average position, for a given keyword.
Figure 2: Number of clicks, average CPC and bid as a function of average position, for a given keyword.

The example in Table 1 shows how each position can generate different profitability levels for a specific keyword. By assuming each conversion (e.g. subscription, membership, sale or other similar event) is worth $60 to the advertiser (this value will vary from one business to another) and the conversion rate is constant from one position to another, it is possible to estimate the performance of every position. In this case, we conclude that position No. 6 is the most profitable because it offers the best balance between click volume and cost. As it is the case with the majority of keywords, the data from this example clearly shows how ad positioning can influence the efficiency of a campaign.

The previous example suggests that the corresponding click, CPC and bid values are known for each possible position. If this were the case, optimizing a campaign’s performance would be relatively simple. However, the reality is that advertisers don’t know exactly how many clicks they would receive in each position, how much these clicks would cost or even how much they should bid to reach their targeted position. They must predict these values based on their historical data, which represents a challenge in itself. The assumptions of constant profit per conversion and constant conversion rates per position can also generate some uncertainty. In fact, in most types of businesses, conversions occur very rarely. Based on our studies, typical conversion rates range between 1 percent and 4 percent, which means about 25 to 100 clicks are required in order to obtain a conversion. Consequently, considering such low conversion volumes, it can be difficult to determine the average profit associated with a conversion and the average conversion rate of a keyword for each position.

To further complicate matters, sponsored search campaigns are typically formed of thousands of keywords. Usually, advertisers will try to bid on all the keywords they judge relevant to their business. For example, a company selling shoes will want to bid on keywords such as “shoes,” “buy shoes,” “shop shoes,” “running shoes,” “tennis shoes,” “basketball shoes” and many others. With multiple combinations of verbs, adjectives and nouns, as well as many misspells and singular/plural forms possible, it’s easy to understand why campaigns can contain incredibly high amounts of keywords.

Table 1: Performance estimations of 10 ad positions for a specific keyword.
Table 1: Performance estimations of 10 ad positions for a specific keyword.

Advantages of Sponsored Search Advertising

Sponsored search advertising has become increasingly popular over the past few years. It presents several advantages that distinguish it from other Web publicity channels and traditional marketing mediums such as television, radio and newspaper ads.

First, it allows advertisers to target specific audiences by choosing exactly which keywords they wish to associate with their products or services, as well as which geographic locations they want to consider. When the keywords forming a campaign are carefully selected, ads are mostly shown to users who represent real potential customers and are truly interested in the product or service offered.

Second, sponsored search campaigns are accessible to all types of businesses, because advertisers have the liberty of deciding exactly how much they are willing to pay for each click. Large businesses with high profit margins could be willing to pay more for each click, whereas smaller businesses with low profit margins could still benefit by setting lower bid values. Marketing campaigns should remain profitable as long as the bid values are lower than the expected profit per click, which can be calculated in the presence of sufficient historical data.

Finally, the fact that advertisers usually pay for the number of clicks they receive rather than the number of times their ad appears is particularly interesting; they only pay for customers who are directed to their Web site. With the use of click and conversion tracking tools, it is possible to closely monitor every single keyword’s performance. Unlike with most other marketing mediums, an exact profit figure can easily be attributed to each portion of a campaign.

Research Context and Objectives

In order to effectively manage a campaign, every keyword must be closely monitored and bid values must be adjusted periodically. Considering the large number of keywords contained in a campaign, it is virtually impossible to analyze all the trends in the data and manage each bid individually. That’s why several automated campaign management tools have emerged on the market. These tools assist advertisers in tasks such as the creation of campaigns, the management of bids using a variety of algorithms and the generation of performance reports.

Our research was performed in collaboration with Acquisio, creator of a performance media platform designed to help marketers handle tasks associated with performance advertising across all publicity channels. Acquisio’s platform is used by more than 300 marketing agencies, managing a total annual budget in excess of $500 million. Acquisio has invested in various research initiatives, seeking to develop adapted optimization tools that would allow advertisers to manage their campaigns more quickly and efficiently.

Our research focused specifically on sponsored search marketing campaigns. Our main objective was to effectively model and predict keyword behavior in order to optimize overall performance. More precisely, we wanted to develop algorithms that could exploit the information given by the keywords’ historical data in order to implement them in Acquisio’s platform, ultimately allowing advertisers to manage their bids in the most efficient and profitable way possible.

Modeling, Prediction and Optimization

We use a linear programming model that seeks to maximize the overall performance of a campaign. Depending on the advertiser’s intentions, the linear program’s objectives may vary; some will want to maximize expected profits, while others will try to maximize the number of clicks they receive for a certain budget. With these objectives in mind, we must consider constraints such as limited advertisement budgets, maximal bid values and acceptable position ranges.

In order to model the situation, we must estimate click, CPC and bid values associated with each possible position. In some cases, traditional regression methods can be used effectively. For instance, clicks, CPC and bids of the keyword shown in Figure 2 could easily be predicted using single variable regressions. With statistically acceptable curve fittings, it is possible to extrapolate any click, CPC and bid value outside the range covered by the historical data. However, many keywords require more sophisticated prediction approaches. In fact, the historical data is not always sufficiently dispersed among the different positions, and it is often impossible to observe the decreasing trends that characterize the click, CPC and bid variables. Consider the keyword in Figure 3. Although 30 days of data have been collected for this keyword, very few positions have been covered and no obvious trend can be observed. This makes it impossible to generate accurate predictions using regressions.

Figure 3: Clicks, average CPC and bid graphs with which it is impossible to apply regressions.
Figure 3: Clicks, average CPC and bid graphs with which it is impossible to apply regressions.

Confronted with this problem, we realized it would be necessary to develop alternative prediction methods in order to expand the scope of our optimization model. Of course, it would be possible to obtain more information on each position’s performance by varying the keyword’s bid values. However, this would require many days to experiment and could generate significant costs. Thus, our research focused mainly on applying generic prediction equations to different groups of keywords. More specifically, we found that the decrease rates of the click, CPC and bid graphs are usually very similar from one keyword to another, within a group. Therefore, by simply scaling these values to each of the keywords we wish to predict, it is possible to obtain estimation functions, even when there is very little data available. When tested on our databases, this approximation method provided reasonable error margins, which allowed us to conclude that it could be used to predict the behavior of keywords that would have originally been excluded from the scope of the model.

At first, the application of this method may seem relatively simple. However, various keyword characteristics can make the prediction process much more complicated. Some keywords generate very high volumes of clicks and conversions, while others obtain little or even no volume. For example, keywords such as “shoes” are very general and will usually be associated with many searches. Consequently, they will generate more clicks than very specific keywords such as “buy Adidas black tennis shoes.” However, specific keywords will generate much higher click rates; customers entering specific queries are generally more advanced in their buyer cycle and will more likely click on ads that meet their needs. Furthermore, some keywords have periodic behaviors (weekly, monthly or seasonal volume peaks) while others are relatively stable. For instance, keywords such as “outdoor soccer shoes” will have much higher search volumes during the spring and summer periods. Time series analyses are therefore necessary in order to detect the periodic variations in volume.

In brief, the generic equation parameters used to predict some of the keywords might vary depending on keyword characteristics such as specificity and periodicity. In order to be assigned to the most efficient prediction methods available, keywords must be classified into several groups. This ultimately maximizes the number of keywords that can be included in the scope of the optimization model.

Summing up, the world of sponsored search advertising is so vast and complex that the use of campaign management software and decision support tools is almost necessary in order to achieve satisfying profitability levels. Because data are stored on a daily basis for each keyword that forms a campaign, the use of statistical and optimization methods could help advertisers manage their campaigns more efficiently.

Patrick Quinn is a supply chain management consultant with Deloitte whose master’s degree project at Ecole polytechnique de Montréal involved the Acquisio project described in this article. Michel Gamache (, INFORMS member, is a professor in the Department of Mathematics and Industrial Engineering at École Polytechnique de Montréal. Sandrine Paroz is an optimization specialist at Acquisio, a Montreal-based company that provides automated tools for search, display and social advertising.



business analytics news and articles

Analytics Blog

Electoral College put to the math test

With the campaign two months behind us and the inauguration of Donald Trump two days away, isn’t it time to put the 2016 U.S. presidential election to bed and focus on issues that have yet to be decided? Of course not.


Holiday Retirement earns Edelman Award

Holiday Retirement won the 2017 Franz Edelman Award for Achievement in Operations Research and the Management Sciences from INFORMS for its use of operations research (O.R.) to improve the pricing model for its more than 300 senior living communities across the United States. Read more →

U.S. Air Force and Disney receive the 2017 INFORMS Prize

The U.S. Air Force and The Walt Disney Company both received the 2017 INFORMS Prize for their pioneering and enduring integration of operations research (O.R.) and analytics programs into their organizations. The prizes were presented at the INFORMS Conference on Business Analytics & Operations Research in April in Las Vegas. Read more →

Air Force Academy’s O.R. program saluted

The U.S. Air Force Academy won the 2017 UPS George D. Smith Prize for its operations research (O.R.) program, which prepares graduates to become frontline O.R. practitioners as analysts in the Air Force. The program exposes more than 50 percent of cadets to at least one O.R. course and provides cadets the opportunity to graduate with a Bachelor of Science degree in O.R. Read more →




2017 INFORMS Healthcare Conference
July 26-28, 2017, Rotterdam, the Netherlands


CAP® Exam computer-based testing sites are available in 700 locations worldwide. Take the exam close to home and on your schedule:

For more information, go to