Conference articles PUBLISHED

1. Conitzer, V; Feng, Z; Parkes, DC; Sodomka, E, Welfare-Preserving ε -BIC to BIC Transformation with Negligible Revenue Loss, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13112 LNCS (January, 2022), pp. 76-94 [doi].
   (last updated on 2024/04/24)

   Abstract:
   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.