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

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 propose a suite of techniques for worst-case mechanism design via neural networks. 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 [8] 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 (i.e., "draw" a ticket). We run MIP-based worst-case training on the drawn subnetwork and evaluate the resulting mechanism's worst-case performance (i.e., "scratch" the ticket). 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 (i.e., redraw from the original ticket pot while 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 conjectured theoretical upper bounds. For up to 20 agents, we derive significantly improved worst-case mechanisms, surpassing a long list of existing manual results. Definition 1 (Public Project Problem). n agents decide whether or not to build a public project that costs 1. Agent i's type is θ i (0 ≤ θ i ≤ 1). If the mechanism decision is NOT BUILD, then agent i retains her share of the project cost 1 n and her valuation is 1 n for this outcome. If the mechanism decision is to BUILD, then agent i's valuation is θ i .