- 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 complexity under "symmetric Jacobian" condition and complexity without "symmetric Jacobian" condition, where is the number of bidders and is the convergence precision. The paper also applies their framework in non-truthful auction learning experiments up to bidders and items, with % 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
-
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 and consequently ). The paper briefly discusses it in line 165 by claiming that " is computationally intractable", but the reason is not clear to me.
-
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 represents the parameters of a neural network that parameterize bidder 's bidding strategy. How can it satisfy that is strongly monotone on ?
Questions for authors
-
See above weaknesses.
-
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?
-
I'm confused by some presentations, and I appreciate the authors if the authors could response to them.
- In line 195-197, in which cases in auction learning the symmetric Jacobian condition holds?
- 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.
- In line 237, what is "the transpose operator missing in (6)."?
- In line 370, how do you compute the NE ? In my understanding, is neural network parameters, optimizing global optimal network parameters is extremely hard, let alone computing the NE of many neural networks.
- In line 398, what is ?
- 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:
In line 398, what is ?
Answer:
It denotes the set of local Nash equilibrium. is a local Nash equilibrium of the game if and only if
for some neighborhood . 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 , we solve for the equilibrium of the learned mechanism with temperature , initialized by the original equilibrium strategies. Finally, we evaluate the revenue of the mechanism with temperature and equilibrium . 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 . We modified Table 1 to report the revenue at different temperatures and added Table 2 to report the natural residuals.
References:
Kwon, Jeongyeol, et al. "A fully first-order method for stochastic bilevel optimization." International Conference on Machine Learning. PMLR, 2023.
Liu, Bo, et al. "Bome! bilevel optimization made easy: A simple first-order approach." Advances in neural information processing systems 35 (2022): 17248-17262.
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.
Kornowski, Guy, et al. "First-order methods for linearly constrained bilevel optimization." Advances in neural information processing systems 37 (2024): 141417-141460.
Huang, Kexin, et al. "Learning Bayesian Nash equilibrium in auction games via approximate best response." Forty-second International Conference on Machine Learning. 2025.
Mehra, Akshay, and Jihun Hamm. "Penalty method for inversion-free deep bilevel optimization." Asian conference on machine learning. PMLR, 2021.
Bichler, Martin, et al. "Learning equilibria in symmetric auction games using artificial neural networks." Nature machine intelligence 3.8 (2021): 687-695.
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.
Huang, Kexin, et al. "Learning Bayesian Nash equilibrium in auction games via approximate best response." Forty-second International Conference on Machine Learning. 2025.
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:
- 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.
- 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.
- 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?
Question:
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:
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:
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−1, whereas the exact hypergradient requires J−⊤. 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:
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^. The non-smooth and numerically unstable property of hypergradient makes approximate gradient descent actually perform better empirically.
Question:
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:
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].