Modern combinatorial auctions sell many items at once, such as spectrum licenses. Bidders care about packages ("bundles") of items, so with $m$ items there are $2^m$ possible bundles. Recent systems handle this by learning each bidder's values from a few hundred questions with a neural network. They then pick the winners by encoding the trained networks as a mixed-integer program (MIP), an optimization problem with both continuous and integer variables, and handing it to a commercial solver. Every paper in this line reports that the MIP is the bottleneck. None asks what kind of bottleneck it is.
Research on SAT and constraint problems offers two very different answers to that question. One view holds that hardness is built into the instance: runs stall near a structural threshold no matter which solver is used. The other holds that hardness is often an accident of one algorithm's early wrong turn, and that another algorithm erases it. This note proposes to measure which answer holds for neural winner-determination MIPs, round by round inside a real auction. It also proposes a cheap, solver-independent statistic of the trained network that predicts which case a given instance falls into. The answer decides the practical remedy. If the hardness is built in, auction designers should reformulate the problem or change the model class. If it is mostly bad luck, randomized restarts and solver portfolios should recover most of the lost time and efficiency at almost no cost.
Core Claim
We hypothesize that the heavy tail of solve times in neural-surrogate winner determination is dominated by exceptionally hard instances in the sense of Sparse Constraint Graphs and Exceptionally Hard Problems. That paper found a sparse binary CSP needing 376 million consistency checks under forward checking. The same instance needed 3 million under conflict-directed backjumping. We expect the same pattern here: runs that are catastrophic under one solver configuration and routine under another.
We further hypothesize that the instances whose hardness survives every configuration form a separate, predictable group. We expect them to be marked by a high fraction of unstable ReLUs: hidden units whose on/off state cannot be fixed by bound propagation over the feasible bundle box, so each one demands a genuine branching decision. If both hypotheses hold, the field's "MIP bottleneck" splits into two problems. Restarts can absorb the algorithm-dependent part. The intrinsic part is diagnosable before solving.
To make the split measurable, each instance $x$ is solved under a set $C$ of solver configurations, each with several random seeds. Let $T_c(x)$ be the median solve time under configuration $c$. We define intrinsic hardness as $H(x)=\min_{c\in C} T_c(x)$ and algorithm-dependent excess as
$$E(x)=\frac{\operatorname{median}_{c\in C} T_c(x)}{\min_{c\in C} T_c(x)}.$$
$H$ is the best any tried method achieves. $E$ measures how much a typical method overpays relative to that best. The structural view in Extending Deep Structure and Summarizing CSP Hardness with Continuous Probability Distributions predicts that hard instances have large $H$, small $E$, and high agreement in hardness rank across configurations. The algorithmic view predicts large $E$ and weak agreement. The file identifies this contradiction as unresolved for learned bundle spaces, and this design tests it directly.
Relation to Prior Work
The proposal reuses the method of three auction papers and studies the solver they treat as a black box. Deep Learning-Powered Iterative Combinatorial Auctions encodes ReLU networks as Big-M MIPs, which use large constant bounds to switch constraints on and off, and solves them with CPLEX. It notes sensitivity to the Big-M constants but never analyzes solve-time distributions. Monotone-Value Neural Networks and Machine Learning-Powered Combinatorial Clock Auction enforce that adding items never lowers a bundle's value. The latter also solves inner MILPs during training, which it calls a scaling limit. Prices, Bids, Values combines price-based and value-based questions in one mechanism and inherits the same solver.
Unlike all three, we study the hardness of the instances their pipelines generate, not the economic efficiency of the mechanism.
Fourier Analysis-based Iterative Combinatorial Auctions attacks speed by changing the representation to a few Walsh-Hadamard coefficients. It still solves a MIP. We treat it as a competing remedy for intrinsic hardness, not as a substitute for the diagnosis.
Classical tree search for winner determination in An Algorithm for Optimal Winner Determination in Combinatorial Auctions works on explicit bids, not learned networks, so it motivates the question rather than answering it.
From the hardness literature, Where the Really Hard Problems Are and Experimental Results on the Crossover Point in Satisfiability Problems supply the method of sweeping an order parameter to look for an easy-hard-easy peak. The second paper also supplies a constraint: secondary peaks can be heuristic artifacts. Any peak we find must therefore be checked across configurations before we call it structural. The EHP paper supplies the cross-algorithm comparison. The deep-structure papers supply the competing prediction we try to falsify. One limitation cuts our way: the deep-structure theory does not model restarts or learning, so it makes no claim about modern solvers that we would be contradicting.
Research Program
The first step is to build a corpus of real winner-determination instances, not synthetic ones. We run the published DNN-based, monotone-network-based, and hybrid mechanisms on the four Spectrum Auction Test Suite (SATS) domains. These are GSVM, LSVM, SRVM, and MRVM, the last with 98 items and 10 bidders. We save every MIP the auctioneer solves, tagged with domain, round, network width, and the number of questions asked so far. For the clock-auction mechanism we also save the inner training MILPs. The file lists no linked SATS code artifact, so we will obtain the suite from its original distribution.
The second step is to solve each saved instance under a configuration set $C$. The set crosses three factors: Big-M constants (as published versus tightened by interval bound propagation), branching rule, and randomized restarts on or off. Each configuration runs with multiple seeds, so that seed-to-seed variance is separated from configuration-to-configuration variance.
The third step computes candidate predictors from the network and instance alone, before any solving. These are the fraction of unstable ReLUs, the total Big-M slack, bidders times hidden units divided by items, and a complementarity score from the network's second differences on queried bundles. We then test whether any predictor shows an easy-hard-easy profile in $H$, as clause density does in random 3-SAT. We also test whether exceptionally hard instances concentrate where few bundles have been queried. That would parallel the sparse-graph finding in the EHP paper, where dense graphs with $p_1=1.0$ produced none in 50,000 instances.
The fourth step closes the loop to economics. We rerun auctions under a fixed wall-clock budget per winner-determination solve, as a real auction would impose. We record how much allocative efficiency is lost when a solve times out, and how much each remedy recovers.
Baselines
The do-nothing reference is the published pipeline exactly as released: default CPLEX, published Big-M constants, a single run, no time limit. This gives the reference solve-time distribution and efficiency. The strongest existing end-to-end result in the file is 95.04% efficiency on MRVM for the DNN-based auction in Deep Learning-Powered Iterative Combinatorial Auctions. The SVR-based mechanism of Combinatorial Auctions via Machine Learning-based Preference Elicitation reports 94.6% under its pseudo-VCG mechanism. No reported result was found on Lacuna for the distribution of winner-determination solve times in any of these systems, so our default-solver measurements will be the first such baseline. A remedy counts as a success if, under a fixed per-solve budget, it reaches at least the unlimited-time efficiency of the default pipeline while cutting the 95th-percentile solve time by an order of magnitude.
The strongest competing speed remedy is the Fourier-domain mechanism of Fourier Analysis-based Iterative Combinatorial Auctions. It reports computational speedups over the earlier MLCA system of 6x on GSVM, 3x on LSVM, and 2x on MRVM. We run it on the same domains and seeds and give it the same hardware and per-solve budget as everything else. Restarts beat it on this question if they match or exceed its speedups while keeping the neural model unchanged.
The key ablation isolates bound tightening from restarts. Tightened Big-M with a single run, and published Big-M with restarts, are each compared against both factors combined. This shows whether the excess $E$ comes from the encoding or from search luck. For the predictor, the baseline is instance size alone (items times bidders times hidden units). Our statistic must predict $H$ and $E$ better than size does under held-out-domain evaluation.
Why not just…?
Why not just tighten the Big-M constants and stop? This is the most serious threat. Weissteiner and Seuken already flag Big-M sensitivity, and tighter bounds shrink the LP relaxation, which could remove most stalls. Our ablation measures exactly this. If tightening alone collapses both $H$ and $E$, we will report that the bottleneck was an encoding artifact, and the restart and predictor contributions shrink accordingly. That is still a useful negative result for the field. Our prior is that tightening reduces $H$ but leaves seed-dependent tails, because the EHP mechanism is an early branching error, not a weak relaxation. The data settle it.
Why not just give the solver more time? Auctions run on schedules. A winner-determination solve that times out returns a worse allocation, and that corrupts the next round's questions. The fixed-budget experiment measures the efficiency cost directly. More time is a remedy only if that cost is negligible, which we do not assume.
Why not just switch to a model class with an easier MIP, such as quadratic SVR or Fourier-sparse values? The file shows these trade accuracy for tractability. DNNs beat SVRs by 1.74 percentage points on LSVM, and the Fourier method relies on sparsity that its authors say fails when item synergies are dense. Both still solve MIPs. We include both as baselines. If their solve-time tails are as heavy as the DNN's, model choice does not address the problem.
Why not just run a commercial solver portfolio and ignore diagnosis? If restarts and portfolios absorb all hardness, the portfolio is the practical answer, and we would say so. The diagnosis still matters for the instances where every configuration is slow, and the predictor is what flags those in advance. That lets an auctioneer change the number of questions, the network width, or the representation before a round stalls.
Proposed Experiments
The decisive check is the cross-configuration rank agreement of hardness on the MRVM corpus. We compute the Spearman correlation of $T_c(x)$ across configurations, restricted to the slowest 5% of instances. High agreement together with low $E$ supports the intrinsic view. Low agreement together with a heavy-tailed $E$ supports the EHP view. Either outcome is informative.
The second check fits the runtime distributions of each configuration. Summarizing CSP Hardness with Continuous Probability Distributions found Weibull-shaped effort for solvable instances and lognormal-shaped effort for unsolvable ones. We ask whether neural MIPs show the same shape, or a heavier tail that only appears without restarts.
The third check sweeps the unstable-ReLU fraction, both by varying network width and by sampling across elicitation rounds. We look for a peak in $H$, and we confirm that any peak persists under every configuration before calling it structural, following the artifact warning in the 3-SAT crossover paper.
The fourth check is economic. On all four SATS domains, under a fixed per-solve budget, we compare final efficiency and number of questions for default CPLEX, tightened Big-M, restarts, the combination, and the Fourier mechanism. The unlimited-time published figures serve as ceilings.
References
- Sparse Constraint Graphs and Exceptionally Hard Problems
- Extending Deep Structure
- Summarizing CSP Hardness with Continuous Probability Distributions
- Deep Learning-Powered Iterative Combinatorial Auctions
- Monotone-Value Neural Networks: Exploiting Preference Monotonicity in Combinatorial Assignment
- Machine Learning-Powered Combinatorial Clock Auction
- Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All
- Fourier Analysis-based Iterative Combinatorial Auctions
- An Algorithm for Optimal Winner Determination in Combinatorial Auctions
- Where the Really Hard Problems Are
- Experimental Results on the Crossover Point in Satisfiability Problems
- Combinatorial Auctions via Machine Learning-based Preference Elicitation