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

Abstract 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.