Adwords with Unknown Budgets and Beyond

• 成果类型: Article
• 署名作者: Udwani, Rajan
• 署名单位: University of California System; University of California Berkeley
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2021.03243
• 发表日期: 2025
• 关键词: Adwords; randomized algorithms; unknown budgets; competitive ratio

摘要

In the classic Adwords problem introduced by [Mehta A, Saberi A, Vazirani U, Vazirani V (2007) Adwords and generalized online matching. J. ACM 54(5):22-es.], we have a bipartite graph between advertisers and queries. Each advertiser has a maximum budget that is known a priori. Queries are unknown a priori and arrive sequentially. When a query arrives, advertisers make bids, and we (immediately and irrevocably) decide which (if any) Ad to display based on the bids and advertiser budgets. The winning advertiser for each query pays their bid up to their remaining budget. Our goal is to maximize total budget used without any foreknowledge of the arrival sequence (which could be adversarial). We consider the setting where the online algorithm does not know the advertisers' budgets a priori and the budget of an advertiser is revealed to the algorithm only when it is exceeded. A naive greedy algorithm is 0.5 competitive for this setting, and finding an algorithm with better performance remained an open problem. We show that no deterministic algorithm has competitive ratio better than 0.5 and give the first (randomized) algorithm with strictly better performance guarantee. We show that the competitive ratio of our algorithm is at least 0.522 but also strictly less than (1 - 1/e). We present novel applications of budget oblivious algorithms in search ads and beyond. In particular, we show that our algorithm achieves the best possible performance guarantee for deterministic online matching in the presence of multichannel traffic [Manshadi V, Rodilitz S, Saban D, Suresh A (2022) Online algorithms for matching platforms with multi-channel traffic. Proc. 23rd ACMConf. Econom. Comput. (ACM, NewYork), 986-987.].