Optimal Bidding Strategy for Brand Advertising

1 Introduction

Background andMotivation Real-time bidding is themost successful framework for online advertising [Zeff and Aronson, 1999]. In this framework, each impression (a user's view of a website) is instantly sold in an auction, and each advertiser bids for the impression to display his advertisement to the user. An important advantage of this framework is the personalization: it can optimize advertisements for each user by selecting impressions. This reduces ineffective advertisements with their wasteful cost, and increases the effect of advertisements; thereby it increases the advertising revenue.

The fundamental optimization problem in real-time bidding is the bid optimization problem. The task of the bid optimization problem is to find the optimal bid price for each impression to maximize the advertising effect under limited budget. Since we do not know the winnable price and the advertising effect in advance to the bidding, the problem is an optimization problem with uncertainty. This problem has been studied in various setting, e.g., [Zhou et al., 2008; Mehta et al., 2007; Chakrabarti and Kale, 2015; Buchbinder and Naor, 2009].

In this study, we consider a bid optimization problem for brand advertising [Hansen and Christensen, 2003]. Brand advertising aims at increasing the awareness of the companies or products, as opposed to the direct response advertising, which aims at selling specific products. As indicated by marketing studies, consumers' purchasing behaviors are influenced by their brand knowledge and familiarity [Chen and He, 2003; Park and Stoel, 2005]. Therefore, brand advertising is considered a useful tool to increase future revenues.

Brand advertising is studied in the area of economics [De Mooij and Hofstede, 2010], marketing [Randall, 2000; Zielske, 1959], and psychology [Aaker and Biel, 2013]. However, to the best of our knowledge, there are no existing studies in the area of online (computational) advertising. This may be because evaluating the effect of brand advertising is difficult since it requires conducting questionnaire surveys, or analyzing search engine queries and access logs; however, these cannot be obtained immediately and are difficult to quantify; therefore, they cannot be used in real-time bidding systems. On the other hand, brand advertising appears highly compatible with online advertising because it can be personalized for each user. For example, if a user is already exposed to an advertisement with a high frequency, it may be better to limit the user's level of exposure since the user may already recall the advertisement, and to show the advertisement to other users. Also, if a user is exposed to an advertisement with a low frequency, it may be good to show more advertisement to the user to make a strong retention about the advertisement.

To achieve large advertising effects, we have to balance the above two factors (i.e., broad users vs strong retentions). However, it is very difficult to find the optimal balance by hand. Therefore, we have to formulate user's memory retention by a mathematical model, and propose an online algorithm algorithm for brand advertising that automatically balance the factors.

Contributions In this study, we make the following theoretical contributions:

• We propose a new objective function to represent the brand advertising effect. This function represents the users' forgetting curve (memory retention over time), which is consistent with the existing studies in psychology [Ebbinghaus, 1913]. Moreover, our function is a monotone submodular function 1 , which admits efficient optimization algorithms in various situations (Section 2).
• We propose an algorithm for the bid optimization problem under the second price mechanism 2 ,which is commonly used in real-world systems. We first suppose that the winnable price of each impression is known. In this case, the problem is formulated as an online knapsack constrained submodular maximization problem, and we derive an algorithm for this case with a competitive ratio 3 of (2 - L/U + O(ϵ)) log(Ue/L), where e is the base of the natural logarithm, ϵ is the capacity ratio, and U and L are the lower and upper bounds of marginal efficiency, respectively. Then, we convert the algorithm for the case that the winnable price of each impression is unknown by using the technique introduced in [Zhou et al., 2008] (Section 3).

We also made the following experimental contributions:

• We conducted a questionnaire survey for the awareness of an advertisement. The result shows the submodularity of the forgetting curve in a real-world dataset; hence it supports the validity of the proposed objective function.
• We conducted a numerical experiment to evaluate the proposed algorithm on a real-world dataset collected from our real-time bidding system. We observed that the proposed algorithm has an issue in practical use that it exhausted the budget too early (Section 4).

2 ProblemFormulation

2.1 General Framework

We consider an advertiser's optimization problem. Let V = {1, . . . , n} be a sequence of impressions that arrives in a oneby-one manner in an online context. Each impression j ∈ V has arriving time tj, target user uj, and some features, e.g., ip address, browser, webpage, etc. When impression j arrives, the advertiser must determine the bid price ˜ cj ∈ R for this impression in real-time under the condition that the total spent budget is at most his budget B ∈ R. We assume the second price mechanism. Then, an advertiser wins the auction if his bid price is greater than the highest bid cj ∈ R made by the other advertisers, and his payment is cj . If he loses the auction, he does not spend any money.

1 A set function f : 2V → R is said to be monotone if for any X ⊆ Y , f(X) ≤ f(Y ). f is said to be submodular if for any j ∈ V and X ⊆ Y ⊆ V \ {j}, f(j|X) ≥ f(j|Y ) where f(j|X) = f(X∪{j})-f(X) is termed as the marginal contribution of j at X.

2 The second price mechanism is an auction mechanism such that the highest bidder wins the auction and pays the second-highest bid price.

3 Algorithm ALG has competitive ratio of α if for any input sequence σ, OPT(σ) ≤ αALG(σ) where OPT is an optimal offline algorithm.

Let f : 2V → R be a function such that f(X) represents the advertising effect when the advertiser presents the advertisements for impressions X ⊆ V . We only consider a non-stochastic advertising effect, e.g., an expected value of something. Then, the problem is mathematically formulated as follows:

where c(X) = ∑j∈X cj .

2.2 Objective Function

The primary consideration in the problem (2.1) is what objective function f should be used. For brand advertising, f should correspond to the expected number of individuals who recall the advertisement, integrated over time. By ignoring the interaction between users, we obtain the following formula:

where Xu denotes the subset of X associated with user u, and gu(Xu; t) denotes the probability that user u recalls the advertisement at time t when the advertisements are displayed for impressions j ∈ Xu. 4

In cognitive psychology, the function of memory retention is referred to as the forgetting curve. [Ebbinghaus, 1913] observed in his seminal work that a forgetting curve has the following properties:

1. A forgetting curve decreases rapidly (rapid decreasing property).
2. The decline of a forgetting curve slows down due to repetition (repetition effect).

Now these are well-established facts in cognitive psychology [Baddeley, 1999]. However, a theoretical model that is unanimously agreed upon by several researchers does not exist [Averell and Heathcote, 2011]. Moreover, existing models in cognitive psychology [Greene, 1989; Rawson and Dunlosky, 2013] are not suited for use in mathematical and algorithmic analysis. Therefore, we introduce a new mathematical model of the forgetting curve, which captures the above two properties and admits an efficient algorithm.

Let pj : R → [0, 1] be an arbitrary rapidly decreasing function 5 , which denotes the forgetting curve of a user when he is exposed to just one advertisement by impression j. Typically, the following Wickelgren's power law [Wickelgren, 1974; Wixted and Carpenter, 2007] can be employed:

4 We can add any kernel function k(t) to the integral as f(X) = ∫ ∞ -∞ g(X; t)k(t)dt to give a weighting to the time.

5 We say that a function p : R → [0, 1] is rapidly decreasing if ∫ ∞ -∞ p(t)dt < ∞

where tj is the arrival time of impression j and λj, βj, and γj are the parameters. The parameters would be determined by the features of the impression j. Then, the forgetting curve for user u when he is exposed to multiple advertisements for impressions Xu is defined as follows:

As shown below, this function captures the repetition effect of the forgetting curve.

The definition of function (2.4) is motivated by study-phase retrieval theory [Greene, 1989]. This assumes that the previous presentations (study-phase) are retrieved later, and this causes the repetition effect of the forgetting curve. Here, (2.4) shows that the probability of recalling the advertisement at time t is the probability of recalling at least one presentation that is shown for impression j ∈ X, which constitutes the same idea as the study-phase retrieval theory.

2.3 Properties of the Objective Function

Psychological Justification First, a simple numerical experiment is performed to see that the function is consistent with the standard findings in cognitive psychology.

Suppose that a user u is exposed to three impressions Xu = {1, 2, 3} at time t1 = 0, t2 = 1/2, and t3 = 1. We set the parameters of power law (2.3) as λj = 1, βj = 1, and γj = 2 for all impressions. Then the corresponding forgetting curve gu(Xu; t) is obtained as Figure 1, which looks similar to the forgetting curve that we can see in psychological literatures [Ebbinghaus, 1913]. This shows that the proposed function captures the two properties of forgetting curves. Specifically, the function successfully captures the repetition effect, i.e., the decline on the second learning is slower than that on the first learning, and consequently decline on the third learning is slower than that on the second learning.

Algorithmic Property From an algorithmic viewpoint, the most important property of our objective function f is monotone and submodular. Therefore, the problem expressed in (2.1) is a kind of online knapsack constrained monotone submodular maximization problem. This allows the construction of an efficient approximation algorithm, which will be presented in Section 3.

Proposition 1. The objective function f : 2V → R that is defined by (2.2) and (2.4) with any integrable functions pj is monotone submodular.

Proof. We use the fact that the sum of monotone submodular functions is also monotone submodular.

First, we fix time t. Then, gu(X; t) = E[min{|X ∩ R|, 1}] where R ⊆ V is a random set in which each element j appears with probability pj(t) and the expectation is with respect to R. Since min{|X ∩ R|, 1} is monotone submodular in X for any R, its expectation, gu, is also monotone submodular in X6 . Since f is obtained by taking the integral of gu over t, it is also monotone submodular.

Function Evaluation Evaluating the marginal contribution of f is often required to implement an algorithm for the submodular maximization problem. For the proposed objective function (2.2), we have

where u is the user for impression j.

Even for Wickelgren's power law (2.3), the above integral (2.5) cannot be evaluated analytically because it involves the hypergeometric function 2F1. Therefore, numerical integration [Davis and Rabinowitz, 2007] must be employed. If pj(t) is smooth except t = tj , the function f(j|X) has finitely many discontinuities at t = ti for i ∈ Xu and is smooth and rapidly decreasing in each interval. Thus, a standard numerical integrator (e.g., Gauss-Lobatto integrator) works well by splitting the integral into the intervals.

The complexity for evaluating the marginal contribution is O(|Xu|). In a real-world problem, this is not very large because it is inefficient to display the advertisement to the same person very often.

3 Algorithm

In this section, we propose an algorithm for the bid optimization problem. We derive our algorithm in the following two steps. First, we suppose that the winnable price cj is known before making the bid, and derive an algorithm for this case (Section 3.1). Then, we convert the algorithm to the case that the winnable price cj is unknown (Section 3.2).

3.1 Online Knapsack ConstrainedMonotone Submodular Maximization Problem

Suppose that the winnable price cj (the highest bid made by the other advertisers) is known before making a bid. Then, Algorithm 1 Algorithm for online knapsack constrained monotone submodular maximization problem.

6 In fact, the submodularity of gu(X; t) is immediately obtained from the observation that it has the same form of the function used in the budget allocation problem [Alon et al., 2012], which is known to be submodular.

since we can win the auction by bidding marginally greater than cj , we can fix our bidding price to 0 (ignore the impression) or cj (take the impression), and hence the problem is reduced to an online knapsack constrained monotone submodular maximization problem:

where the impressions j ∈ V arrive in a one-by-one manner. Because the problem involves the standard online knapsack problem, some assumptions are necessary to arrive at a provable competitive ratio [Marchetti-Spaccamela and Vercellis, 1995]. Here, we assume the following conditions:

1. The price of each impression is very small compared to the knapsack capacity, i.e., cj/B ≤ ϵ for all j ∈ V .
2. The lower and upper bounds of marginal efficiency are known, i.e., U and L such that for any j ∈ V and X ⊆ V \ {j}, L ≤ (f(j|X))/cj ≤ U.

The first condition is usually satisfied in real-time bidding setting. The second condition is "approximately" satisfied by learning the bounds from a training set in practice, but it may cause some difficulty in theory.

The proposed algorithm is shown as Algorithm 1. This is a "submodular version" of the algorithm for the online knapsack problem proposed by Zhou et al. [Zhou et al., 2008]. Let

be a threshold function where z denotes the fraction of the current budget, and e is the base of the natural logarithm. The algorithm bids impression j if its marginal efficiency f(j|X)/cj exceeds the current thresholdΨ(z). This algorithm has the following theoretical guarantee.

Theorem 2. Given assumptions (3.2), Algorithm 1 has a competitive ratio of (1 + κ + O(ϵ)) log(Ue/L), where κ ∈ [0, 1] is the curvature of f 7 .

Proof. This is obtained by carefully combining submodularity and curvature into the proof of the linear case [Zhou et al., 2008]. For self-completeness, we give a full proof. First, we modify the threshold function by

7 A submodular function f : 2V → R has curvature κ ∈ [0, 1] if for any j ∈ V and X ∈ V \ {j}, f(j|X) ≥ (1 - κ)f(j).

This does not affect anything to the algorithm. Let zL be such that Ψ(zL) = L. This is given by

The algorithm bids all the impression when z < zL.

Fix an input sequence V . Let X and X∗ be the obtained solution and the optimal solution, respectively. Note that all the impressions in X and X∗ are winnable. Let Xj and (X∗ ∪ X)j denote the subset of X and X∗ ∪ X that arrive before j-th iteration, respectively. Let zj ∈ [0, 1] and Z ∈ [0, 1] be the fraction of the budget filled by the algorithm at j-th iteration and the end of the algorithm.

In general,

Here, each term in the right-hand side is evaluated as follows. For the first term, by telescoping and submodularity,

For the second term, by telescoping, curvature, and submodularity,

Also, by telescoping,

Therefore

Since the algorithm bid j ∈ X, the first term in the numerator (and the denominator) is evaluated as

Also, the third term in the denominator is evaluated as

Similarly, since the algorithm did not bid j ∈ X∗ \ X, and the algorithm never rejects impressions due to the shortage of Algorithm 2 Algorithm for bid optimization problem.

1: X = ∅ 2: for j = 1, 2, . . . do 3: Bid ˜ cj = f(j|X)/Ψ(c(X)/B) for j-th impression 4: if we won the auction then 5: X ← X ∪ {j} 6: end if 7: end for 8: return X

the budget since Ψ(z) > U if z > 1 - ϵ, the second term is evaluated as∑

Therefore, by monotonicity of fraction, monotonicity of Ψ, and feasibility of X and X∗ ,

where ∆zj denotes the difference between the consecutive zj for j ∈ X, i.e., ∆zj = cj/B. The summation in the denominator is approximated by the integral, and is evaluated as follows:

The theorem is obtained from (3.15) and (3.16).

Under assumptions (3.2) the curvature of f satisfies κ ≤ 1 -L/U. Therefore, the following corollary is obtained by removing κ from Theorem 2.

Corollary 3. Given assumptions (3.2), Algorithm 1 has a competitive ratio of (2 - L/U + O(ϵ)) log(Ue/L).

The competitive ratio in Theorem 2 is optimal if κ = 0 [Zhou et al., 2008]. Note that when κ → 1, we have L/U → 0; therefore the approximation ratio becomes unbounded. The tightness of the competitive ratio for κ ∈ (0, 1) is open.

3.2 Bid Optimization Problem

Under the second price mechanism, the algorithm proposed in the previous section can be converted to the algorithm for the bid optimization problem, i.e., it can be executed without knowing winnable prices. This technique is originally introduced in [Zhou et al., 2008].

Our bid optimization algorithm (Algorithm 2) maintains the impressions X that we made successful bids, and for each arriving impression j, it determines the bid price by f(j|X)/Ψ(c(X)/B). This value can be computed in realtime bidding setting since we know the winnable prices ci for i ∈ X. We prove the following.

Theorem 4. Under the second price mechanism, Algorithm 1 and Algorithm 2 produce the same solution with the same payment.

Proof. Due to the second price mechanism, the payment for impressions does not depend on the bid prices. Thus we only have to show that the impressions obtained by Algorithm 1 and Algorithm 2 are the same.

We prove this by the induction. Consider the step that impression j is arrived. By the induction, so far, Algorithm 1 and Algorithm 2 obtained the same set of impression X. If j satisfy f(j|X) ≥ cjΨ(c(X)/B), Algorithm 1 takes this impression. Also, Algorithm 2 bids ˜ cj = f(j|X)/Ψ(c(X)/B), which is greater than or equal to cj; thus it wins the auction and gets this impression. The same is true for the converse case (f(j|X) < cjΨ(c(X)/B)).

This means that Algorithm 2 perfectly emulates Algorithm 1 without knowing cj; hence, it has the same theoretical guarantees given in Theorem 2 and Corollary 3.

4 Experiments

Numerical experiments were conducted to evaluate the proposed model and algorithm.

All codes were implemented in Python 3.5. For the numerical integration, we use the adaptive Gauss-Lobatto integrator, implemented in scipy.integrate. The program was executed in a standard laptop computer (2.3GHz CPU, 8.0GB Memory).

The datasets used in the experiments are collected by our real-time bidding system. We selected a campaign of brand advertising that has sufficiently many impressions and unique users. Then, we collected bid log data, which is used to evaluate the performance of the algorithm by a numerical simulation. We also conducted a questionnaire survey to justify the our proposed psychological model.

4.1 Model Justification by Questionnaire Survey

A few days after the end of the campaign, a questionnaire survey was conducted electronically through a web survey company. 8 The survey included questions such as "Do you remember this advertisement?." The surveys were returned by 10,000 users, 2,000 of them had watched the advertisement, and 426 of them remembered the advertisement. The fraction of the returned survey by the latter users with the answer "YES" was considered to denote awareness.

Points in Figure 2 shows the relationship between awareness and the time elapsed since the last time when the users watch the advertisement. This can be interpreted as a forgetting curve for brand advertising. By manually fitting (2.3) to the points in Figure 2, we obtain the following formula:

8 Each respondent is a member of the web survey company. By using the cookies, the company can identify the number of times each respondent was exposed to the advertisement. Note that the members agree to fill in the questionnaire for the purpose of research; thus there are no ethical issue.

which is presented as the curve in Figure 2.

Figure 3 shows the relationship between the number of times the users see the advertisements and their awareness. A three-point moving average was performed for smoothing. This indicates the diminishing return property; therefore modeling by a submodular function would be reasonable.

4.2 Evaluation of Bidding Algorithm

Dataset Description To evaluate the performance of the algorithm in a real-world setting, the bidding log data on two days (November 12 and 13, 2016) of the campaign are collected from our system. The first day's data, which comprises of 1,440,641 impressions with 731,029 unique users, is used for a training set and the second day's data, which comprises of 1,455,002 impressions with 735,560 unique users (including the users who appeared in the first day's data) is used for an evaluation set. Each impression is marked with its arrival time, user id, and winnable price. 9

The distribution of the number of presented advertisements related to the users, which follows a power-law distribution (Figure 4). Specifically, there is a user who had too many presentations. Therefore the bid optimization is promising for this data.

Experimental Setting For the purpose of the experiments, we determined the shape of the forgetting curve. We used the same forgetting curve function for all users as

where p′0 is a function estimated in (4.1) where the constant term is ignored since the constant term can be understood as the fraction of people who already know the advertisement.

This setting means that we ignored the difference of users, which is reasonable because we do not have sufficiently many dataset to learn the difference of the users. In addition, it is also reasonable in psychological viewpoint because there are no significant difference in the memory retention ability among the individuals [Ebbinghaus, 1913].

Algorithms We implemented three online algorithms (Proposed, FixedBid, and Random) and one offline algorithm (Offline).

• Proposed is the proposed algorithm with the parameters estimated in Section 4.1. The lower and upper bounds L and U were optimized by the training set.

9 Since we need the winnable prices of all impressions to evaluate the performance of the algorithms, we only use the impressions that are obtained by the successful bids. Our system used the fixed price bidding strategy; therefore the all winnable prices are at most the fixed price. This makes dataset biased.

• FixedBid is the algorithm that always bids a fixed price. The fixed price is optimized by the training set. Note that this is a baseline method, which is implemented in our current system.
• Random is the algorithm that bids randomly for each impression. Again, the probability is determined for spending the budget. Note that this is also implemented in our current system.
• Offline is the offline greedy algorithm for the knapsack constrained monotone submodular maximization problem [Khuller et al., 1999], which has an approximation ratio of 1 - 1/e - O(ϵ). Because this algorithm determines the bidding strategy by taking future impressions into account, this will give an upper-bound of the performance.

Result The performance (obtained advertising effect) of these algorithms are summarized in Table 1. The proposed algorithm has 1.4 times larger advertising effect (i.e., f(X)) than the two baseline online algorithms. This is not very large, but a solid improvement from the baseline algorithms. On the other hand, the proposed algorithm has a room to improve the practical performance since the offline greedy algorithm attains 2 times larger advertising effect.

Figure 5 shows the total amount of memory retentions, g(X; t), in each time, obtained by the algorithms. Here, the area under the curve is the objective value. From this figure, we can point out that the proposed algorithm exhausted the budget in early stage, compared with other strategies. Therefore, it overlooked the efficient impression in later stage. The reason of this phenomena is that the algorithm is designed to have a guaranteed competitive ratio, i.e., it must have a provable objective value even if the input is immediately terminated in early stage. To overcome this issue, we may need some (possibly stochastic) information about future impressions.

5 RelatedWork

Bid Optimization Problem The bid optimization problem is a very actively studied problem in real-time bidding, and several formulations and algorithms have been proposed [Zhou et al., 2008; Mehta et al., 2007; Chakrabarti and Kale, 2015; Buchbinder and Naor, 2009; Cai et al., 2017; Zhang et al., 2016; 2014]. However, as mentioned in Section 1, there is a paucity of studies that focus on brand advertising. Mathematically, the existing studies formulated the advertising effect as a sum of effects of the impressions; thus they ignored the correlation effect between the impressions. In brand advertising, this correlation is important due to the repetition effect of the forgetting curve; thus we need a new formulation.

Figure 3: Histogram of the number of advertisements presented.

Figure 5: Forgetting curves g(X; t) of each algorithm. The campaign is stopped at t = 1.

Online Knapsack Constrained Monotone Submodular Maximization We formulated the bid optimization problem as an online knapsack constrained monotone submodular maximization problem and proposed the algorithm. Our algorithm is based on the algorithm for the online knapsack problem proposed by [Zhou et al., 2008] since it does not assume anything about the arrival order of items. This is an important property for us since the impressions have natural ordering according to the arrival time; hence, we cannot use the algorithms that have better approximation guarantee under the random arrival assumption (e.g., [Lueker, 1998] and [Babaioff et al., 2007]).

To best of our knowledge, there is no algorithm that can be applied to the present formulation of bid optimization problem. Specifically, it is not possible to apply the algorithms for the knapsack constraint submodular secretary problem [Bateni et al., 2010; Kesselheim and T¨onnis, 2016] because they assume the arrival order of items is random. Also, it is not possible to apply the algorithm for streaming knapsack constrained submodular maximization problem [Kumar et al., 2015] because the algorithm keeps more than one solutions, which is impossible to use in real-time bidding systems.

Forgetting Curves For the function modeling, in cognitive psychology, following the seminal study by Ebbinghaus [Ebbinghaus, 1913], several models for the forgetting curve were proposed [Greene, 1989; McClelland et al., 1995; Murre et al., 2013]. However, most of the models focused on understanding the "actual mechanism" of human memory. The present study is the first study that formulates memory retention as a computationally tractable model.

6 Conclusion

In this study, we proposed a new formulation of the bid optimization problem for brand advertising. We introduced a psychologically reasonable and computationally tractable objective function. Then we derive a bid optimization algorithm with a provable competitive ratio. The validity of our objective function is justified by the questionnaire survey, and the performance of the algorithm is evaluated by the bid log data collected from a real time bidding system.

There are several directions for future research. First, from a psychological viewpoint, it is important to propose a more realistic (and computationally tractable) model for the forgetting curve. Second, from a theoretical viewpoint, future studies could develop an algorithm that achieves better competitive ratio or prove a matching lower bound. Third, from a practical viewpoint, as shown in Section 4, the proposed algorithm has the potential to improve performance by using the information of remaining time. This may require another formulation of the problem, because the competitive ratio guarantees the worst case input, which can terminate immediately. Finally, apart from computational advertising, it is interesting to develop applications of the proposed objective function and algorithm in other areas such as a learning system for education.

Acknowledgements

The authors thank the reviewers for their helpful comments. This work was supported by JSPS KAKENHI Grant Number 16K16011.