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

@article{Conitzer2020WelfarePreservingT, title={Welfare-Preserving $\epsilon$-BIC to BIC Transformation with Negligible Revenue Loss}, author={Vincent Conitzer and Zhe Feng and David C. Parkes and Eric Sodomka}, journal={ArXiv}, year={2020}, volume={abs/2007.09579} }

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 (Bei and Huang, 2011), or suffer welfare… Expand

#### One Citation

Technical Report Column

- Computer Science
- SIGACT News
- 2020

This report presents a meta-modelling system that automates the very labor-intensive and therefore time-heavy and therefore expensive and expensive process of manually cataloging and cataloging all the components of a smart phone. Expand

#### References

SHOWING 1-10 OF 32 REFERENCES

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

- Computer Science
- SODA
- 2021

A new polynomial time transformation is provided that converts any ε-BIC mechanism to an exactly BIC mechanism with only a negligible revenue loss and a new algorithm is developed that can accommodate arbitrary edge weights. Expand

Understanding Incentives: Mechanism Design Becomes Algorithm Design

- Computer Science, Economics
- 2013 IEEE 54th Annual Symposium on Foundations of Computer Science
- 2013

We provide a computationally efficient black-box reduction from mechanism design to algorithm design in very general settings. Specifically, we give an approximation-preserving reduction from… Expand

Bayesian incentive compatibility via fractional assignments

- Computer Science, Mathematics
- SODA '11
- 2011

A black-box reduction is proposed for designing BIC multi-parameter mechanisms that converts any algorithm into an ε-BIC mechanism with only marginal loss in social welfare and achieves constant approximation. Expand

Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity

- Computer Science, Mathematics
- EC
- 2015

The main result is to derive a bound on how bad this degradation can be (and dub such a bound a proof of approximate revenue monotonicity); it is shown that better bounds on approximatemonotonicity imply a better analysis of the authors' simple mechanisms. Expand

Optimal Multi-dimensional Mechanism Design: Reducing Revenue to Welfare Maximization

- Computer Science, Economics
- 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science
- 2012

The results are computationally efficient for all multidimensional settings where the bidders are additive, or can be efficiently mapped to be additive, albeit the feasibility and demand constraints may still remain arbitrary combinatorial. Expand

Efficiency-Revenue Trade-Offs in Auctions

- Computer Science, Economics
- ICALP
- 2012

This work provides polynomial-time deterministic mechanisms that approximate with arbitrary precision any point of the trade-off between these two fundamental objectives for the case of two bidders, even when the valuations are correlated arbitrarily. Expand

Simple mechanisms for subadditive buyers via duality

- Computer Science, Mathematics
- STOC
- 2017

It is proved that the better of the following two simple, deterministic and Dominant Strategy Incentive Compatible mechanisms, a sequential posted price mechanism or an anonymous sequential post price mechanism with entry fee, achieves a constant fraction of the optimal revenue among all randomized, Bayesian Incentivistic mechanisms, when buyers' valuations are XOS over independent items. Expand

Payment Rules through Discriminant-Based Classifiers

- Computer Science, Mathematics
- ACM Trans. Economics and Comput.
- 2015

By replacing the incentive compatibility requirement with the goal of minimizing expected ex post regret, this work is able to adapt statistical machine learning techniques to the design of payment rules, applicable to domains with multi-dimensional types and situations where computational efficiency is a concern. Expand

Strategy-Proofness in the Large

- Economics, Computer Science
- 2017

We propose a criterion of approximate incentive compatibility, strategy-proofness in the large (SP-L), and argue that it is a useful second-best to exact strategy-proofness (SP) for market design.… Expand

Dominant-Strategy versus Bayesian Multi-item Auctions: Maximum Revenue Determination and Comparison

- Economics, Computer Science
- EC
- 2017

This paper derives exact formulas for the maximum revenue when k=2 and Fij are any IID distributions on support of size 2, for both the dominant-strategy (DIC) and the Bayesian (BIC) implementations. Expand