Welfare-Preserving ε -BIC to BIC Transformation with Negligible Revenue Loss
In this paper, we provide a transform from an ε -BIC mechanism into an exactly BIC mechanism without any loss of social welfare and with additive and negligible revenue loss. This is the first ε -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 ε -BIC to BIC transformations preserve social welfare but have no revenue guarantee [4], or suffer welfare loss while incurring a revenue loss with both a multiplicative and an additive term, e.g., [9, 14, 28]. The revenue loss achieved by our transformation is incomparable to these earlier approaches and can be significantly less. 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 fractional rotation step and a payment reducing step iteratively to make the mechanism Bayesian incentive compatible. We also analyze ε -expected ex-post IC (ε -EEIC) mechanisms [18]. 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.
Duke Scholars
Published In
DOI
EISSN
ISSN
ISBN
Publication Date
Volume
Start / End Page
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences
Citation
Published In
DOI
EISSN
ISSN
ISBN
Publication Date
Volume
Start / End Page
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences