  Constraints on agent's ability to pay play a major role in auction design for
any setting where the magnitude of financial transactions is sufficiently
large. Those constraints have been traditionally modeled in mechanism design as
\emph{hard budget}, i.e., mechanism is not allowed to charge agents more than a
certain amount. Yet, real auction systems (such as Google AdWords) allow more
sophisticated constraints on agents' ability to pay, such as \emph{average
budgets}. In this work, we investigate the design of Pareto optimal and
incentive compatible auctions for agents with \emph{constrained quasi-linear
utilities}, which captures more realistic models of liquidity constraints that
the agents may have. Our result applies to a very general class of allocation
constraints known as polymatroidal environments, encompassing many settings of
interest such as multi-unit auctions, matching markets, video-on-demand and
advertisement systems.
  Our design is based Ausubel's \emph{clinching framework}. Incentive
compatibility and feasibility with respect to ability-to-pay constraints are
direct consequences of the clinching framework. Pareto-optimality, on the other
hand, is considerably more challenging, since the no-trade condition that
characterizes it depends not only on whether agents have their budgets
exhausted or not, but also on prices {at} which the goods are allocated. In
order to get a handle on those prices, we introduce novel concepts of dropping
prices and saturation. These concepts lead to our main structural result which
is a characterization of the tight sets in the clinching auction outcome and
its relation to dropping prices.
