First-Order Bilevel Optimization for Non-truthful Auction Design
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 𝒪̃(ε−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.
Related
- An Ω(κy8ε−6) Lower Bound for Stochastic NC-SC Bilevel Optimization with First-order Oracles
- Accelerating Finite-Sum Bilevel Optimization with Fully First-Order Oracles
- Optimal Stochastic Bilevel Optimization with First-Order Oracles
- Improved KKT Complexity for First-Order Bilevel Optimization under Weak Lower-Level Convexity
- The Minimax Cost of Smoothness in Fully First-Order Stochastic Bilevel Optimization
BibTeX
@misc{ho2026firstorder,
title = {{First-Order Bilevel Optimization for Non-truthful Auction Design}},
author = {Shing-Hei Ho and April Niu and Ellen Vitercik and Kai Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40403},
eprint = {2610.40403},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40403},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - First-Order Bilevel Optimization for Non-truthful Auction Design
AU - Shing-Hei Ho
AU - April Niu
AU - Ellen Vitercik
AU - Kai Wang
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.40403
UR - https://arxiv.org/abs/2610.40403
AB - 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 𝒪̃(ε^−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.
ER -