An Efficient ∊-BIC to BIC Transformation and Its Application to Black-Box Reduction in Revenue Maximization

We consider the black-box reduction from multidimensional revenue maximization to virtual welfare maximization. Cai et al. [12, 13, 14, 15] show a polynomial-time approximation-preserving reduction, however, the mechanism produced by their reduction is only approximately Bayesian incentive compatible (∊-BIC). We provide two new polynomial time transformations that convert any ∊-BIC mechanism to an exactly BIC mechanism with only a negligible revenue loss. Our first transformation applies to any mechanism design setting with downward-closed outcome space and only requires sample access to the agents' type distributions. Our second transformation applies to the fully general outcome space, removing the downward-closed assumption, but requires full access to the agents' type distributions. Both transformations only require query access to the original ∊-BIC mechanism. Other ∊-BIC to BIC transformations for revenue exist in the literature [23, 36, 18] but all require exponential time to run in both of the settings we consider. As an application of our transformations, we improve the reduction by Cai et al. [12, 13, 14, 15] to generate an exactly BIC mechanism.