#2 KPI Forecasts & Assignment

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

• The algorithm rewards similar filling levels (in %), i.e. fulfilment of the constraint

-Highly relevant cookiepool

• Especially users with high v_ij, i.e. users who contribute disproportionately well to the campaign objective, will be grouped in the corresponding campaigns.

-interweaving of reach campaigns and broad-based OTTO campaigns

• Users with typically low click rates for all campaigns, amongst other user characteristics, tend to be sorted into view campaigns because all users can contribute to this target.
• Users for whom there is no (focused) partner campaign are rather assigned broad OTTO campaigns.

-Correlation of campaigns

• The correlation of campaigns' KPI forecasts shows which campaigns will compete for the same users.

-Randomization of assignment depends on the user profile

• Users with very closely focused interests always tend to end up in these respective campaigns; users with broad interests can also be assigned to different campaigns in different runs.

Benchmarking:
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: