WWW 2008 / Refereed Track: Internet Monetization - Online Advertising April 21-25, 2008 · Beijing, China A Combinatorial Allocation Mechanism With Penalties For Banner Advertising Centrum voor Wiskunde en Informatica uriel.feige@weizmann.ac.il Amsterdam, the Netherlands Weizmann Institute Rehovot 76100, Israel Uriel Feige Nicole Immorlica immorlic@cwi.nl Hamid Nazerzadeh Stanford University Stanford, CA 94305 mirrokni@theory.lcs.mit.edu Microsoft Research Redmond, WA 98052 Vahab S. Mirrokni hamidnz@stanford.edu ABSTRACT Most current banner advertising is sold through negotiation thereby incurring large transaction costs and p ossibly sub optimal allocations. We prop ose a new automated system for selling banner advertising. In this system, each advertiser sp ecifies a collection of host webpages which are relevant to his product, a desired total quantity of impressions on these pages, and a maximum p er-impression price. The system selects a subset of advertisers as winners and maps each winner to a set of impressions on pages within his desired collection. The distinguishing feature of our system as opp osed to current combinatorial allocation mechanisms is that, mimicking the current negotiation system, we guarantee that winners receive at least as many advertising opp ortunities as they requested or else receive ample comp ensation in the form of a monetary payment by the host. Such guarantees are essential in markets like banner advertising where a ma jor goal of the advertising campaign is developing brand recognition. As we show, the problem of selecting a feasible subset of advertisers with maximum total value is inapproximable. We thus present two greedy heuristics and discuss theoretical techniques to measure their p erformances. Our first algorithm iteratively selects advertisers and corresp onding sets of impressions which contribute maximum marginal p erimpression profit to the current solution. We prove a bicriteria approximation for this algorithm, showing that it generates approximately as much value as the optimum algorithm on a slightly harder problem. However, this algorithm might p erform p oorly on instances in which the value of the optimum solution is quite large, a clearly undesirable failure mode. Hence, we present an adaptive greedy algorithm which again iteratively selects advertisers with maximum marginal p er-impression profit, but additionally reassigns impressions at each iteration. For this algorithm, we prove a structural approximation result, a newly defined framework for evaluating heuristics [10]. We thereby prove that this algorithm has a b etter p erformance guarantee than the simple greedy algorithm. Categories and Subject Descriptors F.2 [Theory of Computation]: Analysis of Algorithms and Problem Complexity--General ; J.4 [Computer Applications]: Social and Behavioral Sciences--Economics General Terms Algorithm, Theory, Economics Keywords Internet Advertising, Supply Guarantee, Combinatorial Auctions, Structural Approximation 1. INTRODUCTION Online advertising is one of the most profitable business models for Internet services to date, accounting for annual revenues approaching $17 billion dollars according to the Internet Advertising Bureau [21]. According to the same rep ort, 22% of this revenue comes from banner advertising, or graphic-based advertisements which app ear emb edded in content pages on a host website. Current models of banner advertising require advertisers to negotiate rates directly with the sales representatives of the host on a monthly basis. These negotiations involve several parameters. First, the advertiser sp ecifies a subset of content pages which are relevant to his or her ad. Next, the advertiser requests a desired numb er of impressions, or advertising opp ortunities, on pages from among his or her sp ecified subset, and a p erimpression price. Finally, if the negotiation is successful and the contract is accepted, the advertisement is shown on some subset of the sp ecified content pages. By accepting a contract the supplier is committed to the supply. If the supply is not met, the bidder is comp ensated in two ways: he is not charged for the parts that are not met, and moreover, he gets them for free in the next time p eriod. This process requires a lot of overhead for advertisers who must negotiate with sales representatives, and a lot of guesswork for sales representatives who must decide based on intuition which advertising contracts to accept. As a result, small advertisers tend to b e locked out of the system, unable to b ear the cost of the smallest-sized contracts, and the system overall suffers additional inefficiencies from the suboptimal decisions of the sales representatives. In this paper, Copyright is held by the International World Wide Web Conference Committee (IW3C2). Distribution of these papers is limited to classroom use, and personal use by others. WWW 2008, April 21­25, 2008, Beijing, China. ACM 978-1-60558-085-2/08/04. 169 WWW 2008 / Refereed Track: Internet Monetization - Online Advertising we consider automating this system. We design a system which each month considers the supply of page views and a set of bids, each sp ecifying a desired set of pages, a desired numb er of impressions, and a p er-impression value, and then selects a subset of bids which maximizes the value while sustaining p enalties for under-allocated impressions. Whereas in practice, the p enalties are realized in the form of free impressions, in our system we represent these p enalties with a monetary payment from the host to the advertiser equal to a sp ecified multiple of the p er-impression value for each under-allocated impression. The p enalty factor reflects an estimate of how much next month's impressions are going to b e worth. There are several factors which make this system harder to design than general combinatorial allocation mechanisms. The most significant difference comes from the fact that the host must "guarantee" supply by paying a p enalty for underallocated impressions. Such guarantees are quite characteristic of the banner advertising market, and are imp ortant in branding campaigns where it is essential for the advertiser to receive at least some minimum numb er of impressions ­ the McDonald's arches or the Nike swoosh are recognizable precisely b ecause they are ubiquitous. However, these guarantees also make the underlying optimization problem hard to approximate: for example, if the p enalty is very large, then each winner must receive all of his requested impressions and so we can reduce our problem from the well-known set packing problem [15]. In fact, as we show, even for small p enalties, our problem is not approximable within any constant factor. We therefore focus on designing heuristics with varying sorts of provable guarantees. A common approach to combat inapproximability is to develop bi-criteria approximations, or algorithms that do almost as well as the optimum solution on a slightly harder problem. For example, in -balanced graph partitioning, the goal is to cut the minimum numb er of edges to divide a graph on n vertices into two parts, each with at most n vertices. The seminal pap er of Leighton and Rao [18] provides a bi-criteria approximation algorithm for (2/3)-balanced graph partitioning which cuts at most a factor of O(log n) more edges than the optimum solution on the harder problem of bisection, or (1/2)-balanced graph parti tioning. This was improved to O( log n) by Arora et al. [3]. The bi-criteria framework has also b een applied to min sum clustering [5] and selfish routing [22]. In our case, we apply the bi-criteria framework by designing an algorithm that does approximately as well as the optimum algorithm with larger p enalties. Our algorithm is extremely simple and trivial to implement: it selects at each iteration a new winner and a corresp onding set of impressions with maximum marginal p er-impression profit. We show that this algorithm gets at least 23% of the optimum profit on a problem with 2.26 times the p enalty (i.e., whereas our algorithm just pays an advertiser his p er-impression bid for each under-allocated impression, the optimum must pay 2.26 times the p er-impression bid). Despite the bi-criteria guarantee, we note that this greedy algorithm may p erform p oorly when the optimum solution has large value. These are exactly the instances in which we would like to p erform well. Hence, we present a refined greedy algorithm which involves solving a flow computation and prove guarantees on its p erformance in the structural approximation [10] framework, a newly develop ed frame- April 21-25, 2008 · Beijing, China work for evaluating the approximation factor of heuristic algorithms. This framework allows one to evaluate the approximation factor of an algorithm based on the structure of the optimal (or any) solution, and not only the value of the optimal solution. In particular, it provides a p erformance guarantee that improves as the p erformance of the optimum solution improves, and unlike the bi-criteria framework, it provides these guarantees with resp ect to the optimum on the same problem instance. Our refined greedy algorithm iteratively selects advertisers with maximum marginal p er-impression profit, as b efore, but additionally considers re-allocating impressions to already selected advertisers at each step. In evaluating this algorithm, we consider the fraction of demand that the optimum satisfies for each advertiser. We show as this fraction increases, hence increasing the optimum value, our algorithm's value also increases. For example, if the optimum always satisfies 75% of the demand of each advertiser, then our algorithm gets at least 10% of the optimum, wherease if the optimum satsifies 99% of the demand of each advertiser, then our algorithm gets at least 30% of the value of the optimum. See Section 5.1 for the exact trade-off curve. We note that the refined greedy algorithm outp erforms the simple greedy algorithm on many classes of instances. However, this improved p erformance comes at the exp ense of increased difficulty in the implementation (and an additional linear factor in the running time). It is imp ortant to note that we ignore incentives throughout this work, i.e., we analyze the value of our allocation mechanism in an idealized world where advertisers truthfully rep ort their typ es and not in an economic equilibrium. While incentive issues are very imp ortant in practice, they tend to have less effect in highly comp etitive settings. In successful banner advertising systems, where lots of advertisers comp ete for limited supply, we intuitively exp ect incentives to play a minimal role. We leave it as further work to study incentives in our prop osed systems and/or calculate payments to make our prop osed systems truthful. 1.1 Related Work The problem of maximizing welfare is a central problem in algorithmic mechanism design. This problem, even for sp ecial cases such as single-minded bidders, is known to b e hard even to approximate [23, 17, 16, 7, 8]. However, under some conditions such as submodularity or subadditivity of valuations, constant-factor approximation algorithms have b een develop ed [8, 9]. For several problems with packing constraints linear programming-based and greedy constantfactor approximation algorithms have b een prop osed [1, 13]. In the context of Internet advertising, sp onsored search auctions have b een studied extensively. The closest works to ours in this literature are the 1 - 1 -comp etitive algorithms e that have b een designed for maximizing revenue for online allocation of advertisement space [20, 6, 19]. Our work is distinguished from previous work in the literature by the existence of supply guarantees, implemented through p enalties. These p enalties reflect the non-linearity of bidder valuations, a characteristic of advertisers in banner advertising markets. 1.2 Organization This pap er is organized as follows. We give a formal definition of the model in Section 2. In this section, we also 170 WWW 2008 / Refereed Track: Internet Monetization - Online Advertising give the following basic observation ab out our problem: in the guaranteed banner advertisement problem, if the set of served advertisers is fixed, the optimal allocation can b e found in p olynomial time. This indicates that the challenging part of the problem is to find the set of advertisers that should b e served to maximize the value. In Section 3, we prove that the problem does not admit a constant-factor approximation algorithm even for weak supply guarantee conditions. Next, in Section 4, we give a bi-criteria approximation algorithm for the problem. In Section 5, we give an adaptive greedy algorithm and analyze it in the structural approximation framework. maximize sub ject to April 21-25, 2008 · Beijing, China X yi (2xi - di )bi X zij 1 X zij (2) iA j U : iA i A : x i = j Ii i A : x i di i A, j U : zij {0, 1} i A : yi {0, 1} As we show in the next section, it is NP-hard to even approximate the solution of this optimization program within any constant ratio. The main difficulty comes from the multiplicative terms yi xi in the ob jective function of the program ab ove. However, we show that once the set of winning advertisers is determined (i.e., once we fix the {yi } variables), the resulting program can b e solved combinatorially using a maximum weighted matching algorithm. Lemma 2.1. Given the set T of winning advertisers, the problem of finding the optimum al location of items to advertisers in T can be optimal ly solved in polynomial time. Proof. We can rewrite the ab ove mathematical program by setting yi P 1 for i T and yi = 0 otherwise, and by = setting xi = j Ii zij . The negative term in the resulting ob jective function is now a constant, and so the problem reduces to the following program: maximize sub ject to XX 2zij bi X iT j Ii 2. MODEL The banner advertisement problem can b e modeled as follows. We are given a set A of m advertisers {1, . . . , m} and a set U of advertising opp ortunities that can b e allocated to them. Each advertising opp ortunity is an impression of an advertisement on a webpage. For the rest of the pap er, we refer to each advertising opp ortunity as an item. Without loss of generality, we assume all items of U are distinct. The bid of an advertiser i is a tuple (Ii , di , bi ) where Ii U sp ecifies the subset of items in which advertiser i is interested 1 , di sp ecifies the numb er of items the advertiser requires, and bi sp ecifies the p er-unit price the advertiser is willing to pay (up to his required numb er of units). Allocating more than di items to advertiser i has no marginal b enefit. Following the convention of current banner advertising systems, we require our system to guarantee the supply of an advertiser. That is, by accepting the bid of advertiser i, we enter a contract for the sale of di items from the set Ii . Should we fail to fulfill this contract, we are required to pay a penalty. This p enalty can b e a fixed price paid for every under-allocated impressions; or more commonly, can b e filled by delivering the same numb er of impressions for free during the following p eriod. Both of these p enalty schemes can b e formalized in the following way: If the advertiser requested di units and was allocated only xi units for some xi < di , then the system collects only bi xi - bi (di - xi ) = (( + 1)xi - di )bi (1) iT j Ii j U : i T : zij 1 zij di X i T , j U : zij {0, 1} (3) This integer program is equivalent to a maximum weighted b-matching problem, or f -factor problem, in which, given a weighted graph G, the goal is to find a maximum-weight subgraph of G in which the degree of each node i is at most f (i). The mapping is as follows: consider a bipartite graph G(V , E ) with node set V (G) = U T , edge set E (G) = {(i, j )|i T , j Ii }, and edge weights w(i, j ) = 2bi . The solution to the integer program is then the maximum weighted f -matching in which f (i) = di for i T and f (j ) = 1 for j U . We can therefore use the combinatorial or LP-based algorithms for f -matching (see, e.g., [25, 24, 4]) to solve our problem. The ab ove discussion shows that the challenging part of the banner advertising problem is to decide the set T of winning advertisers. in value, where is a fixed constant. The sp ecial case of = 1 can b e interpreted as delivering the same numb er of impression for free the following month. Henceforth, we will b e primarily concerned with the case = 1, unless otherwise stated, although all results can b e appropriately generalized to other values of . Now we can formalize the banner advertisement problem in the following way: Given a set of advertisers A and their bids, {(Ii , di , bi )}, find a subset of advertisers, or winners, for which accepting their bids maximizes the value. This problem is captured by the following mathematical program. Let yi b e the indicator variable that advertiser i is a winner; zij b e the indicator variable that item j is allocated to advertiser i; and xi b e the total numb er of items allocated to advertiser i. 1 Each advertiser is interested in advertising on webpages with sp ecific content such as finance, sp orts, etc. Advertising can b e even more targeted by using demographic information of the current viewer of the webpage such as gender, geographic location, or age. 3. HARDNESS OF APPROXIMATION In this section, we show that the banner advertising problem is NP-hard to approximate within any constant ratio. In other words, for any constant 0 < c 1, it is not p ossible 171 WWW 2008 / Refereed Track: Internet Monetization - Online Advertising to find an allocation with value at least c times the optimum value (defined as the value of the mathematical program (2)) in p olynomial time unless P = N P . This result is immediate for arbitrarily large p enalties via a reduction from the inapproximable maximum set-packing problem [15], i.e., the problem of finding the maximum numb er of disjoint sets in a given set family. For arbitrary p enalties, we provide a reduction from the k-uniform regular set cover problem. In this problem, we are given a family of sets over a universe of elements. Each set in the family has exactly k elements, and each element in the universe is covered by exactly k sets. The goal is to select the minimum numb er of sets which cover all the elements. It is shown in Feige et al. [14], Theorem 12, that: Proposition 3.1. [11, 14] For every choice of constants s0 > 0 and > 0, there exists k dependent on and instances of k-uniform regular set cover with n elements on which it is NP-hard to distinguish between the case in which al l elements can be covered by t = n disjoint sets, and the case k in which every s s0 t sets cover at most a fraction of 1 - 1s (1 - t ) + of the elements. By introducing an advertiser with bid (Ii , |Ii |, 1) for each set Ii in the set cover instance, there is a trivial reduction from the problem ab ove which shows that it is NP-hard to compute the optimum value of the banner advertising problem. In the case in which all elements can b e covered by t = n disjoint sets, the optimum value would b e n, but, k the case in which every s s0 t sets cover at most a fraction of 1 - (1 - 1 )s + of the elements, the optimum value would t b e less than n. In order to prove hardness of approximation, we find an upp er b ound on the value of the optimum solution in the second case, which leads to the theorem b elow. Theorem 3.2. The banner advertising problem is NPhard to approximate within any constant ratio 0 < c 1. The theorem is proved by showing that if one can approximate the solution within a constant ratio, then it is p ossible to distinguish b etween the instances of the set cover problem describ ed ab ove. The complete proof is given in app endix A. Although the proof in the app endix is presented assuming the p enalty is equal to one, the result holds for any constant linear p enalty. April 21-25, 2008 · Beijing, China The value that algorithm greedy obtains from the instance in the previous example is equal to the optimum value. 4.1 Performance Guarantee: Bi-Criteria Approximation We analyze algorithm greedy by developing bi-criteria approximations for our problem. To do so, we compare the value of our solution to the value of the optimal solution with a greater p enalty. We say an algorithm is an (, )-approximation if it always outputs a solution with value at least times that of the optimal solution with (larger) p enalties . More formally, an algorithm is an (, )-approximation for the problem of selling banner ads if it can always obtains a fraction of the value of the linear program b elow ­ this is the same as LP 2 but with a different ob jective. maximize sub ject to X yi (( + 1)xi - bi di )bi X zij 1 X zij (4) iA j U : iA i A : x i = j Ii i A : x i di i A, j U : zij {0, 1} i A : yi {0, 1} In other words, while our algorithm pays a p enalty of 1 for under-allocation, the optimal solution is charged a p enalty of for some > 1. For algorithm greedy we can prove the following theorem: ln 2 Theorem 4.1. For 1-ln 2 2.26, the approximation ratio of greedy algorithm is 1-ln 2 0.23. For 1 < < 2-ln 2 ln 2 , the approximation ratio is 1-ln 2 2x - 1 - ln 2x ( + 3)x - - 1 - ln 2x (5) where x [ 1 , 1] is the root of the equation 1/x + (1 + + 1/) ln 2x = 2. Proof. For any > 1, let opt b e an optimal solution for the p enalty . We provide lower b ounds on the approximation ratio of greedy and opt . Let A b e the set of all advertisers who contribute a p ositive profit to opt . For i A, let Si b e the set opt allocated to advertiser i. To i simplify notation, we use si to denote |Si | . Without loss of d generality, we may assume 1 < si 1. + In the analysis of greedy algorithm, we will partition each item into two subitems: the P subitem that takes up a p fraction of the item, and the Q subitem that takes up a (1 - p) fraction of the item; we will determine the value of p later. We will develop lower b ounds on the profit of greedy by a case analysis. In each case, we will compare the profit opt gets to one of two kinds of profit that greedy gets: only to the part computed over P subitems, or only to the part computed over Q subitems. Summing over all 4. A GREEDY ALGORITHM In lieu of the ab ove hardness result, we present a greedy heuristic which at each step assigns items to an advertiser that maximizes the profit-p er-item. The description of the algorithm is given in Figure 1. Note that it is imp ortant to choose an advertiser that maximizes profit-p er-item. The example b elow shows that a naive greedy algorithm which chooses the advertiser with maximum overall profit p erforms quite p oorly even in "easy" instances. Example Supp ose there are n + 1 advertisers and n items. Advertiser i, 1 i n, is interested only in item i and bids 1 for it. Advertiser n + 1 bids 1 + for receiving all the n items. While the optimal solution yields a value of n by allocation items 1 to n to advertisers 1 to n, the naive greedy algorithm obtains a value of just 1 + . 172 WWW 2008 / Refereed Track: Internet Monetization - Online Advertising greedy Algorithm: Initialize the set of allocated items Q to b e the empty set While there exists an unassigned advertiser: 1. For each unassigned advertiser i: April 21-25, 2008 · Beijing, China 2. Choose the advertiser i whose p er-item profit pi is maximum. (a) Let J i = Ii \ Q b e the set of remaining items that we can allocate to i and Ji Ji b e an arbitrary subset of size min(di , |Ji |). (b) Let pi = (2 - di /|Ji |)bi b e the profit-p er-item obtained by allocating Ji to i. 3. If pi is p ositive, then set i to b e a winner, allocate Ji to i , and set Q to b e Q Ji ; otherwise terminate the algorithm. Figure 1: greedy algorithm advertisers, the P part and Q part of each item, and hence the whole item, is counted at most once. For i A, there are two cases: 1. greedy allocates strictly less than |Si | - di /2 items from Si . In this case we consider the profit greedy obtains from P subitems assigned to i. When j elements of Si are remaining, greedy could allocate these elements to i with profit-p er-item 2j -di bi . j This profit is p ositive for di /2 < j |Si |. Therefore, in this case, greedy must have allocated a nonempty set to advertiser i since otherwise greedy could get p ositive p er-item profit by adding i to the solution and allocating the unallocated items of Si to i. Furthermore, as greedy has items of Si available when assigning items to i, it follows that the demand di of advertiser i is fully satisfied. Hence greedy gets complete profit for P subitems, giving a profit of pdi bi . 2. greedy allocates at least |Si | - di /2 items from Si In this case we consider the profit greedy gets from Q subitems of Si . Note, greedy must have obtained a profit of at least 2j -di bi from the (|Si | - j + 1)'th item allocated from j Si as this is the p er-item profit greedy obtains by allocating the remainder of Si to i. Summing over j , di /2 + 1 j |Si |, greedy must have allocated these items with total profit at least: |S i | X most once since the assignment in case 1 is a subset of the solution for greedy and hence disjoint. Similarly, the Q part is also counted at most once since the Si considered in case 2 is a subset of the optimum solution and hence disjoint. Therefore, we have shown that greedy gets a profit of at least: X min{p, (1 - p)(2si - 1 - ln 2si )}di bi . (7) iA The profit of opt from Si is (( + 1)si - )di bi . Therefore, the ratio of the profit of greedy to opt is at least min{p, (1 - p) }, where is defined as = min{ i 2si - 1 - ln 2si } ( + 1)si - (8) Choosing p = 1+ gives the approximation ratio 1+ . We find a lower b ound on using the first and second order conditions. The details of calculations are given in ln 2 app endix B. For 1-ln 2 , takes its minimum for si = 1. 2 Plugging in (8), we get = (-1-lin 2 = 1 - ln 2 and p = +1)s - 1-ln 2 2-ln 2 ln 2 For 1 < < 1-ln 2 , as we prove in app endix B, there exists a p oint x in [ +1 , 1] for which si = x gives the minimum value of . This p oint is the root of the equation b elow which is derived by taking the derivatives of (8): j = di /2 +1 2j - di bi j = Z Z |S i | di / 2 |S i | di / 2 2x - di bi d x x (2 - di )bi d x x (6) Plugging this value for into 1+ , we get (5) as a lower ln 2 b ound on the approximation ratio for 1 < < 1-ln 2 . /x - 2 + ( + 1) ln 2x = 0. = (2|Si | - di - di (ln |Si | - ln = (2si - 1 - ln 2si )di bi di ) )b i 2 We give an example which shows the analysis is tight ln 2 for 1-ln 2 . In this example, the optimal solution allocates all of the items to the advertisers without paying any p enalty. However, the greedy algorithm obtains just a 1-ln 2 fraction of the optimal solution. 2-ln 2 Example Assume for an even numb er k, there are m = 3k/2 advertisers and km items. Supp ose these items are represented by an m × k matrix C . Each advertiser has a demand of k items. Advertiser i, 1 i k, is only interested in items in row i, i.e. {cij |1 j k}, and bids 1 for each of k these items. Advertiser i, k +1 i 3k/2, bids 2- i+1-(k/2) Taking into account that this profit comes only from the Q part of items, this gives a profit of (1 - p)(2si - 1 - ln 2si )di bi . For each advertiser i, exactly one of the ab ove cases happ ens. Furthermore, for each item, the P part is counted at 173 WWW 2008 / Refereed Track: Internet Monetization - Online Advertising 0.25 April 21-25, 2008 · Beijing, China X xj k x j k dj X xik = ci (9) maximize sub ject to kIj 0.2 0.15 kIj X 0.1 i Gt : k U : 1 1.5 2 2.5 kIi 0.05 iA X xik 1 0 i A, k U : xik {0, 1} t Also, let rj t = jfjt j · bj b e the maximum p er-item profit that we could obtain from advertiser j , sub ject to the constraints. At step t, algorithm adaptive greedy chooses the advertiser with maximum rj t , j Gt . The algorithm is / given in Figure 5. To compute fj t , one can solve the linear relaxation of the ab ove program and round the solution to an integer solution (without decreasing the ob jective function). For a complete description of the algorithm, we refer the reader to [4]. 2 2f -d Figure 2: The bi-criteria approximation ratio of ln 2 greedy for 1 < < 1-ln 2 k for each item in row i. He also bids 2 - i+1-(k/2) for each item in column i - k/2. By induction, one can show that at step j , for 1 j k/2, greedy may allocate the top k items in column k - j + 1, to advertiser 3k/2 - j + 1. Therefore, the total profit of greedy is: 3k/2 k i=k+1 X 2- X k 1 = 2k 1- i + 1 - (k/2) 1 + (2i + 1)/k i=1 k /2 5.1 Performance Guarantee: Structural Approximation As we observed in Section 3, the hardness result implies that we do not hop e to analyze the adaptive greedy algorithm by the traditional multiplicative approximation framework. However, in order to distinguish the quality of different algorithms in practice, we can use other approximation measures such as the bi-criteria approximation. In this section, we analyze the adaptive greedy algorithm using a newly defined framework for evaluating heuristics called structural approximation [10]. The main feature of this framework is that it is designed to evaluate the approximation ratio of an algorithm based on the structure of an optimal (or any) solution, and not only the value of an optimal solution. In this framework, given a solution with some value, we define the recoverable value of the solution based on its structure. The goal is to show that the value of our algorithm is at least as much as the the recoverable value of any solution. 3 We would like to design a recoverable value function that is very close to the real value. Note that in the traditional multiplicative approximation framework, the recoverable value is restricted to a multiplicative ratio of the value of the solution. By allowing more general functions for the recoverable value, the structural approximation framework is more flexible, and therefore can distinguish among different algorithms with the same worst-case multiplicative approximation guarantees. Additionally, this framework provides a way for comparing the quality of our solution to that of the optimal solution of the same problem (with the same parameters). This is in contrast to the bicriteria approximation framework in which we compare the value of our solution to the value of a problem with different parameters. We refer the reader to [10] for a more detailed discussion of the structural approximation framework. One can also solve the problem by modeling it as a flow problem with lower b ound and upp er b ound on the capacities. 3 Note that the recoverable value of different optimal solutions may differ. In fact, our guarantees hold with resp ect to the largest recoverable value of any solution. 2 We can make k arbitrary large. Hence, profit of greedy can b e approximated by k2 (1 - ln 2), with arbitrary high accuracy: 3k/2 k i=k+1 X 2- k k 2 (1 - i + 1 - (k/2) 2 Z 1 x= 0 1 dx ) 1+x = k (1 - ln 2) The optimal solution gives advertiser i, 1 i m, all the items in row i. Hence, it gets a profit k2 from the first k advertiser and a profit k2 (1 - ln 2) from the rest. Therefore, the approximation ratio of greedy is b ounded by 1-ln 2 . 2-ln 2 5. AN ADAPTIVE GREEDY ALGORITHM As suggested by Example 4.1, fixing the items allocated to each advertiser may hurt the p erformance of the algorithm. In this section, we give an adaptive greedy algorithm called adaptive greedy. Similar to the previous greedy algorithm, this algorithm iteratively selects new winners. However, in each iteration, it fixes only the number of items assigned to the new winner and not the precise set of items. This flexibility allows adaptive greedy to find the optimum solution in Example 4.1 and, as we will show, allows us to prove b etter approximation guarantees in general. We use the following notation throughout this section. For a winning advertiser i, let ci b e the numb er of items allocated to i. Note as mentioned ab ove that ci remains fixed although the set of allocated items may change throughout the course of the algorithm. Let Gt b e the set of advertisers chosen by the algorithm up to but not including time t. For j Gt , let fj t b e the maximum numb er of items that we / could allocate to advertiser j , sub ject to the constraint that each advertiser i Gt gets exactly ci items. More formally, fj t is the solution of the following integer program. 174 WWW 2008 / Refereed Track: Internet Monetization - Online Advertising adaptive greedy Algorithm: Initialize G, the set of chosen advertisers, to b e the empty set. Let t, the numb er of steps, b e zero. While there exists an unassigned advertiser: 1. t t + 1 April 21-25, 2008 · Beijing, China / 2. For each advertiser j G: (a) Let fj t b e sub ject to (b) Let rj t b e sub ject to th e th e th e th e 3. Choose an advertiser j with maximum rj t . 4. If rj t is p ositive: (a) Add advertiser j to G. (b) Let cj = fj t . Otherwise terminate the algorithm. maximum numb er of elements that can b e allocated to advertiser j , constraints that each advertiser i G gets exactly ci items. maximum profit-p er-item that could b e obtained by choosing advertiser j , constraints, i.e. rj t = (2 - dj /fj t )bj . Figure 3: adaptive greedy algorithm We now analyze adaptive greedy algorithm using the structural approximation framework. Let W b e the set of advertisers that are allocated a non-empty set in the optimal solution, i.e., the winners. For each advertiser i W , let Si b e the set of items allocated to i in an optimal solution. For i i W , Si is taken to b e the empty set. Let si = |Si | . Then d P the value of the optimal solution is: iW (2si - 1)di bi . We define X (2si - 1 - ln 2si )di bi iW 0.35 0.3 0.25 0.2 0.15 0.1 0.05 0 0.5 as the recoverable value of this solution. Note that any optimal solution makes profit only from the advertisers with si > 1 . We show that the value of adaptive greedy is 2 at least equal to this recoverable value. This gives a p erformance guarantee based on the the structure of the optimal solution. In particular, the p erformance of the algorithm is b etter if si 's are closer to 1. This statement is formalized in the following theorem. Theorem 5.1. Let Si be the set of items assigned to adi vertiser i by an optimal solution. Also, let si = |Si | . adapd tive greedy algorithm obtains a value of at least: X (2si - 1 - ln 2si )di bi . iW ,si > 1 2 0.6 0.7 0.8 0.9 1 Figure 4: The approximation ratio of adaptive greedy when at least a s fraction of the demand of all winner advertisers is satisfied in the optimum solution. Proof. To prove Theorem 5.1, without loss of generality, we assume the algorithm chooses advertisers 1, 2, . . . , T in order. We inductively construct a sequence of assignments of items to advertisers which we call canonical assignments. Let C0 b e the empty set. The t-th element of the sequence of assignments, denoted by Ct , is an assignment of items to advertisers 1, . . . , t which satisfies the following prop erties. · Each advertiser i, 1 i t, is assigned exactly ci items. · All items that are assigned in Ct-1 are also assigned in Ct , i.e. are assigned to advertisers 1, . . . , t. · For each advertiser i, 1 i t, all the items in Si (namely, the items allocated to i by the optimal solution, if i W ) are assigned. (This prop erty trivially holds for i W .) In the following lemma, we show that such a sequence of assignments exists. Corollary 5.1. Consider a col lection {(qi , i )} corresponding to an optimal solution, where qi is the fraction of the value of the solution comes from the advertisers for which an i fraction of the demand is satisfied. Then, the approximation ratio of adaptive greedy is at least: P i qi (2i - 1 - ln 2i ) P i qi (2i - 1) In particular, when in the optimal solution, at least an s fraction of the demand of all winning advertisers is satisfied, adaptive greedy obtains at least a fraction (2s - 1 - ln 2s) of the value of the optimal solution. Figure 4 depicts this 1 lower b ound on the value for 2 s 1. 175 WWW 2008 / Refereed Track: Internet Monetization - Online Advertising Lemma 5.1. There exists a sequence {C1 , C2 , . . . , Ct } of canonical assignments which satisfies the properties above. Proof. We prove the lemma by induction on t. For t = 1, the only nontrivial prop erty is the third one, if 1 W . In this case we observe that c1 |S1 |, and hence a canonical assignment exists. Therefore, the base of induction holds. Now consider t > 1. Assume a sequence of canonical assignments C1 , . . . , Ct-1 , and let Ct b e an optimal solution for LP (9). We change Ct to a canonical assignment satisfying the ab ove three prop erties. For 1 i < t, let Bi b e the set of item that are assigned to advertiser i in Ct-1 . Also, let Bt the set of items in St that are not assigned to any advertiser in Ct-1 . Note that |Bt | ct , b ecause if we assign each item in Bi , 1 i t, to advertiser i, it gives us a feasible solution of LP (9). We rep eat the following procedure as long as there exists an item x such that x Bi , for an advertiser 1 i t, and x is not assigned to any advertisers in Ct . Since advertiser i has received ci items in Ct , and |Bi | ci , there exists an item y Bi that is assigned to i in Ct . We up date Ct by / assigning x to i and removing y from the set of items allocated to i. Note that each time we p erform the procedure, the numb er of items that is allocated to each advertiser remains the same. However, the numb er of items that are allocated to the same advertisers in Ct and the assignment defined by Bi 's increases by 1. Since the numb er of items that are allocated to the same advertiser in Ct and the asP signment defined by Bi 's is at most 1it ci , after some numb er of steps, we reach a p oint where no such up date is p ossible. Therefore, the final assignment after these set of up dates satisfies all the three prop erties. Now we are ready to prove Theorem 5.1. Note that the value obtained from each assignment only dep ends on the numb er of items allocated to each advertiser. Therefore, without loss of generality, we might assume that adaptive greedy allocates to each advertiser the same set of items assigned to this advertiser in canonical assignment CT . For i W , let kit b e the numb er of items of Si that are not assigned in Ct-1 . Since we can construct a feasible solution with value kit for LP (9) using Ct-1 , we observe that fit kit . Therefore, the value-p er-item that adaptive greedy would obtain at this p oint if it chooses advertiser i and assigns to it all not previously assigned items of Si at d least (2 - kiit )bi . Thus, the value adaptive greedy obtains by the end of the algorithm is at least: |S i | m XX 0.35 0.3 0.25 April 21-25, 2008 · Beijing, China Adaptive Greedy 0.2 Greedy 0.15 0.1 0.05 0 0.5 0.6 0.7 0.8 0.9 1 Figure 5: Comparison of the lower bounds on the competitive ratio of the two greedy algorithms when at least s fraction of the demand of all winners is satisfied by an optimal solution. Note that while we stated all our results with resp ect to the recoverable value of an optimal solution, our proofs in fact follow when considering the recoverable value of any solution. 5.2 Comparison of GREEDY and ADAPTIVE GREEDY We analyzed adaptive greedy algorithm using the structural approximation framework. We also analyzed the greedy algorithm using the bi-criteria approximation framework. In order the compare these two greedy algorithms, we now analyze the greedy algorithm in the structural approximation framework. Let W b e the set of the winners in an optimum solution (or any feasible solution). Assume that this solution satisfies a si fraction of the demand of advertiser i W . Note that si 1 , i W . By equation (7), in the proof of Theorem 4.1, 2 for any p, 0 p 1, greedy obtains a value of at least: 1 iW ,si > 2 X min{p, (1 - p)(2si - 1 - ln 2si )}di bi (10) i=1 j =kiT (2 - di )bi j For i W , if advertiser i is chosen by adaptive greedy then kiT = 0, and if advertiser i is not chosen by adaptive greedy then necessarily kiT di . Therefore: 2 |S i | m XX Given si 's, one can compute the value of p which maximizes the sum and gives a recoverable value for each solution. However, by Theorem 5.1, the value of adaptive greedy algorithm from the same instance is at least: X (2si - 1 - ln 2si )di bi 1 iW ,si > 2 i=1 j =kiT (2 - m X di )bi j i=1 j = di /2 +1 |S i | X (2 - di )bi j By the same calculation as in Theorem 4.1, equation (6), the value obtained by adaptive greedy is at least: X (2si - 1 - ln 2si )di bi iW ,si > 1 2 This immediately shows that adaptive greedy gives us a b etter guarantee on the value of the solution. When in an optimum solution, fraction s of the demand of all advertisers is satisfied, we can easily compare the guarantees on the value given in Theorems 4.1 and 5.1. In this case, 1 2 the optimum value for p in (10) is equal to 2s---ln s s , which 2s ln 2 leads to the same guarantee on the approximation ratio of greedy algorithm. The guarantee on the approximation ratio of adaptive greedy algorithm is 2s - 1 - ln 2s. Figure 5 depicts these guarantees on the approximation ratio for 1 s 1. 2 176 WWW 2008 / Refereed Track: Internet Monetization - Online Advertising One way to see that adaptive greedy strictly outp erforms greedy is to observe that adaptive greedy algorithm obtains the optimum value of the instance describ ed in Example 4.1. As a result, the ratio b etween the values of the solutions obtained by these two algorithms is 2 - ln 2. April 21-25, 2008 · Beijing, China [9] 6. CONCLUSION [10] In this pap er we showed that having supply guarantees makes the problem of maximizing the value of selling banner advertisements inapproximable. In the lieu of this hardness result, we prop osed two greedy heuristics for the banner advertising problem and analyzed them rigorously in the bi-criteria and structural approximation frameworks. Given the simple and flexible nature of these algorithms, we exp ect that these algorithms can help in automating the negotiation process for banner advertising. In order to make our algorithms even more applicable to practical settings, we would like to consider the online or stochastic settings, in which advertisers arrive over time and submit bids which must b e immediately accepted or rejected, without knowledge of exact future demand. Also along these lines, it would also b e useful to relax the assumption that the supply of items is known a priori. In practice, hosts have good estimates of the numb er of page views. However, these estimates may have large variance, and we should ideally provide algorithms which are robust with resp ect to errors in the supply estimates. Finally, to completely automate the banner advertising process and replace it with a rep eated auction mechanism, it is necessary to design a pricing mechanism to accompany our allocation mechanism and analyze the resulting incentives. [11] [12] [13] [14] [15] [16] [17] 7. REFERENCES [18] [1] G. Aggarwal and J. D. Hartline, Knapsack Auctions, Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006. [2] G. Ausiello, A. D'Atri, and M. Protasi. Structure Preserving Reductions Among Convex Optimization Problems. Journal of Computer and System Sciences, 21, 136-153, 1980. [3] S. Arora, S. Rao, and U. Vazirani. Expander Flows, Geometric Emb eddings, and Graph Partitionings. Proceedings of 36th Annual Symposium on the Theory of Computing (STOC), 222-231, 2004. [4] D. Bertsimas and J. Tsitsiklis. Introduction to Linear Optimization. IIE Transactions, 1998. [5] Y. Bartal, M. Charikar, and D. Raz, Approximating Min-Sum k-Clustering in Metric Spaces, Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), 2001. [6] Niv Buchbinder, Kamal Jain, and Seffi Naor. Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue. Proceedings of the 15th Annual European Symposium on Algorithms (ESA), 2007. [7] P. Cramton, Y. Shoham, and R. Steinb erg.f Combinatorial Auctions. MIT Press, Cambridge, MA, 2005. [8] S. Dobzinski, M. Schapira, and N. Nisan Truthful Randomized Mechanisms for Combinatorial Auctions. [19] [20] [21] [22] [23] [24] [25] Proceedings of the 38rd Annual ACM Symposium on Theory of Computing (STOC), 2006. U. Feige. On Maximizing Welfare When Utility Functions Are Subadditive. Proceedings of the 38rd Annual ACM Symposium on Theory of Computing (STOC), 2006. U. Feige, N. Immorlica, V. Mirrokni, and H. Nazerzadeh. Structural Approximations - a framework for analyzing and designing heuristics. manuscrip. U. Feige. A Threshold of ln n for Approximating Set Cover. Journal of ACM, 45(4):634-652, 1998 U. Feige, V. Mirrokni, and J. Vondrak. Maximizing Non-Monotone Submodular Functions. Proceedings of 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2007. L. Fleischer, M. Goemans, V. Mirrokni, and M. Sviridenko. Tight Approximation Algorithms for Maximum General Assignment Problems. Symposium of Discrete Algorithms (SODA), 2006. U. Feige, L. Lovasz and P. Tetali, Approximating Min ´ Sum Set Cover, Algorithmica 40(4): 219-234, 2004. M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. WH Freeman & Co New York, 1979. B. Lehmann, D. Lehmann, and N. Nisan. Combinatorial Auctions with Decreasing Marginal Utilities. Proceedings 3rd ACM Conference on Electronic Commerce (EC), 2001. D. J. Lehmann, L. O'Callaghan, and Y. Shoham. Truth revelation in approximately efficient combinatorial auctions. J. ACM, 49(5), 577-602, 2002. F. T. Leighton and S. Rao. An Approximate Max-Flow Min-Cut Theorem For Uniform Multicommodity Flow Problems with Applications to Approximation Algorithms. Proceedings of 29th Annual Symposium on Foundations of Computer Science, pages 422-431, 1988. M. Mahdian, H. Nazerzadeh, and A. Sab eri Allocating Online Advertisement Space with Unreliable Estimates Proceedings 8th ACM Conference on Electronic Commerce (EC), 2007. A. Mehta, A. Sab eri, U. Vazirani, and V. Vazirani. AdWords and Generalized Online Matching. Journal of the ACM, Volume 54 , Issue 5, 2007. Pricewaterhouse Coop ers LLP. IAB Internet Advertising Revenue Rep ort. http://www.iab.net/resources/adrevenue/pdf/IAB PwC 2006 Final.pdf ´ T. Roughgarden and E. Tardos. How Bad is Selfish Routing?. Proceedings of IEEE Symposium on Foundations of Computer Science, 93­102, 2000. T. Sandholm. Algorithm for Optimal Winner Determination in Combinatorial Auctions. Artificial Intelligence, 135:1-54, 2002. A. Schrijver. Combinatorial Optimization. Springer, 2003. D. B. West. Introduction to Graph Theory. Prentice Hal l, 2001. 177 WWW 2008 / Refereed Track: Internet Monetization - Online Advertising April 21-25, 2008 · Beijing, China APPENDIX A. PROOF OF THEOREM 3.2 Proof. We prove that claim holds even if the advertisers have large demands. We define a sp ecial case of selling banner advertisements . Consider m sets A1 , · · · , Am , each of size k; let A = m 1 Ai and n = |A|. Also consider a set i= Q of size q which is disjoint from A. Also, assume k = O(q ) and kq = o( n). Problem B(k, q , n) is defined with m advertisers. Let c = pq 2(1 - n + ). Let the bid of advertiser i, (Ii , di , bi ), b e equal to (Q Ai , ck, 1). We show that p is NP-Hard to it q approximate B(k, q , n) within a ratio of 2 n + . Consider the k-uniform regular set cover instances defined in the prop osition 3.1, for and s0 = 3. We say an instance is of typ e YES if all elements can b e covered by t disjoint sets. An instance is of typ e NO if every s s0 t sets cover at most a fraction of 1 - (1 - 1 )s + of the elet ments. We show if an algorithm can approximate problem pq B(k, q , n) within a ratio of 2 n + , then this algorithm can distinguishes b etween YES and NO instances. For the YES instances, there are t = n disjoint set which k cover all the n elements. Hence, the value in this case is at least t(k - (kc - k)) = n(2 - c). For a NO instance, any s sets, 0 s s0 t, cover at most q + (1 - (1 - 1 )s + )n elements. Therefore, the value of any s t sets is at most 2(q + (1 - (1 - 1 )s + )n) - csk. Note that t can t b e made arbitrary large ([14]); hence, we can approximate -1 (1 - 1 ) with e t with arbitrary accuracy. Thus, the value t of any s sets is at most: 2(q + (1 - e -s t B. c cc + + 1 - 2 + 2 ( 2 - 1) c 1- 2 r q =2 + n pq c Recall that 1- 2 = n + , which completes the proof. < q n FINDING A LOWER BOUND ON Here, we compute a lower b ound on the value of defined si s in (8). Taking the derivative of 2(-1-lin 2i with resp ect to +1)s - si : (2 - 1/si )(( + 1)si - ) - (2si - 1 - ln 2si )( + 1) (( + 1)si - )2 /si - 2 + ( + 1) ln 2si (12) = (( + 1)si - )2 Define f (x) = /x - 2 + ( + 1) ln 2x, x (0, 1]. The first and the second derivative of f with resp ect to x are: d f +1 =- 2 + dx x x d f 2 +1 = 3- d2 x x x2 Hence, for > 1 and x (0, 1], function f is strictly convex and takes its minimum at x = 1 . Therefore, f is + increasing in [ 1 , 1]. + If f (1) = ln 2 - (1 - ln 2) 0, then f is negative in [ 1 , 1]. Hence, (12) is decreasing in [ 1 , 1], and take its + + ln 2 minimum at 1. For 1-ln 2 , f (1) 0. Plugging in (8), 2 = (-1-lin 2 = 1 - ln 2. Therefore, for this range of , the +1)s - approximation ratio is 1-ln 2 . 2-ln 2 ln 2 For 1 < < 1-ln 2 , as we prove later, f ( 1 ) is negative. + Because f (1) is p ositive, by the intermediate value theorem, there exists a p oint x in [ 1 , 1] for which f is zero. This + p oint is the root of equation: Because f is increasing in [ 1 , 1], by convexity, x gives + the minimum value of (12). Plugging this value for into , we get (5) as a lower b ound on the approximation ratio 1+ ln 2 of 1 < < 1-ln 2 . Now we only need to show that for > 1, f ( 1 ) is + 1 negative. For x = 2 , f ( 1 ) = 2- 2+(+1) ln 1 = 0. Also, 2 f is strictly convex and takes its minimum at 1 > 1 . + 2 Therefore, f ( 1 ) < 0. + f (x) = /x - 2 + ( + 1) ln 2x = 0. + )n) - csk We find the optimum value for s by the first order conditions: 1 -s c 2 e t n - ck = 0 s = -t log s0 t t 2 (11) c Plugging s = -t log 2 in (11), the maximum value is at c c most 2(q +(1- 2 + )n)+ cn log 2 . Note that the value for any choice of m s0 t sets is negative, b ecause the total demand is more than double of the numb er of elements. Therefore, the ratio b etween the value from a NO instance and a Yes instance is at most: 2(q + (1 - + )n) + cn log n(2 - c) c 2 c 2 = q n c ++1- 2 + c 1- 2 c 2 log c 2 178