Monotone Fourier Valuations Learned from Price Responses

In a combinatorial auction with $m$ items, each bidder has a value for every one of the $2^m$ possible packages. Nobody can report that many numbers. The most practical way to learn preferences is the demand query: the auctioneer posts item prices and the bidder names the package they would buy. Separately, Fourier analysis of set functions shows that many valuations are carried by a small number of low-order interaction terms, such as "these two licenses are worth more together." The two ideas have never been combined in a principled way. Existing Fourier auctions learn only from direct value reports. Existing demand-query auctions use black-box neural networks, and those networks cannot say which synergies they have found.

This note proposes to fit a sparse Fourier model of each bidder's valuation directly from demand-query answers, while forcing the model to satisfy free disposal. Free disposal is the economic rule that adding items never lowers value. The core technical contribution is a characterization of which Fourier supports make free disposal a tractable convex constraint. An answered demand query is a set of linear inequalities in the Fourier coefficients. If monotonicity is also a polynomial-size linear system, then elicitation, surrogate fitting and winner determination all reduce to linear and mixed-integer programs. These programs expose explicit synergy structure and carry identification guarantees that neural surrogates lack.

Core Claim

Let $\mathcal{F}$ be a downward-closed family of item subsets: whenever $T \in \mathcal{F}$, all subsets of $T$ are in $\mathcal{F}$. An example is all subsets of size at most 2. For such families, two sets of functions coincide. Linear combinations of Walsh-Hadamard characters indexed by $\mathcal{F}$ are exactly linear combinations of the products $\prod_{i \in T} x_i$ for $T \in \mathcal{F}$. So we can move freely between the Fourier view and the "interaction-term" view, $v(S)=\sum_{T\in\mathcal{F},\,T\subseteq S} a_T$.

Free disposal says that every marginal value of an item is non-negative: $$\partial_i v(S) \;=\; \sum_{T \in \mathcal{F},\, i \in T,\, T\setminus\{i\} \subseteq S} a_T \;\ge\; 0 \quad \text{for all items } i \text{ and bundles } S \not\ni i.$$

Each marginal $\partial_i v$ is itself a set function, and its support is $\{T\setminus\{i\}: i\in T\in\mathcal{F}\}$. Monotonicity therefore holds exactly when the minimum of each marginal is non-negative. That observation gives the following characterization, which we will prove and sharpen.

When $\mathcal{F}$ has degree at most 2, each marginal is linear. The condition becomes $a_i + \sum_j \min(0, a_{ij}) \ge 0$, which is an exact linear description with $O(m^2)$ auxiliary variables.

When $\mathcal{F}$ has degree 3, each marginal is a quadratic function over subsets. Minimizing such a function is as hard as max-cut. Certifying monotonicity for arbitrary degree-3 supports is therefore coNP-hard.

When the "interaction hypergraph" of each marginal has bounded treewidth, meaning its interactions form a tree-like pattern, the minimum can be computed by dynamic programming. The dual of that dynamic program gives a polynomial-size linear description of the monotone cone.

The characterization depends on the shape of the support, not on the coefficient values. This is the sense in which we extend the value-restricted characterizations of Boolean functions, such as A Generalization of a Theorem of Rothschild and van Lint, which classifies functions whose coefficients lie in $\{0,\pm1/2^k,\pm2/2^k\}$. Our characterization applies to arbitrary real coefficients on a structured support, and the structural property it tracks is an economic one.

Relation to Prior Work

The closest work is Fourier Analysis-based Iterative Combinatorial Auctions. It models valuations as Fourier-sparse and uses a neural network to guess the important frequencies. It then queries bidders' values at bundles chosen from those frequencies and solves winner determination as a mixed-integer program in the Fourier domain, reporting 6x, 3x and 2x speedups in the Global Synergy (GSVM), Local Synergy (LSVM) and Multi-Region (MRVM) test domains. That work supplies our allocation machinery. We differ in three ways: we learn only from demand queries, we enforce free disposal, and we choose support structurally rather than through a heuristic neural guess.

Learning Fourier Sparse Set Functions supplies the method template. It recovers $k$-sparse set functions from $O(k\log^4 p)$ random value samples by $L_1$ minimization, and it adds submodularity as linear constraints on coefficients, cutting samples from over 450 to 300 on third-order functions. We borrow the idea of encoding an economic axiom in coefficient space, with two changes. Submodularity rules out the complementarities that spectrum auctions are built on, so we use monotonicity instead. And we replace value samples with inequality observations.

Monotone-Value Neural Networks motivates the monotonicity constraint. It shows that non-monotone surrogates lose substantial efficiency, and that enforcing monotonicity through architecture cut efficiency loss by more than a factor of four in LSVM and the Single-Region Value Model (SRVM). It achieves this by giving up any explicit interaction structure. Machine Learning-Powered Combinatorial Clock Auction and Prices, Bids, Values motivate the demand-query setting. The first trains monotone networks on demand-query answers through loss penalties. The second finds that value queries help mainly when targeted at the allocated bundle. Neither offers identification guarantees or interpretable synergies.

BundleFlow scales menu mechanisms to 500 items but is restricted to a single bidder. It therefore constrains our scope rather than competing on the multi-bidder allocation question. Two further papers justify extending the approach to multi-unit lots over products of cyclic groups, which we treat as a secondary extension. On Fourier Analysis of Sparse Boolean Functions over Certain Abelian Groups tests sparsity over general Abelian groups with poly$(s,1/\varepsilon,\log\Delta)$ queries. Learning Bayesian Networks with Low Rank Conditional Probability Tables shows that deterministic Fourier signatures can replace heuristics for support recovery, but it is limited to binary variables.

Research Program

