Online Adwords Allocation Shoshana Neuburger May 6, 2009 1Overview Many search engines auction the advertising space alongside search results. When Google inter- viewed Amin Saberi in 2004, their advertisement model became the focus of a new research area. Although he did not land the job, the interview was an important stimulus in his academic ca- reer. Upon his return to Georgia Tech, Saberi shared the question with another graduate student, Aranyak Mehta, and their thesis advisor, Vijay Vazirani. Vazirani recognized a connection between this new problem and the online bipartite matching problem, a problem he had solved 14 years earllier. When the Vazirani brothers and Karp proved a solution to it in 1990, the researchers saw online matching as a beautiful research problem. Umesh Vazirani says. “At the time, we had no idea it would turn out to have practical value.” 7 Based on previous algorithms for online allocation, Mehta et. al. devised an innovative deterministic algorithm. They prove the optimality of their algorithm in the general case when there is no prior knowledge about the input queries. The primary assumption of the algorithm is that bids are small compared to an advertisers daily budget. 5 Together with Gagan Goel, Mehta explored the Adwords problem when assumptions can be made about the distribution of search queries. They showed that a simple greedy algorithm achieves the same competitive ratio as the more complex algorithm of Mehta et. al. in the random input model, as wall as in i.i.d. input models. This factor is 1 1 e. 1 2Online Bipartite Matching The online bipartite matching problem is classically described with the following problem.A matchmaker and n boys are gathered in a room. n girls appear, one at a time. Each girl has a list of boys who are acceptable to her, which she reveals to the matchmaker as she appears. The matchmaker immediately matches the new girl to one of the boys on her list, if any of them are available. The goal is to maximize the number of matches. Vazirani, Vazirani, and Karp devised a randomized algorithm that achieves the optimal competitive ratio of 1 1 e. Online bipartite matching can also be described as the task of fi nding a matching of minimum weight in a bipartite graph. An edge connects a server node to a request it can handle. The set of 1 server nodes is known, while the set of requests arrive one at a time. As a node arrives, the weights of all edges incident on the node, i.e., servers that can fulfi ll the request, are divulged. Each server can service a single request. The task is to fi nd a minimum weight matching of requests to servers online as each node arrives. 3 The eff ectiveness of an online algorithm is measured by competitive analysis. We say an algorithm ALG is -competitive if the ratio between its performance and the optimal offl ine performance, OPT, is bounded by . In other words, ALG(I) OPT(I) for any instance of the problem I. Karp et. al. describe an optimal randomized algorithm for online bipartite matching in 4. The input is represented as adjacency matrix B for G(U,V,E), a bipartite graph on 2n vertices that contains a perfect matching. We can let the rows represent the nodes in U, the boys, and the columns represent the nodes in V, the girls. Then, an entry in the adjacency matrix B, bij, is a boolean value. bij= 1, if boy i is acceptable to girl j, 0, otherwise. The online matching is constructed while the matrix is revealed column-by-column. We can consider a simple greedy algorithm. greedy matches a girl whenever possible. greedy achieves a maximal matching of size at least n/2. An adaptive adversary can limit any deterministic algorithm to a matching of size n/2. As an example, let the fi rst n/2 columns contain all ones and the last n/2 columns contain ones only in those rows which are matched by the deterministic algorithm in the fi rst n/2 steps. Thus, the competitive ratio of greedy is 1 2. The randomized algorithm ranking of 4 achieves a competitive ratio of 1 1 e. The algorithm fi xes a random permutation of the fi rst set of vertices, assigning a rank to each boy. As each girl arrives, she is matched to the eligible boy (if any) of highest rank. Karp et. al. proved that this algorithm is optimal for online bipartite matching. Online bipartite matching is a special case of the Adwords allocation problem in which advertisers are restricted to unit bids and unit daily budgets. For this special case, the ranking algorithm matches ads as they arrive with a competitive factor of 1 1 e. 3Online b-matching The work of Karp, Vazirani, and Vazirani was extended to b-matching by Bala Kalyanasundaram and Kirk Pruhs in 2. In a b-matching prolem, each server can be matched to several requests within a predetermined service limit. This is unlike the assignment problem in which a server vertex is matched only once. A b-matching problem seeks to allocate requests to servers so that the maximum number o