Cost-recovering bayesian algorithmic mechanism design

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).