Reducing Revenue to Welfare Maximization: Approximation Algorithms and other Generalizations

DOI10.1137/1.9781611973105.42MaRDI QIDQ5741750zbMATH OpenOpenAlexFDO

Authors Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg

Publication date 15 May 2019

Published in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.4000

zbMATH Keywords

approximation algorithmsmulti-dimensional Bayesian auctionwelfare maximization

Mathematics Subject Classification ID

Approximation algorithms (68W25) Welfare economics (91B15) Auctions, bargaining, bidding and selling, and other market models (91B26)

Abstract: It was recently shown in [1] that revenue optimization can be computationally efficiently reduced to welfare optimization in all multi-dimensional Bayesian auction problems with arbitrary (possibly combinatorial) feasibility constraints and independent additive bidders with arbitrary (possibly combinatorial) demand constraints. This reduction provides a poly-time solution to the optimal mechanism design problem in all auction settings where welfare optimization can be solved efficiently, but it is fragile to approximation and cannot provide solutions to settings where welfare maximization can only be tractably approximated. In this paper, we extend the reduction to accommodate approximation algorithms, providing an approximation preserving reduction from (truthful) revenue maximization to (not necessarily truthful) welfare maximization. The mechanisms output by our reduction choose allocations via black-box calls to welfare approximation on randomly selected inputs, thereby generalizing also our earlier structural results on optimal multi-dimensional mechanisms to approximately optimal mechanisms. Unlike [2], our results here are obtained through novel uses of the Ellipsoid algorithm and other optimization techniques over {em non-convex regions}.

Recommendations

• Approximating the revenue maximization problem with sharp demands
• Approximating the revenue maximization problem with sharp demands
• On revenue-maximizing mechanisms assuming convex costs
• Approximation algorithms for a generalization of the maximum budget allocation
• Good approximations to maximin allocations
• scientific article; zbMATH DE number 7651150
• Reductions of approximate linear programs for network revenue management
• On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP

Cited in

(10)

• Welfare-preserving \(\varepsilon \)-BIC to BIC transformation with negligible revenue loss
• A simple mechanism for a budget-constrained buyer
• Optimal mechanisms for selling two items to a single buyer having uniformly distributed valuations
• On optimal mechanisms in the two-item single-buyer unit-demand setting
• A Duality-Based Unified Approach to Bayesian Mechanism Design
• scientific article; zbMATH DE number 7204414 (Why is no real title available?)
• Black-box randomized reductions in algorithmic mechanism design
• Walrasian pricing in multi-unit auctions
• How to sell information optimally: an algorithmic study
• An algorithmic framework for black-box reductions from Bayesian mechanism design to algorithm design

This page was built for publication: Reducing Revenue to Welfare Maximization: Approximation Algorithms and other Generalizations

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