An Efficient \(\varepsilon\)-BIC to BIC Transformation and Its Application to Black-Box Reduction in Revenue Maximization

We consider the black-box reduction from multi-dimensional revenue maximization to virtual welfare maximization. Cai et al. show a polynomial-time approximation-preserving reduction, however, the mechanism produced by their reduction is only approximately Bayesian incentive compatible (\(\varepsilon...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-11
Main Authors: Cai, Yang, Oikonomou, Argyris, Velegkas, Grigoris, Zhao, Mingfei
Format: Article
Language:English
Subjects:
Maximization
Optimization
Polynomials
Reduction
Revenue
Transformations
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the black-box reduction from multi-dimensional revenue maximization to virtual welfare maximization. Cai et al. show a polynomial-time approximation-preserving reduction, however, the mechanism produced by their reduction is only approximately Bayesian incentive compatible (\(\varepsilon\)-BIC). We provide two new polynomial time transformations that convert any \(\varepsilon\)-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 \(\varepsilon\)-BIC mechanism. Other \(\varepsilon\)-BIC to BIC transformations for revenue exist in the literature 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. to generate an exactly BIC mechanism.
ISSN:2331-8422