Theory. We first prove the support-shape characterization above. We then study identification from demand queries. A demand answer $S^\star$ at prices $p$ imposes $v(S^\star)-p^\top S^\star \ge v(S)-p^\top S$ for every bundle $S$. For a fixed family $\mathcal{F}$, this is a polyhedral cut on the coefficient vector. We ask when the intersection of such cuts with the monotone cone shrinks to a small neighborhood of the true coefficients. This is a polyhedral analogue of one-bit compressed sensing. We expect the number of queries needed to scale with $|\mathcal{F}|$ times a margin term, because each price vector that changes the chosen bundle cuts one face of the feasible region. We will state the conditions under which this holds.

Algorithm. Each bidder's surrogate is fit by an $L_1$-regularized linear program over $\mathcal{F}$, subject to the monotone cone and the demand cuts. The exponentially many cuts per query are handled lazily. Finding a violated cut means finding the bundle the current surrogate prefers at price $p$, which is a small mixed-integer program over the Fourier representation. The support $\mathcal{F}$ grows adaptively. We start with all pairs of items, then add triples only where the dual variables of the cuts suggest missing interaction mass, keeping the interaction hypergraph within the tractable class. Prices for the next round come from the clearing objective of Machine Learning-Powered Combinatorial Clock Auction, evaluated on the Fourier surrogates. The final allocation uses the Fourier winner-determination program. A bridge bid, meaning a single value query at the allocated bundle as in Prices, Bids, Values, is an optional last step.

Diagnostics. GSVM and LSVM have 18 items, so they have $2^{18}$ bundles and the exact Walsh-Hadamard transform is computable. We will measure how much of each bidder's spectral energy lies at each interaction degree, and whether the true functions fall inside the tractable monotone class. This tells us before any auction runs whether degree-2-plus-tree supports are a realistic modeling choice.

Baselines

The naive reference point is the standard Combinatorial Clock Auction (CCA), which raises item prices by fixed increments and uses no learned model. The file reports that it reached exact market clearing in only 3% of GSVM instances (Machine Learning-Powered Combinatorial Clock Auction).

The strongest demand-query-only competitor is ML-CCA, which trains multiset monotone networks on demand answers. It reports clearing in 56% of GSVM instances and a 7.8 to 9 percentage-point efficiency gain over CCA in GSVM and LSVM.

The strongest hybrid method is MLHCA from Prices, Bids, Values. It reports a tenfold reduction in efficiency loss over the earlier leading method BOCA in LSVM, reports 100% efficiency in SRVM, and exceeds CCA by over 2% efficiency in MRVM. The file gives relative figures only; no reported absolute efficiency values were found on Lacuna for ML-CCA or MLHCA on these domains. We will therefore rerun both from their described configurations rather than quote absolute numbers.

The Fourier value-query auction of Fourier Analysis-based Iterative Combinatorial Auctions is the closest method. The file reports winner-determination speedups for it but no absolute efficiency number.

All methods will run on the same instance seeds from the Spectrum Auction Test Suite (SATS), with the same query budgets counted separately by query type and the same solver time limit. Neural baselines receive hyperparameter tuning of matched cost, measured in grid points.

Two ablations isolate the key ingredient. The first is the same Fourier demand-query linear program with the monotone cone removed. The second replaces the cut-based fit with a hinge-loss regression on demand answers using the same support.

Beating the field means one of two outcomes. The first is higher mean efficiency than ML-CCA at an equal demand-query budget, with confidence intervals across at least 50 instances that do not overlap. The second is matching MLHCA's efficiency without MLHCA's value-query phase.

Why not just…?

Why not just use ML-CCA's monotone networks on demand queries? This is the real threat. On raw efficiency it may win in MRVM, where interactions are dense. The experiments settle it directly with an equal-budget comparison. If the Fourier surrogate matches efficiency, it additionally provides explicit synergy terms, an identification certificate, and faster winner determination, a speed advantage Fourier Analysis-based Iterative Combinatorial Auctions already reports for the value-query setting. If it loses clearly even in GSVM and LSVM, where the spectral diagnostics show low-degree structure, the proposal's premise fails.

Why not just run $L_1$ regression on a degree-2 basis and skip the monotonicity theory? For 98 items the degree-2 basis has about 4,900 terms. That is entirely feasible, which is exactly why this approach is our main ablation rather than a straw man. The evidence against it is indirect. Non-monotone surrogates lost several times more efficiency in Monotone-Value Neural Networks. Separately, axiom constraints cut the samples needed for recovery in Learning Fourier Sparse Set Functions. If removing the cone changes efficiency by less than the noise across instances, we will report that monotonicity is unnecessary in the Fourier setting.

Why not just use a standard clock auction? The reported clearing rate of 3% versus 56% and the efficiency gap of 7.8 to 9 points in Machine Learning-Powered Combinatorial Clock Auction show that model-guided prices matter. CCA stays in the study only as the reference floor.

Why not use BundleFlow's continuous menus? It handles a single bidder and does not enforce that each physical item is allocated only once across competing bidders. The multi-bidder allocation problem studied here is outside its current reach.

Decisive Checks

The first check is whether the exact transforms of GSVM and LSVM valuations place most of their energy on degree-2 or tree-structured supports. If they do not, the tractable class is too narrow for these domains.

The second check is whether, at equal demand-query budgets, the monotone Fourier auction beats ML-CCA in GSVM and LSVM and stays within noise of it in MRVM.

The third check is whether removing the monotone cone measurably lowers efficiency or raises the number of queries to clearing. This is what shows that the characterization, and not just the Fourier basis, is doing the work.

Finally, on synthetic valuations with known sparse monotone coefficients, recovery error should fall with query count at the rate the identification analysis predicts. A mismatch there would indicate a flaw in the theory, independent of auction performance.