2013/05/02 by Hu Fu, Fu, Hu, Brendan Lucier +5
Computer Science · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #cs.GT
paper · pdf · doi:10.48550/arxiv.1305.0598
This paper will appear in Proceedings of the ACM Conference on Electronic Commerce 2013 (EC'13)
arxiv created 2013/05/02 · arxiv updated 2013/05/06
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(minn, 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(minn, h)). This is an improvement over previously-known constructions with inflation factor O(log n).