acceptodds
Under review as a conference paper at ICLR 2027

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 -stationary point using 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.

Primary area:
optimization
Keywords:
first-order oracle, bilevel optimization, mechanism design, non-truthful auction

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_rKdCOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3(+1)
Soundness
2
Read review
Paper summary

This paper studies the problem of non-truthful auction learning through the lens of bi-level optimization framework. The paper first transforms the "non-truthful auction learning problem" to "multi-follower Stackelberg game problem", then derives first-order algorithms with provable convergence guarantees for the "multi-follower Stackelberg game problem", with O~(Nϵ−2)\tilde{O}(N \epsilon^{-2}) complexity under "symmetric Jacobian" condition and O~(N2ϵ−2)\tilde{O}(N^2 \epsilon^{-2}) complexity without "symmetric Jacobian" condition, where NN is the number of bidders and ϵ\epsilon is the convergence precision. The paper also applies their framework in non-truthful auction learning experiments up to 22 bidders and 22 items, with ≈4\approx 4 % gap compared with state-of-the-art results.

Critical strengths
  • This paper integrates bi-level optimization framework to non-truthful auction learning. This is a novel direction in my knowledge, and I also think it is interesting.
  • This paper also tries to conduct experiments to apply their framework, which further validate the practical usefulness of their framework.
Critical weaknesses
  1. The motivation for designing first-order algorithms for "multi-follower Stackelberg game problem" is confusing. In my understanding there is a broad literature of bi-level optimization algorithms, including first-order algorithms and second-order algorithms. It's not clearly stated why the paper focuses on first-order algorithm design. It seems to me that second-order algorithms are more natural choices (directly computing J(x,y∗)−TJ(x,y^ *)^ {-T} and consequently ∇F(x)\nabla F(x)). The paper briefly discusses it in line 165 by claiming that "J(x,y∗)J(x,y^ *) is computationally intractable", but the reason is not clear to me.

  2. The connection between bi-level optimization and non-truthful auction learning is weak in my view. The paper reframes "auction learning problem" as "multi-follower Stackelberg game problem", and builds their theoretical framework based on the "multi-follower Stackelberg game problem". This is acceptable, but it raises many natural questions about whether the assumptions made in "multi-follower Stackelberg game problem" also apply to "auction learning problem"? For examples: 1) Section 4 analyzes the case with symmetric Jacobian, but the paper fails to give concrete examples of "auction learning problems" that can induce symmetric Jacobian. The paper gives a brief answer in line 195-197, but this does not give enough details, and I still feel that "symmetric Jacobian" condition is too strong for "auction learning problems"; 2) The paper states many assumptions in Assumption 3.4, 3.5 and the statements of Theorem 6.1. Whether "auction learning problems" satisfy these assumptions? Specifically, in experiments yiy_ i represents the parameters of a neural network that parameterize bidder ii's bidding strategy. How can it satisfy that V(x,y)V(x,y) is strongly monotone on yy?

Questions for authors
  1. See above weaknesses.

  2. In the experiment the paper considers a second-order algorithm that computes exact hypergradients. Since first-order algorithm only computes approximate hypergradients, could the authors give some insights about why first-order algorithm outperforms second-order algorithms with same epochs in Figure 2?

  3. I'm confused by some presentations, and I appreciate the authors if the authors could response to them.

    1. In line 195-197, in which cases in auction learning the symmetric Jacobian condition holds?
    2. In line 224-225, not really a question. The most important result of convergence under "symmetric Jacobian" condition is left to appendix, while only the intermediate result (Theorem 4.1) is presented in Section 4. It makes me confused in my first sight, and I believe this could be improved.
    3. In line 237, what is "the transpose operator missing in (6)."?
    4. In line 370, how do you compute the NE y∗y^*? In my understanding, yy is neural network parameters, optimizing global optimal network parameters is extremely hard, let alone computing the NE of many neural networks.
    5. In line 398, what is LNE(G)LNE(\mathcal{G})?
    6. In line 431, what does "replace softmax with max" mean? If "softmax" means the equation in line 385, it means that this replacement changes the auction mechanism, and it will also change the NEs of the bidders. As a result, previous NEs under "softmax" will no longer be the NEs under "max". Is my understanding correct?
