An asymptotically optimal VCG redistribution mechanism for the public project problem

摘要

We study the classic public project problem, where the agents 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 an optimal mechanism for 3 agents. Unfortunately, no optimal mechanisms have been identified for more than 3 agents. We propose an automated mechanism design approach that is capable of handling worst-case objectives. With its help, we identify a different optimal mechanism for 3 agents. For more agents, we identify mechanisms with better worst-case efficiency ratios than previous results. Using a dimension reduction technique, we extend the newly identified optimal mechanism for 3 agents to n agents. The resulting mechanism’s worst-case efficiency ratio equals \(\frac{n+1}{2n}\). In comparison, the best previously known worst-case efficiency ratio equals 0.102 asymptotically. We then derive an asymptotically optimal mechanism under a minor technical assumption: we assume the agents’ valuations are rational numbers with bounded denominators. Previous studies conjectured that the optimal asymptotic worst-case efficiency ratio equals 1. We confirm this conjecture.