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. For VCG redistribution mechanisms, the mechanism design task is only on setting the payments, subject to strategy-proofness and the non-deficit constraint, while maximizing the worst-case allocative efficiency ratio. We use a multilayer perceptron (MLP) with ReLU activation to model the payment function. We 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. We require a tiny network structure for MIP 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. 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 training result's worst-case performance (i.e., scratch the ticket). If the subnetwork can 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). With a large enough initial network and a large enough number of draws, we expect to eventually encounter a tiny trainable subnetwork. We find an optimal mechanism for 3 agents that uses only 2 hidden nodes! We also find previously unknown optimal mechanisms for 4 and 5 agents. For up to 20 agents, we derive significantly improved worst-case mechanisms compared to existing manual results.