Lying Coherently: Measuring How Far a Strategic Bidder Can Steer Machine-Learned Combinatorial Auctions

When many items are sold together, as in spectrum licenses or airport slots, each bidder can value any of the $2^m$ possible bundles. No one can report $2^{20}$ numbers, let alone $2^{98}$. The best recent auctions therefore ask each bidder a small number of questions, fit a neural network to the answers, and let that learned model decide what to ask next and who wins. These auctions waste far less value than the clock auctions used in practice. They also share an assumption: bidders answer honestly. A bidder who knows the auctioneer is learning from her answers can try to shape what it learns. We propose to build that bidder as a multi-objective optimizer. She looks for false answers that raise her own payoff while staying consistent and plausible enough that the auctioneer's audits cannot tell her from an honest bidder with different tastes. We then measure the full trade-off between gain and detectability that she can achieve against each auction format.

The main technical idea is to borrow the structure that makes the bundle space learnable and use it to make the attack tractable. Bidder valuations tend to be "Fourier-sparse": viewed as functions on $\{0,1\}^m$, they are dominated by a few low-order interaction terms. So the attacker does not search over arbitrary misreports. She searches over sparse, low-degree edits to her true valuation and answers every query as a coherent fake bidder would. The search space shrinks from exponential to roughly $k \cdot \binom{m}{d}$ choices, for $k$ edited interaction terms of order at most $d$. The resulting gain-versus-stealth frontier answers a question the field has flagged but not measured: does putting machine learning into the elicitation loop make auctions more exploitable than the simple clock auction it replaces?

Core Claim

Our hypothesis is that ML-powered iterative auctions have a manipulation surface that clock auctions with linear prices lack, because the learned model extrapolates from a few answers. A small, coherent, low-order distortion therefore changes which bundles are queried later and what the model believes about bundles that are never queried. We expect a sparse-Fourier, multi-objective attacker to find misreports that (a) give substantially more surplus than truthful bidding and (b) never violate the revealed-preference consistency checks an auctioneer could run. We also expect this frontier to sit well above what classic hand-designed manipulations achieve, such as uniform bid shading or demand reduction. If true, the efficiency gains reported for these mechanisms are fragile in a specific, measurable way. If false, and simple shading matches the optimized attacker, then ML elicitation is no more exploitable than its predecessors. That would also be a useful result, and the experiments are designed to tell the two cases apart.

What Exists and What Is Missing

The auction side supplies the mechanisms under attack. Probably Approximately Efficient Combinatorial Auctions via Machine Learning fits support-vector regressors to bidders' answers and reaches 92–100% efficiency in GSVM with 40 queries. Deep Learning-Powered Iterative Combinatorial Auctions replaces these with ReLU networks encoded as integer programs and reaches 95.04% efficiency in the 98-item MRVM domain. Machine Learning-Powered Combinatorial Clock Auction learns monotone value networks and chooses prices by descending excess demand. Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All (MLHCA) mixes price-based "demand queries" ("which bundle do you want at these prices?") with exact "value queries", and joins them with a "bridge bid". Fourier Analysis-based Iterative Combinatorial Auctions learns a sparse Fourier support of each valuation. All five motivate this proposal for the same reason: each assumes truthful reports, and the file notes that the PAE and Fourier papers explicitly leave strategic manipulation open. None of them evaluates a manipulating bidder.

The Fourier literature supplies the attack's parameterization. Learning Fourier Sparse Set Functions and Efficiently Learning Fourier Sparse Set Functions show that low-degree sparse set functions are recoverable from few samples. We use the converse: a perturbation in that same class is exactly the kind of signal a sparse learner absorbs and extrapolates. The second paper also constrains us, because its exact recovery relies on bounded noise. We deliberately keep our edits inside the low-degree class, so that what the auctioneer learns is a clean, wrong valuation rather than noise.

