Asymptotically optimal algorithm for stochastic adwords
Asymptotically optimal algorithm for stochastic adwords
复制标题
随机adwords的渐近最优算法
DOI：
10.1145/2229012.2229043
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Y. Azar
中科院分区：
文献类型：
--
作者：
Nikhil R. Devanur;Balasubramanian Sivan;Y. Azar
本文研究了分布未知模型下的广告词问题。我们考虑的情况下，预算投标比k至少是2，并给出了改进的竞争比。早期的结果只有在k“足够大”时才有比1-1/e更好的竞争比，而我们的竞争比随着k的增加而不断增加。当k=2时，我们得到的竞争比为0.729，当k=16时为0.9。我们还提高了大k的渐近竞争比从1 - O（1-log n/k）到1 - O（1 - 1/k），从而消除了对广告商数量n的任何依赖。这个比例是最佳的，即使是已知的分布。也就是说，即使一个算法是针对分布定制的，它也不能得到1 - o（1/k）的竞争比，而我们的算法不依赖于分布。该算法相当简单，它根据每个广告客户的原始预算、剩余预算和算法中剩余的步骤数计算得分，并将查询分配给出价最高的广告客户加上他的得分。分析是基于一个“混合参数”，认为算法是部分实际的，部分假设，以证明我们的（实际）算法比一个完全假设的算法，其性能是很容易分析。
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(√log n/k) to 1 - O(√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(√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.