Learning Revenue-Maximizing Auctions With Differentiable Matching

Michael J. Curry, Uro Lyi, Tom Goldstein, John Dickerson

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 an auction that maximizes revenue while remaining "strategyproof"—ensuring bidders have no incentive to misreport their valuations—is a fundamental challenge in mechanism design. While Myerson's work provided elegant solutions for single-item auctions, multi-item and multi-bidder settings are often analytically intractable. Recent "differentiable economics" approaches, such as RegretNet, have used neural networks to learn these auctions from data. However, these models often rely on simple softmax-based allocation rules that struggle with complex constraints, such as settings without "free disposal" where an auctioneer is obligated to allocate an exact number of items.

Methods: Differentiable Matching via Sinkhorn

The core innovation of this work is a dual-network architecture consisting of an allocation network and a payment network. Unlike previous models, the allocation network treats the auction as a bipartite matching problem between bidders and items, solved using the Sinkhorn algorithm.

The dual-network architecture featuring a Sinkhorn layer for differentiable matching.

By unrolling the iterations of the Sinkhorn algorithm, the entire allocation process becomes end-to-end differentiable. This allows the model to enforce specific marginal constraints—such as "exactly-k" demand—by adjusting the marginal vectors fed into the Sinkhorn layer. The model is trained using an augmented Lagrangian objective that seeks to maximize revenue while penalizing "regret," which measures the potential gain a bidder could achieve by lying about their valuations.

Key Results

The proposed architecture was evaluated using synthetic valuation data drawn from uniform distributions. In single-agent tests, the model successfully recovered known analytical optima. A significant breakthrough was the model's performance in "Exactly-One" demand settings, where each bidder must receive exactly one item. Previous architectures like RegretNet are mathematically unable to guarantee valid allocations in such scenarios.

Allocation probabilities for Exactly-One and Unit-Demand settings.

In multi-agent settings (e.g., 2 agents and 3 items), the learned auctions significantly outperformed standard baselines like the VCG auction in terms of revenue. Furthermore, the model maintained very low empirical regret (often < 0.001), indicating that the learned mechanisms are nearly strategyproof.

Conclusion and Future Work

By framing auction allocation as a differentiable matching problem, this architecture provides a flexible, "plug-and-play" framework for diverse auction rules. While the Sinkhorn algorithm introduces some computational overhead compared to simpler models, it enables the discovery of high-revenue mechanisms in complex settings that were previously unreachable. Future work will explore scaling these methods to even larger auctions and optimizing the Sinkhorn layer for faster training.

Summary updated

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.
BibTeX
@inproceedings{curry2022learning,
  author = {Michael J. Curry and Uro Lyi and Tom Goldstein and John Dickerson},
  title = {{Learning Revenue-Maximizing Auctions With Differentiable Matching}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=xL3xhFATsu},
}
Figure