Measuring How Many Menu Options Near-Optimal Auctions Need

A seller with several goods and one buyer can always write the best selling strategy as a menu: a list of options, each a bundle or a lottery over bundles with a price, from which the buyer picks the one she likes most. Theory says these menus can get very large. Exact optimality can require infinitely many options, and even approximately optimal menus can grow exponentially in the number of goods. Neural methods for designing auctions from data now find menus that are close to optimal, but they fix the menu length by hand. As a result nobody knows how many options the learned mechanisms actually need, or whether that number follows the theory.

We propose to learn with a long menu, prune it into a short one, and certify the result. The output is an empirical revenue-versus-menu-size curve for a given buyer distribution. Each point on the curve is backed by an upper bound on the optimal revenue computed by a linear program, together with a held-out generalization check whose sample cost depends on the short deployed menu rather than the long training menu. Two sentences for a colleague: overparameterization makes auction networks easy to train, and small menus make them statistically cheap, so we train wide, prune to the smallest menu within ε of optimal, and certify it. Applied across standard benchmarks, this lets us check known menu-size theorems and gather evidence on an open question: for a fixed error such as 1%, must menu size grow exponentially with the number of independent goods?

Core Claim

Two results pull in opposite directions, and the tension between them has not been resolved. Mode Connectivity in Auction Design analyzes RochetNet, a network that directly parameterizes a single buyer's menu. It proves the training landscape has no bad isolated optima once the menu has about $(2/\epsilon)^{4n}$ options for $n$ items, and it shows a one-option menu can get stuck. This work motivates training wide.

On the other side, Sample Complexity of Automated Mechanism Design proves that richly parameterized auction classes need exponentially many samples. Sampling and Representation Complexity of Revenue Maximization proves that auctions needing exponential menus need exponential samples to learn. These results constrain what we can deploy.

Our claim is that the two pressures separate in practice. Width is needed only during optimization. The deployed mechanism can be pruned to a menu whose size tracks the economic complexity of the distribution, meaning the menu-size bounds proved by theory, rather than the training width.

The prediction is falsifiable. On benchmarks where theory pins down menu size, the pruned menu should match it. The first such benchmark is the "FedEx" setting, where a buyer has a value and one of $n$ private deadlines. There, exact optimality needs $2^n-1$ options, while $O(n^2/\epsilon)$ options suffice for a $(1-\epsilon)$ approximation (The menu complexity of "one-and-a-half-dimensional" mechanism design). The second is two goods with Beta values, where $\Omega(1/\epsilon)$ options are necessary (Bounding the menu-size of approximately optimal auctions via optimal-transport duality).

Research Program

The method has three parts.

Training. We train a RochetNet-style menu network with a deliberately large number $K_{\text{train}}$ of options, in the style of Optimal Auctions through Deep Learning: Advances in Differentiable Economics. Because the buyer simply picks her favorite option, incentive compatibility and individual rationality hold exactly by construction. This is the same guarantee that MENUNET obtains with its explicit buyer module (Automated Mechanism Design via Neural Networks).

Pruning. We then repeatedly delete the option whose removal costs the least validation revenue, and briefly re-optimize the remaining prices and lotteries after each deletion. This turns the "ε-reducibility" notion of Hertrich et al. from a proof device into an algorithm. The pass traces a whole curve $\hat R(K)$ of revenue at every menu size $K$ from $K_{\text{train}}$ down to 1.

Certification. On a finite set of $N$ sampled buyer types, the optimal randomized mechanism is a linear program, following the classical formulation of Conitzer and Sandholm et al.. We solve it with constraint generation, adding only the violated incentive constraints. This matters because Optimal Auctions through Deep Learning reports a naive LP taking 69 hours on a small grid. The LP value $R^{\star}_N$ bounds any menu's revenue on those types.

We report the smallest menu size meeting a given error level:

$$K^{\star}(\epsilon)=\min\{K : \hat R(K)\ge (1-\epsilon)\,R^{\star}_N\},$$

where $\hat R(K)$ is the pruned menu's revenue on those $N$ types. We also report its revenue on fresh held-out types.

The theory component is a generalization bound for a menu with $K$ options over $n$ items. The deployed menu is described by $K(n+1)$ numbers: $n$ allocation probabilities and one price per option. Standard counting arguments of the kind used by Morgenstern and Roughgarden should therefore give sample cost that grows with $Kn$, up to log factors, and does not depend on the training width. Proving this cleanly is part of the work. Checking that held-out revenue loss actually shrinks with $K^{\star}$ rather than $K_{\text{train}}$ is an experiment.

