betaFeedback

WorksComputer Science

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(ε)O(ε)-stationary point using O~(ε−2)\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.

Introduction

Automated mechanism design (AMD) uses computation and data to optimize auction mechanisms when analytical solutions are unavailable. Early AMD approaches formulate mechanism design as large-scale mathematical programs ([9, 10]), while recent work uses neural networks to learn approximately revenue-optimal mechanisms from valuation samples ([13, 15, 35, 31]). These methods primarily focus on truthful mechanisms, where incentive compatibility makes truthful reporting an equilibrium and therefore removes the need to compute bidders’ strategic responses.

Many widely deployed auctions, however, are non-truthful ([7, 18, 17]). Although the revelation principle often permits mechanism designers to restrict their attention to truthful mechanisms without loss, it does not apply in many settings, such as when bidders have type-dependent constraints on their feasible actions [3]. Moreover, practical considerations may limit the mechanism to a prescribed family of non-truthful auctions, such as first-price auctions with reserves. Such auction formats are common in practice; for example, first-price auctions are widespread in online advertising due to their simplicity and transparency [20]. However, optimizing non-truthful mechanisms is substantially harder: changing the mechanism changes bidders’ equilibrium strategies, so the revenue must be optimized through the equilibrium of an induced multi-player game.

We formulate non-truthful AMD as a multi-follower Stackelberg problem, where the auctioneer is the leader and bidders are strategic followers. This formulation connects mechanism design to bilevel optimization. Existing approaches to non-truthful mechanism optimization either use zeroth-order optimization ([16]) or assume access to a differentiable equilibrium oracle ([33, 34]). Meanwhile, current fully first-order bilevel methods primarily consider a single-follower setting ([28, 26]). Unlike the single-follower bilevel problem, however, a multi-follower equilibrium couples the responses of all followers: changing one follower’s strategy affects the incentives of the others, and these cross-player effects are generally asymmetric, so standard first-order bilevel constructions do not extend directly. This leaves open how to develop a scalable fully first-order method for multiple strategic followers.

Main contributions. Our contributions are threefold. First, we formulate non-truthful auction design as a Stackelberg game with N>1N > 1 followers and develop a fully first-order method for symmetric-Jacobian games, achieving ϵ\epsilon-stationarity with O(Nϵ−2)O(N\epsilon^{-2}) gradient oracle complexity. We also show why this approach fails in asymmetric games: the true hypergradient requires Jacobian J−TJ^{-\mathsf{T}} whereas our method yields J−1J^{-1}. Second, we resolve this mismatch using a finite-difference potential function that induces an auxiliary game with a local Jacobian approximating J−TJ^{-\mathsf{T}}. We prove local strong monotonicity and non-asymptotic hypergradient guarantees for the auxiliary game, provide a fully first-order algorithm that converges to ϵ\epsilon-stationarity using O~(N2ϵ−2)\widetilde{O}(N^2\epsilon^{-2}) oracle calls, and extend the analysis to linear inequality-constrained follower games. Lastly, we formulate a neural-network-parameterized auction design problem in which the auctioneer optimizes revenue while bidders respond strategically. We develop a warm-start strategy for tracking differentiable branches of local Nash equilibria, allowing the first-order method to be applied without assuming a globally unique equilibrium. We evaluate the approach on symmetric and asymmetric single-item auctions and multi-item auctions, demonstrating its applicability to equilibrium-dependent mechanism design.

Related Works

Neural Approaches to Learning Truthful Auctions. Classical approaches to revenue-maximizing mechanism design face two obstacles in practice. First, they typically assume the designer knows the distribution of buyers’ values in advance [e.g., 29]—information that is often unavailable. Second, a general closed-form characterization of revenue-optimal multi-item auctions is unknown [e.g., 12, 32]. Automated mechanism design (AMD) aims to circumvent these challenges by optimizing for revenue-maximizing mechanisms using sample valuation profiles and computational search [9, 10]. The first neural approach to AMD is the work of Dütting et al. [13], which represents allocation and payment rules using neural networks and penalizing bidders’ gains from misreporting to approximately enforce dominant-strategy incentive compatibility. More recently, GemNet [35] uses bidder-independent menus and a post-training transformation to guarantee incentive compatibility. In contrast, we optimize neural pay-your-bid mechanisms whose revenue depends on bidders’ strategic responses, requiring us to account for how equilibrium strategies change with the mechanism.

Non-truthful Auction Design: Optimizing non-truthful auctions requires accounting for how mechanism changes affect bidders’ equilibrium strategies. Several papers show that gradient dynamics empirically converge to Nash equilibria in auction games, but focus on computing bidders’ strategies rather than optimizing the auction itself [4, 5, 24, 21]. More directly related, Feng et al. [16] optimize first-price auction reserves via zeroth-order gradient descent. They compute gradient estimates based on bidders’ responsiveness to experimental shocks in reserves, rather than differentiating through a computed equilibrium. Unlike reserve optimization, our framework learns the allocation rule itself, including for multi-item auctions. Meanwhile, [33] formulate mechanism design as a bilevel optimization problem with (coarse) correlated equilibria as the lower-level solution. They assume access to a neural network that outputs a differentiable equilibrium for discrete-action games and its gradient with respect to mechanism parameters. In contrast, we develop novel fully first-order bilevel optimization algorithms with convergence guarantees for Stackelberg games with multiple followers, and apply them to auction design. We design auction mechanisms parameterized by neural networks and compute Nash equilibria through gradient dynamics. Scalability is a key limitation of [33]; their models are only trained on two-player games with at most 16 discrete actions for each player. In contrast, our action space is continuous.

Bilevel Optimization: Bilevel optimization (BO) is an optimization problem constrained by the solution of another optimization problem. It is essentially a Stackelberg game with a single follower. A body of work studies fully first-order methods for BO. These works typically assume a strongly convex lower-level problem to ensure a unique lower-level solution and an invertible KKT matrix. For an unconstrained lower-level problem, [28] derives an approximate hypergradient using a penalty function and achieves a complexity of O(ϵ−1.5)O(\epsilon^{-1.5}) in deterministic BO. For linearly constrained lower-level problems, [26, 37] achieves a complexity of O(ϵ−3δ−1)O(\epsilon^{-3}\delta^{-1}) to converge to a (ϵ,δ)(\epsilon,\delta)-Goldstein stationary point. To the best of our knowledge, existing first-order algorithms for solving Stackelberg games with multiple followers with implicit differentiation is only applicable when Jacobian is block-diagonal [30].

Non-truthful Auction Design as a Stackelberg Game

Consider a sealed-bid auction of NN bidders and JJ items. Bidder ii has a private valuation ti∈Ti⊆R+Jt_i \in\mathcal{T}_i \subseteq\mathbb{R}^{J}_{+}, drawn independently from a distribution FiF_i, and submits a bid ai∈Ai⊆R+Ja_i \in\mathcal{A}_i \subseteq\mathbb{R}^{J}_{+}. Let t=(t1,…,tN)t = (t_1, \ldots, t_N) and a=(a1,…,aN)a = (a_1, \ldots, a_N). An auction mechanism is parametrized by x∈X⊆Rpx \in\mathcal{X} \subseteq\mathbb{R}^{p} and consists of a randomized allocation rule ρx\rho_x and a payment rule PxP_x. Given the auction xx, a bid profile aa, and valuation tit_i for bidder ii, bidder ii's expected utility can be computed by ui(x,a,ti)u_i(x, a, t_i).

For a given mechanism xx, each bidder ii chooses a parametrized bidding strategy βyi:Ti→Ai\beta_{y_i}: \mathcal{T}_i \to\mathcal{A}_i. This strategy maps the bidder's valuation tit_i to a bid in Ai\mathcal{A}_i, and yiy_i is a parameter vector defining the strategy. Unless stated otherwise, yi∈Yi(x):=Rniy_i \in\mathcal{Y}_i(x) := \mathbb{R}^{n_i}. Let y:=(y1,⋯ ,yN)∈Y(x):=∏i=1NYi(x)⊆Rny := (y_1, \cdots, y_N) \in\mathcal{Y}(x) := \prod_{i=1}^{N}\mathcal{Y}_i(x) \subseteq\mathbb{R}^{n} and write y¬i:=(yj)j≠iy_{\neg i} := (y_j)_{j \ne i}. The mechanism and bidding strategies induce an ex-ante expected cost for each bidder. We work with costs rather than utilities so that the follower game can be expressed as a minimization problem.

Definition 3.1 (Ex-ante expected cost). Bidder ii's ex-ante expected cost is

gi(x,yi,y¬i):=−Et1,…,tN[ui(x,{βyj(tj)}j=1N,ti)].g_i(x, y_i, y_{\neg i}) := -\mathbb{E}_{t_1,\ldots,t_N}\left[u_i\left(x,\{\beta_{y_j}(t_j)\}_{j=1}^{N},t_i\right)\right].

Thus, minimizing gig_i is equivalent to maximizing bidder ii's ex-ante expected utility.

For a fixed mechanism xx, the bidders therefore play a normal-form game G(x):=(x,[N],{Yi}i∈[N],{gi}i∈[N])\mathcal{G}(x) := (x, [N], \{\mathcal{Y}_i\}_{i \in[N]}, \{g_i\}_{i \in[N]}). We assume bidders follow a Nash equilibrium with respect to the ex-ante expected cost functions. A Nash equilibrium is a strategy profile in which no player can reduce their expected cost by unilaterally changing their strategy parameter while holding everyone else's strategies fixed.

Definition 3.2 (Nash equilibrium). We say y∗∈Y(x)y^* \in\mathcal{Y}(x) is a Nash equilibrium of the game G(x)\mathcal{G}(x) if and only if

gi(x,y∗)≤gi(x,yi,y¬i∗),∀i∈[N], ∀yi∈Yi(x).g_i(x,y^*) \leq g_i(x,y_i,y^*_{\neg i}),\quad\forall i \in[N],\ \forall y_i \in\mathcal{Y}_i(x).

We denote the set of Nash equilibria as NE⁡(G(x))\operatorname{NE}(\mathcal{G}(x)).

The auction design problem is to choose the expected payment rule PxP_x and allocation rule ρx\rho_x that maximize some objective, assuming bidders play Nash equilibrium strategies. We focus on maximizing the auctioneer's expected revenue. Because our framework is written as a minimization problem, let f(x,y)f(x,y) denote the negative expected revenue under mechanism xx and bidding-strategy profile yy. We first consider the setting in which the induced lower-level game has a unique Nash equilibrium y∗(x)y^*(x) and formulate the auction design problem as a Stackelberg Game.

min⁡x∈XF(x):=f(x,y∗(x))s.t. y∗(x)∈NE⁡(G(x)).(1)\min_{x \in\mathcal{X}} F(x) := f(x,y^*(x)) \quad\text{s.t. } y^*(x) \in\operatorname{NE}(\mathcal{G}(x)). \tag*{(1)}

§ 6 extends this formulation to auction games with multiple equilibria.

To solve Problem P1, we run gradient descent on F(x)F(x) to optimize the parameter xx. Our goal is to find an ϵ\epsilon-stationary point, which is defined as any point x∈Rpx \in\mathbb{R}^{p} such that ∥∇F(x)∥≤ϵ\|\nabla F(x)\| \leq\epsilon.

Hypergradient and second-order information: Due to the nested structure in Problem P1, computing the gradient of the function F(x)F(x) requires differentiating through the Nash equilibrium y∗(x)y^*(x). To show how to compute dy∗dx\frac{d y^*}{d x}, we define the gradient operator:

Definition 3.3 (gradient operator). V(x,y):=(∇y1g1(x,y),⋯ ,∇yNgN(x,y))∈Rn\mathcal{V}(x,y) := (\nabla_{y_1}g_1(x,y), \cdots, \nabla_{y_N}g_N(x,y)) \in\mathbb{R}^{n}.

We can write the optimality conditions of the Nash equilibrium y∗y^* using the gradient operator, and apply the Implicit Function Theorem to solve dy∗dx\frac{d y^*}{d x}:

V(x,y∗)=0 (optimality)⟹∂∂xV(x,y∗)+∂∂yV(x,y∗)ddxy∗(x)=0(2)\mathcal{V}(x,y^*) = 0 \ \text{(optimality)} \quad\Longrightarrow\quad\frac{\partial}{\partial x}\mathcal{V}(x,y^*) + \frac{\partial}{\partial y}\mathcal{V}(x,y^*)\frac{d}{d x}y^*(x) = 0 \tag*{(2)}

Solving Equation (2) to get dy∗dx\frac{d y^*}{d x}, we get the following exact hypergradient:

∇F(x)=∇xf(x,y∗(x))+(ddxy∗(x))T∇yf(x,y∗(x))=∇xf(x,y∗(x))−(∂∂xV(x,y∗))TJ(x,y∗)−T∇yf(x,y∗).(3)\begin{aligned} \nabla F(x) = \nabla_x f(x,y^*(x)) + \left(\frac{d}{d x}y^*(x)\right)^{\mathsf{T}}\nabla_y f(x,y^*(x)) \\ &= \nabla_x f(x,y^*(x)) - \left(\frac{\partial}{\partial x}\mathcal{V}(x,y^*)\right)^{\mathsf{T}}J(x,y^*)^{-\mathsf{T}}\nabla_y f(x,y^*). \tag*{(3)} \end{aligned}

where J(x,y):=∂∂yV(x,y)J(x,y) := \frac{\partial}{\partial y}\mathcal{V}(x,y) is the Jacobian of the gradient operator.

Equation (3) gives us the exact hypergradient to solve Problem P1. However, the hypergradient involves the Jacobian J(x,y∗)J(x,y^*) of the gradient operator, which is second-order and can be computationally intractable. The main goal of this work is to construct an approximate hypergradient estimator that bypasses second-order information and solves Problem P1 efficiently.

Definitions and Assumptions: Below we summarize the definitions and assumptions needed for the later hypergradient and convergence analysis for solving Problem P1.

References

  1. [1]Abien Fred Agarap. Deep learning using rectified linear units (relu). arXiv preprint arXiv:1803.08375, 2018.arxiv.org/abs/1803.08375
  2. [2]Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv:1607.06450, 2016.arxiv.org/abs/1607.06450
  3. [3]Batya Berzack, Rotem Oshman, and Inbal Talgam-Cohen. Optimal auctions for constrained buyers. arXiv preprint arXiv:2606.30776, 2026.
  4. [4]Martin Bichler, Maximilian Fichtl, Stefan Heidekrüger, Nils Kohring, and Paul Sutterer. Learning equilibria in symmetric auction games using artificial neural networks. Nature machine intelligence, 3(8):687–695, 2021.DOI
  5. [5]Martin Bichler, Nils Kohring, and Stefan Heidekrüger. Learning equilibria in asymmetric auction games. INFORMS Journal on Computing, 35(3):523–542, 2023.DOI
  6. [6]Martin Bichler, Stephan B Lunowa, Matthias Oberlechner, Fabian R Pieroth, and Barbara Wohlmuth. On the convergence of learning algorithms in bayesian auction games. arXiv preprint arXiv:2311.15398, 2023.arxiv.org/abs/2311.15398
  7. [7]Jason Bigler. An update on first price auctions for google ad manager. Retrieved October, 22:2025, 2019.
  8. [8]Frank H Clarke. Optimization and nonsmooth analysis. SIAM, 1990.
  9. [9]Vincent Conitzer and Tuomas Sandholm. Complexity of mechanism design. arXiv preprint cs/0205075, 2002.arxiv.org/abs/1408.1486
  10. [10]Vincent Conitzer and Tuomas Sandholm. Self-interested automated mechanism design and implications for optimal combinatorial auctions. In Proceedings of the 5th ACM Conference on Electronic Commerce, pp. 132–141, 2004.DOI
  11. [11]Ashok Cutkosky, Harsh Mehta, and Francesco Orabona. Optimal stochastic non-smooth non-convex optimization through online-to-non-convex conversion. In International Conference on Machine Learning, pp. 6643–6670. PMLR, 2023.arxiv.org/abs/2302.03775
  12. [13]Paul Dütting, Zhe Feng, Harikrishna Narasimhan, David Parkes, and Sai Srivatsa Ravindranath. Optimal auctions through deep learning. In International Conference on Machine Learning, pp. 1706–1715. PMLR, 2019.
  13. [14]Francisco Facchinei and Jong-Shi Pang. Finite-dimensional variational inequalities and complementarity problems. Springer, 2003.
  14. [15]Zhe Feng, Harikrishna Narasimhan, and David C Parkes. Deep learning for revenue-optimal auctions with budgets. In Proceedings of the 17th international conference on autonomous agents and multiagent systems, pp. 354–362, 2018.DOI
  15. [16]Zhe Feng, Sébastien Lahaie, Jon Schneider, and Jinchao Ye. Reserve price optimization for first price auctions in display advertising. In International Conference on Machine Learning, pp. 3230–3239. PMLR, 2021.
  16. [17]Rigel Galgana and Negin Golrezaei. Learning in repeated multiunit pay-as-bid auctions. Manufacturing & Service Operations Management, 27(1):200–229, 2025.DOI
  17. [18]Shumpei Goke, Gabriel Y Weintraub, Ralph Mastromonaco, and Sam Seljan. Bidders’ responses to auction format change in internet display advertising auctions. arXiv preprint arXiv:2110.13814, 2021.arxiv.org/abs/2110.13814
  18. [19]Allen A Goldstein. Optimization of lipschitz continuous functions. Mathematical Programming, 13(1):14–22, 1977.DOI
  19. [20]Matt Harada. The ad exchange’s place in a first-price world. Marketing Technology Insights, 2018. URL https://martechseries.com/mts-insights/guest-authors/ad-exchanges-place-first-price-world/.
  20. [21]Kexin Huang, Ziqian Chen, Xue Wang, Chongming Gao, Jinyang Gao, Bolin Ding, and Xiang Wang. Learning bayesian nash equilibrium in auction games via approximate best response. In *Forty-second International Conference on Machine Learning*, 2025.
  21. [22]Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. *arXiv preprint arXiv:1412.6980*, 2014.arxiv.org/abs/1412.6980
  22. [23]Günter Klambauer, Thomas Unterthiner, Andreas Mayr, and Sepp Hochreiter. Self-normalizing neural networks. *Advances in neural information processing systems*, 30, 2017.arxiv.org/abs/1706.02515
  23. [24]Nils Kohring, Fabian Raoul Pieroth, and Martin Bichler. Enabling first-order gradient-based learning for equilibrium computation in markets. In *International Conference on Machine Learning*, pp. 17327–17342. PMLR, 2023.arxiv.org/abs/2303.09500
  24. [25]Guy Kornowski and Ohad Shamir. An algorithm with optimal dimension-dependence for zero-order nonsmooth nonconvex stochastic optimization. *Journal of Machine Learning Research*, 25(122):1–14, 2024.arxiv.org/abs/2307.04504
  25. [26]Guy Kornowski, Swati Padmanabhan, Kai Wang, Zhe Zhang, and Suvrit Sra. First-order methods for linearly constrained bilevel optimization. *Advances in Neural Information Processing Systems*, 37:141417–141460, 2024.arxiv.org/abs/2406.12771
  26. [27]Vijay Krishna. *Auction theory*. Academic press, 2009.
  27. [28]Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D Nowak. A fully first-order method for stochastic bilevel optimization. In *International Conference on Machine Learning*, pp. 18083–18113. PMLR, 2023.arxiv.org/abs/2301.10945
  28. [29]Roger B Myerson. Optimal auction design. *Mathematics of operations research*, 6(1):58–73, 1981.DOI
  29. [30]April Niu, Kai Wang, and Juba Ziani. Finding a multiple follower stackelberg equilibrium: A fully first-order method. *arXiv preprint arXiv:2509.08161*, 2025.arxiv.org/abs/2509.08161
  30. [31]Mai Pham, Vikrant Vaze, and Peter Chin. Advancing differentiable economics: A neural network framework for revenue-maximizing combinatorial auction mechanisms. *arXiv preprint arXiv:2501.19219*, 2025.arxiv.org/abs/2501.19219
  31. [33]Vinzenz Thoma, Georgios Piliouras, and Luke Marris. Deep incentive design with differentiable equilibrium blocks. *arXiv preprint arXiv:2603.07705*, 2026.arxiv.org/abs/2603.07705
  32. [34]Kai Wang, Lily Xu, Andrew Perrault, Michael K Reiter, and Milind Tambe. Coordinating followers to reach better equilibria: End-to-end gradient descent for stackelberg games. In *Proceedings of the AAAI conference on artificial intelligence*, volume 36, pp. 5219–5227, 2022.arxiv.org/abs/2106.03278
  33. [35]Tonghan Wang, Yanchen Jiang, and David C Parkes. Gemnet: Menu-based, strategy-proof multi-bidder auctions through deep learning. *arXiv preprint arXiv:2406.07428*, 2024.arxiv.org/abs/2406.07428
  34. [36]Jingzhao Zhang, Hongzhou Lin, Stefanie Jegelka, Suvrit Sra, and Ali Jadbabaie. Complexity of finding stationary points of nonconvex nonsmooth functions. In *International Conference on Machine Learning*, pp. 11173–11182. PMLR, 2020.arxiv.org/abs/2002.04130
  35. [37]Zihao Zhao, Kai-Chia Mo, Shing-Hei Ho, Brandon Amos, and Kai Wang. A fully first-order layer for differentiable optimization. *arXiv preprint arXiv:2512.02494*, 2025.arxiv.org/abs/2512.02494

Paper details

vlnc:W_8eqakesa
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents