cs.GT
Welfare Preserving varepsilon BIC to BIC Transformation with Negligible Revenue Loss. In this paper, we provide a transform from an varepsilon BIC mechanism into an exactly BIC mechanism without any loss of social welfare and with additive and negligible revenue loss. This is the first varepsilon BIC to BIC transformation that preserves welfare and provides negligible revenue loss. The revenue loss bound is tight given the requirement to maintain social welfare. Previous varepsilon BIC to BIC transformations preserve social welfare but have no revenue guarantee citep BeiHuang11 , or suffer welfare loss while incurring a revenue loss with both a multiplicative and an additive term, e.g., citet DasWeinberg12, Rubinstein18, Cai19 . The revenue loss achieved by our transformation is incomparable to these earlier approaches and can be significantly less. newnew Our approach is different from the previous replica surrogate matching methods and we directly make use of a directed and weighted type graph (induced by the types' regret), one for each agent. The transformation runs a emph fractional rotation step and a emph payment reducing step iteratively to make the mechanism Bayesian incentive compatible. We also analyze varepsilon expected ex post IC ( varepsilon EEIC) mechanisms citep DuettingFJLLP12 . We provide a welfare preserving transformation in this setting with the same revenue loss guarantee for uniform type distributions and give an impossibility result for non uniform distributions. We apply the transform to linear programming based and machine learning based methods of automated mechanism design.