We study online combinatorial auctions with production costs proposed by Blum
et al. using the online primal dual framework. In this model, buyers arrive
online, and the seller can produce multiple copies of each item subject to a
non-decreasing marginal cost per copy. The goal is to allocate items to
maximize social welfare less total production cost. For arbitrary (strictly
convex and differentiable) production cost functions, we characterize the
optimal competitive ratio achievable by online mechanisms/algorithms. 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. Our positive results improve or match the results in
several previous work, e.g., Bartal et al., Blum et al., and Buchbinder and
Gonen. Our lower bounds apply to randomized algorithms and resolve an open
problem by Buchbinder and Gonen.

本文研究使用在线主次对偶框架的生产成本拍卖问题，对于任意（严格凸可微的）生产成本函数，表征了在线机制 / 算法可实现的最优竞争比率，并构建了下界实例，其中在线张贴定价机制可以实现接近最优的竞争比率。