7 comments

Question:

It's not clearly stated why the paper focuses on first-order algorithm design.

Answer:
It is observed in bilevel optimization that explicitly inverting the Jacobian is computationally expensive. That's why many papers [1,2,3,4,6] restrict attention to first-order methods. Our paper is along this line of works and shows that first order oracle is sufficient for solving Stackelberg game with multiple followers. Empirically, [2] and [6] also demonstrate that first-order methods can outperform second-order methods in terms of computational efficiency and convergence speed.

Question:

Computational tractability for inverting the Jacobian.

Answer:
We agree that "Computationally expensive" is a better way to put it. Claiming that inverting the Jacobian matrix is computationally intractable is too strong. We thank the reviewer for the suggestion and we have fixed the manuscript.

Question:

Section 4 analyzes the case with symmetric Jacobian, but the paper fails to give concrete examples of auction learning problems" that can induce symmetric Jacobian. The paper gives a brief answer in line 195-197, but this does not give enough details, and I still feel that symmetric Jacobian" condition is too strong for ``auction learning problems".

Answer:
For example, [5] shows that symmetric first-price auction can induce a symmetric positive definite Jacobian at the equilibrium strategy. However, we would like to clarify that Section 4 is intended as a motivating special case, rather than the problem setting we ultimately aim to address. Specifically, Section 4 introduces a natural first-order perturbation of the followers' objectives and demonstrates that it yields a valid hypergradient approximation when the game Jacobian is symmetric. More importantly, this analysis reveals a fundamental limitation of the perturbation approach: it produces a term involving J−1J^{-1}, whereas the exact hypergradient requires J−⊤J^{-\top}. These two quantities are generally different when the Jacobian is asymmetric.

This observation is precisely what motivates our construction in Section 5. We introduce a new finite-difference potential function and an auxiliary game to fix the desired transpose-Jacobian property, thereby extending the first-order approach to general asymmetric-Jacobian games without imposing the symmetry assumption. This general setting is the focus of our theoretical contribution and its application to non-truthful auction design.

We revise the introduction to Section 4 and the transition to Section 5 to clarify that Section 4 serves to motivate the general construction. We appreciate the reviewer's feedback and hope that the revised version clarifies the algorithmic challenges and contributions better.

Question:

In the experiment the paper considers a second-order algorithm that computes exact hypergradients. Since first-order algorithm only computes approximate hypergradients, could the authors give some insights about why first-order algorithm outperforms second-order algorithms with same epochs in Figure 2?

Answer:
Similar phenomenon was observed in [1, 2, 6, 10] empirically. Since the linear system involving the Jacobian is highly ill-conditioned, solving for the hypergradient may be unstable and may also amplify the inaccuracy of the approximate equilibrium y^\hat{y}. The non-smooth and numerically unstable property of hypergradient makes approximate gradient descent actually perform better empirically.

Question:

Confusion with assumptions, symmetric Jacobian, transpose operator.

Answer:
Assumptions 3.4 and 3.5 provide sufficient conditions for the global convergence analysis of our first-order method. When bidders' strategies are parameterized by neural networks, their expected costs are generally nonconvex functions of the network parameters, and global strong monotonicity cannot be guaranteed.

To address the potential nonuniqueness of equilibria in neural auction games, Section 6.2 considers a local equilibrium branch instead. Theorem 6.1 assumes local strong monotonicity in a neighborhood of the relevant local Nash equilibria, rather than global strong monotonicity over the entire parameter space. Under this assumption, the equilibrium branch can be tracked locally. This provides a conditional theoretical justification for the warm-start approach.

The goal of Sections 6 and 7 is to demonstrate the empirical applicability and computational efficiency of the proposed first-order method on neural-network-parameterized auctions, even if the assumptions do not necessarily hold. The experiments complement our theoretical result.

Question:

In line 370, how do you compute the NE?

Answer:
We compute NE by simultaneous gradient descent on the neural network parameters. Computing NE is very difficult in general. However, several papers show that gradient dynamics empirically converge to Nash equilibria in auction games [7,8,9].

Question:

In line 398, what is LNE(G)\text{LNE}(\mathcal{G})?

Answer:
It denotes the set of local Nash equilibrium. y∗∈Y(x)y^* \in Y(x) is a local 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∈Uig_i(x,y^*) \leq g_i(x,y_i, y_{-i}^*) \quad \forall i \in [N],\\ \forall y_i \in U_i for some neighborhood Ui⊆Yi(x)U_i \subseteq Y_i(x). A local Nash equilibrium is a necessary condition for being a Nash equilibrium.

Question:

In line 431, what does "replace softmax with max" mean? If "softmax" means the equation in line 385, it means that this replacement changes the auction mechanism, and it will also change the NEs of the bidders. As a result, previous NEs under "softmax" will no longer be the NEs under "max". Is my understanding correct?

Answer:
We ran additional experiments to validate the relationship between different temperatures of softmax and max, and the results suggest that we can match the revenue of max allocation by choosing a smaller temperature. We obtain the mechanism weights and equilibrium strategies after training. For each temperature τ∈{0.05,0.04,0.03}\tau \in \{0.05, 0.04, 0.03\}, we solve for the equilibrium yτy^\tau of the learned mechanism with temperature τ\tau, initialized by the original equilibrium strategies. Finally, we evaluate the revenue of the mechanism with temperature τ\tau and equilibrium yτy^\tau. We observe that the revenue increases and approaches to that of max allocation as the temperature decreases. To measure convergence, we measure stationarity of bidders by natural residual ∥V(x,yτ)∥\|V(x,y^\tau)\|. We modified Table 1 to report the revenue at different temperatures and added Table 2 to report the natural residuals.

References:
[1][1] Kwon, Jeongyeol, et al. "A fully first-order method for stochastic bilevel optimization." International Conference on Machine Learning. PMLR, 2023.
[2][2] Liu, Bo, et al. "Bome! bilevel optimization made easy: A simple first-order approach." Advances in neural information processing systems 35 (2022): 17248-17262.
[3][3] Sow, Daouda, Kaiyi Ji, and Yingbin Liang. "On the convergence theory for hessian-free bilevel algorithms." Advances in Neural Information Processing Systems 35 (2022): 4136-4149.
[4][4] Kornowski, Guy, et al. "First-order methods for linearly constrained bilevel optimization." Advances in neural information processing systems 37 (2024): 141417-141460.
[5][5] Huang, Kexin, et al. "Learning Bayesian Nash equilibrium in auction games via approximate best response." Forty-second International Conference on Machine Learning. 2025.
[6][6] Mehra, Akshay, and Jihun Hamm. "Penalty method for inversion-free deep bilevel optimization." Asian conference on machine learning. PMLR, 2021.
[7][7] Bichler, Martin, et al. "Learning equilibria in symmetric auction games using artificial neural networks." Nature machine intelligence 3.8 (2021): 687-695.
[8][8] Kohring, Nils, Fabian Raoul Pieroth, and Martin Bichler. "Enabling first-order gradient-based learning for equilibrium computation in markets." International Conference on Machine Learning. PMLR, 2023.
[9][9] Huang, Kexin, et al. "Learning Bayesian Nash equilibrium in auction games via approximate best response." Forty-second International Conference on Machine Learning. 2025.
[10][10] Chen, Lesi, Yaohua Ma, and Jingzhao Zhang. "Near-optimal nonconvex-strongly-convex bilevel optimization with fully first-order oracles." Journal of Machine Learning Research 26.109 (2025): 1-56.

Thank you for the authors' responses. Most of my initial confusion has been addressed. As a consequence, I would like to maintain my positive rating and increase the Presentation score to 3.

Minor comments:

  1. It's better to use "approximate Bayesian Nash equilibrium" rather than claiming that the experiments computed "NE" for the non-truthful auctions. Additionally, it's expected to report the approximation degree of the "approximate NEs" / regret of the bidders.
  2. I have read other reviewers' reviews, and I do not feel that falling behind SOTA is really a weakness, as the authors have justified that non-truthful auctions are widely deployed for practicality, and this justification is satisfactory to me. However, this raises a natural question that existing non-truthful learning approaches like RegretNet [Dutting, 2019] and many follow-up works can also learn non-truthful auctions as well, and it would be exciting to see how proposed method perform when it's compared with some of existing non-truthful learning approaches.
  3. I'm still confused about the connection between the sections starting with and before section 6. In my understanding, sections 3-5 are used to derive the algorithm that can learn multi-follower Stackelberg games, and to derive the convergence theorem under arguably somewhat restrictive conditions; sections 6-7 apply the algorithm to auction learning problems and show it empirically works. Is my understanding correct?
Reviewer_JGPfOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies revenue optimization when bidders respond strategically. It formulates auction design as a Stackelberg game with multiple followers. The main contribution is a fully first-order approximation to the revenue gradient through the followers’ equilibrium. For general games, the authors identify a mismatch between the inverse game Jacobian and its transpose, and construct an auxiliary game using finite differences to recover the required sensitivity. Under smoothness and strong-monotonicity assumptions, they establish hypergradient approximation and stationarity guarantees, including an extension to linearly constrained follower games.

The implementation combines neural allocation rules, pay-your-bid payments, and neural bidding strategies. A warm-start procedure tracks a local equilibrium as the mechanism changes. Experiments cover symmetric and asymmetric single-item auctions and a two-item setting. The method reports revenue close to truthful benchmarks, faster optimization than second- and zeroth-order baselines, and lower backward-pass costs as the number of bidders grows.

Critical strengths
  1. The auxiliary game addresses the important transpose mismatch in extending first-order bilevel methods to interacting followers. Its approximation and convergence analysis constitutes a meaningful technical contribution.

  2. The experiments connect the method to a relevant auction-design problem. Comparisons with truthful revenue benchmarks and optimization baselines provide useful initial evidence of practical value.

Critical weaknesses
  1. The local equilibrium-tracking claim is stronger than its proof supports. The solver returns an approximate equilibrium, but the theorem concludes that the iterates lie exactly on an equilibrium branch; the proof only establishes a tolerance bound. Local strong monotonicity is also assumed rather than established for the neural bidding games. A finite-error tracking statement and a clearer account of applicability are needed to substantiate the theoretical link to the auction implementation.

  2. Equilibrium revenue is not sufficiently validated for the reported mechanism. Training uses softmax allocations, whereas revenue is reported after replacing softmax with max, which changes bidders’ incentives. The paper does not clearly establish that strategies are recomputed and checked for profitable deviations under this modified rule. Without that check, proximity to truthful revenue benchmarks may reflect the evaluated strategy profile rather than an approximate auction equilibrium.

Questions for authors
  1. Can the equilibrium-tracking statement be corrected to include the solver tolerance, and what conditions keep the implemented iterates within the required local neighborhood?

  2. After replacing softmax with max, are bidding strategies recomputed? What existing convergence or deviation checks support interpreting the reported revenue as equilibrium revenue?

1 comment

We thank the reviewer for the thoughtful and constructive feedback. Below, we provide a point-to-point response to the comments of reviwer JGPf.

Question:

The local equilibrium-tracking claim is stronger than its proof supports. The solver returns an approximate equilibrium, but the theorem concludes that the iterates lie exactly on an equilibrium branch.

Answer:
The proof of equilibrium-tracking is correct and accounts for solver tolerance already. The theorem statement just contains a typo. The correct statement is ``each lower-level iterate satisfy ∥yk−z∗(xk)∥≤δ^\|y_{k} - z^*(x_{k})\| \leq \hat{\delta} where δ^\hat{\delta} is the tolerance level". The theorem provides intuition for adapting our Stackelberg game algorithm to the neural auction design problem. For example, we need small hyperobjective learning rate and accurate initial equilibrium solve.

Question:

Local strong monotonicity is also assumed rather than established for the neural bidding games. A finite-error tracking statement and a clearer account of applicability are needed to substantiate the theoretical link to the auction implementation.

Answer:
We would like to highlight that our method performs well even when the leader and followers in a Stackelberg game are parameterized by neural networks. Instead of assuming the neural game satisfies local strong monotonicity exactly, we explain below why local strong monotonicity is a reasonable assumption:
(1) It is assumed in most of the bilevel optimization literature [1, 2, 3, 4, 5] since strong convexity (an analogue of strong monotonicity in single-agent game) guarantees uniqueness and differentiability of the lower-level minimizer, thus enabling theoretical analysis of the algorithm.
(2) In symmetric first-price auction, [6] shows that the Jacobian at the equilibrium strategy (JJ in our work) is symmetric and positive definite, which implies local strong monotonicity. However, auction games are inherently difficult to solve and may not satisfy nice properties (e.g. monotonicity, Minty condition) in general [7]. Empirically, even without local strong monotonicity, our algorithm can still find reasonably good solutions for general auctions.
(3) There is a branch of work investigating more general assumptions such as the PL-condition [8], which can also be used to relax the strong local monotonicity assumption while the proofs still work [8].

Question:

Equilibrium revenue is not sufficiently validated for the reported mechanism. Training uses softmax allocations, whereas revenue is reported after replacing softmax with max, which changes bidders’ incentives.

Answer:
We ran additional experiments to validate the relationship between different temperatures of softmax and max, and the results suggest that we can match the revenue of max allocation by choosing a smaller temperature. We obtain the mechanism weights and equilibrium strategies after training. For each temperature τ∈{0.05,0.04,0.03}\tau \in \{0.05, 0.04, 0.03\}, we solve for the equilibrium yτy^\tau of the learned mechanism with temperature τ\tau, initialized by the original equilibrium strategies. Finally, we evaluate the revenue of the mechanism with temperature τ\tau and equilibrium yτy^\tau. We observe that the revenue increases and approaches to that of max allocation as the temperature decreases. To measure convergence, we measure stationarity of bidders by natural residual ∥V(x,yτ)∥\|V(x,y^\tau)\|. We modified Table 1 to report the revenue at different temperatures and added Table 2 to report the natural residuals.

References:
[1][1] Kwon, Jeongyeol, et al. "A fully first-order method for stochastic bilevel optimization." International Conference on Machine Learning. PMLR, 2023.
[2][2] Liu, Bo, et al. "Bome! bilevel optimization made easy: A simple first-order approach." Advances in neural information processing systems 35 (2022): 17248-17262.
[3][3] Sow, Daouda, Kaiyi Ji, and Yingbin Liang. "On the convergence theory for hessian-free bilevel algorithms." Advances in Neural Information Processing Systems 35 (2022): 4136-4149.
[4][4] Kornowski, Guy, et al. "First-order methods for linearly constrained bilevel optimization." Advances in neural information processing systems 37 (2024): 141417-141460.
[5][5] Ghadimi, Saeed, and Mengdi Wang. "Approximation methods for bilevel programming." arXiv preprint arXiv:1802.02246 (2018).
[6][6] Huang, Kexin, et al. "Learning Bayesian Nash equilibrium in auction games via approximate best response." Forty-second International Conference on Machine Learning. 2025.
[7][7] Bichler, Martin, et al. "On the convergence of learning algorithms in bayesian auction games." arXiv preprint arXiv:2311.15398 (2023).
[8][8] Chen, Lesi, Jing Xu, and Jingzhao Zhang. "On finding small hyper-gradients in bilevel optimization: Hardness results and improved analysis." The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024.

Reviewer_myjhOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes a Stackelberg game formulation of auction design and develops a first-order algorithm for revenue optimization in non-truthful auctions, with non-asymptotic guarantees. Experiments relative to second-order and zeroth-order baselines show advantages in terms of scalability as the number of bidders increases, while also achieving revenue close to truthful baselines.

Critical strengths
  • The paper is part of an exciting line of work that develops computational methods for auction design. This goes back to Conitzer and Sandholm in the early 2000s, and has been recently invigorated using neural networks. The main questions raised in the paper are certainly interesting and well-motivated.
  • The approach developed in the paper is quite natural and theoretically grounded. It has the advantage of relying solely on first-order feedback, and is thus more scalable relative to other approaches; this is also demonstrated in the experiments.
Critical weaknesses

My main concern is about the novelty and significance of the results.

  • First, the experiments do not go far enough. In the settings considered, the first two fall in the purview of Myerson's characterization, so the revenue-optimal mechanism is already known. Testing the method in such settings is a good sanity check, but does not convey much besides that. Moreover, in the third setting, where Myerson's characterization does not apply, the proposed method still falls short of the state-of-the-art method, which is GemNet. What I hoped to see is a class of problems where prior approaches did not capture, but somehow the techniques of this paper are able to address. Instead, in all the experiments the proposed method is inferior relative to the state-of-the-art.
  • Second, the underlying formulation does not seem to be particularly novel. Auction design can be naturally phrased as a Stackelberg game. Moreover, first-order methods have been introduced before for finding equilibria in Stackelberg games (see below).
  • At parts, the writing of the paper is not good enough. For example, the main contributions paragraph, which is one of the most important parts of the paper, is poorly written. At this point, it's clear at all to the reader what "symmetric-Jacobian games" are, and how those relate to the previous discussion. The challenge in non-symmetric games is not explained well at all. I was really unable to follow this paragraph. Some things became clear after reading further, but an effective introduction should be, to the extent possible, self-contained.

For these reasons, I'm not convinced that the contribution of the paper is strong enough for acceptance.

Questions for authors

It would be helpful if the authors can compare their approach with the following two papers:

  • "Convex-Concave Min-Max Stackelberg Games" by Goktas and Greenwald, as well as follow-ups to that paper. This paper also develops first-order methods for Stackelberg games.
  • "Computing optimal equilibria and mechanisms via learning in zero-sum extensive-form games" by Zhang et al. That paper has a general framework for casting auction design as a zero-sum game. Can the authors comment on differences between the two?
6 comments
AuthorsOpenReview ↗

Response to the first and third weaknesses

We thank the reviewer for the thoughtful and constructive feedback. Below, we provide a point-to-point response to the comments of reviwer myjh.

Question:

First, the experiments do not go far enough. In the settings considered, the first two fall in the purview of Myerson's characterization, so the revenue-optimal mechanism is already known. Moreover, in the third setting, where Myerson's characterization does not apply, the proposed method still falls short of the state-of-the-art method, which is GemNet.

Answer:
We are designing non-truthful revenue-optimal auctions because they are more realistic in practice, i.e., the non-truthful auction is more transparent and does not rely on truth to the auctioneer. Google Ad Manager also switched to using the first-price auction in 2019 [1].

To our knowledge, there are currently no effective non-truthful auction design algorithms in the literature. Even the state-of-the-art method GemNet is a truthful auction design method. In theory, when the revelation principle holds, the revenue of optimal non-truthful auction is upper bounded by that of the optimal truthful auction. However, the revelation principle does not imply that we can find optimal non-truthful auctions from truthful auctions, and this is exactly the strength of our algorithm. In symmetric single-item auction, we find that the optimal non-truthful auction is just first-price auction with reserve as known in the literature. In asymmetric single-item auction, we are not aware of any non-truthful auction that has the same revenue as Myerson's optimal auction, but our algorithm finds one non-truthful auction that is close to Myerson's auction. In multi-item auction, no optimal non-truthful auction has been considered. Our algorithm provides an effective way to design non-truthful auctions in all these settings without relying on the truthfulness.

Question:

At parts, the writing of the paper is not good enough.

Answewr:
The term ``symmetric-Jacobian'' is now defined properly in the introduction. We also made changes to the presentation to make the paper more readable. We thank the reviewer for the suggestion.

