It was recently shown that revenue optimization can be efficiently reduced to welfare optimization in all multi-dimensional Bayesian auction problems. In this paper, we ex-tend 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.
Auto282
Reducing Revenue to Welfare Maximization: Approximation Algorithms and other Generalizations