This proposal differs from A Scalable Neural Network for DSIC Affine Maximizer Auction Design, whose AMenuNet fixes the menu length at values like 128 or 1024 and names adaptive menu size as open. We do not learn a size inside the network. We produce a certified frontier and choose the size from it.

The proposal also differs from MENUNET, which verifies optimality with hand-built optimal-transport dual solutions. Our certificate is automatic, at the price of being tied to a finite type sample.

We restrict to a single buyer, where menus are unambiguous. Carrying the same method over to multi-bidder affine maximizer menus is a natural second step, but it is not a claim of this note.

Baselines

Simple mechanisms (the naive reference). Selling items separately, selling only the grand bundle, and mixed bundling with item-specific reserves are all tuned on the same training samples. Mixed bundling is especially attractive because Sample Complexity of Automated Mechanism Design shows its sample cost does not depend on the number of items. These mechanisms tell us when a tiny menu already suffices. On the correlated constructions of Selling Multiple Correlated Goods, they are known to capture a vanishing fraction of optimal revenue. Beating them means a strictly higher certified fraction of $R^{\star}_N$ at comparable menu size.

Fixed-size menu networks (the strongest existing method). RochetNet/MENUNET is trained directly at each target size $K$, on the same data, with the same total gradient steps summed across the sweep, and with the same seed and learning-rate budget. MENUNET reports an optimality ratio above 99.9996% of the theoretical optimum on multi-item synthetic auctions (Automated Mechanism Design via Neural Networks). No reported result found on Lacuna for revenue as a function of menu size for any learned mechanism. Beating this baseline means reaching the same certified revenue with a smaller $K$, or reaching higher revenue at equal small $K$, averaged over seeds.

Exact menu-constrained optimum (small-scale ground truth). On small type sets, a mixed-integer program that picks the best $K$-option menu gives the true frontier. This tells us how far pruning is from optimal pruning.

Ablation of the key ingredient. We compare prune-with-re-optimization against prune-without-re-optimization, and against "train wide, keep the top-$K$ options by buyer mass." This isolates whether the gain comes from wide training, from the pruning order, or from the re-fitting.

Why not just…?

Why not just sweep the menu size and train each one directly? This is the real threat. If direct small-$K$ training matches pruned menus, the pruning step adds nothing beyond compute savings. The evidence against it is that Mode Connectivity in Auction Design exhibits bad local optima at small menus. We expect direct training to suffer most exactly where theory says the optimal menu is structured, as in FedEx and Beta. The compute-matched comparison above settles the question. If the sweep wins or ties, we report that honestly. The certified frontier and the fixed-ε scaling study stand regardless of which method produces the menus.

Why not just solve the linear program and read off its menu? The LP optimum on $N$ types can use up to $N$ distinct options. It overfits the sample, which is precisely the failure mode that the representation–sample link of Han et al. warns about. It also does not tell us how few options suffice. We use the LP as the certificate, not the answer, and we report its held-out revenue next to the pruned menus to show the overfitting gap.

Why not just use mixed bundling, which is provably cheap to learn? Where it works, we will say so. The FedEx bound of $2^n-1$ options for exactness and the two-goods $\Omega(1/\epsilon)$ lower bound show that rigid formats cannot reach $(1-\epsilon)$ in general. The frontier plots will show where they fall short.

Proposed Experiments

The first check is calibration against theory. We use the uniform two-item setting with its known optimum (Manelli–Vincent and Pavlov), two i.i.d. Beta goods, and FedEx with $n$ from 2 to 8. We use the RegretNet-scale protocol of 640,000 training profiles and 10,000 test profiles. We plot $K^{\star}(\epsilon)$ for $\epsilon$ from $10^{-1}$ to $10^{-3}$.

The method passes if the Beta curve grows at least as $1/\epsilon$ and the FedEx curve grows no faster than roughly $n^2/\epsilon$. It fails if pruning either stalls far above these sizes or claims sizes below proved lower bounds. The second outcome would signal a broken certificate.

The second check is the open question left by The menu-size complexity of revenue approximation. With independent additive uniform and exponential items, $n$ from 2 to 10, and $\epsilon$ fixed at 0.01, does $K^{\star}$ grow exponentially or polynomially in $n$? Finite $n$ cannot prove asymptotics. A clean log-linear fit versus a polynomial fit, stable across sample sizes $N$, would still be the first data on the question and could guide the search for a proof.

The third check targets correlation, using Hart's pathological distributions. Here the frontier should keep rising with $K$, consistent with the $m^{1/7}$ revenue growth reported in Selling Multiple Correlated Goods.

Finally, we measure the gap between train-sample and held-out revenue as a function of $K^{\star}$ and of $K_{\text{train}}$. The decisive signature of the core claim is that this gap tracks the pruned size and is flat in the training width.