  We study the online budgeted allocation (also called 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 (FOCS 2005). 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. A simple example is an advertising campaign that is
constrained by an overall budget but is also accompanied by a set of
sub-budgets for each target demographic. 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 paper, 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. However for
our main result, we observe that in many real-world scenarios (as in the above
example), multi-tier budgets have a laminar structure, since most relevant
consumer or product classifications are hierarchical. For laminar budgets, we
obtain a competitive ratio of e/(e-1) in the small bids case, which matches the
best known ADWORDS result for single budgets. Our algorithm has a primal-dual
structure and generalizes the primal-dual analysis for single- budget ADWORDS
first given by Buchbinder, Jain, and Naor (ESA 2007).
