BundleFlow: Deep Menus for Combinatorial Auctions by Diffusion-Based Optimization
Tonghan Wang, Yanchen Jiang, David Parkes
Differentiable economics---the use of deep learning for auction design---has driven progress in multi-item auction design with additive or unit-demand valuations. However, progress in combinatorial auctions (CAs), even for the simplest and yet important single bidder case, remains limited due to the exponential growth of the bundle space with the number of items. We address this challenge by introducing a deep menu-based mechanism, which is, to our knowledge, the first dominant-strategy incentive compatible (DSIC) and revenue-optimizing single-bidder CA. Our idea is to generate a bundle distribution through an ordinary differential equation (ODE) applied to a tractable initial distribution. Our method learns suitable ODE-based transforms, one for each menu element, to optimize expected revenue.  Our method achieves 1.11$-$2.23$\times$ higher revenue than baselines on standard CA testbeds and scales up to 150 items. Relative to menu-learning baselines that we introduce, our method also reduces training iterations by 3.6$-$9.5$\times$ and cuts training time by about 80\% in settings with 50 and 100 items.