The adversarial side supplies the optimization lens. MOS-Attack optimizes a set of candidate perturbations against several surrogate losses at once. Exploring the Adversarial Frontier replaces single-budget robustness with the hypervolume under a perturbation-versus-damage frontier. Attacking all tasks at once shows that fixed loss sums fall into a "dominance trap", where one objective's gradient swamps the others. Greedy Coordinate Diffusion shows in language models that an attack optimized jointly for success and stealth survives filters that drive a single-objective attack (GCG) to 0%. All of these work on images or token strings, and none has an economic payoff or a set-function input. We adopt their frontier-centric evaluation and their joint stealth objective, but our search variables are Fourier coefficients and our "model" is an entire multi-round auction.

The closest bridging work, Advancing Differentiable Mechanism Design, balances revenue and regret as two tasks. However, it scales only to 5 items and never confronts an adaptive manipulator. BundleFlow reaches 500 items, but only for single-bidder menus. Neither studies how a strategic bidder exploits iterative elicitation. That gap is ours.

Research Program

Attacker parameterization. Let $v_i:\{0,1\}^m\to\mathbb{R}$ be bidder $i$'s true valuation and $\chi_T(S) = (-1)^{|S\cap T|}$ the Walsh–Hadamard basis function for an item set $T$. The attacker chooses a fake valuation

$$\hat v_i(S) = v_i(S) + \sum_{T\in\mathcal{T}} \theta_T\,\chi_T(S),\qquad |\mathcal{T}|\le k,\ |T|\le d,$$

where $\mathcal{T}$ is the set of edited interaction terms and $\theta_T$ their weights. A projection step then enforces monotonicity and nonnegativity, since free-disposal violations are trivially detectable. Every demand query is answered by maximizing $\hat v_i(S) - p(S)$ with an integer program. Every value query and the bridge bid return $\hat v_i$. Because all answers come from one valuation, the report history is internally consistent by construction.

Objectives. The first objective is the attacker's realized surplus gain, $\mathbb{E}[u_i(\hat v_i) - u_i(v_i)]$. It is measured under her true valuation and averaged over draws of the other bidders from the SATS generator, since she does not know their values. The second is detectability, the score of the strongest auditor we can build. The auditor combines three signals: revealed-preference violations across the demand-query history; the likelihood of the report under a density model of SATS bidder types, trained on honest draws; and the shift in the auctioneer's own model uncertainty that the report induces. The third, collateral welfare loss to the market, is tracked but not optimized. It tells us whether manipulation is a transfer between bidders or a destruction of value.

Search. Running the auction is a black box with discrete outcomes. We therefore use population-based multi-objective search over $(\mathcal{T},\theta)$: support moves add, drop, or swap a term, and weight moves apply Gaussian steps. This is in the spirit of the evolutionary trade-off search in LADDER, keeping a non-dominated archive. For the auctions whose learned model is differentiable, ML-CCA and the DNN auction, we add a cheaper inner loop. It differentiates the attacker's predicted allocation through a surrogate of the auctioneer's next-round model fit, in the way MOS-Attack pushes a candidate set toward several losses at once. The attack is scored only by full auction re-runs.

Robustness metric. Following the adversarial-hypervolume idea, each mechanism gets one number: the area under its gain-versus-detectability frontier, with detectability normalized to the auditor's false-positive rate on honest bidders. This lets a 98-item spectrum auction and a 18-item GSVM auction be compared on the same scale.

Baselines

The naive reference point is truthful bidding. Its surplus defines zero gain, and its welfare reproduces each mechanism's reported efficiency. We will check our reimplementations against the published figures before any attack is run, for example 95.04% for DNN-ICA on MRVM. If a reproduction misses by more than about one point, we report against our own number.

The strongest existing competitors are not prior attacks: we found no reported manipulation result on Lacuna for any of these mechanisms. They are instead the classic manipulations from auction practice. The first is uniform shading, which reports $\alpha v_i$ for a single $\alpha$. The second is demand reduction, which zeroes the value of one or more items. Both are coherent by construction, so they pass revealed-preference audits, and they are what a real bidder would try first. We tune $\alpha$ and the dropped item set by grid search with the same number of full auction runs our attacker receives. Beating them means our frontier strictly dominates theirs, with higher gain at equal false-positive rate, on at least the LSVM and MRVM domains.

