First-order method improves design of non-truthful auctions with multiple bidders
First-Order Bilevel Optimization for Non-truthful Auction Design
Computer Science and Game Theory
Summary
Designing auctions where bidders do not just tell the truth about their values is hard because bidders change their bid strategies as the auction changes. The authors treat this as a game between an auction designer and many strategic bidders and create a new method that uses only gradient information to optimize auction revenue. Their approach can find good auction designs faster than older methods and works well even when there are many bidders or multiple items for sale. It also finds auctions that earn almost as much as those with truthful bidding, offering a new way to automate the design of complex auctions.
What this means in practice
- •For online advertising platforms: Optimize ad auction mechanisms to increase revenue even when bidders try to strategize rather than bid truthfully.$Commercial implications: This enables building better auction-based ad platforms that extract higher revenues by exploiting bidder strategies at scale.
- •For marketplace platform engineers: Automatically design complex multi-item auctions that adapt as users change their bidding behavior, improving platform earnings.
Authors
Shing-Hei Ho, April Niu, Ellen Vitercik, Kai Wang
Abstract
Automated mechanism design has enabled the learning of complex auction mechanisms using neural networks. However, designing non-truthful auctions remains challenging because bidders' equilibrium strategies depend on the auction mechanism and thus evolve as the mechanism is optimized. In this work, we formulate auction design as a Stackelberg game with multiple strategic followers and develop a fully first-order algorithm for revenue optimization in non-truthful auctions. We establish non-asymptotic guarantees for hypergradient approximation and show that, under standard smoothness and strong-monotonicity assumptions, our method reaches an $O(ε)$-stationary point using $\tilde{\mathcal{O}}(ε^{-2})$ first-order oracle calls. Experiments on symmetric and asymmetric single-item auctions, as well as multi-item auctions, show that our method converges faster than second- and zeroth-order baselines and scales better as the number of bidders increases. Our method also discovers auctions that achieve revenue close to truthful baselines. These results provide a scalable framework for automated mechanism design beyond truthful auctions.