Welfare maximization with production costs: a primal dual approach

DOI10.1016/J.GEB.2018.03.003MaRDI QIDQ2278952zbMATH OpenOpenAlexWikidataFDO

Authors Zhiyi Huang, Anthony Kim

Publication date 12 December 2019

Published in Games and Economic Behavior (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.4384, http://hdl.handle.net/10722/209631

zbMATH Keywords

combinatorial auctionscompetitive analysismechanism designonline algorithmsposted pricing mechanismswelfare maximization

Mathematics Subject Classification ID

Mechanism design theory (91B03) Welfare economics (91B15) Auctions, bargaining, bidding and selling, and other market models (91B26)

Abstract: 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.

Recommendations

• Welfare maximization with production costs: a primal dual approach
• Welfare and profit maximization with production costs
• scientific article; zbMATH DE number 4125173
• Welfare bounds in the cooperative production problem
• scientific article; zbMATH DE number 4060945
• Dual preference in Leontief production problem and its extension
• Duality of welfare and profit maximization
• Social welfare and profit maximization from revealed preferences
• Optimal allocation of a fixed production under price uncertainty
• Drèze equilibria and welfare maxima

Cites work

• Combinatorial auctions
• Dynamic and nonuniform pricing strategies for revenue maximization
• Fast algorithms for online stochastic convex programming
• From convex optimization to randomized mechanisms, toward optimal combinatorial auctions
• Incentive compatible mulit-unit combinatorial auctions: a primal dual approach
• Lagrangian duality in online scheduling with resource augmentation and speed scaling
• Limitations of randomized mechanisms for combinatorial auctions
• Multi-parameter mechanism design and sequential posted pricing
• Online Energy Storage Management: an Algorithmic Approach.
• Online matching with concave returns
• Online primal-dual for non-linear optimization with applications to speed scaling
• Optimal approximation for the submodular welfare problem in the value oracle model
• Primal Dual Gives Almost Optimal Energy Efficient Online Algorithms
• Resource augmentation for weighted flow-time explained by dual fitting
• Robust price of anarchy bounds via LP and Fenchel duality
• Tatonnement beyond gross substitutes? Gradient descent to the rescue
• The Design of Competitive Online Algorithms via a Primal—Dual Approach
• Towards polynomial simplex-like algorithms for market equilibria
• Truthful and Near-Optimal Mechanism Design via Linear Programming
• Welfare and profit maximization with production costs
• Welfare maximization with production costs: a primal dual approach

Cited in

(3)

• Dual preference in Leontief production problem and its extension
• Welfare maximization with production costs: a primal dual approach
• Welfare and profit maximization with production costs

This page was built for publication: Welfare maximization with production costs: a primal dual approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2278952)