Address

1410 Rue Stanley
Suite 606
Montreal, QC H3A 1P8
Canada


122 East 42nd Street
Suite 2005
NY, NY 10168
USA

 

Email

info@datacratic.com

Adresse

1410 rue Stanley 606
Montréal, QC H3A 1P8


122 East 42nd Street
Suite 2005
NY, NY 10168
USA

 

Courriel

info@datacratic.com

 

Location map

Contact Us

How can we contact you?
http://
Your submission, excluding personal information, will be analyzed for spam. By submitting this form, you accept the Mollom privacy policy.

Contact us

Peeking Into the Black Box, Part 1: Datacratic’s RTB Algorithms

This article is about the statistical and economic theory that underlies Datacratic’s real-time bidding strategies, as a follow-up to my previous article on how we apply control theory to pace our spending, which I’m grandfathering in as “Part 0” of this series called Peeking Into the Black Box.

At Datacratic, we develop real-time bidding algorithms. In order to accomplish advertiser goals, our algorithms automatically take advantage of other bidders’ sub-optimal behaviour, as well as navigate around publisher price floors. These are bold claims, and we want our partners to understand how our technology works and be comfortable with it.  No “trust the Black Box” value proposition for us. In Part 1 of this series I’ll explain the basics of our algorithm, first how we determine how much to bid, and then how we determine when to bid. In Part 2 I’ll show how this approach responds in some real-world situations.

First, Tell the Truth

Let’s say, for sake of illustration, that you are Datacratic's bidder.  You’re configured for a 3-month direct-response campaign with a total budget of $100,000 and a target cost-per-click (CPC) of $1.00.  Like every other participant in real-time auctions, you subscribe to a stream of several thousand bid requests (also known as ad calls) per second, each representing an opportunity to immediately show an ad to a particular user on a particular site. You must respond to each bid-request which matches your targeting criteria with a bid, within a few dozen milliseconds. How do you decide what amount to bid? Most real-time auctions are what are known as Vickrey, or second-price, auctions.  The winner is the one who places the highest bid, but pays the amount of the second-highest bid. This type of auction was likely chosen by the designers of real-time exchange because the best strategy for bidders in such a situation is to “bid truthfully” (one of the well-known results of auction theory). This means that the bid you place should be equal to the amount that the good is worth to you.  In this case the “good” is the right to show an ad.  How much is that “worth”? The target CPC is $1.00, so it’s not a bad assumption that a click is worth at least that much to the advertiser.  Let’s say that the average click-through rate (CTR) is 0.05% for this campaign: one out of every two thousand impressions gets clicked on.  So if you win this auction, you have a 0.05% chance of getting something that is worth a dollar, and multiplying those together we can say that the expected value of winning this auction is 0.05 cents.  If you’re bidding truthfully (which auction theory says you should), that’s how much you should bid.  One equation you could use to come up with a bid is therefore:

bid = value = targetCPC * CTR

That’s a bit too simplistic, though, and doesn’t take advantage of the real-time nature of the exchange.  We’re a predictive analytics company, so as our bidder you have access to some fancy models.  These models predict, in real-time and on a bid-request by bid-request basis, the probability that this specific user will click on this specific ad in this specific context at this specific time. This means that you don’t have to use the campaign-wide average CTR when computing your bid, you can use the probability that our predictive model has generated for this request:

 bid = value = targetCPC * P(click)

So far so good, but not particularly groundbreaking: where is the secret sauce, other than in the probability-of-click prediction model which is beyond the scope of this article? That predictive model is certainly part of it, but there’s actually an additional wrinkle to the above equation: it only tells you what the bid should be if you actually decide to bid. And when deciding whether or not to bid, you shouldn’t just look at the value of winning the auction, but the cost as well.

To Bid or Not To Bid, or: Cost is not Value

As I talked about in Part 0, if you just bid on every bid-request that comes your way, you’ll spend the budgeted $100,000 way ahead of the 3-month schedule. In that article I also detailed a system for spreading your spend out over time by using a closed-loop control system to vary the probability of a bid being submitted.  Let’s try to take that idea further: what if instead of randomly selecting which requests to bid on, you could find a way to bid on only the best requests? I just showed a way to model the expected value of winning an auction but in this context “best” doesn’t just mean “highest value”; that’s only half the picture. As an example of this, let’s look at an importer purchasing one of two types of goods for resale. Good A has a 10% lower resale value than Good B, but it costs half as much:

Two goods with similar values but different surpluses. 

In this case the less valuable Good A is “better” because because what matters isn’t just the value or the cost but the difference between the two, or the surplus.  In business this is called profit and in game theory this is usually called the payoff.

surplus = profit = payoff = value - cost

The equation above holds for the RTB context if you win the auction, but what if you don’t? In that case, you get no chance at a click, so the value is zero, and you also don’t pay anything, so the cost is zero (modulo fixed costs, which are out of the scope of this article).  So for our purposes, the expected surplus is the same as above, multiplied by the probability of you actually winning the auction:

surplus = (value - cost) * P(win)

Now assuming that alongside Datacratic's click-probability predictor, you also have access to a clearing-price-predictor (again beyond the scope of the current article) that tells you for each bid-request how likely you are to win the auction at each price, you can now compute the expected surplus.  (As it happens, one can also maximize this equation as a function of the bid to prove the well-known “bid truthfully” result mentioned above: the bid which gives you the highest surplus, no matter the price distribution, is equal to the value).

A surplus surface as a function of bid and value. For any given value, the maximum surplus occurs where bid=value.

So now when our closed-loop pacing control system says that in order to meet the budget requirements, you should only bid on a quarter of the request stream, you can choose to bid only on the bid-requests which have expected surpluses in the top quartile. This means that the control value is no longer the probability of bidding, but some measure of selectivity in the auctions you are willing to participate in: the lower the control value, the more selective you should be. You’re still placing the optimal bid every time, but now you’re specifically targeting the auctions where you think you will make the most profit given the target CPC, thereby increasing your chances of actually achieving a much lower CPC.

Algorithm Meets World

This post explains the two major components of our system: bidding truthfully and pacing economically. In Part 2 of this Peeking Into the Black Box series, I’ll show how this approach to RTB handles some real-world situations advantageously.  

Update Sept 25, 2013: In Part 3 and Part 4 of this series, I actually go back on some of this work and show that we can do better than using surplus to pace, and even better by bidding untruthfully.

Category: 

Comments

When you calculate the surplus as (value - cost) * P(win) and have a clearing-price-predictor that predicts P_win(value) then you still miss an estimator for the cost. Or do you simply take the value that maximizes the win probability argmax_value(P_win(value)) as an estimate for the cost since this is likely the second best bid in the auction???

Submitted by Sebastian B on

Hi Sebastian,

We set the cost to be E[price | win-at-x] and computed that as the integral from 0 to x of t*f(t)*dt normalized by F(x), where x is the bid, f is the clearing-price PDF and F is the clearing-price CDF. Sorry for the lack of real equation support in this blog :)

Nick

Submitted by Nicolas Kruchten on

Add new comment