Research map / Learning theory and algorithms / Submodular and game algorithms
Worst-Case VCG Redistribution Mechanism Design Based on the Lottery Ticket Hypothesis
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Uses MIP-based worst-case training of ReLU MLP payment functions, combined with lottery-ticket-style pruning and redrawing, to find near-optimal worst-case VCG redistribution mechanisms for the public project problem for up to 20 agents.
Problem
Worst-case VCG redistribution mechanism design for the binary non-excludable public project problem: find a Groves term h maximizing the worst-case allocative efficiency ratio, where exact worst-case evaluation is computationally expensive for large networks.
Approach
Train a large ReLU MLP, prune it into a tiny subnetwork (ticket) guided by worst-case type profiles from MIP, and redraw from the original initialization while avoiding previously bad tickets; the MIP-found worst-case profiles serve as training samples, and ensembles of the resulting mechanisms are combined.
Key results
- For 4 and 5 agents, near-optimal mechanisms match conjectured upper bounds (2/3 and 5/7) with gaps below 0.0001.
- For n=10, the ensemble reaches worst-case gap 0.1924 vs manual 0.3320, and lottery approach beats manual results for n=6 to 20 in the scalability test except n=16 where Reinit was best.
- Lottery draws beat repeated reinitialization in ablations: Lottery min gaps were best in every n=6-10 setting with ticket size 10 and 20.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Ensemble the two best tickets with 0.5 probability each | Lottery mechanism · Public project, 6–10 agents | gap to theoretical upper bound: 0.1541 -> 0.1531; 0.0364 -> 0.0354; 0.0629 -> 0.0621; 0.0845 -> 0.0837; 0.1929 -> 0.1924 | Helped |
| Use Lottery instead of Reinit | Lottery worst-case training · Public project, 12, 14, 18, and 20 agents | gap to theoretical upper bound: 0.1947 -> 0.1690; 0.3408 -> 0.2767; 0.4013 -> 0.3610; 0.3136 -> 0.2903 | Helped |
| Use Lottery instead of Reinit | Lottery worst-case training · Public project, 16 agents | gap to theoretical upper bound: 0.2613 -> 0.2662 | Hurt |
| Remove the trick of running MIPs only when needed (ablation) | WCT · Public project, 6–10 agents | gap to theoretical upper bound: WCT-1 min gaps: 0.1830, 0.0933, 0.0939, 0.1917, 0.3086; WCT min gaps: 0.1775, 0.0888, 0.0973, 0.1329, 0.2576 | Mixed |
| Stop revisiting old worst-case type profiles (ablation) | WCT · Public project, 6–10 agents | gap to theoretical upper bound: WCT-2 min gaps: 0.1906, 0.0916, 0.1078, 0.1575, 0.2848; WCT min gaps: 0.1775, 0.0888, 0.0973, 0.1329, 0.2576 | Hurt |
| Fix the goal to the theoretical upper bound instead of adjusting it (ablation) | WCT · Public project, 6–10 agents | gap to theoretical upper bound: WCT-3 min gaps: 0.2213, 0.0644, 0.1054, 0.1683, 0.3514; WCT min gaps: 0.1775, 0.0888, 0.0973, 0.1329, 0.2576 | Mixed |
| Draw pruned tickets rather than directly reinitialize target-size networks (ablation) | Lottery worst-case training · Public project, 6–10 agents; ticket sizes 10 and 20 | minimum gap to theoretical upper bound: Lottery beats Reinit0, Reinit1, and Reinit2 in every listed setting | Helped |
| Share worst-case profiles across draws (ablation) | Reinit1 · Public project, 6–10 agents; ticket sizes 10 and 20 | minimum gap to theoretical upper bound: Reinit2 is worse than Reinit1 in 9 out of 10 cases | Helped |
| Reinitialize the network across draws (ablation) | Reinit2 · Public project, 6–10 agents; ticket sizes 10 and 20 | minimum gap to theoretical upper bound: Reinit0 is worse than Reinit2 in 7 out of 10 cases | Helped |
| Use a larger initial network rather than repeatedly initializing a tiny network (ablation) | Lottery ticket training · Public project, 3 agents | near-optimal mechanisms found out of 10 trials: [2]: 0; [5]: 2; [10]: 3; [15]: 7 | Helped |
| Use a 2-node network initialized directly instead of pruning a larger network (ablation) | WCT · Public project, 3 agents | gap to theoretical upper bound: 0.1179 | Hurt |
Surprising findings
- Tiny networks ([2] for n=3) rarely train from random initialization, with 8 of 10 trials failing completely, yet pruning from a larger network finds trainable tickets.
- Monte Carlo evaluation inflates worst-case ratio substantially (0.685 exact vs 0.765 simulated for n=10).
Limitations
- Scalability limited: ticket sizes above 6 often cause out-of-memory in MIP even with 128 GB, so 20 agents is the practical limit.
- Results are near-optimal due to floating-point errors; the approach relies on exponential trials and is not guaranteed to find a winning ticket.
Experimental setup
Benchmarks: worst-case allocative efficiency ratio for public project problem with n=3 to 20 agents
Metrics: gap to theoretical upper bound worst-case allocative efficiency ratio
Baselines: SBR mechanism ABR mechanism automated mechanism design (0.600 for n=4) manual mechanisms for n=6-20 Monte Carlo-evaluated neural mechanisms Reinit0/Reinit1/Reinit2 ablations
Builds on: Lottery Ticket Hypothesis VCG redistribution mechanisms Holmström characterization certified regret via MIP (Duan et al.)
Closest papers by meaning
- Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask (NeurIPS 2019 · similarity 0.85)
- The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks (ICLR 2019 · similarity 0.85)
- The Elastic Lottery Ticket Hypothesis (NeurIPS 2021 · similarity 0.84)
- Revenue maximization via machine learning with noisy data (NeurIPS 2021 · similarity 0.84)
- Find A Winning Sign: Sign Is All We Need to Win the Lottery (ICLR 2025 · similarity 0.83)
- Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win (ICML 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.