Combining Powers of Two Predictors in Optimizing real-time Bidding Strategy under Constrained Budget

1 background

The real-time bidding process is shown below

In ORTB bidding strategy, the probability of winning w(b(θ(x)) w(b(\theta(x)))w(b(θ(x))) depends on θ\theta theta(click rate), that is, if the click rate is estimated incorrectly, the probability of winning is estimated incorrectly, which leads to an inaccurate bid. Therefore, the work of this paper is: Two models were used to bid, one to estimate CTR and one to estimate winning price (WP).

2 methods

2.1 Problem Definition

ψ:{x⃗1,x⃗2… , x ⃗ n} \ psi: \ left \ {\ vec {x} _ {1}, \ vec {x} _ {2}, \ ldots, \ vec {x} _ {n} \} \ right bits: {x x 1, 2,… , n}, x features represented by x ⃗ I ∣ 1 I n \ vec or less or less {x} _ {I} \ | 1 leq I \ leq nx I ∣ 1 I n or less, or less each time the campaign budget for B. There are problems with bidding

  • Whether to bid on x⃗ I \vec{x}_{I} xi
  • If we bid, what’s the bid value? I (x ⃗ I) = 1 I (\ vec {x} _ {I}) = 1 (I) (I) x = 1 for success, I (x ⃗ I) = 0 I (\ vec {x} _ {I}) = 0 I (I) x = 0 means for failure
  • The winning price is P(x⃗ I)P(\vec{x}_{I})P(x I), that is, for the winning price to be paid, under the generalized second-highest pricing mechanism, the winning price is less than the bidding price

So the bidding strategy problem is

For each bid activity x ⃗ I \ vec {x} _ {I} x, I bid for b (x ⃗ I) b (\ vec {x} _ {I}) b (I) x, maximize the ∑ ni (x ⃗ I) I = 1 \ sum_ {I = 1} ^ {n} I (\ vec {x} _ {I}) ni (I) x ∑ I = 1, Constraints for ∑ np (x ⃗ I) I = 1 B or less \ sum_ {I = 1} ^ {n} P (\ vec {x} _ {I}) \ leq B ∑ np (x I) I = 1 B or less.

2.2 PERF algorithm

PERF algorithm is an ideal algorithm, assuming that CTR and WPare are 100% accurate, which can make the most efficient use of the budget.

Phase 1 (model training)

Input:

  • Exposure of the log

Output:

  • I: CTR estimation model
  • P: Winning price prediction model
  • ω : Probability density function of click-earned price for advertising series (conforming to lognormal distribution)
  • NtrN_{tr}Ntr; NteN_{te}Nte: number of hits on training and test sets

Phase 2 (online bidding)

Input:

  • B: Campaign budget
  • X ⃗ I \vec{x}_{I}x I: Characteristics of bidding

State variables:

  • BcurB_{cur}Bcur: current budget with an initial value of B

Output:

  • B (x ⃗ I) b (\ vec {x} _ {I}) b: (I) x x ⃗ I \ vec {x} _ {I} the value of x I

Process:

  1. Pboundp_ {bound}pbound by budget constraint ∫0βpNte ω (p)dp=B\int_{0}^{\beta} p N_{t e} \Omega(p) \mathrm{d} p=B∫0βpNte ω (p)dp=B
  2. For input x⃗ I \vec{x}_{I}x I, if I(x⃗ I)=1I(\vec{x}_{I}) =1I(x I)=1 (this step should be determined directly from the available data), go to step 3; If I(x⃗ I)=0I(\vec{x}_{I}) =0I(x I)=0, continue to bid
  3. Use P(x⃗ I)P(\vec{x}_{I})P(x I) to find the winning price
  4. If P (x ⃗ I) < BP (\ vec {x} _ {I}) BP (I) x < < B and P (x ⃗ I) < pboundP (\ vec {x} _ {I}) < p_ {bound} P (I) x < pbound, Return pbound+δp_{bound}+\deltapbound+δ, where δ\deltaδ can be a minimum unit of currency, jump to 5; Otherwise jump to 2
  5. If the price pWP (x ⃗ I) + delta pWP (\ vec {x} _ {I}) + \ deltapWP (I) x + delta won the bid, Update the budget Bcur = Bcur – P (x ⃗ I) B_ {cur} = B_ {cur} – P (\ vec {x} _ {I}) Bcur = Bcur – P (I) x. If BcurB_{cur}Bcur becomes 0, bidding stops, otherwise jumps to 2

2.3 PRUD algorithm

Phase 1 (model training)

Input:

  • Exposure of the log

Output:

  • PCTRpCTRpCTR: CTR estimate
  • PWpWpW: Beat price estimates
  • ρcut\rho_{cut}ρcut: bidding efficiency cut-off value, calculation method is: Rho (x ⃗ I) = pCTR (x ⃗ I)/pWP (x ⃗ I) \ rho (\ vec {x} _ {I}) = pCTR (\ vec {x} _ {I})/pWP (\ vec {x} _ {I}) rho (I) x = pCTR (I) x/pWP (x I), When pCTR (x ⃗ I) pCTR (\ vec {x} _ {I}) pCTR (I) x is low, pWP (x ⃗ I) pWP (\ vec {x} _ {I}) pWP (I) x is high, the high conversion rate low bid, rho (x ⃗ I) \ rho (\ vec {x} _ {I}) rho (I) x will be lower, Filter these cases

Phase 2 (online bidding)

Input:

  • B: Campaign budget
  • X ⃗ I \vec{x}_{I}x I: Characteristics of bidding

State variables:

  • BcurB_{cur}Bcur: current budget with an initial value of B

Output:

  • B (x ⃗ I) b (\ vec {x} _ {I}) b: (I) x x ⃗ I \ vec {x} _ {I} the value of x I

Process:

  1. For x⃗ I \vec{x}_{I}x I, check for ρ(x⃗ I)≥ρcut\rho(\vec{x}_{I}) \geq \rho_{cut}ρ(x I)≥ρcut
  2. If the pWP (x ⃗ I) < BcurpWP (\ vec {x} _ {I}) < B_ {cur} pWP (I) x < Bcur, return pWP (x ⃗ I) + delta pWP (\ vec {x} _ {I}) + \ deltapWP (I) x + delta, skip to step 3, otherwise it returns 0, Skip to step 1
  3. If the price pWP (x ⃗ I) + delta pWP (\ vec {x} _ {I}) + \ deltapWP (I) x + delta win the bid. Update the budget Bcur = Bcur – P (x ⃗ I) B_ {cur} = B_ {cur} – P (\ vec {x} _ {I}) Bcur = Bcur – P (I) x. If BcurB_{cur}Bcur becomes 0, stop bidding.

Experiment 3

The experimental results are shown in the figure below

Let’s look at the left hand side

  • Season2 is better than season for CTR estimates
  • There is a large margin of error for the winning price estimates, but RMSE

It can be seen that the predicted mean value of WP is less than the real mean value of WP, so the forecast WP is corrected as follows. A deviation is added so that the predicted winning price is greater than the real winning price in 95% of the data. This deviation can be solved by training data. In online bidding, the optimal ρcut\rho_{cut}ρcut is selected.

PWP ⃗ (x) + L > P (x) ⃗ P W P (\ vec {x}) > P + L (\ vec {x}) \ quadpWP > P (x) (x) + L for 95 \ % 95% and 95% of {x ⃗ ∣ I ⃗ (x) = 1} \ quad \ {\ vec {x} \ mids I (\ vec {x}) = 1 \} {x ∣ I (x) = 1}

Define a metric that is the number of clicks generated by ORTB or PRUB divided by the number of clicks generated by PERF.


C R = # C l i c k O R T B ∣ P R U D # C l i c k P E R F CR = \frac{\#Click_{ORTB|PRUD}}{\#Click_{PERF}}

Because PERF is the desired result, CR<1. The experimental results are as follows. PRUD has better effect than ORTB in most cases (similar conclusions can also be drawn in Table 1)

The eCPC comparison results of the two models are as follows: PRUD’s eCPC is lower than ORTB’s eCPC, that is, more effective (I think it is because of the bidding efficiency).

4 discuss

Compared with ORTB, the PRUD method proposed in this paper has a significant improvement effect on CLICK, and eCPC is also relatively good, with simple thinking and high feasibility.

Points worth reference are:

  • Used for the efficiency of rho (x ⃗ I) = pCTR (x ⃗ I)/pWP (x ⃗ I) \ rho (\ vec {x} _ {I}) = pCTR (\ vec {x} _ {I})/pWP (\ vec {x} _ {I}) rho (I) x = pCTR (I) x/pWP (x I) Filter invalid bids
  • Two models were used to predict CTR and winning price respectively

Questions are:

  • Validity of winning price prediction, skeptical of experimental results (the mean of predicted winning price and actual winning price is a little bit different)

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign