Welfare maximization with production costs: A primal dual approach

• 成果类型: Article
• 署名作者: Huang, Zhiyi; Kim, Anthony
• 署名单位: University of Hong Kong; Stanford University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2018.03.003
• 发表日期: 2019
• 页码: 648-667
• 关键词: Combinatorial auctions; Online algorithms; mechanism design; Competitive analysis; Posted pricing mechanisms; Welfare maximization

摘要

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.