Welfare maximization with production costs: A primal dual approach

摘要

We study online auctions with production costs using an online primal dual framework. The seller allocates items to buyers and can produce multiple copies of each item subject to a non-decreasing marginal cost per copy. The buyers have arbitrary valuation functions and arrive one by one online in some arbitrary order. The goal is to design an online mechanism that maximizes the social welfare, that is, the sum of the buyers' values less the total production cost. For any strictly convex and differentiable production cost function, we characterize the optimal competitive ratio achievable by online mechanisms and, more generally, algorithms without incentive guarantees. We show that online posted pricing mechanisms, which are incentive compatible, can achieve competitive ratios arbitrarily close to the optimal, and construct lower bound instances on which no online algorithms, not necessarily incentive compatible, can do better. (C) 2018 Elsevier Inc. All rights reserved.