Improvements in Practical Aspects of Optimally Scheduling Web Advertising
Atsuyoshi Nakamura
NEC Internet Systems Research Laboratories
411 Miyazaki, Miyamaeku
Kawasaki 2168555 JAPAN
atsu@ccm.cl.nec.co.jp
WWW2002, May 711, 2002, Honolulu, Hawaii, USA.
ACM 1581134495/02/0005.
Abstract:
We addressed two issues concerning the practical aspects of optimally scheduling web advertising proposed by Langheinrich et al. [5], which scheduling maximizes the total number of clickthroughs for all banner advertisements. One is the problem of multiimpressions in which two or more banner ads are impressed at the same time. The other is inventory management, which is important in order to prevent overselling and maximize revenue. We propose efficient methods which deal with these two issues.
Categories and Subject Descripters:
C.3[Computer Systems
Organization]:Specialpurpose and Applicationbased Systems
I.2[Computing Methodologies]Artificial Intelligence
I.2.8[Artificial Intelligence]Problem Solving, Control Methods, and
Search  Scheduling
General Terms:
Algorithms, Management, Design
Keywords:
Online Advertisement, WorldWide Web, Electronic Commerce, Optimization, Inventory Management
1. Introduction
The idea of optimal scheduling of web ads so as to maximize the number of clickthroughs was proposed by Langheinrich et al. [5]. They reduce the problem of maximizing the number of clickthroughs to a transportation problem, a kind of linear programming (LP) problem, which is known to be one that can be solved efficiently by making use of special features of the problem.
For this LP model of web advertising, some proposals to improve the method were made by Abe and Nakamura [1] and Tomlin [6]. Abe and Nakamura studied adaptive methods of estimating clickthrough rates, which is very important especially in the initial phase. They also studied clustering of target attribute values, which helps reduce the dimensionality. Tomlin pointed out ``overtargeted'' solutions of the LP model, and proposed an entropy model that incorporates a form of randomization.
The effectiveness of the LP model has been demonstrated not only in largescale simulation experiments [5,1] but also in an experiment using a web site opened to the public [3].
In this paper, we describe our study of two practical aspects of optimallyscheduled web advertising using the LP model. One is how to deal with a multiimpressions in which two or more banner ads are impressed at the same time. Most of us are familiar with web pages on which multiple banner ads are displayed. What should be considered is that all the banner ads displayed on a web page at the same time must be distinct, but the same ads can be selected if we select ads randomly according to display probabilities scheduled in the LP model. In one selection of a set of ads on a web page, our solution makes use of an ad queue to which an ad is added when it is selected more than once through the display probabilities. In the selection of the next set, we first select ads from the queue and the rest through the display probabilities. Note that, if no more than three ad banners are displayed on a page, any display probability must be at most 1/3 so as not to cause queue overflow. Thus, when we calculate display probabilities, such constraints must be taken.
The other aspect we studied is inventory management. Overselling causes no solution for the LP problem. In order to ensure solution existence, it is important not to oversell impressions to advertisers. What makes this difficult is the constraints that advertisers specify. For example, consider a case where one advertiser requests that his ad be displayed on a sports page only while another advertiser requests that his ad be displayed in the afternoon only. Note that here page views of a sports page in the afternoon satisfy the both constraints. In this case, to check whether 1000impressionselling of the sports page causes overselling or not, we must also consider impressions sold for the afternoon constraint. Of course, this can be checked by solving the LP problem and determining whether solutions exist or not. Its problem, however, is that we cannot grasp how many impressions remain for the sportspage constraint. To address this issue, we propose a method of calculating the number of remaining sellable impressions, which is formalized as another LP problem.
This paper is organized as follows. In the next section, we review the LP model proposed by Langheinrich et al. Then, we explain our solutions for the multiimpression issue (Sec. 3) and inventory management (Sec. 4). Finally, we conclude with some relevant remarks.
2. LP model
In this section, we review the LP model proposed by Langheinrich et al. [5] and explain the idea of introducing `degree of importance' to settle a certain problem. In their original paper, they considered only keyworddriven and pagedriven ads. For any attribute, however, we can also consider attributedriven ads. Furthermore, we can consider attributesetdriven ads for any attribute set. So, here, we consider a fixed set of attributes such as the set of `time of day' and `page category'.
Before describing the formalization, we first show an example which helps to illustrate the problem and the need for an LP solution. Assume that the accurately estimated numbers of page views for combinations of attribute values (afternoon, sports), (afternoon, not sports), (not afternoon, sports) and (not afternoon, not sports) are 10,000, 10,000, 5,000 and 50,00, respectively. Also assume that there are three ads for each of which 10,000 impressions have been promised, and that the accurately estimated clickthrough rates of these ads for the combinations of attribute values are as shown in Table 1.

