Speed up Automated Mechanism Design by Sampling Worst-Case Profiles: An Application to Competitive VCG Redistribution Mechanism for Public Project Problem

摘要

Computationally Feasible Automated Mechanism Design (CFAMD) combines manual mechanism design and optimization. In CFAMD, we focus on a parameterized family of strategy-proof mechanisms, and then optimize within the family by adjusting the parameters. This transforms mechanism design (functional optimization) into value optimization, as we only need to optimize over the parameters. Under CFAMD, given a mechanism (characterized by a list of parameters), we need to be able to efficiently evaluate the mechanism's performance. Otherwise, parameter optimization is computationally impractical when the number of parameters is large. We propose a new technique for speeding up CFAMD for worst-case objectives. Our technique builds up a set of worst-case type profiles, with which we can efficiently approximate a mechanism's worst-case performance. The new technique allows us to apply CFAMD to cases where mechanism performance evaluation is computationally expensive. We demonstrate the effectiveness of our approach by applying it to the design of competitive VCG redistribution mechanism for public project problem. This is a well studied mechanism design problem. Several competitive mechanisms have already been proposed. With our new technique, we are able to achieve better competitive ratios than previous results.