Ad Auction and Ranking Example

cX::ad Auction workflow

There are multiple stages involved in determining which ad(s) to return for a single ad request, a simplified view is:

• Request Augmentation:
  The ad request is augmented with extra matching terms based on user location, user device and user data from cX::analytics

• Candidate Selection:
  Based on their matching criteria (keywords, location, dayparting, etc) we determine which ads are candidates to be shown for this request.
  This could be anywhere between zero and several hundred candidate ads.

• Ranking:
  Each candidate ad is scored based on a product's Rank Model.
  Ads are then sorted by priority, then by rank score.

• Deduplication:
  Filtering of duplicate ads is performed to ensure we do not show multiple ads from the same campaign, etc (product configurable)

• Costing:
  We determine the final cost per click (zero for CPM campaigns) for each of the ranked ads based on the Cost Model.
  This is done as a separate step from ranking as the ordering of displayed ads can effect their cost (but not their ranking score).

• Post Auction Filtering:
  Any ads which have either:
  

  1. Insufficient budget available (possibly due to smoothing) or

  2. A cost below the AdSpace's minimum price [1]

  are removed from the set of candidate ads.

  
  

• Returned Ads:
  The requested number of ads (and their creatives) are returned by the adserver.

Yield Model example

To conduct ad auctions in cX::ad, each product is required to select a Rank Model and a  Cost Model.

There are a wide variety of models to choose from, each appropriate for different situation or products.
When creating a CPC product, a common choice is to use a Yield Rank Model and a Yield Cost Model.

If we request ads from such a product, we may see something like the following produced by the adspace diagnostic tool:

Based on the steps described above we can see that:

• Four ads were returned by the Candidate Selection step (all for the keyword "apple" in this case, but if a query were augmented with profile data there would likely be other matches too).

• The Yield Rank Model produces the scores in the 'Auction Rank Weight' column (more on this below).
  Our ads are then sorted by a) ad Priority then b) the rank score, with any increase in priority trumping the rank score.

• The Yield Cost Model produces the auction costs in the "Auction Cost / Pinned" column (For single currency brokers these numbers will always be the same, for other brokers 'pinned' will be in a common currency).
  This number is the amount charged per click.

Calculation of Rank:

The Yield Rank Model uses the following formula to score each ad:

score = bid * ctr * expression_weight * ad_quality
 
where:
  bid               -> The ad's bid for the selected keyword
  ctr               -> The predicted CTR for this Ad
  expression_weight -> The weight of the selected keyword.  This will be 1.0 for a "k=" type parameter, but often much lower for terms from a user's behavioural/contextual profile.
  ad_quality        -> Always set to 1.0

It is straightforward to apply this calculation to the table above (where ad_quality = 1, and expression_weight = 1).

Calculation of Cost:

The Yield Cost Model uses the following algorithm to determine the cost for each ad.

