Abstract
We propose a new architecture to approximately learn incentive compatible, revenue-maximizing auctions from sampled valuations. Our architecture uses the Sinkhorn algorithm to perform a differentiable bipartite matching which allows the network to learn strategyproof revenue-maximizing mechanisms in settings not learnable by the previous RegretNet architecture. In particular, our architecture is able to learn mechanisms in settings without free disposal where each bidder must be allocated exactly some number of items. In experiments, we show our approach successfully recovers multiple known optimal mechanisms and high-revenue, low-regret mechanisms in larger settings where the optimal mechanism is unknown.
Introduction
Designing auctions that maximize revenue while ensuring bidders remain truthful (strategyproof) is a fundamental challenge in economic theory. While optimal mechanisms for single-item auctions are well-defined, the multi-item, multi-bidder case remains largely unsolved. Recent advances in deep learning, such as RegretNet, have attempted to approximate these mechanisms. However, existing architectures often struggle with strict combinatorial constraints, such as "exactly-k demand," where bidders must receive a specific number of items—a common requirement in industrial applications like display advertising.
Methodology
The core innovation of this work is treating the auction allocation as a minimum-cost bipartite matching problem between bidders and items, solved via a differentiable pipeline.
Architecture
The proposed model consists of two primary components: an allocation network that maps bidder valuations to a "cost matrix," and a separate payment network.
Differentiable Matching via Sinkhorn
To enforce allocation constraints, the cost matrix is processed using the Sinkhorn algorithm. By incorporating predefined marginals representing supply and demand, the algorithm iteratively scales the matrix into a valid, feasible allocation matrix. Because the Sinkhorn algorithm is composed of differentiable operations, the entire system can be trained end-to-end using backpropagation to maximize revenue while minimizing bidder regret.
Experimental Results
The architecture was evaluated using synthetic datasets where bidder valuations for items were drawn independently from a uniform distribution $U[0,1]$.
Recovery of Optimal Mechanisms
The model successfully recovered known optimal mechanisms for single-agent settings under both unit-demand and exactly-one demand constraints. Figure 2 illustrates the learned allocation probabilities, showing sharp boundaries that align with theoretical expectations.
Performance in Complex Settings
In settings where the optimal mechanism is unknown—such as a 2-agent, 15-item auction with exactly-one demand—the Sinkhorn architecture achieved high revenue (0.571) with negligible regret (0.003). This is a significant result, as previous architectures like RegretNet are structurally unable to represent such constraints. While RegretNet remains faster due to its simpler softmax-based operations, the Sinkhorn approach offers superior flexibility for constrained mechanism design.
Discussion and Conclusion
This research demonstrates that framing allocation as an optimal transport problem allows for the decoupling of auction constraints from the neural network architecture. By simply adjusting the marginals in the Sinkhorn algorithm, the same model can adapt to various auction rules.
However, challenges remain regarding computational overhead and hyperparameter sensitivity, particularly the entropy regularization parameter ($\epsilon$). Future work will focus on improving training efficiency and extending the framework to better handle randomized allocations. Overall, this work marks a significant step toward maturing differentiable economics for complex, real-world mechanism design.
Summary updated