  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 \Omega(log(n)) or \Omega(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).
