Abstract
We study worst-case VCG redistribution mechanism design for the public project problem. We use a multilayer perceptron (MLP) with ReLU activation to model the payment function and use mixed integer programming (MIP) to solve for the worst-case type profiles that maximally violate the mechanism design constraints. We collect these worst-case type profiles and use them as training samples to train toward better worst-case mechanisms. In practice, we require a tiny network structure for the above approach to scale. The Lottery Ticket Hypothesis states that a large network is likely to contain a "winning ticket" -- a much smaller subnetwork that "won the initialization lottery", which makes its training particularly effective. Motivated by this hypothesis, we train a large network and prune it into a tiny subnetwork. We run MIP-based worst-case training on the drawn subnetwork and evaluate the resulting mechanism's worst-case performance. If the subnetwork does not achieve good worst-case performance, then we record the type profiles that cause the current draw to be bad. To draw again, we restore the large network to its initial weights and prune using recorded type profiles from earlier draws, therefore avoiding drawing the same ticket twice. We expect to eventually encounter a tiny subnetwork that leads to effective training for our worst-case mechanism design task. Lastly, a by-product of multiple ticket draws is an ensemble of mechanisms with different worst cases, which improves the worst-case performance further. Using our approach, we find previously unknown optimal mechanisms for up to 5 agents. Our results confirm the tightness of existing theoretical upper bounds. For up to 20 agents, we derive significantly improved worst-case mechanisms, surpassing a long list of existing manual results.
Introduction
In the field of mechanism design, the public project problem addresses how a group of agents should decide whether to implement a shared resource (e.g., a bridge or public park) when their individual valuations are private. The classic Vickrey-Clarke-Groves (VCG) mechanism provides a framework to ensure agents report their valuations honestly. However, VCG typically results in a budget surplus—money collected from agents that cannot be returned to them without potentially distorting their incentives.
Redistribution mechanisms aim to return this surplus to the agents while maintaining strategy-proofness and ensuring a non-deficit. The primary objective is to maximize the worst-case allocative efficiency ratio, which represents the minimum possible ratio between the utility achieved by the mechanism and the maximum possible social utility. While theoretical bounds for these ratios have been conjectured, finding the specific mathematical functions—known as "Groves terms"—to reach these bounds has remained an open challenge for groups larger than three agents.
Methodology: Neural Networks and the Lottery Ticket Hypothesis
This research reformulates mechanism design as a deep learning optimization problem with an adversarial component. The redistribution function ($h$) is modeled using a Multilayer Perceptron (MLP) with ReLU activations.
MIP-Based Adversarial Training
Standard neural network training relies on random sampling (Monte Carlo). However, in mechanism design, the worst-case performance often occurs in obscure regions of the input space that random sampling might never encounter. To address this, the authors employ Mixed Integer Programming (MIP) as an adversary. The MIP solver identifies the exact valuation profiles that most severely violate the mechanism's constraints, which are then used as training samples to refine the model.
Leveraging the Lottery Ticket Hypothesis (LTH)
A significant hurdle is that MIP solvers do not scale well with large neural networks. To maintain computational feasibility, the authors utilize the Lottery Ticket Hypothesis (LTH). They start with a large network and prune it down to a "tiny" subnetwork—a "winning ticket." This subnetwork is small enough for the MIP solver to process but retains the specific initial weights necessary to learn complex redistribution functions effectively.
As shown in the experimental results above, the LTH-based approach (LOTT) consistently outperforms various re-initialization strategies (REINIT), confirming that the specific initial weights of the pruned subnetwork are vital for achieving lower performance gaps.
Key Results and Insights
The proposed approach successfully identified previously unknown optimal mechanisms for 4 and 5 agents, matching theoretical upper bounds ($2/3$ for $n=4$ and $5/7$ for $n=5$) that had stood unreached for years. For larger groups of up to 20 agents, the neural-generated mechanisms significantly outperformed existing manual designs.
The table above illustrates the efficacy of the Worst-Case Training (WCT) method. Across various agent counts ($n$), the WCT variants generally achieve the lowest average and minimum gaps compared to baseline configurations. Notably, the use of MIP as a "certifier" ensures that these efficiency ratios are mathematically exact, exposing that some previous state-of-the-art results had inflated performance metrics due to a reliance on simple Monte Carlo evaluation.
Conclusion
By combining neural modeling with the rigorous verification of Mixed Integer Programming and the architectural efficiency of the Lottery Ticket Hypothesis, this work provides a powerful new toolkit for mechanism design. The discovery of optimal mechanisms for $n=5$ and the scalability to $n=20$ demonstrate that "elegant" mathematical solutions can be found within the search space of tiny, pruned neural networks. Future work will explore extending this framework to more complex auction settings and multi-item environments.
Summary updated