  Combinatorial Auctions are a central problem in Algorithmic Mechanism Design:
pricing and allocating goods to buyers with complex preferences in order to
maximize some desired objective (e.g., social welfare, revenue, or profit). The
problem has been well-studied in the case of limited supply (one copy of each
item), and in the case of digital goods (the seller can produce additional
copies at no cost). Yet in the case of resources---oil, labor, computing
cycles, etc.---neither of these abstractions is just right: additional supplies
of these resources can be found, but at increasing difficulty (marginal cost)
as resources are depleted.
  In this work, we initiate the study of the algorithmic mechanism design
problem of combinatorial pricing under increasing marginal cost. The goal is to
sell these goods to buyers with unknown and arbitrary combinatorial valuation
functions to maximize either the social welfare, or the seller's profit;
specifically we focus on the setting of \emph{posted item prices} with buyers
arriving online. We give algorithms that achieve {\em constant factor}
approximations for a class of natural cost functions---linear, low-degree
polynomial, logarithmic---and that give logarithmic approximations for more
general increasing marginal cost functions (along with a necessary additive
loss). We show that these bounds are essentially best possible for these
settings.
