Gopher refers to north
Online advertising, also known as online advertising, Internet advertising, as the name implies, refers to advertising placed in online media. Usually we can see it in the news stream, short video, news and micro blog. For large advertising platforms, there will still be a large number of ads to be delivered after user orientation, and the selection of appropriate ads from a large number of ads to show to users is the topic of this paper — online advertising allocation strategy.
Term to describe
To better understand this article, do some noun descriptions in advance.
ECPM (Effective Cost Per Mille): The amount of advertising revenue generated Per 1,000 impressions. This measure reflects profitability and does not represent actual revenue. Different advertisers will choose different bidding methods such as CPC and CPM, so it is impossible to compare advertising allocation with pure bidding. That is why ECPM is used to evaluate the revenue brought to advertising platform by advertising with different bidding methods.
Targeted advertising: the so-called “targeted” is actually the screening of the audience, that is, the display of advertising is determined by visitors, advanced advertising management system can provide a variety of targeted ways.
The best one will fit
Maximizing revenue is a priority for advertising platforms. In order to maximize revenue, we choose the AD with the highest ECPM for each AD request. This logic is correct in theory, but not necessarily in practice, so what could possibly be wrong with it?
- Advertising consumption exceeds the budget limit.
- The advertising budget is endless.
- Empty result problem.
- Part of the advertising consumption too fast affect advertisers to put experience and user product experience.
Problem analysis
Question 1
When analyzing problem 1, we need to have a consensus that there is a certain delay in the reporting of data such as advertisement clicks and exposure.
As the advertising allocation strategy does not consider the budget consumption information, it fails to slow down the exposure speed when the consumption is close to the budget limit, so that the traffic that should be allocated to other advertisers is still allocated to advertisers with limited budget, which is a waste of the advertising platform traffic (the larger the traffic is, the more serious the waste will be).
Question 2
Some small and medium-sized advertisers have weak competitiveness (low bid), it is difficult to get enough exposure, this situation is especially obvious when there is plenty of advertising.
Question 3
This may be due to a lack of advertising resources, but it may also be due to fast consumption of targeted advertising (see the examples below).
Question 4
The ranking of advertisements according to ECPM will lead to a large difference in the speed of advertisement consumption and directly affect the advertising experience of advertisers, and even the repeated advertisements will directly affect the product experience of users, and in turn affect the CVR of advertisements.
To further illustrate the shortcomings of the pure premium algorithm, see the special example below.
| advertising | Price ($) | Budget ($) | directional |
|---|---|---|---|
| A | 0.5 | 100 | Male, game |
| B | 1 | 100 | Male, games, sports |
Take the above advertisement as an example, the existing male, game and male, sports request 100 each. The ideal maximum revenue is $150, but when the ads are allocated according to the above strategy, there will be male, game, the first 100 requests to consume B ads, male, sports, the first 100 requests to consume no ads. The ECPM-sorted algorithm, also known as the Greedy algorithm, allows high-value ads to be consumed quickly.
What fits is best
The Balance algorithm
Different from the Greedy algorithm, the Balance algorithm proposed by Kalyanasundaram and Pruhs ignores a single bidder bid and tries to Balance the budget consumption of all bidders, making them online for as long as possible, that is, trying to keep all advertising at a constant speed. The algorithm is described as follows:
{continue} else {select an AD with the smallest (cost/budget) value}Copy the codeCompared with the greedy algorithm, the Balance algorithm balances the consumption speed of all advertisements and can effectively solve the problem of the greedy algorithm’s fast consumption of advertisements, but it is still not the best solution to the problem of the inexhaustible consumption of advertisements. Let’s look at the following special example:
| advertising | Price ($) | Budget ($) | directional |
|---|---|---|---|
| A | 1 | 100 | Male, game |
| B | 0.01 | 100 | Male, games, sports |
Take the above advertisement as an example, the existing male, game and male, sports request 100 each. The ideal pair has a maximum payoff of $110 and a total budget cost of only a few dollars according to the Balance algorithm. When the male, the game of the 100 requests arrived first, B ads will be used up first, when the male, sports’ 100 requests arrived there will still be no ads to consume.
What is the applicable scenario of the Balance algorithm? Let’s consider this problem with the limit method.
Hypothesis 1: If AD A and AD B bid $1000 and $1, respectively (CPC)
Obviously, AD A has the greater advantages and should be shown first. Based on the previous example, the Balance algorithm is unable to solve this extreme scenario, while the Greedy algorithm takes care of both the platform’s interests and the advertiser’s eagerness to spend.
Hypothesis 2: If all advertising bids are $10 each (CPC)
The Greedy algorithm is concerned with bidding, while the Balance algorithm is concerned only with budgeting. It is easy to know from the control variable method that the Balance algorithm is designed for this kind of scenario.
Summary: Based on the previous assumptions and the description in the paper, we conclude the following conclusions:
- The Balance algorithm is more suitable for scenarios where advertising bids are close
- The Greedy algorithm is more suitable for scenarios where there are large differences in advertising bids
MSVV algorithm
Only kids take choices. We adults all take them. The Balance algorithm and Greedy algorithm have their own advantages and disadvantages and are applicable to different scenarios. Is there an algorithm that can combine the advantages of both? This is the idea of MSVV algorithm.
To describe the new algorithm more clearly, some basic definitions are given:
- Consumption ratio:
'Consumption/Total budget'And remember
. The total budget is set by the advertiser and can be adjusted dynamically. - Weighing function: Ψ (nu) = 1 – e (nu – 1) \ Psi (\ upsilon) = 1 – e ^ {(\ upsilon – 1)} Ψ (nu) = 1 – e (nu – 1)
- Scaling bid: Bid ∗ ψ (υ) bid * \Psi(\upsilon) bid ∗ ψ (υ)
The algorithm is described as follows:
{continue} else {select an AD with the maximum 'zoom bid' value}Copy the codeThe above tradeoff function is a monotonically decreasing function with the υ\upsilonυ range [0,1]. The distribution diagram of the tradeoff function is as follows:
When all advertising bids are equal, the MSVV algorithm just degenerates into the Balance algorithm because the tradeoff function is a monotonically decreasing function. On the other hand, if the bidding differences are very large, the MSVV algorithm does not change the order of the bids in most cases, at which point MSVV behaves more like the Greedy algorithm. Consider the more extreme case, where all advertising budgets are infinite, the MSVV algorithm simply degenerates into the Greedy algorithm, since the tradeoff function is the constant 1− 1E1 – {\ FRAc 1e}1− E1.
To verify the adaptability of the MSVV algorithm, let’s look at the following code:
type ad struct {
cost float64
total float64
price float64
}
func scaled(price, cost, total float64) float64 {
return price * (1.0 - math.Pow(math.E, cost/total- 1))}func main(a) {
a := &ad{0.100.1}
b := &ad{0.100.0.01}
// When the game arrives, a and B consume at the same time
for i := 0; i < 100; i++ {
aCp := scaled(a.price, a.cost, a.total)
bCp := scaled(b.price, b.cost, b.total)
if a.cost >= a.total || b.cost >= b.total {
break
}
if aCp >= bCp {
a.cost += a.price
} else {
b.cost += b.price
}
}
// Only B can be consumed when the simulated 'male' movement arrives
for i := 0; i < 100; i++ {
if b.cost >= b.total {
break
}
b.cost += b.price
}
fmt.Println(a.cost + b.cost)
}
Copy the codeMSVV algorithm gains 116.5 and 101 respectively in the previous extreme example, and its overall performance basically meets expectations.
conclusion
Now, looking back at the previous problem, the Balance algorithm can consume too much and slow down the exposure time. The Greedy algorithm is better from an AD platform revenue perspective. Then the MSVV algorithm combining the advantages of the two is a necessary tool for each advertising platform to travel at home.
Xu is also new to online advertising, and is trying to store knowledge for sustainable development in the future. If there are incorrect places in the article, readers are welcome to correct and exchange.