# Welfare-Preserving varepsilon-BIC to BIC Transformation with Negligible Revenue Loss

arXiv: https://arxiv.org/abs/2007.09579 · HTML: https://mlsanity.com/paper/2007.09579/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jul 2020.

## Built on by (most cited first, 2 of 2)

- [GemNet: Menu-Based, Strategy-Proof Multi-Bidder Auctions Through Deep Learning](https://mlsanity.com/paper/2406.07428/) (2024)
- [Data Market Design through Deep Learning](https://mlsanity.com/paper/2310.20096/) (2023)

## Abstract (arXiv)

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~citepBeiHuang11, or suffer welfare loss while incurring a revenue loss with both a multiplicative and an additive term, e.g.,~citetDasWeinberg12, Rubinstein18, Cai19. The revenue loss achieved by our transformation is incomparable to these earlier approaches and can be significantly less. newnewOur 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 fractional rotation step and a payment reducing step iteratively to make the mechanism Bayesian incentive compatible. We also analyze varepsilon-expected ex-post IC (varepsilon-EEIC) mechanisms~citepDuettingFJLLP12. 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.