Lune

SODA2021Top-tier venue

An Efficient ∊-BIC to BIC Transformation and Its Application to Black-Box Reduction in Revenue Maximization

Yang Cai, Argyris Oikonomou, Grigoris Velegkas, Mingfei Zhao

Abstract

We consider the black-box reduction from multidimensional revenue maximization to virtual welfare maximization. Cai et al. [12, 13, 14, 15] show a polynomial-time approximation-preserving reduction, however, the mechanism produced by their reduction is only approximately Bayesian incentive compatible (∊-BIC). We provide two new polynomial time transformations that convert any ∊-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 ∊-BIC mechanism. Other ∊-BIC to BIC transformations for revenue exist in the literature [23, 36, 18] 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. [12, 13, 14, 15] to generate an exactly BIC mechanism.

Ask Lune

Know where this paper stands in minutes, not an afternoon.

Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.

8 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

its abstract · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Mechanism Design via the Interim Relaxation cites On the Robustness of Mechanism Design under Total Variation Distance
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers8

  1. Auction Learning as a Two-Player GameJad Rahme, Samy Jelassi, S. Matthew WeinbergICLR 2021 · 54 citations
  2. Data Market Design through Deep LearningSai Srivatsa Ravindranath, Yanchen Jiang, David C. ParkesNeurIPS 2023 · 17 citations
  3. Computing simple mechanisms: Lift-and-round over marginal reduced formsYang Cai, Argyris Oikonomou, Mingfei ZhaoSTOC 2022 · 6 citations
  4. On the Robustness of Mechanism Design under Total Variation DistanceAnuran Makur, Marios Mertzanidis, Alexandros Psomas, Athina TerzoglouNeurIPS 2023 · 4 citations
  5. Mechanism Design via the Interim RelaxationKshipra Bhawalkar, Marios Mertzanidis, Divyarthi Mohan, Alexandros PsomasNeurIPS 2025 · 2 citations

Related papers

  1. Limitations of Incentive Compatibility on Discrete Type SpacesTaylor Lundy, Hu FuAAAI 2020
  2. A Reduction from Multi-Parameter to Single-Parameter Bayesian Contract DesignMatteo Castiglioni, Junjie Chen, Minming Li, Haifeng Xu et al.SODA 2025 · 5 citations
  3. Efficient two-sided markets with limited informationPaul Dütting, Federico Fusco, Philip Lazos, Stefano Leonardi et al.STOC 2021 · 18 citations
  4. Characterization of Incentive Compatibility of an Ex-ante Constrained PlayerBonan Ni, Pingzhong TangAAAI 2022 · 1 citation
  5. Bulow-Klemperer-Style Results for Welfare Maximization in Two-Sided MarketsMoshe Babaioff, Kira Goldner, Yannai A. GonczarowskiSODA 2020 · 12 citations
Dusk over the sea between two cliffs drawn in fine vertical lines