Neural auction design trains a neural network to act as an auctioneer. Given everyone's bids, the network decides who gets which items and what each bidder pays. It is trained to maximize the seller's revenue while making lying unprofitable for bidders. These methods now beat hand-designed auctions in multi-item and combinatorial settings, where bidders value bundles of goods. Many real goods sit on a graph, though: adjacent radio licenses, contiguous land parcels, segments of a route. A bidder who wins two disconnected pieces of a corridor has won something nearly worthless, and regulators often forbid such awards. Existing neural auctions treat items as unordered indices. Their randomized allocations can spread probability over broken bundles, the same way image segmentation networks break thin vessels and roads into fragments while still scoring well on pixel-overlap metrics.
We propose an allocation layer whose every possible outcome is a connected bundle, so connectivity holds by construction rather than being encouraged by a penalty. Each bidder's share is "grown" outward from a seed item along the item graph, using the same iterated max-pooling dilation that differentiable skeleton losses use. Any threshold of the grown field is then a connected set. Reading the field as a lottery over thresholds gives a bidder's expected value in closed form, and the result is differentiable. In short, we import the mechanics that the topology-preserving segmentation literature uses to measure connectivity and turn them into a parameterization that guarantees it. We then ask how much revenue and truthfulness connectivity costs.
What the two directions supply, and what is missing
The auction side supplies the training recipe and the benchmarks. RegretNet (Optimal Auctions through Deep Learning) trains allocation and payment networks with an augmented Lagrangian penalty on regret, meaning the most a bidder could gain by misreporting, which an inner gradient search estimates. Three later lines of work refine this recipe. Auction Learning as a Two-Player Game replaces the inner search with a learned misreporting network. Optimal-er Auctions through Attention adds attention layers and a hard regret budget. CAFormer (Advancing Differentiable Mechanism Design) splits a combinatorial allocation into item-to-bundle and bundle-to-bidder matrices. All of these enforce feasibility as "each item goes to at most one bidder." None of them sees a graph over the items.
Learning Revenue-Maximizing Auctions With Differentiable Matching comes closest in spirit. It routes allocations through Sinkhorn matching to impose exact demand constraints such as "exactly $k$ items each." Row and column sums still cannot say whether those $k$ items touch. On the other side, Machine Learning-Powered Combinatorial Clock Auction works with spatial value models such as LSVM, where licenses are adjacent and values reward contiguity. That work optimizes welfare in an iterative clock auction, not revenue in a learned sealed-bid mechanism, and it never constrains bundle shape. Multi-Agent Pathfinding as a Combinatorial Auction does insist on connected path bundles, but it uses exact search with VCG payments. VCG maximizes welfare, not seller revenue, and exact search scales poorly.
The topology side supplies the diagnosis and the operator. clDice shows that overlap losses ignore fragmentation. It extracts soft skeletons with iterated min/max pooling at under 10% training overhead. Betti matching shows something sharper. Standard persistent-homology losses pair the wrong features up to 99.4% of the time, because they compare topological summaries without regard to where those features sit. They also cost $O(n^3)$ to compute. Efficient Betti Matching reduces that cost in 3D. The persistent-homology representation-learning papers (Connectivity-Optimized Representation Learning, Topology-Aware Contrastive Learning) penalize fragmentation in embedding spaces. All of this work treats topology as a loss on a soft output.
That framing transfers badly to auctions. The thing that must be connected is the bundle a bidder actually receives after the lottery is drawn. The expected allocation, a vector of per-item win probabilities, is not that thing. A marginal vector can look perfectly connected while every realized bundle in its support is broken. This is the auction analogue of the spatial blindness that Betti matching exposed. The gap is therefore structural, and we do not try to close it with a better penalty.
Core Claim
A randomized combinatorial allocation over graph-structured goods can be parameterized so that, with probability one, every bidder receives a connected bundle, the bundles of different bidders are disjoint, and expected utility is an exact, piecewise-differentiable function of the network output. We claim this layer matches unconstrained neural auctions in revenue when connectivity is not binding. When the valuation model or a feasibility rule rewards contiguity, we claim it beats them, along with penalty-based and post-processing fixes, at equal regret. We also claim it keeps scaling past the graph sizes where enumerating connected bundles becomes impractical.
The allocation layer
For each bidder $i$ and each candidate seed item, the network outputs gates $g^i_j \in (0,1]$ on items $j$. Working in log space, we write $s = \log x$ for the growth field and grow it on the item graph with neighborhoods $N(j)$:
$$ s^i_{t+1}(j) = \max\Big(s^i_t(j),\ \max_{k \in N(j)} s^i_t(k) + \log g^i_j\Big), \qquad s^i_0 = 0 \text{ at the seed},\ -\infty \text{ elsewhere}. $$
After $T$ steps, $x^i = \exp(s^i)$ equals the best product of gates along any path from the seed. Values can only fall along such a path. Any superlevel set $\{j : x^i(j) \ge \tau\}$ therefore contains the whole maximizing path to each of its members, so it is connected.
In persistent-homology terms, the superlevel filtration of $x^i$ has a single connected component at every level. The layer reaches by construction the zeroth-order topology that clDice and Betti matching try to reach through a loss.
To make bundles disjoint, each item goes to the bidder with the largest $x^i(j)$, which works like a Voronoi partition of the graph. Under consistent tie-breaking, the maximizing path to an item stays inside the winner's cell, so thresholded cells stay connected. A single shared threshold $\tau \sim U[0,1]$ then gives bidder $i$ the bundle $S_i(\tau)$, and the seller keeps the remaining items. Sort bidder $i$'s values within its cell as $x_{(1)} \ge \dots \ge x_{(m)}$, set $x_{(m+1)} = 0$, and let $v_i$ be the bidder's reported bundle valuation. Expected value has the form of a Lovász extension:
$$ \mathbb{E}_\tau\big[v_i(S_i(\tau))\big] = \sum_{k=1}^{m} \big(x_{(k)} - x_{(k+1)}\big)\, v_i(\{(1),\dots,(k)\}). $$
This expression is exact. It needs only $m$ queries to the valuation function and is differentiable wherever the sort order is fixed. A one-dimensional lottery is not rich enough on its own. We therefore mix $M$ such templates, each with its own seeds and gates, using softmax weights, plus a seller-keeps-all template.
Payments use the standard scaled-sigmoid head for individual rationality, meaning no bidder pays more than its expected value. Regret is trained with the misreporter network of Rahme et al. under the regret budget of RegretFormer. The input encoder is a graph-aware attention model, so the comparison with GNN-style encoders isolates the decoder.
The log-space recursion uses only max and plus, so for fixed seeds the allocation map is piecewise linear. That property matters because Certifying Strategyproof Auction Networks had to replace softmax with piecewise-linear sparsemax before mixed-integer certification became possible. On the smallest instances, our layer can be encoded the same way. A certificate there would cover both regret and connectivity, and connectivity holds trivially by construction.
Research Program
The work has four parts. The first is diagnosis. We train RegretNet, RegretFormer-style and CAFormer mechanisms on graph-structured goods and measure fragmentation directly. The measure is the probability mass of realized bundles with more than one connected component, which requires exposing a bundle-level lottery. CAFormer's bundle decomposition gives one directly. For item-wise models we use independent rounding.
The second part builds the grown-allocation layer described above. The third part asks what connectivity costs in incentives, a gap no prior work has measured. Truthful implementability needs a form of monotonicity, and forcing contiguity could interact with it. We compare the revenue achievable at matched regret by the best connected mechanism and the best unconstrained one, and we call the difference the "price of connectivity." We also check whether connected mechanisms show a larger gap between gradient-estimated and certified regret on small instances. The fourth part is scaling. We follow how revenue and wall-clock time change as the graph grows from paths to grids of LSVM size and beyond.
Baselines
The naive reference is VCG run on the same graph instances. VCG is truthful and allocates efficiently, and it awards connected bundles whenever bidders value only connected bundles. It is the "do nothing clever" mechanism. CAFormer's paper and RegretNet report that it yields clearly lower revenue than learned mechanisms in combinatorial settings, but the file gives no VCG number. Beating it by a clear revenue margin is a minimum bar, not a result.
The strongest existing method is CAFormer. Its best reported result is revenue 11.534 at regret 0.004 in the asymmetric 2-bidder, 5-item combinatorial Setting C, against 11.140 for the ABAMA heuristic (Advancing Differentiable Mechanism Design). We run CAFormer in two forms. The first is unmodified, with disconnected realized bundles counted as infeasible in the hard-constraint regime. The second is the strong structural variant, with its bundle set restricted to the enumerated connected subgraphs of the item graph. That second form is exact wherever enumeration is affordable, and it is the baseline we most need to match.
We also run a topology-penalty baseline. It is CAFormer plus a persistence-based zeroth-homology penalty on the realized bundle lottery, in the style of Betti matching, and alternatively a soft-clDice-style penalty on marginals. This baseline tests whether a loss suffices. For exact-$k$ demand variants we add the Sinkhorn mechanism of Curry et al.. They report revenue 0.571 and regret 0.003 on 2 agents and 15 items, but on no graph instance.
On the graph-structured instances themselves, there is no reported result on Lacuna for any method. Every number there comes from our own runs.
Fairness rules apply to all methods. Each uses the same 640,000 training and 10,000 test valuation profiles, the same misreporter-based regret estimator, the same normalized regret budget, and the same hyperparameter-search budget and GPU-hours. Final regret for every method is re-estimated with a much stronger held-out attack: many random restarts plus the trained misreporter. "Beating" a baseline means higher test revenue at equal or lower attacked regret, with zero fragmentation in the hard-constraint regime, across five seeds.
Two ablations isolate the key ingredient. The first keeps the grown decoder but samples thresholds independently per bidder and drops the Voronoi assignment, enforcing disjointness by a penalty instead. This tests whether shared-threshold coupling matters. The second keeps everything else but replaces gated growth with a softmax over items followed by a connectivity penalty. This tests whether the guarantee itself, rather than the encoder or the mixture over templates, produces the gains.
Why not just…?
Why not just enumerate connected bundles and run CAFormer over them? On small graphs this is the right answer, and we treat it as the exact reference rather than a straw man. The real question is where it stops working. The number of connected subgraphs grows exponentially on grids, and CAFormer's own paper flags input explosion over $2^m - 1$ bundles as its central difficulty. Our scaling experiment plots revenue and training time for both methods from 5-item paths to 6x6 grids. If enumeration stays tractable and wins at every size we can run, the grown layer is not needed, and we would report that.
Why not just discard disconnected bundles after training? Post-processing destroys the incentive guarantees that training bought. Removing outcomes changes utilities, so the learned payments no longer match the allocations, and regret measured after filtering can jump. Our diagnosis experiment measures this directly. We report revenue and attacked regret of trained CAFormer before and after filtering, and we expect a regret increase proportional to the fragmented probability mass.
Why not just add a topology loss such as clDice or a persistence penalty? A loss on per-item win probabilities targets the wrong object, because connected marginals do not imply connected realized bundles. Even a loss on realized bundles is soft, so some fragmented mass survives. The loss also adds non-monotone coupling between neighboring items, which could disturb the regret optimization. The Betti matching results warn that naive topological losses misassign features, and they cost $O(n^3)$ per evaluation. The topology-penalty baseline settles this empirically. It wins if it reaches comparable revenue with near-zero fragmentation at equal regret and similar cost.
Why not just encode the graph with a GNN or graph-aware attention? Graph structure in the input does not constrain the output. The segmentation literature shows that high-capacity architectures still fragment thin structures when trained with overlap-style losses (clDice). Our encoder is already graph-aware in every variant, so the second ablation measures how much the decoder adds beyond it.
Proposed Experiments
We use three benchmark families. The first is CAFormer's Setting C with its five items placed on a path and on a complete graph. On the complete graph every bundle is connected, so this checks how much expressiveness the grown layer loses when topology does not bind, and its revenue should approach 11.534. The second is synthetic grids of size 3x3, 3x6, 5x5 and 6x6. There, uniform base values combine with bundle values that count only the largest connected component, or with single-minded bidders who need a path between two given cells, following the pathfinding auction setup. The third is the LSVM model from the Spectrum Auction Test Suite with a small number of bidders, run as a sealed-bid revenue problem.
We run two regimes. In the soft regime, connectivity matters only through values. In the hard regime, a regulator rule makes any fragmented bundle infeasible.
Metrics are expected revenue, attacked regret, fragmented probability mass, the price of connectivity, and wall-clock training time. On 1-2 bidder instances with 4-6 items, we also compute certified regret with the mixed-integer approach of Certifying Strategyproof Auction Networks.
Three checks decide the claims. The first is the complete-graph Setting C. If the grown layer falls well short of CAFormer there, the mixture-of-nested-lotteries family is too narrow, and we would increase $M$ or revise the decoder before any other claim. The second is the 3x6 LSVM-sized grid in the hard regime. There the proposal must match connected-enumeration CAFormer within a few percent in revenue at equal regret, and beat the penalty and post-processing baselines. The third is the 6x6 grid. There enumeration should be impractical, and the grown layer must still train within the shared compute budget and clearly exceed VCG revenue.
If the price of connectivity turns out near zero in the soft regime, the honest conclusion is that contiguity-rewarding values already steer neural auctions toward connected bundles. The contribution would then rest on the hard regime and on scaling.
References
- Optimal Auctions through Deep Learning
- Auction Learning as a Two-Player Game
- Optimal-er Auctions through Attention
- Advancing Differentiable Mechanism Design: Neural Architectures for Combinatorial Auctions
- Learning Revenue-Maximizing Auctions With Differentiable Matching
- Machine Learning-Powered Combinatorial Clock Auction
- Multi-Agent Pathfinding as a Combinatorial Auction
- clDice - A Novel Topology-Preserving Loss Function for Tubular Structure Segmentation
- Topologically Faithful Image Segmentation via Induced Matching of Persistence Barcodes
- Efficient Betti Matching Enables Topology-Aware 3D Segmentation via Persistent Homology
- Connectivity-Optimized Representation Learning via Persistent Homology
- Topology-Aware Contrastive Learning: Regulating Representation Connectivity via Persistent Homology
- Certifying Strategyproof Auction Networks