TY - GEN

T1 - Welfare and profit maximization with production costs

AU - Blum, Avrim

AU - Gupta, Anupam

AU - Mansour, Yishay

AU - Sharma, Ankit

PY - 2011

Y1 - 2011

N2 - 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 posted item prices with buyers arriving online. We give algorithms that achieve 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.

AB - 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 posted item prices with buyers arriving online. We give algorithms that achieve 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.

UR - http://www.scopus.com/inward/record.url?scp=84863324294&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84863324294&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2011.68

DO - 10.1109/FOCS.2011.68

M3 - Conference contribution

AN - SCOPUS:84863324294

SN - 9780769545714

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 77

EP - 86

BT - Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011

PB - IEEE Computer Society

T2 - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011

Y2 - 22 October 2011 through 25 October 2011

ER -