An Asymptotically Optimal VCG Redistribution Mechanism for the Public Project Problem

Abstract

We study the classic public project problem, where a group of agents need to decide whether or not to build a non-excludable public project.  We focus on efficient, strategy-proof, and weakly budget-balanced mechanisms (VCG redistribution mechanisms). Our aim is to maximize the worst-case efficiency ratio --- the worst-case ratio between the achieved total utility and the first-best maximum total utility. Previous studies have identified the optimal mechanism for 3 agents.  It was also conjectured that the worst-case efficiency ratio approaches 1 asymptotically as the number of agents approaches infinity.  Unfortunately, no optimal mechanisms have been identified for cases with more than 3 agents. We propose an asymptotically optimal mechanism, which achieves a worst-case efficiency ratio of 1, under a minor technical assumption: we assume the agents' valuations are rational numbers with bounded denominators.  We also show that if the agents' valuations are drawn from identical and independent distributions, our mechanism's efficiency ratio equals 1 with probability approaching 1 asymptotically.  Our results significantly improve on previous results. The best previously known asymptotic worst-case efficiency ratio is 0.102.  For non-asymptotic cases, our mechanisms also achieve better ratios than all previous results.