Table 1: Case that the local strategy fails
Consider the local strategy that selects an ad with the highest clickthough rate among the ads whose promised number of impressions has not been achieved yet. We can easily see that this local strategy, which many people seem to think is effective, does not work in the above case as follows. Assume that page views for all combinations of attribute values occur randomly^{1}. The local strategy always selects ad 1 for the first 10,000 page views, ad 2 for the second 10,000 page views and ad 3 for the last 10,000 page views, because (the clickthrough rate of ad 1)>(the clickthrough rate of ad 2)> (the clickthrough rate of ad 3) holds for all combinations of attribute values. As a result, we find that the actual clickthrough rates for ad 1, ad 2 and ad 3 are 2.2%, 1.76...% and 1.33...%, and the total clickthrough rate for all ads is 1.76...%, which is the same rate as one obtained by random selection.
In the above case, according to the optimal display schedule in the LP model, ad 1 is always selected for (afternoon, sports), ad 2 for (afternoon, not sports) and ad 3 otherwise. The total clickthrough rate of this optimal schedule is 2.1% and the actual clickthrough rates for ad 1, ad 2 and ad 3 are 2.2%, 2.1% and 2.0%, respectively.
Now let us describe the formalization. Let i(=1,...,n) denote combinations of attribute values and j(=1,...,m) denote ads. We define k_{i}, h_{j} and c_{i,j} as follows:
The estimation of k_{i} is calculated based on the number of recent page views for combination i of attribute values. Desired display rate h_{i} is calculated from the contracted number of impressions by subtracting the number of actual impressions so far and considering the remaining contracted period. The estimation of c_{i,j} is calculated based on the recent clickthrough rate for combination i of attribute values and ad j.
Let d_{i,j} denote the display probability of ad j for combination i of attribute values. The problem we have to solve is the following Problem 1.
Maximize
(1) 
under the conditions
=  (2)  
=  (3)  
d_{i,j}  (4) 
Problem 1 is a ``transportation problem'' (see e.g. [4]) and efficient algorithms (see e.g. [2]) for this problem are known. In this model, constraints specified by advertisers are easily incorporated. Assume that ad j_{0} is NOT allowed to be displayed for combination i_{0} of attribute values by a contract with an advertiser. Then, you incorporate this constraint into Problem 1 by considering pair only. Another approach is to set to 1, which prevents the problem from having no solution. (See [5].)
One of the problems in the above model is that the optimal solution of Problem 1 maximizes `total' clickthrough rate for `all' ads. This means that some ads may have to put up with low clickthrough rate in order to obtain high total clickthrough rate. Consider the two ads for each of which 10,000 impressions have been promised. Assume that the accurately estimated clickthrough rates (%) of these ads for combination 1 and 2 of attribute values are as shown in the following table.
ad 1  ad 2  
combination 1 of attribute values  4.0  2.5 
combination 2 of attribute values  2.0  1.0 
Then, the optimal solution^{2} is the one that always displays ad 1 for combination 1 and always displays ad 2 for combination 2. By this solution, ad 1 has high clickthrough rate 4.0% while ad 2 put up with low clickthrough rate 1.0. This is a problem if the advertiser of ad 2 is more important than the advertiser of ad 1. This problem can be settled to some extent by introducing `degree of importance' g_{j}>0 for each ad j. The default value of g_{j} is 1.0, and the greater the value is, the more important ad j is. A modification of objective function (1) incorporating degree of importance is
(5) 
If degrees of importance for ad 1 and ad 2 are 1.0 and 2.0, respectively, the optimal solution for the above example is the one that always displays ad 2 for combination 1 and always displays ad 1 for combination 2. This decreases the clickthrough rate of ad 1 from 4.0 to 2.0, but increases the one of ad 2, which is supposed to be more important than the one of ad 1, from 1.0 to 2.5. In practical operation, if you find that a certain ad of an important advertiser has low clickthrough rate after a part of the contract period has passed, you can improve the clickthrough rate by increasing degree of importance for the ad.
3. Multiimpressions
Figure 1: Example of multiimpressions
In this section, we explain our method of realizing multiimpressions while maintaining the scheduled display probabilities.
Figure 1 is an example of multiimpressions, where two ad banners are seen at the top of a page displayed on a web browser. One important thing to note here is that the selected two ads must be distinct.
Assume that we want to select two different ads according to the following display probabilities.
ad 1  ad 2  ad 3 
0.5  0.4  0.1 
Consider the method of selecting ads according to the probability distribution restricted to ads that have not been selected yet. In the above example, the first one is selected from the three ads according to the probabilities above, and if the first one is ad 1, then the second one is selected from the set of ad 2 and ad 3 according to the probability 0.8 and probability 0.2, respectively, which are calculated from the above probabilities by restricting to ad 2 and ad 3 and normalizing. It can be easily verified that, when two ads are selected using this method, the display proportion of ad 1, ad 2 and ad 3 is 20:19:6, which is different from the desired proportion 5:4:1. Thus, in our solution, we do not restrict the probability distribution but append the ads which have already been selected to a queue and select from the queue later. A detailed description of our selection algorithm ADSelect is shown in Figure 2.

Figure 2: Ad selection algorithm for multiimpressions
Function ADSelect uses one queue for each combination of attribute values. Given a requested number N of ads and the combination i of attribute values, ADSelect returns set S of N different ads according to a scheduled probability distribution for combination i. ADSelect first selects as many different ads from the queue as possible (pop(i)), and then selects according to the scheduled probability distribution (select(i)). If selected ad f has already been selected (), ADSelect appends it to the queue (append(i,f)). The algorithm repeats the selection until selected set S of ads contains the requested number of ads.
There is one thing that must be borne in mind, however. We have to determine the scheduled display probabilities so as not to exceed 1/N, where N is the number of ads displayed on the page at the same time. If this rule is broken, the possibility of queue overflow becomes very high. The rule is formulated as follows using the notation in the previous section:
(6) 
Note that this constraint moderates the `overtargeted' feature of the LP solution which is pointed out by Tomlin [6] when . Since Problem 1 is still a transportation problem even if these constraints are incorporated, modifying Problem 1 with these constraints enables it to be efficiently solved.
4. Inventory management
Web ad agencies and companies that host web sites want to contract for as many ad impressions as possible to earn as much ad revenue as possible. However, overselling results in additional cost and reduced revenue. The important thing for preventing overselling and maximizing revenue is to grasp how many sellable impressions remain. Assuming that the estimated number of page views is accurate^{3}, this is easy if no constraints are specified by advertisers. However, this becomes nontrivial when such constraints are taken into account.
Figure 3: Two example cases of inventory status
Consider Case 1 in Figure 3, where the estimated numbers of page views for afternoon and sportscategory constraints are 10,000 each and 4,000 of them satisfy both constraints. Assume that there exists a contract which requests 8,000 impressions on sportscategory pages only. In this case, 8,000 sellable impressions remain for afternoon constraint when no other contracts exist. In this manner, calculation of the remaining sellable impressions for a certain constraint t needs to take contracts for other constraints which overlap constraint t into consideration. Should only overlapping constraints be considered? Consider Case 2 in Figure 3, where the estimated number of page views is 10,000 for each of three constraints and the afternoon constraint overlaps the sportscategory and businesscategory constraints while sportscategory and businesscategory constraints do not overlap. The estimated numbers of page views for the two overlaps are 4,000 each. Assume that there exist two contracts, one requesting 8,000 impressions on sportscategory pages only and the other requesting 6,000 impressions in the afternoon only. In this case, 8,000 sellable impressions for businesscategory constraint remain when no other contracts exist. Thus, the sportscategoryconstraint contract affects the number of remaining sellable impressions for the businesscategory constraint, which does not overlap the sportscategory constraint.
We formalize this problem as follows. Assume that we want to know the number of remaining impressions for constraint t. Let i(=1,...,n) denote other constraints and j(=1,...,m) denote attribute subspaces divided by all constraints. Define N_{i} and P_{j} as follows:
Note that N_{i} is the total sum of the impressions for all contracts which specify constraint i. In order to equalize the sum of N_{i} and the sum of P_{j}, we introduce dummy constraint n+1 and dummy attribute subspace m+1 and let N_{n+1} be and P_{m+1} be . We assume that constraint n+1 contains every attribute subspace j and attribute subspace m+1 is contained in every constraint i. We define S and Q as follows:
(7)  
(8) 
Let x_{i,j} be the number of scheduled impressions for . Then, the problem is described as follows.
Minimize
(9) 
under the conditions
=  (10)  
=  (11)  
x_{i,j}  (12) 
Objective function (9) is seen as cost function
where C_{i,j} is a unit cost for (i,j) that is 2 for i=1,...,n and j=m+1, 1 for and and 0 otherwise. The first term of function (9) is the cost of the impressions for the contracts for other constraints which are scheduled for page views available for constraint t. Since the purpose is to know the maximum estimated number of page views available for constraint t, we want this cost to be as low as possible. The second term of function (9) is overflow cost that charges for the impressions scheduled for the page views of the dummy attribute subspace. If there exists such that x_{i,m+1}>0, this means overselling for other constraints but does not mean overselling for constraint t.
Let the solution of Problem 2 be
x_{i,j}=a_{i,j}.
Then, the number of remaining sellable impressions for constraint
t is
(13) 
where N_{t} is the number of impressions contracted for constraint t.
Since Problem 2 also falls into the ``transportation problem'' category, it can be solved efficiently.
Figure 4: Solution of case 2 using our formalization
Figure 4 shows a solution of case 2 using our formalization. Left nodes represent constraints i and right nodes represent attribute subspaces j. An arrow from a left node to a right node is drawn for each . An arrow with a coarse broken line, a continuous line and a fine broken line means that the unit cost is 0, 1 and 2, respectively. Black nodes means that the corresponding attribute subspaces belong to Q. A solution for the problem is represented by an assignment of the number of scheduled impressions to each arrow. An arrow with a bold line is the one to which nonzero number of scheduled impressions is assigned in the optimal solution (the assigned number is parenthesized in the figure). For the arrows from the dummyconstraint node to the black nodes, the assigned numbers of scheduled impressions are 2,000 and 6,000. Therefore, the number of remaining sellable impressions for business constraint is 8,000.
5. Concluding remarks
We have provided solutions for two practical issues of optimally scheduling web advertising. Our solutions are not only efficient but also easy to implement, and an actual system incorporating these solutions has already been developed.
There is one important issue relevant to inventory management we did not address in this paper  inventory estimation. Our solution for inventory management is based on the assumption that the estimated number of page views is accurate to some extent. In order to accurately estimate the amount of inventory, periodicity and adaptivity should be taken into consideration, while the most important thing is to find what information it depends on. In our current system, we adopt a simple method based on statistics but we hope and plan to develop a sophisticated method in the future.
Bibliography
 1
 N. Abe and A. Nakamura.
