  A central issue in applying auction theory in practice is the problem of
dealing with budget-constrained agents. A desirable goal in practice is to
design incentive compatible, individually rational, and Pareto optimal auctions
while respecting the budget constraints. Achieving this goal is particularly
challenging in the presence of nontrivial combinatorial constraints over the
set of feasible allocations.
  Toward this goal and motivated by AdWords auctions, we present an auction for
{\em polymatroidal} environments satisfying the above properties. Our auction
employs a novel clinching technique with a clean geometric description and only
needs an oracle access to the submodular function defining the polymatroid. As
a result, this auction not only simplifies and generalizes all previous
results, it applies to several new applications including AdWords Auctions,
bandwidth markets, and video on demand. In particular, our characterization of
the AdWords auction as polymatroidal constraints might be of independent
interest. This allows us to design the first mechanism for Ad Auctions taking
into account simultaneously budgets, multiple keywords and multiple slots.
  We show that it is impossible to extend this result to generic polyhedral
constraints. This also implies an impossibility result for multi-unit auctions
with decreasing marginal utilities in the presence of budget constraints.
