09. Dezember 2020
Listen – and repeat. In the last blog post we repeated what real-time bidding is, the role of Compass in OTTO’s own display network, and how we get great insights into auctions and customer behaviour from the data available to us.
We’re now going to use this information to take a close look at bidding strategies. But let’s take things one step at a time – before we get to that, we want to address the following problem: an advertising partner wants to show its campaigns to the most suitable users possible, for instance to optimize click rates or increase reach. Since we have a large number of campaigns and advertising partners but can naturally fill an advertising space for a user just once, we have to get to grips with a multidimensional problem:
1. several campaigns could suit one user
2. campaigns pursue different goals
3. campaigns have very different daily budgets in some cases.
First of all, let's try to make a prediction. A KPI is determined for each user for each campaign. At the moment, this is only about ‘view’ or 'click' (that is, CPM or CPC minimisation). We plan to add more selectable KPIs in future – but as mentioned above, let’s take things one step at a time.
When modelling click probability, we use supervised machine learning algorithms that take into account users’ browsing behaviour on OTTO.de, long-term user-profile information, as well as users’ past interaction with advertising banners. This allows us to evaluate the value of the individual user to the respective target KPI of each campaign.
The next step is to assign users to campaigns. Users should be assigned precisely to the campaign in which they contribute most to the target KPI. At the same time (more or less as a constraint), all campaigns need to be assigned exactly the proportion of users that their partial budget represents in the total budget. Given the millions of users and hundreds of campaigns we’re working with, this is a colossal generalized assignment problem.
Achieving optimal assignment is impossible due to the vast range of possible solutions. This is where approximation algorithms help us out. In applying these we’re adapting an idea from Chakrabarty et al., who designed an o(n) algorithm and determined a worst-case bound.
Within the campaign, we first Z-score normalise the KPIs to make them comparable and trim them to (-3,3). Each value now expresses how many standard deviations the user suits the campaign better than the overall average for the campaign. We then add 4 to all to move them to the range (1,7).
As part of the assignment, we now iterate through the users in the data set in random order, and in each step assign user in the following way:
The weighting with Ψ means that less-filled campaigns are somewhat preferred at each step, meaning they catch up progressively.
The algorithm is not parallelizable, because the level of assignment needs to be known everywhere at all times.
What are the advantages of this procedure?
-Compliance with the side condition that a campaign's budget must not be exceeded
-Highly relevant cookiepool
-interweaving of reach campaigns and broad-based OTTO campaigns
-Correlation of campaigns
-Randomization of assignment depends on the user profile
To show that the algorithm works very well, we ran it on a subset of our real data against benchmark models (all o(n)).
For the assignment we chose five campaigns (CA_2 to CA_5 with click as KPI; CA_6 with view as KPI) and 100,000 users. We set the budget distribution for the five campaigns at 10:40:30:10:10. Here’s the user rating for each campaign:
We tested the following algorithms here:
M1: Assignment is completely random
M2: Each user receives the campaign with the highest value
M3: Each user receives the highest-value campaign which is not yet fully assigned
M4: Each user receives the campaign with a z-score value which is not yet fully assigned
M5: Our approach.
Due to correlation, the overall objective – assigning each campaign its required top users – is unattainable. We measure the performance of the models relative to this objective in order to evaluate the results regarding the main goal – to assign highly relevant users – and the Kullback Leibler (KL) divergence between budget distribution and user distribution to measure the compliance to the side condition. We measured the following results:
Approaches M1 and M2 completely failed to fulfil the side condition (KL_div >0.01). M2 only distributed users to CA_6 (because this campaign’s KPI is always higher than the click probabilities of all the others). Using the z-scores in M4 delivered an advantage over M3. Our own approach delivered the best scores for each campaign and simultaneously fulfilled the side condition. The greedy algorithms M3 and M4 underperformed the cooperative algorithm M5.
By splitting up the optimisation problem into individual smaller steps and using approximative algorithms, we were able to solve the ‘impossible’ assignment problem in the best possible way. This means that an optimal user pool can now be assigned to each campaign.
In the next post, we’ll focus on the final part of COMPASS – defining the optimal bid strategy.