Two ablations isolate the key ingredient. The first is a dense-perturbation attacker, which edits values only on the bundles the auction actually queries, unrestricted in form, under the same search budget. If Fourier sparsity matters, the dense attacker should either gain less, because its edits do not generalize through the learned model, or be more detectable. The second is a fixed weighted-sum attacker, which combines gain and detectability with fixed coefficients and is tuned over five weightings within the same budget. It tests whether frontier search buys anything over scalarization.

On the mechanism side, the standard combinatorial clock auction with linear prices is the control. The headline comparison is whether ML-CCA, MLHCA, and the Fourier auction have larger attack hypervolume than the clock auction. ML-CCA reports 7.8–9 points higher welfare than the clock auction in GSVM and LSVM, so we ask how much of that advantage survives a single manipulating bidder.

Why not just…?

Why not just shade bids uniformly, since that is what real bidders do? This is the real threat to the proposal. Under VCG-style payment rules, shading can already be profitable, and our sophistication may add little. We do not argue around it: shading and demand reduction are tuned with an equal budget. A result in which they match the optimized frontier would be reported as the finding that ML elicitation adds no new manipulation surface. Our prediction that it does rests on one mechanism, extrapolation from few queries. Shading cannot target extrapolation; a low-degree edit can, for instance by inflating a complementarity among items that are never jointly queried.

Why not just combine the objectives with a weighted sum? In multi-task attacks, a fixed sum lets the dominant loss swamp the rest; dynamic balancing improved effectiveness by up to 80.41% in Attacking all tasks at once. The two objectives here, gain and detectability, sit on different scales that change across domains. Even so, the fixed-weight ablation will show directly whether our frontier search improves on scalarization in auctions.

Why not just train the mechanism to be incentive compatible, as differentiable mechanism design does? Regret-penalized networks such as CAFormer reach regret 0.004, but only at 2 bidders and 5 items in Advancing Differentiable Mechanism Design, because they enumerate bundles. BundleFlow scales further but is single-bidder. Neither covers multi-round elicitation at 98 items, which is the regime where the deployed-style mechanisms operate and where our attack applies.

Why not just audit reports for inconsistency? Our attacker answers every query from one monotone valuation, so revealed-preference checks are passed by construction. We include such checks in the auditor precisely to show this. The informative auditor signals are therefore distributional plausibility and the uncertainty shift. Whether those catch the attack is an outcome of the experiment, not something we assume.

Proposed Experiments

All experiments use the Spectrum Auction Test Suite domains GSVM, LSVM, SRVM, and MRVM. These are the benchmarks on which every attacked mechanism reports results, with 50 seeds per configuration. One bidder per instance is the attacker, and we rotate across bidder types (national versus regional bidders in MRVM, for example). The attacker gets a fixed budget of full auction simulations, with $k\in\{1,2,4,8\}$ and $d\in\{1,2,3\}$. The metrics are surplus gain as a percent of truthful surplus, auditor true-positive rate at 5% false-positive rate on honest bidders, market efficiency loss, and frontier hypervolume.

The first decisive check is the mechanism comparison: is the attack hypervolume for ML-CCA and MLHCA significantly larger than for the clock auction across seeds? If it is not, the central hypothesis fails. The second is the ablation: does the sparse attacker dominate both the dense-perturbation attacker and tuned shading at equal budget? If shading matches it, we report that simple manipulation suffices. The third is a mechanism-specific probe. We expect the Fourier-based auction to be most exposed to degree-matched edits; if it is, then sparsity priors that make elicitation cheap also make it steerable. As a constructive follow-up, we will rerun the strongest attack against the same mechanism with randomized query selection and with the auctioneer's model fit penalizing reliance on low-query interaction terms. This asks whether any part of the efficiency advantage can be kept while shrinking the frontier.