Worst-Case VCG Redistribution Mechanism Design Based on the Lottery Ticket Hypothesis

Mingyu Guo

Abstract

We study worst-case VCG redistribution mechanism design for the public project problem. The mechanism design task comes down to designing a payment function that maximizes the worst-case allocative efficiency ratio. 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 neural 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 mechanism design, the Vickrey-Clarke-Groves (VCG) mechanism is a cornerstone because it ensures strategy-proofness and efficiency. However, VCG often generates a payment surplus that cannot be returned to agents without potentially compromising these properties. Redistribution mechanisms seek to return this surplus to maximize the worst-case allocative efficiency ratio. While the 3-agent case was solved years ago, finding optimal redistribution functions for $n \ge 4$ has remained an open challenge, often relying on complex manual derivations.

Methodology

This paper proposes a novel automated approach combining deep learning with formal optimization:

  1. Neural Representation: The redistribution function is modeled as a Multilayer Perceptron (MLP) with ReLU activations.
  2. MIP-Based Training: Instead of standard gradient descent on random samples, the author uses Mixed Integer Programming (MIP) to identify the exact type profiles that represent the "worst-case" for the current model. These profiles are then used as training samples to improve the mechanism where it is weakest.
  3. The Lottery Ticket Hypothesis (LTH): MIP is computationally expensive and scales poorly with network size. To maintain a "tiny" network (5-20 nodes) that is still capable of reaching optimality, the author leverages LTH. By pruning a large, initialized network down to a subnetwork that "won the initialization lottery," the model can be trained effectively despite its small size.
  4. Iterative Pruning and Ensembles: If a subnetwork fails, the system "redraws" a ticket by pruning the original large network again, guided by previously discovered worst-case profiles. Finally, multiple "winning tickets" are combined into an ensemble to further smooth and improve performance.

Key Results

Optimality for Small Groups

The approach successfully identified mechanisms for 4 and 5 agents that match long-conjectured theoretical upper bounds (2/3 and 5/7, respectively) with near-perfect precision (gaps < 0.0001). This confirms the tightness of these theoretical bounds for the first time.

Surpassing Manual Benchmarks

For medium to large groups ($n$ up to 20), the automated neural approach significantly outperforms existing manual results. As shown in the comparison for $n=6$ to $10$, the ensemble of "winning tickets" consistently achieves lower gaps (higher efficiency) than previous manual benchmarks.

Comparison of Lottery Ticket (LOTT.) and Ensemble performance against Manual benchmarks for n=6 to 10.

For even larger groups, the scalability of the tiny subnetwork approach allows the discovery of mechanisms that set new performance benchmarks for up to 20 agents, where manual derivation becomes increasingly intractable.

Performance benchmarks for large groups (n=12 to 20) showing LOTT. superiority over manual results.

Conclusion and Limitations

By bridging the Lottery Ticket Hypothesis with formal optimization, this work provides a powerful framework for automated mechanism design. While the MIP approach eventually hits a computational wall around 20 agents due to the increasing complexity of the type space, it has already succeeded in closing decade-old theoretical gaps and establishing new state-of-the-art results for redistribution mechanisms.

Summary updated

Abstract

We study worst-case VCG redistribution mechanism design for the public project problem. The mechanism design task comes down to designing a payment function that maximizes the worst-case allocative efficiency ratio. 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 neural 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.
BibTeX
@inproceedings{guo2024worst,
  author = {Mingyu Guo},
  title = {{Worst-Case VCG Redistribution Mechanism Design Based on the Lottery Ticket Hypothesis}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=wmz4N6dXlk},
}
Figure