Asymptotically Optimal Algorithm for Stochastic Adwords

In this paper we consider the adwords problem in the unknown distribution model. We consider the case where the budget to bid ratio k is at least 2, and give improved competitive ratios. Earlier results had competitive ratios better than 1 − 1/e only for “large enough” k, while our competitive ratio increases continuously with k. For k = 2 the competitive ratio we get is 0.729 and it is 0.9 for k = 16. We also improve the asymptotic competitive ratio for large k from 1 − O( p log n/k) to 1 − O( p 1/k), thus removing any dependence on n, the number of advertisers. This ratio is optimal, even with known distributions. That is, even if an algorithm is tailored to the distribution, it cannot get a competitive ratio of 1 − o( p 1/k), whereas our algorithm does not depend on the distribution. The algorithm is rather simple, it computes a score for every advertiser based on his original budget, the remaining budget and the remaining number of steps in the algorithm and assigns a query to the advertiser with the highest bid plus his score. The analysis is based on a “hybrid argument” that considers algorithms that are part actual, part hypothetical, to prove that our (actual) algorithm is better than a completely hypothetical algorithm whose performance is easy to analyze.