AuthorsOpenReview ↗

Response to the rest of weaknesses and questions

Question:

Second, the underlying formulation does not seem to be particularly novel. Auction design can be naturally phrased as a Stackelberg game. Moreover, first-order methods have been introduced before for finding equilibria in Stackelberg games (see below).

Answer:
(1) Our work focuses on non-truthful auctions because they are more valuable in practice. In contrast, majority of prior works focus on truthful auction design [3,4], but truthfulness assumption is rarely satisfied in practice. Similarly, `Computing optimal equilibria and mechanisms via learning in zero-sum extensive-form games by Zhang et al. restricts the mechanism to be truthful (assuming knowledge about direct strategy d. They do not need to solve the Nash equilibrium of the lower-level game (which can be general-sum and difficult to solve) induced by the mechanism. Instead, they formulate truthful mechanism design as a two-player zero-sum game using duality. Moreover, it requires discretization which may prohibit its applications to auctions with continuous valuations and bids.
(2) We would like to emphasize that first-order bilevel optimization with non-asymptotic convergence guarantee is a recent breakthrough in Kwon et al. 2023 [2] and is different from Goktas and Greenwald (2021). Our work establishes non-asymptotic guarantee for Stackelberg game with multiple followers, which is more general than prior works. Convex-Concave Min-Max Stackelberg Games by Goktas and Greenwald (2021) study convex-concave min-max Stackelberg games of the form min⁡x∈Xmax⁡y∈Y(x)f(x,y),\min_{x\in X}\max_{y\in Y(x)}f(x,y), where the leader and follower have opposing objectives and the follower's feasible set may depend on the leader's decision. There are two players: the leader chooses xx to minimize ff and the follower chooses yy to maximize the same function ff subject to the constraint g(x,y)≥0g(x,y)\ge 0. Thus, the problem they studied is a zero-sum Stackelberg game.

In contrast, our problem is min⁡x∈XF(x)=f(x,y∗(x))\min_{x\in X}F(x)=f(x,y^*(x)) subject to $ y_i^*(x)\in \arg\min_{y_i\in Y_i(x)} g_i(x,y_i,y_{-i}^*(x)),$ for all player ii. So the constraint is the followers' subgame equilibrium, and followers interact strategically, so their objectives are generally different from one another and from the leader's objective. Therefore, our lower-level problem is a general-sum Nash game, not a maximization problem involving the auctioneer's objective. The general-sum game cannot, in general, be reduced to the min-max formulation studied by Goktas and Greenwald. Moreover, our first-order method addresses a different challenge: approximating the hypergradient through a multi-player Nash equilibrium without second-order derivatives. The envelope-theorem approach of Goktas and Greenwald exploits the structure of convex-concave min-max optimization to obtain (sub)gradients of the leader's value function. In our general-sum setting, the leader's revenue is not the objective optimized by the followers, so the equilibrium-sensitivity term generally does not vanish. As shown in Equation (2), the exact hypergradient requires J−⊤J^{-\top}, which cannot generally be recovered from a direct perturbation of the followers' objectives. As a result, Goktas and Greenwald (2021) and follow-up works in the lines of Min-Max games do not overlap with our setting. We add these references and clarify the differences in the revised manuscript.

AuthorsOpenReview ↗

References

References:
[1][1] "An update on first price auctions for Google Ad Manager", url: https://blog.google/products/admanager/update-first-price-auctions-google-ad-manager/ 2019.
[2][2] Kwon, Jeongyeol, et al. "A fully first-order method for stochastic bilevel optimization." International Conference on Machine Learning. PMLR, 2023.
[3][3] Dütting, Paul, et al. "Optimal auctions through deep learning." International Conference on Machine Learning. PMLR, 2019.
[4][4] Wang, Tonghan, Yanchen Jiang, and David C. Parkes. "Gemnet: Menu-based, strategy-proof multi-bidder auctions through deep learning." arXiv preprint arXiv:2406.07428 (2024).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.