最近在中表明， 在所有具有任意（可能的组合）可行性约束和受任意（可能组合）需求约束的独立添加的投标人的多维贝叶斯拍卖问题中，收入最优化可以从计算上有效减持至福利最优化。这种减持在所有拍卖假设中给可以得到有效解决的最优化机制设计问题提供了一种多项式时间解决方案，但它的这种逼近很脆弱且不能给这种福利最大化只能易于逼近的假设提供解决方案。在本文中，我们扩展了这种减持以适应逼近算法，提供一种维护从（真实）收益最大化到（非必须真实）福利最大化的减持的逼近。根据随机选取输入，这种减持机制的输出通过暗箱电话选择福利逼近的分配，从而也基于最优多维机制将我们先前的结构性结果归纳至逼近最优化机制。不同于 ，我们在此的结果是通过椭球算法的新颖用途和其他通过非凸区域最优化技术而得到。
It was recently shown in  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 , our results here are obtained through novel uses of the Ellipsoid algorithm and other optimization techniques over non-convex regions.
ABOUT THE AUTHOR
Associate Professor at MIT's Electrical Engineering and Computer Science department, a member of CSAIL, and affiliated with LIDS and ORC.