Scholarlink

<p>Motivated by recent insights into the online bipartite matching problem (<span>OBM</span>), our goal was to extend the optimal algorithm for it, namely <span>Ranking</span>, all the way to the special case of adwords problem, called <span>Small</span>, in which bids are small compared to budgets; the latter has been of considerable practical significance in ad auctions (Mehta et al. in J. ACM (JACM) 54:22-es, 2007). This approach would yield a <i>budget-oblivious algorithm</i>, i.e., the algorithm would not need to know budgets of advertisers and therefore could be used in autobidding platforms. We present such an algorithm for <span>Single-Valued</span>, a special case of <span>Small</span>. However, an extension to <span>Small</span> failed because of failure of the <i>No-Surpassing Property</i>. Since the probabilistic ideas underlying our algorithm are quite substantial, we have stated them formally, after assuming the No-Surpassing Property, and we leave the open problem of removing this assumption.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Towards a Practical, Budget-Oblivious Algorithm for the Adwords Problem Under Small Bids

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年2月19日

查看全文
  • Vijay V. Vazirani

摘要

Motivated by recent insights into the online bipartite matching problem (OBM), our goal was to extend the optimal algorithm for it, namely Ranking, all the way to the special case of adwords problem, called Small, in which bids are small compared to budgets; the latter has been of considerable practical significance in ad auctions (Mehta et al. in J. ACM (JACM) 54:22-es, 2007). This approach would yield a budget-oblivious algorithm, i.e., the algorithm would not need to know budgets of advertisers and therefore could be used in autobidding platforms. We present such an algorithm for Single-Valued, a special case of Small. However, an extension to Small failed because of failure of the No-Surpassing Property. Since the probabilistic ideas underlying our algorithm are quite substantial, we have stated them formally, after assuming the No-Surpassing Property, and we leave the open problem of removing this assumption.