Adwords with Unknown Budgets

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. Prominent online algorithms for the Adwords problem critically rely on knowledge of budgets. We 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.