References & Citations
Computer Science > Data Structures and Algorithms
Title: Adwords with Unknown Budgets
(Submitted on 1 Oct 2021 (v1), revised 19 Jul 2022 (this version, v2), latest version 28 Mar 2024 (v5))
Abstract: Motivated by applications in automated budget optimization, we consider the Adwords problem of Mehta et al. (2005) with unknown advertiser budgets. In this setting, the budget of an advertiser is revealed to the algorithm only when it is exceeded. An algorithm that is oblivious to budgets gives an Ad platform the flexibility to adjust budgets in real-time which, we argue, has tangible benefits. We show that when budgets are unknown, no deterministic algorithm can have competitive ratio better than 0.5 and give the first budget oblivious algorithm for Adwords with competitive ratio guarantee of at least $0.522$ (better than greedy) against an offline algorithm that knows bids and budgets.
Submission history
From: Rajan Udwani [view email][v1] Fri, 1 Oct 2021 16:12:37 GMT (85kb,D)
[v2] Tue, 19 Jul 2022 00:03:07 GMT (89kb,D)
[v3] Thu, 3 Nov 2022 18:20:32 GMT (112kb,D)
[v4] Mon, 3 Jul 2023 23:45:20 GMT (108kb,D)
[v5] Thu, 28 Mar 2024 06:12:57 GMT (121kb,D)
Link back to: arXiv, form interface, contact.