Stochastic Budget Optimization in Internet Advertising
Stochastic Budget Optimization in Internet Advertising
复制标题
DOI：
10.1007/s00453-012-9614-x
复制
发表时间：
2010-01
期刊：
影响因子：
1.1
通讯作者：
B. Dasgupta;S. Muthukrishnan
中科院分区：
文献类型：
--
作者：
B. Dasgupta;S. Muthukrishnan
互联网广告是一个复杂的游戏，许多广告商“玩”，以优化他们的投资回报。广告有许多“目标”，每个“目标”都有一系列游戏，可能涉及不同的玩家群体。在本文中，我们研究了广告客户如何在这些“目标”之间分配预算的问题。特别地，我们把重点放在制定他们的最佳应对策略作为一个优化问题。广告商有一组关键字（“目标”）和一些关于未来的随机信息，即成本与点击组合的概率分布。这总结了假设其他玩家的策略是固定的世界的潜在状态。然后，最佳响应可以抽象为随机预算优化问题，以找出如何在这些关键字上分配给定的预算以最大化预期的点击次数。我们提出了这些问题的第一个已知的非平凡多对数近似，以及第一个已知的在涉及的各种参数中获得优于对数近似比率的硬度结果。我们还确定了这些实际问题的几个特殊情况，例如固定数量的场景或与成本相关的多项式大小的参数，这些问题可以在多项式时间内或使用改进的近似比率来解决。带情景的随机预算优化具有复杂的技术结构。我们的近似和硬度结果来自于将这些问题与其中固有的一种特殊类型的（0/1，二部）二次规划联系起来。我们的研究回答了作者提出的一些开放问题（算法，58(4):1022-1044,2010）。
Internet advertising is a sophisticated game in which the many advertisers “play” to optimize their return on investment. There are many “targets” for the advertisements, and each “target” has a collection of games with a potentially different set of players involved. In this paper, we study the problem of how advertisers allocate their budget across these “targets”. In particular, we focus on formulating theirbest responsestrategy as an optimization problem. Advertisers have a set of keywords (“targets”) and some stochastic information about the future, namely a probability distribution overscenariosof cost vs click combinations. This summarizes the potential states of the world assuming that the strategies of other players are fixed. Then, the best response can be abstracted asstochastic budget optimizationproblems to figure out how to spread a given budget across these keywords to maximize the expected number of clicks.We present thefirst knownnon-trivial poly-logarithmic approximation for these problems as well as the first known hardness results of getting better than logarithmic approximation ratios in the various parameters involved. We also identify several special cases of these problems of practical interest, such as with fixed number of scenarios or with polynomial-sized parameters related to cost, which are solvable either in polynomial time or with improved approximation ratios. Stochastic budget optimization with scenarios has sophisticated technical structure. Our approximation and hardness results come from relating these problems to a special type of (0/1, bipartite) quadratic programs inherent in them. Our research answers some open problems raised by the authors (in Algorithmica, 58(4):1022–1044, 2010).