@inproceedings{lucier2013cost-recovering,
author = {Lucier, Brendan},
title = {Cost-recovering bayesian algorithmic mechanism design},
series = {EC '13},
booktitle = {Proceedings of the fourteenth ACM conference on Electronic commerce},
year = {2013},
month = {June},
abstract = {We study the design of Bayesian incentive compatible mechanisms in single parameter domains, for the objective of optimizing social efficiency as measured by social cost. In the problems we consider, a group of participants compete to receive service from a mechanism that can provide such services at a cost. The mechanism wishes to choose which agents to serve in order to maximize social efficiency, but is not willing to suffer an expected loss: the agents' payments should cover the cost of service in expectation.

We develop a general method for converting arbitrary approximation algorithms for the underlying optimization problem into Bayesian incentive compatible mechanisms that are cost-recovering in expectation. In particular, we give polynomial time black-box reductions from the mechanism design problem to the problem of designing a social cost minimization algorithm without incentive constraints. Our reduction increases the expected social cost of the given algorithm by a factor of O(log(min[n, h])), where $n$ is the number of agents and h is the ratio between the highest and lowest nonzero valuations in the support. We also provide a lower bound illustrating that this inflation of the social cost is essential: no BIC cost-recovering mechanism can achieve an approximation factor better than Ω(log(n)) or Ω(log(h)) in general.

Our techniques extend to show that a certain class of truthful algorithms can be made cost-recovering in the non-Bayesian setting, in such a way that the approximation factor degrades by at most O(log(min[n, h])). This is an improvement over previously-known constructions with inflation factor O(log n).},
publisher = {ACM},
url = {http://approjects.co.za/?big=en-us/research/publication/cost-recovering-bayesian-algorithmic-mechanism-design/},
pages = {453-470},
isbn = {978-1-4503-1962-1},
edition = {Proceedings of the fourteenth ACM conference on Electronic commerce},
}