CATS-Mar-16-2016
Title[edit]
Online Budgeted Allocation with General Budgets
Speaker[edit]
Debmalya Panigrahi
Abstract[edit]
We study the online budgeted allocation or Adwords problem, where a set of impressions arriving online are allocated to a set of budget-constrained advertisers to maximize revenue. Motivated by connections to Internet advertising, several variants of this problem have been studied since the seminal work of Mehta, Saberi, Vazirani, and Vazirani (JACM 2007). However, this entire body of work focuses on a single budget for every advertising campaign, whereas in order to fully represent the actual agenda of an advertiser, an advertising budget should be expressible over multiple tiers of user-attribute granularity. In such a contract scheme, an advertiser can specify their true user-targeting goals, allowing the publisher to fulfill them through relevant allocations.
In this talk, we give a complete characterization of the Adwords problem for general advertising budgets. In the most general setting, we show that, unlike in the single-budget Adwords problem, obtaining a constant competitive ratio is impossible and give asymptotically tight upper and lower bounds. In contrast, we observe that in most real-world scenarios, multi-tier budgets have a hierarchical structure, and obtain a competitive ratio of e/(e-1) for this scenario, thereby matching the optimal result for single budgets.