• The lowest ranked ad is assigned the auction reserve price (i.e., the Product's floorprice) as a cost (In this case, Ad #4 is assigned a cost of $0.10 AUD)

• We then work up the list taking each neighbouring pair of ads A&B (In this example, the pairs are 3 & 4, then 2 & 3, then 1 & 2) and:
  

  • For each pair we calculate the click cost which would make the expected value of showing A higher than the expected value of showing B.
          cost_a = bid_b * (ctr_b / ctr_a)
    Intuitively we can see that if A and B have the same CTR, then the cost of A is set to the bid of B.
    If A has twice (or half) the CTR of B, then the cost of A is half (or twice) the bid of B.

  • We then add $0.01 (the lowest currency amount amount allowed in the specified currency) to cost_a, and ensure that the cost at minimum reaches the auction floor price.

So in our ongoing example:

The cost of Ad #4 is $0.10, as that is the auction reserve of the auction.

For Ad #3:

cost_a = bid_b * (ctr_b / ctr_a)
       = $2.00 * 0.000053 / 0.019366
       = $0.0055

After adding $0.01, the cost is still less than the auction reserve, so the cost is set to $0.10

For Ad #2:

cost_a = bid_b * (ctr_b / ctr_a)
       = $1.00 * 0.019366 / 0.149
       = $0.12

After adding $0.01, the cost becomes $0.13

Finally for Ad #1:

cost_a = bid_b * (ctr_b / ctr_a)
       = $1.00 *  0.149 / 0.01497
       = $9.94

Adding $0.01 gives the click cost of of 9.95

Position Stabilised Yield is similar to Yield Cost Model but the key difference is that the cost always increments as you move up through the result set. For example, an ad in position 3 might have an excellent CTR which may mean that its actual cost is below position 4. This model will force the ad in position 3 to pay at least one minimum currency unit above position 4 (see scenario 1 for Position Stabilised Yield model on Cost Models page).

Predicting Ad Click-through Rates

In the text above we use assume the CTR of each ad is known in the auction, it is worth pointing out that this is the predicted chance that the current user will click, and not the historic proportion of users who have clicked in the past.
This historic CTR can help to guide our predictions, but cannot be used in place of them (e.g. if an ad has 10 impressions, or worse zero impressions, and has never been clicked the historic CTR is 0%, but this would be a poor prediction).

Our current algorithm for predicting Ad CTR primarily relies on a combination of inputs including:

• The Ad's historic Click and Impression counts

• The Ad's historic Click and Impression counts on the current matching Keyword

• The Ad's historic Clicks and Impressions counts on the current AdSpace

• The Broker's historic Click and Impression counts

This list is likely to be expanded as our CTR predictions become more sophisticated.

This approach to CTR calculation works well in practice, but has one small caveat.
Say we have an ad 'A' with a CTR of 1% (which is well above their broker's average CTR of 0.8%) and that 'A' matches on the keyword 'K'
Next an ad 'B' is created which also matches on keyword 'K' (and no other keywords)
Whenever a request is received for keyword 'K' ad 'A' will always be shown, and ad 'B' will never get a chance to show unless 'A' runs out of budget.

To improve this behavior, we need to make a trade-off between explore (showing impressions to improve the accuracy of our CTR calculation) and exploit (maximising current revenue at the expense of showing new ads) behavior.

Beta Randomized CTR

One way to make this trade-off is to divert a small portion (usually 20%) of a broker's traffic to use the Beta-Randomized CTR algorithm instead of the standard CTR calculation algorithm.

With our 'standard' CTR calculation algorithm we attempt to predict CTRs as accurately as possible.
With the 'beta' CTR algorithm, we instead take into account the uncertainty about our prediction and predict a CTR from the range of likely values (technically our posterior probability).

For example, say we have four ads with the following impression counts:

With the 'standard' CTR algorithm, we would always predict the CTR using the 'CTR' column.
Using the 'beta' CTR, we would generate a predicted CTR somewhere in the predicted range (note: numbers are just examples, not the actual range. predictions are skewed towards the observed CTR value, http://en.wikipedia.org/wiki/Beta_distribution )

With the beta distribution, if A and B were in the same auction, both would win roughly 50% of the time.
With the standard algorithm, A would always be shown so long as it's predicted CTR remained above B.
Likewise, under the beta distribution C and D would receive ~50% of impressions if in the same auction, while D would receive all impressions under the standard algorithm.

However if A and C were in the same auction, the the standard algorithm and the beta distribution would both (almost) always prefer 'C' as we can say with a high confidence that C has a higher CTR as we have observed this over 1,000,000 impressions.

Finally in the case where B and D were competing in an auction, the 'standard' algorithm would always select 'D', while the random algorithm would usually (maybe 90% of the time?) select 'D'.
The difference between the A vs C, and B vs D case comes down to how confident we are of our CTR estimates.

• In A vs C we have a large amount of data, so we can confidently say that 'C' should be preferred over 'A'

• In B vs D we only have a limited amount of data which indicates that 'D' outperforms 'B', but we still choose to show 'B' occasionally just in case it is actually better.
  As more data is accumulated, and assuming the CTR values still hold, then 'B' will be shown progressively less often. 

Using the "80% of users rank ads by 'standard', and 20% of users rank by 'beta'" approach gives us a nice tradeoff between explore and exploit.

[1]: In most cases, it is recommended to set an AdSpace's (but not a product's) minimum cost to 0 to avoid this filtering

Last updated: December 27, 2021