``learning to optimally schedule internet banner advertisements''.
In Proc. of the 16th International Conference on Machine Learning, pages 1222, 1999.  2
 G. Bradley, G. Brown, and G. Graves.
``design and implementation of a large scale primal transshipment algorithm''.
Management Science, 24:134, 1977.  3
 D. Chickering and D. Heckerman.
``targeted advertising with inventory management''.
In Proc. of ACM Special Interest Group on ECommerce (EC00), pages 145149, 2000.  4
 G. Dantzig.
``Linear Programming and Extensions''.
Princeton University Press, 1963.  5
 M. Langheinrich, A. Nakamura, T. K. N. Abe,
and Y. Koseki.
``unintrusive customization techniques for web advertising''.
Computer Networks, 31:12591272, 1999.  6
 J. Tomlin.
``an entropy approach to unintrusive targeted advertising on the web''.
In Proc. of the 9th International World Wide Web Conference, 2000.
Footnotes
 ... randomly^{1}
 Though this assumption is not realistic because an attribute value `not afternoon' does not appear in the afternoon, it is not so unreasonable considering on the average.
 ... solution^{2}
 Note that the optimal solution depends on the promised number of impressions for each ads. If ad 2 has been promised to be displayed twice as many times as ad 1, then the optimal solution is the one that always displays ad 2 for combination 1 and always displays ad 1 for combination 2.
 ... accurate^{3}
 Accurately estimating the number of page views itself is an important issue, but this is not the focus of our paper.