Abstract
We study the classic public project problem, where a group of agents must decide whether to fund a non-excludable public project. We focus on VCG redistribution mechanisms that are efficient, strategy-proof, and weakly budget-balanced. Our goal is to maximize the worst-case efficiency ratio—the ratio between the achieved total utility and the first-best maximum total utility. While previous studies identified optimal mechanisms for only three agents, we propose an asymptotically optimal mechanism that achieves a worst-case efficiency ratio of 1 as the number of agents approaches infinity. This result holds under the assumption that agents' valuations are rational numbers with bounded denominators. Our mechanism significantly improves upon the previous best-known asymptotic ratio of 0.102 and outperforms existing methods in non-asymptotic cases.
Introduction
Deciding whether to build a public project, such as a bridge or a park, is a fundamental problem in collective decision-making. To achieve social efficiency, a community needs to aggregate the private valuations of its members. However, individuals may have incentives to misreport their values to influence the outcome or minimize their personal costs. The Vickrey-Clarke-Groves (VCG) mechanism provides a solution by making truthful reporting a dominant strategy. However, VCG typically generates a budget surplus. To maintain budget balance without compromising strategy-proofness, this surplus must be redistributed back to the agents in a way that does not depend on their own reported values. The challenge lies in designing a redistribution rule that minimizes the "waste"—the portion of the surplus that cannot be returned.
Methodology
Dimension Reduction
Optimizing redistribution functions is traditionally difficult because the amount returned to one agent depends on the reports of all other $n-1$ agents. As $n$ grows, the dimensionality of this optimization problem becomes intractable. To overcome this, the authors employ a Dimension Reduction Technique. They design a redistribution function based on a subset of agents—specifically, a triplet. By considering a function that depends only on the values of two other agents and the aggregate sum of all other values, the problem is reduced to a manageable three-dimensional space. This function is then anonymized by averaging over all possible triplets, ensuring a fair and deterministic mechanism for all participants.
Bounded Precision Assumption
A key innovation in this work is the Bounded Precision Assumption. In real-world scenarios, valuations are not arbitrary real numbers but are typically expressed in discrete units of currency (e.g., dollars and cents). By assuming valuations are rational numbers with a bounded denominator, the authors show it is possible to capture the remaining surplus more effectively as the population size increases. This constraint, reflective of practical economic systems, allows the mechanism to reach perfect efficiency in the limit.
Results and Performance
Asymptotic Optimality
The proposed mechanism achieves a worst-case efficiency ratio of 1.0 (100% efficiency) as $n \to \infty$ under the bounded precision assumption. This confirms a long-standing conjecture in the field. Even without this assumption, the authors identify a mechanism with a constant asymptotic ratio of 0.5, a fivefold improvement over the previous state-of-the-art ratio of 0.102.
Small-Scale Comparison
Beyond asymptotic performance, the mechanism demonstrates superior results for small groups. When compared against existing benchmarks—such as the SBR (Scaling-Based Redistribution), ABR (Averaging-Based Redistribution), and AMD (Automated Mechanism Design) methods—the proposed "OC" (Optimal Constant) mechanism consistently yields higher efficiency ratios.
As shown in Table 1, for a group of $n=6$ agents, the proposed mechanism achieves an efficiency ratio of 0.583, significantly higher than the 0.394 achieved by SBR or the 0.497 by AMD. Furthermore, probabilistic analysis indicates that if valuations are drawn from a uniform distribution, the efficiency ratio reaches 1 with 99.1% probability for as few as 50 agents.
Conclusion
This research provides a definitive solution to the asymptotic efficiency of VCG redistribution in public project problems. By combining dimension reduction with a realistic assumption on valuation precision, the authors bridge the gap between theoretical mechanism design and practical implementation. Future work may explore extending these techniques to more complex scenarios, such as multi-item auctions or general resource allocation problems where budget balance and strategy-proofness are equally critical.
Summary updated