**Google Adwords is an integral part of many digital marketing portfolios.** Marketers love it because of a clearly defined set of rules (unlike SEO) and a feeling of total control over the incoming traffic. Pay-per-click advertising is often preached as a way to drive visitors to a new website, blog or a startup landing page. All you need to do is “just” find a niche keyword and visitors will swarm the website to convert.

# The problem

The reality is (as always) a bit more complicated. **The competitive landscape on Adwords is growing rapidly** and even the smallest businesses are joining in to slice out a portion of the “cheap traffic”. **CPCs steadily increase each year** and paying as much as $1 for a click is becoming quite common (see this report). Furthermore, the whole mechanism is based on the Generalized Second-Price Auction which (deliberately) makes optimization difficult. **GSP auctions have multiple, sub-optimal equilibria which often result in “bad” behavior** – bidding wars, CPC attacks etc. It seems the only winner in this game is… Google.

A typical PPC account is often composed of two types of keywords: a core of high volume and high ROI terms (usually related to the brand or a particular product), and a long tail of keywords which occasionally generate clicks and conversions, but as a whole drive a significant portion of traffic. This long tail is set to capture highly targeted traffic with a higher conversion rate. The core keywords are usually easy to manage – it is the long tail that is tricky to optimize. Not only it does not have enough action to quickly estimate metrics like Click-Through Rate or Conversion Rate, but **usually there is never enough money to fund all of the long tail keywords.**

# Adwords optimization algorithm

I recently came across an interesting paper titled “An Adaptive Algorithm for Selecting Profitable Keywords for Search-Based Advertising Services” by P. Rusmevichientong and D. P. Williamson. It provides an algorithm for tackling budget allocation for Google Adwords. **I strongly recommend reading through the whole paper**, but it may be slightly too technical. Authors solve the budget allocation problem by providing a strict, mathematical optimization framework in two key scenarios:

- A static environment where CTR is already known for each keyword. This corresponds to well established accounts with enough data to accurately estimate keyword KPIs.
- A dynamic, exploratory environment where Click-Through Rates need to be discovered on-the-fly.

**The dynamic algorithm is especially interesting for large scale deployments in new accounts**. It also outperforms standard algorithms for the Multi-armed Bandit Problem in terms of the performance bound.

In this post, we will focus only on the static version of the algorithm, which I think could be a great tool for long-tail keyword budget optimization in established accounts.

## Notation

Let \(\{K_1,\dots,K_N\}\) be the set of all keywords in the account.

The algorithm requires us to know:

- \(S_i\) – the total number of Impressions for the i-th keyword with \(\sum_{i=1}^N S_i = S\).
- \(E[S_i] = \mu\) – the average number of impressions per keyword.
- \(\lambda_i = \frac{S_i}{S}\) – fraction of all impressions for the i-th keyword.
- Key performance indicators for each keyword: Click-Through Rate (CTR), Cost-per-Click (CPC) and Margin-per-click (MPC).

Going forward we will assume the Adwords account has been in operation for a while and that we can provide basic performance metrics with a high degree of accuracy.

We **normalize all monetary values (budget, CPC and MPC) so that the total budget for a given time period equals 1**. This is mostly for simplicity and all we need to do is just divide all CTRs, CPCs and Margin-per-Click’s by the total budget available.

$$p_i = \frac{CTR_i}{Budget} \enspace , c_i = \frac{CPC_i}{Budget} \enspace , m_i = \frac{MPC_i}{Budget}$$

## Assumptions

The algorithm requires these assumptions to hold for our account:

**All keywords need to be arranged in the order of decreasing ROI**, where \(ROI_i = \frac{m_i}{c_i}\).**The cost of funding all keywords must be larger than our budget**: \(\sum c_i p_i \lambda_i > 1\). Note that the “1” on the right hand side of the inequality is the normalized budget.- The third requirement is slightly more complicated. We need to find two numbers, \(k\) and \(\alpha\) such that:

$$k \geq 1: c_i \leq \frac{1}{k} \\

0 \leq \alpha < 1: \lambda_i \mu \leq k^\alpha$$

The first of the above requirements states that all **our CPCs are smaller than a certain fraction of the budget** (after normalizing monetary values). We compute \(k\) by finding the largest CPC in our account and calculating the largest k that fulfills the inequality. Once \(k\) is known, we calculate the \(\alpha\) parameter. Note, that \(\lambda_i \mu\) stands for the expected number of impressions for a given keyword. **Remember that we are looking for a single \(k\) and a single \(\alpha\)** that works for all keywords.

For example, assume the total budget for next week is $10,000 and the highest CPC in the account is $0.50 ($0.00005 after normalization by dividing it by the budget). To find \(k\), we plug in the normalized max CPC into the above inequality: \(0.00005 \leq \frac{1}{k}\) and we easily calculate \(k = 20000\). If the average number of impressions per keyword is \(\mu = 100\) and the best keyword gets on average only 2% of these impressions (\(\lambda = 0.02\)), then we plug in both values into the second inequality to get:

$$\lambda \mu \leq k^\alpha \\

0.02 * 100 \leq 20000^\alpha \\

0.07 \leq \alpha$$

**The actual values of k and alpha are very important because they have a direct impact on accuracy of the result.** The algorithm performs best when CPCs are small compared to the total budget and expected impression numbers are fairly uniform across the account.

## Budget optimization

Now, let \(\{K_1,\dots,K_N\}\) be the ordered set of keywords arranged by decreasing ROI. The paper proves that we only need to fund a certain prefix of the list of keywords to get close to an optimal budget allocation. The length of the optimal prefix is:

$$\mathcal{I} = max\{\mathcal{l}: \mu \sum_{i=1}^{\mathcal{l}} c_i p_i \lambda_i \leq 1 – \frac{1}{k} – \frac{1}{k^{(1 – \alpha)/3}}\}$$

The lower bound for accuracy (compared to the optimal keyword set) can be calculated as:

$$Perf = 1 – \frac{1}{k^{(1+2\alpha)/3}} – \frac{2}{k^{(1-\alpha)/3}}$$

As you can see, accuracy depends on the \(k\) and \(\alpha\) parameters. Please check page 5 of the paper to see how accuracy changes for different values of both parameters. **For the above example, with \(k=20000\) and \(\alpha = 0.07\) the algorithm would achieve accuracy of at least 88%** compared to the optimal solution.

# Final thoughts

Optimizing budget allocation for long tail keywords is just one of the possible application of this methodology. Its real beauty lies in an easy to understand mathematical model and the adaptive version of the algorithm where KPIs need to be determined on-the-fly. It is very easy to implement in R or Python and run on large accounts.