Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
Authors: Kexin Huang
Ziqian Chen
Xue Wang
Chongming Gao
Jinyang Gao
Bolin Ding
Xiang Wang
Venue: ICML 2025 poster (2025)
Keywords: Auction
Equilibrium
Optimization
Primary area: applications->social_sciences

Abstract: Auction plays a crucial role in many modern trading environments, including online advertising and public resource allocation. As the number of competing bidders increases, learning Bayesian Nash Equilibrium (BNE) in auctions faces significant scalability challenges. Existing methods often experience slow convergence in large-scale auctions. 
For example, in a classic symmetric auction setting, the convergence rate depends on the number of bidders quadratically.
To address this issue, we propose the *Approximate Best Response Gradient* method, a new approach for learning BNE efficiently in auction games. We leverage an analytic solution for gradient estimation to enable efficient gradient computation during optimization. Moreover, we introduce the *Best Response Distance* objective, which serves as an upper bound of approximation quality to BNE. By optimizing the new objective, our method is proven to achieve a local convergence rate independent of bidder numbers and circumvent the traditional quadratic complexity in the classic symmetric setting.
Extensive experiments across various auction formats demonstrate that our approach accelerates convergence and enhances learning efficiency in complex auction settings.

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
Kexin Huang' Ziqian Chen? Xue Wang? Chongming Gao
Jinyang Gao
Bolin Ding?
Xiang Wang' |
Abstract
Optimization Pipeline
Challenge Computation
fidders
Oprimization Gradient
Non- Hon-smooth utiiity dp win
Networ is Objective E Computation
Auction plays a crucial role in many modern trad- ing environments, including online advertising and public resource allocation. As the number of competing bidders increases, learning Bayesian Nash Equilibrium (BNE) in auctions faces sig- nificant scalability challenges. Existing methods often experience slow convergence in acgge-scale auctions. For example, in classic symmetric auc- tion setting, the convergence rate depends on the number of bidders quadratically. To address this issue, we propose the Approximate Best Rexponse Gradient method, a new approach for learning BNE efficiently auction games. We leverage an analytic solution for gradient estimation enable efficient gradient computation during optimiza- tion. Moreover, we introduce the Best Response Distance objective, which serves as an upper bound of approximation quality to BNE. By opti- mizing the new objective, our method is proven to achieve local convergence rate independent bidder numbers and circumvent the traditional quadratic complexity in the classic symmetric setting. Extensive experiments across various auction formats demonstrate that our approach accelerates convergence and enhances learning efficiency in complex auction settings.
Existing Method blased stility
Estimate Gradient VoF(tu] m?
Analytic Method utlity
Gradient update
Challenge Optimizaiion Method Design
Utility Gradient (existing)
Approx BR Gradient (ours)
Objecttve Utility
Objective: BR de-detance
Vo. Aa, (vri)]
9r,E| (1%,000) bebss]
Local corver under
under
Assump.311 Orollog1/d
Assmm Ollog//d)
Figure I. This work addresses two key challenges in learning BNE for auction games: (1) gradient computation and (2) optimization method design. We utilize an analytic gradient solution avoid the biased utility function and propose a new optimization method, approximate BR gradient, accelerated convergence rate.
mineral rights (Milgrom & Weher, 1982)), to facilitate ef- ficient and transparent market outcomes. At the core of the auction is competitive bidding process, where bidders submit bids to purchase goods or services from auction- eers, with the goal of maximizing their utility. Wherein, bidders adjust their bidding strategies by estimating val- ues or equilibrium to avoid potential losses (Balseiro et al., 2015), while auctioneers analyze the equilibrium to assess the auction mechanism's effectiveness and predict market behavior (Krishna, 2010), aiding in the evaluation of overall market conditions (Milgrom & Weber, 1982). To formalize this equilibrium behavior, the auction
be modeled an incomplete innporlttniooooottionnn game (Harsanyi, 1967), where the equilibrium concept is captured by the Bayesian Nash Equi- librium (BNE). However, solving BNE in auction games is computationally hard, classified as compleo (Filos- Ratsikas et al., 2021;
1. Introduction
et al., 2024), with only limited dloeed-frmm solutions available simplified settings (Kaplan & Zamir, 2012).
Auctions serve as fundamental mechanism for resource allocation and price discovery. They are extensively applied across diverse industries, such as online advertising for ad impression allocation (Shen et al., 2015) and the distribution of public resources (e.g., spectrum bands (Milgrom, 2000),
This fundamental challenge has attracted great interest in integrating machine learning techniques with game theory (Bichler et al., 2021; Huang et al., 2024) to learn the equi- librium bidding strategies. Early efforts have focused on discretized approximations of auction games, using methods such as no-regret learning (Hartline al., 2015; Kolumbus & Nisan, 2022; Ahunbay & Bichler, 2025), reinforcement learning (Feng et al., 2021; Banchio & Skrzypacz, 2022), and online optimization (Bichler et al., 2023a), to approxi-
University of Science and Technology of China, Hefei, China 'Independent Researcher. Correspondence to: Chong- Xiang Wang <xiang-
ming Gao sehhongninggao@ussc.cce wang @23 me33@@mmml.comm.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
mate BNE strategies. However, in discretized auction games, achieving more accurate predictions requires finer discretiza- tion, which will significantly increase computational cost (Bichler et al., 2023a). This limits both the precision and scalability of the discrete learning frameworks.
cally as the number of bidders increases.
We propose the Approximate Best Response Gradient method, optimizing the Best Response Distance objective which provides an upper bound on the approximation quality to the BNE. Our method is proven to achieve local convergence to BNE at a rate independent of the number of bidders and cireumvent the slow convergence issue in the symmetric auction setting.
Distinguishing from discretized auctions where bidding strategies map categorical values to bids, continuous auc- tions model bidding strategies as functions of continuous values. Such differences present two challenges to current learning methods. Specifically, the first challenge lies in the computation of gradients, which is crucial for continuous optimization. Due to the non-smooth nature of utility func- tions in auction games, gradients cannot be computed di- rectly (Bichler et al., 2021), ), necessitating advanced gradient estimation techniques, such as smoothing approximations of the utility function (Li & Wellman, 2021; Kohring al., 2023). However, these approximations will modify the orig- inal utiliiy,, introducing model bias in the learned strategies (Kohring et al., 2023). This issue is compounded by the challenge of designing optimization methods to effectively utilize the estimated gradients. Specifically, existing meth- ods (Bichler et al., 2021; Kohring et al., 2023) that apply gradient ascent with the utility's gradient suffer from slow convergence the number of bidders increases.
We conduct extensive experiments across various auction environments, including different auction mechanisms, asymmetric value prior, risk aversion, and alternative gra- dient estimation approaches. The empirical results show significant improvements in convergence speed and learn- ing efficiency of our method across complex auction sce- narios, confirming the efficacy of our proposed method.
2. Preliminaries
2.1. Auction Game
This paper studies the single-item auction game with n bidders. The value profile v = (UI...., Uv,) is drawn from a joint prior distribution F R - [0, 1] and each bidder E (L...., n observes a private value realization ey for the item, where F is assumed to be common knowledge among all the bidders. Then each bidder submits a bid b: = B.(ss) following his/her bidding strategy B: [E+ - R.. The auction outcome is determined by a mechanism M, which specifies both the allocation of the item and the payments pi for each bidder. The risk-neutral ex-post utility of each bidder is calculated as:
In this work, we address both the gradient computation and optimization method design challenges in continuous auctions, which is summarized in Fig. 1. We introduce a new gradient estimation method with an analytic solution for the utility's 's gradients, avoiding the modified utility and model bias in previous approaches. Leveraging this an- alytic gradient, we identify that the slow convergence of existing methods stems from the inappropriate optimization objective, i.e,, the utility function, whose convergence rate degrades quadratically as the number of bidders increases in a classic symmetric auction setting. To address this, we propose a new optimization objective called Best Response Distance, which measures the gap between current bidding strategies and their local optimal counterparts, providing an upper bound on the approximation quality to BNE, By optimizing this objective, our proposed Approximate Best Response Gradient method achieves a local convergence rate independent of the number of bidders in the symmet- ric auction setting. Extensive experiments further validate the significant improvement in convergence speed across various auction scenarios.
us b,, M. = 1. - I(i wins) Pi,
(1)
where I(.) is the indicator function and the index -i denotes the profile of all bidders except for i.
For example, under the classic first-price (FP) and second- price (SP) auctions, the ex-post utility is formulated as:
u, bi, b_; (FP) = (v. b:) I[(b, > max bj),
(2)
u, (v,, by b SSP) = (u: - -maxby)) I[bb > max b,).
jta
2.2. Bayesian Nash Equilibrium
The Nash Equilibrium is achieved when no one can im- prove his/her utility by unilaterally changing his/her strategy (Nash, 1950). In the auction game with random player type (i.e., value), NE extends to the Bayesian Nash Equilibrium (Harsanyi, 1967). A typical Bayesian auction game unfolds in three stages: (1) In the ex-ante stage, bidders only acquire the value distribution prior; (2) In the ex-interim stage, each bidder privately observes his/her value realization; (3) In the ex-post stage, the bidding decision is determined. Let
Our contribution is summarized below:
We introduce a new gradient estimation technique based on an analytic solution, addressing the biased utility prob- lem present in current methods. Using this analytic gradi- ent, we prove that the traditional learning objective suffers from slow local convergence in classic symmetric auc- tion setting, with the convergence rate degrading quadrati-
2

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
ue be the ex-interim utility of bidder i:
simultaneous gradient ascent on each bidder's utility. The parameter update rule for bidder i can be expressed as:
(vi bi, B-s) = Be- [ui(e, bi, (-((v=)))
(3)
0 = 0 + a Vo. (
where F-1(1) denotes the conditioned distribution of other bidders' value realization e_z. Then, bidder i's ex-ante utility becomes:
(8)
= f + a Eu, Vo, Ue(4,, Bay (1:),
where various approximation methods (Bichler et al., 2021; Kohring et al., 2023) have been proposed to estimate the ex-interim utility's 's gradient Vo, i2. These methods enable practical implementations of learning BNE in complex auc- tion environments.
[a, (v,, Bu,
(1.)),,
(4)
where F; is the marginal distribution of 04-
Following prior studies (Chen & Peng, 2023), the best re- sponse of bidder is computed based on value and others'
3. Gradient Estimation
strategies 3_, as follows:
The need to approximate the utility's gradient Vo, ü arises from the discontinuous nature of the ex-post utility function, which includes a non-smooth indicator operator II()) defined in Eq. (2), As shown in previous work (Kohring et al., 2023), such discontinuities can lead to inaccurate gradient estima- tion for the Monte Carlo (MC) method when calculating the ex-interim utility's gradient Ve, T,(0,, 0.) (we rewrite (vs 0.) = (, Bo, (vt), 3_,) for brevity):
(r, arg max ú. (1, b, B..).
(5)
An ex-interim e-BNE (c 2 0) is reached by bidders strategy profile/ 3* ... (8)) if, for any bidder i S n and
value 83 E dom Ff:
T. (1,, (1t), 2 ū.(u, ((1),,,)),, - (6)
Furthermore, 3 is an ex-ante e-BNE if, for any bidder
Vo, Vo,ū.(v;,0.) = Vo, Eulde [us 8o, (v:), (-)))_);(0=)))
i n:
1 # K
Vo, u Bo, 8- (9)
E Bug [ū:(V;; (1:), 2 E Fi (1;; (r, (2,), (2,0)) -c
(7)
where K denotes the sample size. As result, Bichler et al. (2021) reported that strategies learned using MC estimation gradient tend converge to zero bidding in FP auctions. To illustrate this issue, we exemplify the FP auction with the ex ex-post utility defined in Eq. (2), and compute the MC estimation on gradient MC2 ū. of bidder i as follows:
In this paper, we focus primarily on learning the ex-ante c-BNE (e-BNE for short). Note that ex-ante e-BNE and ex- interim e-BNE are equivalent when 0, which simply referred to as BNE,
8,
2.3. Gradient- Learning
K
1 K
01)
Vo, uu Bo, (v:),
Recent advancements (Bichler et al., 2021; 2023b; Kohring et al., 2023) have investigated the gradient-based learning techniques (Bubeck, 2015; Salimans et al., 2017) to compute BNE in auction games. In these approaches, each bidder's strategy is modeled by a neural network, denoted as Be, (-), with parameters 0, updated through gradient methods to optimize a specific objective L:
j=1
2 Pri( wins)
V So, (v:).
(10)
where Pr(i wins) = .lo, [B0. (2:) > max(b_;)). The key issue here is that the MC-estimated gradient's coefficient for the bidder i's bidding network vo. 8o, (v:) is consistently negative unless the bidder places a minimal bid. This im- plies that the estimated gradient persistently encourages the bidder to lower their bid until So, (1:) O. which explains the zero-bidding problem in MC gradient estimation.
aa Vo, ((o,(Bo,,Bor..))
where a the learning rate and Vo, L represents the gra- dient of the objective function w.n.t. the bidder's strategy parameters. This optimization process depends two key factors: (1) the selection of the learning objective L and (2) the method for estimating the gradient Vo,L.
3.1. Existing Gradient Estimation
To address this issue, existing works (Bichler et al., 2021; Li & Wellman, 2021; Kohring et al., 2023) turn to utilize different gradient estimation methods to approximate the ex ex-interim utility's 's gradient. Early works adopt black-bor box optimization techniques, such as Evolution Strategies (ES),
In practice, most existing methods (Bichler et al., 2021; 2023b; Kohring et al., 2023) unanimously adopt the negative ex-ante utility (U,(8, {_x) as the objective L, resulting in
3

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
to estimate the pseudo-gradient as an approximation of the utility's 's gradient (Bichler et al., 2021; Li & Wellman, 2021). Specifically, the ES algorithm approximates the ex-interim utility with a boussian--mmother utility function, where the bidding strategy's 's parameter 0g is perturbed with Gaussian noise, then the gradient of this smoothed utility can be estimated as follows:
Table I. Comparison of existing gradient estimation methods.
Gradient Estimation
Optimization
Introduced
Approach
Method
Utility Bias
Evolution Strategy V
zeroth-order
Gaussian Noisc
REINFORCE VRE
zeroth-order
Gaussian Noise
Smooth Market V
first-order
Softmax
The Derived Eq.(11)
first-order
Free
V 0 0.) = Vo, Vn 0. + +e]
by leveraging an analytic gradient solution. As elucidated in Tab. 1, this estimation avoids the model bias of existing methods by preserving the original utility function. In par- ticular, we present this analytic gradient computation under FP and SP auctions in Equation (11) (See Appendix C for detailed proof's and additional scenarios):
= =Ee-N(0.0=n) 0² u. 0, + c]].
In addition to perturbing the parameters of the bidding func- tion, this approach can also be applied to perturb the outputs of the bidding function (i.e., bid values). This alternative method, known as the REINFORCE algorithm (Salimans et al., 2017; Kohring et al., 2023), perturbs the bid function 3; into a mixed strategy such that 6; ~ ([ o2)), Similarly, the gradient can be estimated as:
Vo, ūe So, (vi), ob;
ū. (vi, bi, B_z) Vo,8o,
[(i - bi),m, (bx) - Fm; (b:]] Bo, (os-be)) (ba) Vo, (U:))
FP
SP
V RE (us 30, 8-:)
(11)
Here, fmz and Fm, are the probability density function (pdf) and cumulative density function (cdf), respectively, Both of them can be estimated via sampling market prices max (B_;(()(vv-)) with u-; ~ F-;(-(ox) given uy the edf can be naturally estimated via MC estimation and the pdf can be estimated via kernel density estimation (KDE) or using a histogram of sampled market prices. Therefore, the utility gradient Vo, ūy can be correctly approximated by the Monte Carlo estimated distribution, enabling learning with first- order methods based on this analytic gradient computation. We name this method as MC on distribution to differentiate it from the MC on gradient one in Eq. (10).
Va, Eew N
a Iu: Bo (vi) + e, [-1]]
= =Be- u. (v,, Bo (vi) + Vo, Bo, (v:)].
Despite the widely recognized effectiveness in black-box op- timization, the ES algorithm faces criticism for the high vari- ance and computational complexity due to the perturbation- based estimation (Bichler et al., 2023a; Kohring et al., 2023). To alleviate this concern, Smooth Market (SM) (Kohring et al., 2023) introduced a smooth ex-post utility function that approximates the original discontinuous utility by sub- stituting the winning indicator T(i wins) and distributing the payment with a smooth soft-max operator:
Morcover, this analytic gradient computation allows for in- vestigating the convergence ability of gradient methods to BNE strategies. We follow a classic symmetric auction set- ting (Feng et al., 2021) with shared linear bidding strategies: Assumption 3.1. Consider a symmetric n-bidder first-price auction with uniform prior F, = U00 1). Bidders share a linear bidding function Ba, (v:) = wv;; + with non-negative parameter 0: := (w, T)T E R. (to ensure bids 6, 2 0).
V. u. (ve, 0c) x Ep Ve, u
SM (U,, So, (-())))((=)))) D),,
exp(b,/)) where (SM(,, bg, b-:) (u--p,M) Σn exp(b, / Thus the approximated utility function is fully differentiable, mak- ing the first-order optimization applicable: the gradient can be efficiently estimated via sampling and back-propagatte propagation, without relying on noisy perturbations in zeroth-order meth- ods like ES and REINFORCE. This approach improves both approximation quality and computational efficiency compared to previous methods (Kohring al., 2023).
The symmetric BNE solution to this auction game is (v:) n-1 (i.e., 0f ( (~=11_ -)))). Consistent with previous studies (Kohring et al., 2023; Bichler et al., 2021), we focus on maximizing the ex-ante utility via gradient ascent, herein referred to as the Utility Gradient method:
3.2. Proposed Gradient Estimation
Although the aforementioned approaches can estimate the ex-interim utility's 'ss gradient, the utility function under their estimation is modified by either Gaussian noise (e.g., ESS ü. VRE or softmax approximation (e.g., V/M which can introduce error in the final learned strategy (Kohring et al., 2023). Surprisingly, we find that the gradi- ent of ex- ex-interim utility Ve, ū can be directly estimated via Monte Carlo sampling in certain mechanisms (e.g., FP, SP),
0 + 8 + VV U, (Boz Sor Bo.))
(Utility Gradient)
Then we can prove that our derived gradient solution in Eq. (11) converges to the BNE while the MC estimation on gradient in Eq. (10) incorrectly converges to zero bidding: Proposition 3.2 (Convergence Ability). Under Assump. I,
projected gradient ascent' via utility gradient satisfies:
We use projected gradient ascent 0, +1 + --Pro((0 + U.).

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
1. Learning with the derived gradient in Eq. (11) converges to the symmetric BNE: (1:) ---v-- Uz- Learning with MC estimation on gradient in Eq. (10)
Dysomirx
Dysoeiis
converges to the zero-bidding strategy: (vx) = O.
Pain Utily Sid
MD
(Dun)
4. Proposed Learning Algorithm
Panandd
4.1. Convergence Rate of Utility Gradient
(a) Dynamics when 12 = 2 (b) Dynamics when 10
Despite the convergence guarantee in Proposition 3.2, we find the utility gradient method suffers from slow conver- gence in the vicinity of the BNE point 02 when the bidder number n increases. To demonstrate this phenomenon, we conduct numerical experiments under Assump. 3.1 by ini- tializing the parameters 6f in the neighborhood of the BNE point 0- = ( (-= о)T. As depicted in Fig. 2, the utility gra- dient method fails to converge to the BNE point 6* within limited training steps if the bidder number n grows from 2 to 10. Such poor convergence results persist even if we extend the training times twice, labeled as "Utility Grad (+300 steps)" in the figure.
Figure 2. Learning dynamics of different methods under Assump- tion 3.1. The initial point Oe is picked at the vicinity of 07, with of = 0 + ( ) )".AAl All methods run 150 steps by default and we plot the pesf-perfngning results after learning-rate grid search.
Formally, we prove that the local convergence rate satisfies:
Theorem 4.2 (Utility Gradient Converge Rate). Under As- sump. 3.1, for projected gradient ascent via utility gradient: 1. It converges to the BNE 8 at a local rate of O(n² log 2). where d is the last-iterate distance to BNE ||0) 07 Il-
2. Let 6. = (n=² 1 ), it will require [2n2 log 2) itera- n+1 tions to reach |00 01 || S d.
We identify that such slow convergence phenomenon is raised due to the local property of the utility objective: Ui(Be,, ). ). To capture the vicinal property of the BNE point 87 we define a neighbor region with ((+) radius:
These results indicate that the number of iterations required to achieve a specified accuracy increases quadratically with the number of bidders n, highlighting the inefficiency of the utility gradient method. Moreover, this slow-convegging problem still exists when applied with accelerated gradient methods, such the Momentum (Kingma & Ba, 2015) or Nesterov method (Beck & Teboulle, 2009), which we further discuss in Appendix C.2.3 and show that they also suffer from growing complexity with bidder number n. In contrast, in the following sections, we will see that our proposed BR gradient method achieves a convergence rate of Olog 4). proved to avoid the term.
N(O0) == 10, E Rē1110 - 0011 S )
2n
By examining the Hessian matrix (0.) of the objective U, in this neighborhood, we find:
Lemma 4.1. Under Assump. 3.1, the Hessian matrix H (0.) of UB, )) in ((O)) has a condition number in the order of (n²))
In optimization, the convergence speed of gradient- methods depends on the condition number of the objective's ss Hessian; higher condition numbers generally lead to slower convergence (Bubeck, 2015). In our auction setting, the utility function's 's Hessian has a condition number growing quadratically as n. This ill-conditioned property (Tong et al., 2021) explains the slow convergence observed for large n.
4.2. Best- Rest-Responee Distance Objective
The slow convergence of the utility objective encourages us to explore a more robust objective in auction games, which can directly capture the strategy-wist difference of B3, and of so that the convergence rate won't 't degenerate when increases. Inspired by recent success of cquilibrium-ave loss in learning equilibrium (Gemp et al., 2024; Huang et al., 2024), we propose a new objective called Best Response Distance (BR Distance):
Intuitively, for bidder who should submit a low bid when holding a low valuation, his/her chance of winning becomes negligible as n increases. Consequently, the utility gain of deviating from the current strategy 8, to the BNE strategy 33 also diminishes with inereasing n. This results in vanish- ing gradient magnitudes near the BNE for low valuations. Conversely, the bidder's utility gradient remains significant when their valuation is high and does not degenerate with in- creasing n. This imbalance in gradient magnitudes, caused by the vanishing gradient at low valuations, can lead to slower convergence rates during optimization.
LER " isn
1 Be, 13,, (vs) - Po (12)
where br; 30==ag arg max as (vi, b, B)
By directly measuring the distance between current strat- egy 3o, (-) with the best-response bid br(;, B_:) (Armantier et al., 2008), this loss sidesteps the utility objective's 's gradi- ent vanishing problem when bidder numbers increase.
ensure non-negative parameter, where the projection operator is: Proj(w, c) = (max(w, (w. 0), max(c, 0})².
5

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
Moreover, assuming the ex-interim utility ū.(1; ba (-4) to be L-LLipschitz continuous in b;. the BR distance can serve as upper bound of the approximation factor in e-BNE: Lemma 4.3. With an L-Lipschitz continuous ex-interim ulility the strategy profile 33 forms an e-BNE such that e S / (2LBR (8) L.
rather than to optimize the entire objective function. Addi- tionally, the second-order gradient of Lū,/ōbz can also be calculated analytically, similar to the first-order gradient in Eq. (11). Specifically, in FP or SP auctions:
0²u;
(1: bi) (be) 25 (ba), FP 063 (v: bm),m, (bz) - Jmm (b.), SP
(15)
Therefore a lower BR distance leads to a closer approxi- mation to the BNE. Like utility gradient method, we can optimize this objective by applying gradient update for each bidder's s strategy 0,, dubbed as the BR Gradient method:
where fm, (-) is the gradient of market price's pdf. To esti- mate the pdf's gradient, we can use any differentiable esti- mation method, such KDE with differentiable kernel, or other fully differentiable methods like SM
0 1 + 0% agbr, (3oz): )
(BR Gradient)
On the other hand, if the ex-interim utility is locally con- vex, i.e., /0b 2 O, the quadratic approximation has unbounded maxima. To address this, we replace the second- order gradient with a negative constant to ensure the update direction improves the utility, resulting in a first-order ap- proximate best response:
where the gradient is calculated as:
Por: (Bgr) = Eus (Sog (v:)) - br, br, Bos, 1). Bo (vi)
(13)
Furthermore, we've derived the following convergence rate in comparison to the utility gradient method:
+ (b.(
1
(b) R (x(bb)
(b bi)
(b (b-b;)²
Theorem 4.4 (BR Gradient Converge Rate). Under As- sump. 3.1. projected gradient descent via BR gradient con- verges to the BNE 0 = (-=1, ,0) at rate of Oloog 2).
Ob.
27
(16)
1st
= br,
~ b, 7 0u./0b:
With these approximations, we have the following Approxi- mate BR Gradient method:
With an Oloog 2) convergence rate, the BR gradient method is proved to fundamentally avoid the growing complexity with increasing n. As illustrated in Fig. 2, the BR gradient dynamics converge to the BNE point within limited steps, even for large number of bidders n.
05+1 - aggee, (3xz) (Approx BR Gradient)
where 9br, (3gx) = EE, 1[36 (v;) - br:) Vo, (v:)),
4.3. Learning via Approximate BR Gradient
and the approximate best response br; is calculated via Eq. (14) or Eq. (16) depending on the local condition, which we' ve detailed in Algorithm in Appendix E.2.
Although the BR Gradient is proven to avoid the slow con- verging problem, it requires an arg aag-max operator over all bids: (r, 3_x) arg max, üz (v. (,).), which can in- troduce vast computational burdens in practice. To circum- vent this issue, we propose to utilize a locally approximated best response br; instead of directly computing the arg-max.
In fact, when applying the first-order approximation, our method reduces to the previous utility gradient method:
-9be, (Bp) E,, ((3e, (v)) - br, 1st
Ve, (v:)
= = (v,, Go, (cx),
Firstly, we consider to utilize the local second-order Tay- lor's expansion of the ex-interim utility function (we denote ú (b) = ū. (w;, b, :) and by = (x,( for clarity):
But in the vicinity of the BNE, where the slow convergence problem of utility gradient happens, the bid by is close to the best response. Using the optimality condition of best response br; = arg max,, u,(v; b,, B_x). we have:
3. (b) RJ (b.) + (bi) (b- - b.) + 2 0b3
1 8 a, (bx)
(b 6.)2.
ab.
0ū, 0b, = 0, 8² a. /0/ < O.
(17)
If the ex-interim utility is concave locally, i.e., Pū./O0 < 0, the maximum of the quadratic approximation provides an estimate of the best response, resulting in a second-order approximate best repsonse:
Such concavity validates the use of a second-order approxi-
mation for the best response br; 2nd. in the neighborhood of BNE. Consequently, the local convergence properties dif- fer from those of the utility gradient. Specifically, we've established the following local convergence result:
2nd br:
2 b, - -8Pu,003)
-1 Ou,/0b,.
(14)
This formula resembles Newton's 's method (Nesterov, 2018) but is used here to approximate the local best response
'The contribution of optimization objective is orthogonal gradient estimation, allowing for various estimation methods.
6

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
Theorem 4.5 (Approximate BR Gradient Converge Rate). Under Assump. 3.1, projected gradient descent via approx- imate BR gradient locally converges to the BNE 0; = .) at a rate of (log 2)
Table 2. Learned strategies' 1.2 distance BNE using different methods in FP/SP symmetric auctions with varying numbers of bidders n. We report the averaged L2 across initializations after typer-paramete search for every method. The L2 values are evaluated at different steps ("@steps"") during the training stage.
("=,,0)T
Like the original BR gradient, the approximate BR gradient method also achieves an (log 4) local convergence rate, thereby avoiding the locally slow-converging problem of the utility gradient. As depicted in Fig. 2, the learned strategy using approximate BR gradient also successfully converges to the BNE point even with increased bidder numbers.
MM Algorithm
L2@500
L2@ Ik
L2@2k
t/iter
SM
4.12e-3
3.75e-3
3.08c-3
0.013s
2 Approx BR
Utility Grad
5.35c-3
4.75e-3
2.82c-3
0.002s
5.46e-3
5.42e-3
3.01e-3
0.002s
SM
3.74e-2
1.83-2
1.57e-2
0.035s
FP
5
Utility Grad
3.49c-2
1.62c-2
1.51e-2
0.002s
Approx BR
1.35e-2
7.77e-3
5.20e-3
0.002s
5. Experiments
SM
1.05e-1
7.39e-2
5.01e-2
0.091s
10
Utility Grad
8.84c-2
6,94e-2
5,44e-2
0.002s
5.1. Implementation Details
Approx BR
6.21e-2
1.28e-2
9.65e-3
0.002s
We conduct the experiments in more general setting where the bidding function is 3-layer MLP instead of the linear model in Assumption 3.1 and evaluate performance across different mechanisms, asymmetric auctions, risk-averse util- ities, and alternative gradient estimation approaches. To assess the learned bidding strategies and their approxima- tion of the BNE, we analyze several classic auction games with known BNE solutions and measure the 1.2-distance between the learned strategy 39. (-) and the BNE solution 37 (-) by sampling K values vy from the prior Fs:
SM
5.26e-3
4.53e-3
3,57e-3
0.012s
2 Utility Grad
5.31e-3
4.61e-3
3.73e-3
0.002s
Approx BR
5.31e-3
4.62e-3
3.77e-3
0.002s
SM
3.40c-2
1.89c-2
1.73e-2
0.035s
SP
Utility Grad
2.910-2
1.59c-2
1.34c-2
0.002s
Approx BR
7.83e-3
4.89e-3
3.45e-3
0.002s
SM
1,40e-1
7.57e-2
3.51e-2
0.090s
10 Utility Grad
9.35e-2
5.35e-2
3.17e-2
0.002s
Approx BR
1.33e-2
5,91e-3
3.73e-3 0.002s
As shown in Tab. 2, we find that the proposed approximate BR gradient method significantly enhances convergence speed the number of bidders increases. While all meth- ods achieve near-optimal solutions with 1.2 distances at the order of 1e-3 when the number of bidders is small (n = 2), differences become pronounced as n grows. As the number of bidders n increases, the SM and Utility Grad methods exhibit slow convergence, resulting in final L2 distances of approximately 5e-2 and 3e-2 when n 10. In contrast, the Approx BR method consistently delivers solutions with I.2 distances at the 1e-3 order. This reduction in L2 distance indicates that the strategies learned by our method produce a more accurate approximation of the BNE.
1 K L2, = =( M (Bo. - {( j=1
((..)))))B(())))) 1/2
where the BNE solutions are detailed in Appendix E. For comparisons, we primarily utilize the following three meth- ods to learn BNE in different auction game settings:
SM (Kohring et al., 2023): the existing state-of- of-the-art method for learning BNE strategies, which maximizes U/ with soft-max approximated gradient VSM üz.
Utility Grad: the utility gradient method using our derived gradient solution in Eq. (11) to maximize U,.
Approx BR: the proposed approximate BR gradient method (or Approx BR for short), detailed in Algorithm
For a clearer understanding of different L2 magnitudes, Fig. 5b provides a visual comparison of the strategies, where the "SM+aBR" strategy (ours) closely aligns with the BNE solution, while the "SM" strategy exhibits noticeable devi- ation from the BNE. Specifically, the "SM+aBR" strategy achieves an L2 distance of approximately 5c-3, in contrast to the "SM" strategy, which reaches an L.2 distance of about 7e Referring back to the results in Tab. 2, where our Ap- prox BR method consistently yields average I.2 distances at the order of Ie-3, this confirms the precision of the strategies learned through our method in approximating the BNE.
Following (Kohring et al., 2023; Bichler et al., 2021), we use a shared MLP network for bidders with the same value prior and run each method with 2,000 steps. More details can be found in Appendix F.
5.2. Main Results
We benchmark the L2 distance in the symmetric auction games with uniform prior under first-price and second- price mechanisms like previous work (Bichler et al., 2021; Kohring et al., 2023; Huang et al., 2024), where the BNE solutions are 3 (v:) = n-1 U2 and / (v.)= ii respectively. We increase the bidder numbers n and validate the conver- gence improvement of our proposed method in Tab. 2, where we report the averaged 1.2 results across initializations.
Additionally, we explain the substantial reduction in the time required for each step in the Utility Grad and Approx BR methods, as shown in the last column (t/iter) of Tab. 2. The reason is that both methods estimate gradicnts based
7

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
Aire-derriin Lailly
3M
SM Uillly Cred Agarox
3P MMy Dra) Appros
SM Ui Brid Aporox
Mikry brad Appros
Hi
|
humber Didaeaa
Number n
Narrour of odeun
Numterr Bilden
(a) L.2 of the weak bidders
(b) 1.2 of the strong bidders
(a) FP with risk aversion
(b) SP with risk aversion
Figure 3. L2 error of learned strategies under the SP asymmetric auction with 2 different (weak/strong) value priors.
Figure 4. error of learned strategies under the FP/SP symmetric
auction settings with risk-averse bidders
on the proposed MC on distribution estimation with directly computed solution in (11), whereas SM relies on sampling the
Alternative Gradient Estimations. The proposed approxi- mate BR gradient method is not limited to specific gradient estimation technique. To demonstrate its adaptability, we incorporate the SM gradient estimation into the approximate BR (aBR for short) gradient learning framework, referring to this combination as "SM+aBR". Given that SM exhibits slow convergence with large bidder numbers n, we bench- mark both SM and the aBR-augmented version in the 10- bidder FP auction setting of Tab. examine whether our proposed method can enhance convergence speed.
ex ex-post utility and approximating the gradient through backpropagation. The direct estimation significantly im- proves the efficiency of our gradient estimation method.
5.3. Further Extensions
Extension to Asymmetric Auctions. We also explore the asymmetric auction setting, where bidders have different value priors. Following previous work on learning asymmet- ric auction games (Bichler et al., 2023a), we consider the FP auction with 2 bidders whose value priors are [00 0.5] (the weak bidder) and U[0, 1] (the strong bidder). As depicted in Fig. 11 in Appendix 1, the bidding strategies learned via our Approx BR method closely align with the BNE strategy, confirming convergence even in this asymmetric setting.
We run both methods with five initializations and plot the L2 distance over training time in Fig. 5a. As illustrated, after applying the approximate BR gradient method from the 200- th step, the L2 distance decreases significantly faster than the original SM method and quickly converges around 1,000 steps. Moreover, strategies across 5 initialization for both methods in Fig. 5b. The results reveal that the strategy learned by SM shows a noticeable distance from the BNE solution, whereas the learned strategy of SM+aBR aligns closely with the BNE strategy. This confirms the flexibility of the proposed Ap- prox BR method to effectively utilize different gradient estimation techniques without the analytic gradients.
present the pest-performing learned
We then scale up the number of bidders to evaluate con- vergence speed with a similar prior setting in SP auctions, where half of the bidders belong to the weak type U10, 0.5] and the rest strong type follows U0, 1]. As shown in Fig. 3, both SM and Utility Grad methods exhibit L2 distances above 1e-2, while our proposed Approx BR method con- sistently achieves precise solutions with L2 distances at the order of 1e-3 for both types of bidders, demonstrating a much closer approximation to the BNE, In addition, the Util- ity Grad also outperforms the SM's prediction, highlighting the effectiveness of our gradient estimation approach.
Auceege L2 forert Mediodo Durnn
Brne Learred Biäding Brotoggis Dilloiont Malleds
Extension to Risk Aversion. In practical trading scenarios, the bidders might be risk-averse, which means their utility may not be identical to the monetary payoff. To address this, we extend our experiments to cases where each bidder has a Von Neumann-Morgentter utility function (Krishna, 2010). Similar to prior works (Bichler et al., 2021: 2023a), we assume the risk-averse bidders possess the utility function defined as the payoff raised to the power of p < 1.By measuring the L2 distance to analytic BNE solutions, we can evaluate the convergence rates of the three methods in the risk-averse setting. As depicted in Fig. 4, our proposed Approx BR continuously learns precise solutions with the 1.2 distance at the order of 1e-3 for both types of bidders, outperforming other methods by a clear margin.
20:
Tharmng Stepe
1008
Value 91
1.0
(a) Training time L22
(b) Lcarned strategics
Figure 5. Learning results of the SM method (Kohring al., 2023) and the augmented version with our proposed Approx BR method (SM+aBR) under the 10-bidder symmetric FP auction.
6. Conclusion
In this paper, we introduce the Approximate Best Response Gradient method, a new approach for efficiently learning Bayesian Nash Equilibrium in auction games. By utiliz- ing an analytic solution for utility gradient estimation, we
8

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
not only improve the efficiency of the gradient computa- tion but also enable theoretical convergence analysis. Our method optimizes the proposed Best Response Distance objective, which achieves a significantly faster local con- vergence rate Oloog 2) in a classic symmetric auction setting, compared to the traditional utility gradient method's On log 2) rate. Extensive experiments validate the su- perior convergence speed of our approach across various auction scenarios, including different auction mechanisms, asymmetric value distributions, risk-averse utilities, and alternative gradient estimation techniques.
1145/349048663532244 URL https: cetpss//ddi.org 10.1145/349046..55 3538444
Beck, A. and Teboulle, M. A fast iterative shrinkage- thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1):183-022, 2009, doi: 10.1137/0807 16542.
Bichler, M., Fichtl, M., Heidekrüger, S., Kohring, N., and Sutterer, Learning equilibria in symmetric auction games using artificial neural networks. Nature machine intelligence, 3(8):687-695, 2021.
Acknowledgments
Bichler, M., Fichtl, M., and Oberlechner, M. Computing bayes nash equilibrium strategies in auction games via si- multaneous online dual averaging. In Proceedings of the 24th ACM Conference on Economics and Computation, EC '23, pp. 294, New York, NY, USA, 2023a. Associa- tion for Computing Machinery. ISBN 9798400701047. doi: 10.1 14/33500007 URL https: /doi. erg/10. 110.0.11455 1ee111145/8888 3555//33330007777713333 3597713
This research supported by the National Natural Science Foundation of China (92270114) This research was also supported by the advanced computing resources provided by the Supercomputing Center of the USTC.
Impact Statement
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Bichler, M., Kohring, N., and Heidekrüger, S. Learning equilibria in asymmetric auction games. INFORMS Jour- nal on Computing, 35(3):523-553 2023b.
References
Bichler, M., Lunowa, S. B., Oberlechner, M., Pieroth, F. R., and Wohlmuth, B. On the convergence of learning algo- rithms in bayesian auction games, 2023c.
Ahunbay, M. S. and Bichler, M. On the uniqueness of bayesian coarse correlated equilibria in standard first- price and all-pay auctions. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2491-2537. SIAM, 2025.
Bosshard, V., Bünz, B., Lubin, B., and Seuken, S. Comput- ing bayes-nash equilibria in combinatorial auctions with verification. Journal of Artificial Intelligence Research, 69:531-570, 2020.
Armantier, O., Florens, J.PP., and Richard, J.FF. Ap- proximation of nash equilibria bayesian games. Journal of Applied Econometrics, 23(7):965 981, 2008. doi:
Bubeck, S. Convex optimization: Algorithms and complex- ity. Found. Trends Mach. Learn., 83-44)231--377, nov 2015. ISSN 1935-8237. doi: 10.1561/2200000050 URL https: /doii org/ .
1040. URL https: http::///nnnneeeeeeee wi ley. / abs/10.1002/jazt
1561 200...1111//2200005555
Bajari, P. Comparing competition and collusion: numeri- cal approach. Economic Theory, 18:187-205, 2001.
Chen, X. and Peng. B. Complexity of equilibria in first-price auctions under general tie-breaking rules. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pp. 698-709, New York, NY, USA, 2023, Association for Comput- ing Machinery. ISBN 9781450399135. doi: 10.1145/
Balseiro, S. R., Besbes, O., and Weintraub, G. Y. Repeated auctions with budgets in ad exchanges: Approximations and design. Management Science, 61(4):864-88) 2015. doi: 10. 10.1288/mmss.20114.2222 URL https: /doi. org / 10. /a/88//mmmcc../ 201.. 2022.
3564246.3585195 URL https: httpps:////...eeeeeeeeeeeeesesss httt::::/dooooor///0/ org/10.
Banchio, M. and Skrzypacz, A. Artificial intelligence and auction design. In Proceedings of the 23rd ACM Con- ference on Economics and Computation, EC '22, pp. 30-31, New York, NY, USA, 2022. Association for Com- puting Machinery. ISBN 978145988 01814503915000
Chen, X., Deng, X., and Teng, S.-H. Settling the com- plexity of computing two-player nash equilibria. J.
ACM, 56(3), May 2009. ISSN 0004-5411. doi: 10.
1145/15165112.5115566 URL https: http://dooo.rroooo 10. 10.1145/1516512.1
doi: 10.

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
Daskalakis, C., Ilyas, A., Syrgkanis, V., and Zeng, H. Train- ing gans with optimism. In 6th International Confer- ence on Learning Representations, ICLR 2018, Vancou- ver, BC, Canada, 2018. OpenReview.net. URL https: / //openreview.... net forum? pitoormmiiddaae SyJyySb
Hartline, J. D., Syrgkanis, V., and Tardos, É. No-regret learn- ing in bayesian games. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, pp. 3061-3069, Montreal, Quebec, Canada, 2015. Curran Associates, Inc.
Deng, X., Hu, X., Lin, T., and Zheng, W. Nash convergence of mean-based learning algorithms in first price auctions. In Proceedings of the ACM Web Conference 2022, WWW "22, pp. 141-150, New York, NY, USA, 2022. Associa- tion for Computing Machinery. ISBN 9781450390965. doi: 10. 00.1144/34455447351205555 URL httpp::///... //doi. 1145 111.1..1115/34844440 01 3512059.
Huang, K., Chen, Z., Wang, X., Gao, C., Gao, J., Ding, B., and Wang, X. Auctionformer: A unified deep learning algorithm for solving equilibrium strategies in auction games. In Proceedings of the 41st International Confer- ence on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 19635-19659, Vienna, Austria, 21-27 Jul 2024. PMLR.
Feng, Z., Guruganesh, G., Liaw, C., Mehta, A., and Sethi, A. Convergence analysis of no-regret bidding algorithms in repeated auctions. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAA/ 2021. pp. 13999-546,, Virtual Event, 2021. AAAI Press. doi: 10.1609/AAAI..3354 16680. URL https::/p//......... /ttp///o..ooo org/10 1609/ v3516.16688
Hubbard, T. P. and Paarsch, H. J. Investigating bid prefer- ences at low- fow-price, sealed-bid auctions with endogenous participation. International Journal of Industrial Organi- zation, 27(1):1-14, 2009.
Kaplan, T. R. and Zamir, S. Asymmetric first-price auctions with uniform distributions: analytic solutions to the gen- eral case. Economic Theory, 50(2):269 -0000999--0--00000 2012. ISSN 09382259, 14320479.
Filos-Ratsikas, A., Giannakopoulos, Y., Hollender, A., La- zos, P., and Poças, D. On the complexity of equilibrium computation in first-price auctions. In Proceedings of the 22nd ACM Conference Economics and Computation, EC 22,, pp. 454 New York, NY, USA, 2021. Associ- ation for Computing Machinery. ISBN 978 17808533854 doi: 10. 111443/465556644666622 URL https: /doi. STT//10.114/34455455 3467544466.4666222 3467
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. In 3rd International Conference on Learn- ing Representations, ICLR '15, San Diego, CA, USA, 2015. OpenReview.net. URL http:://axxv..rrrr abs / 11///1111... 6980.
Kohring, N., Pieroth, F. R., and Bichler, M. Enabling first-order gradient-based learning for equilibrium com- putation in markets. In Proceedings of the 40th Interna- tional Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 17327- 17342, Honolulu, Hawaii, USA, 23-29 Jul 2023. PMLR.
A., Giannakopoulos, Y., Hollender, A., and Kokkalis, C. On the computation of equilibria in discrete first-price auctions. CoRR, abs/2402. 12068, 2024. doi: 10:45550ARK11122400.2266
URL https: //t::///d.o/////// org 48540/55//0 /tt/5/////iivvvv/ arxiv 2402. 1208..
Freund, Y. and Schapire, R. E. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):7-1033 1999.
Kolumbus, Y. and Nisan, N. Auctions between regret- minimizing agents. In Proceedings of the ACM Web Conference 2022, WWW '22, pp. 100-111, New York, NY, USA, 2022. Association for Computing Machin- doi: 10.1145/3485447, 1145/
Gayle, W.-R. and Richard, J. F. Numerical solutions of asymmetric, first-price, independent private values auc- tions. Computational Economics, 32:245-278, 2008
ery. ISBN 9781450390965.
3512055. URL 3485447.351202
Gemp, I., Marris, L., and Piliouras, G. Approximating nash equilibria in normal-form games via stochastic op- timization. In The Twelfth International Conference Learning Representations, ICLR 2024, Vienna, Austria, 2024. OpenReview.net. URLhttps: :tttlp::://pppeeeeee cpenreview. net/ forum? d=cc8h31334E
Krishna, V. Auction Theory. Academic Press, San Diego second edition edition, 2010.
Lei, Q., Nagarajan, S. G.. Panageas, I., and Wang. X. Last it- erate convergence in no-regret learning: constrained min- max optimization for convex-concave landscapes. In The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, volume 1 130 of Proceedings of Machine Learning Research, pp. 1441-1449, Virtual Event, 2021. PMLR. URL http: / httpp/pooceenngn////ee wtt.ppress/vv10/leeee.s
Harsanyi, J. C. Games with incomplete information played by "bayesian" players, i-iii part i. the basic model. Management Science, 14(3):159-11) 182, 1967. doi: 10. 10.1288/mssc. 159. URL https: http///ooooo// 10.1287 11287/mmss /mnsc./s.... 14. 159..
10

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
Letcher, A., Balduzzi, D., Racanière, S., Martens, Fo- erster, J., Tuyls, K., and Graepel, T. Differentiable game mechanics. Journal of Machine Learning Re- search, 20(84):1-40, 2019. URLattp: htett://jmlr.ogg papers/v20/199 008. htmll
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, I.., and Polosukhin, I. Atten- tion is all you need. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, pp. 5998-6008, Long Beach, CA, USA, 2017. Curran Associates, Inc.
Li, Z. and Wellman, M. P. Evolution strategies for ap- proximate solution of bayesian games. Proceedings of the AAAI Conference on Artificial Intelligence, 35 (6):5531-5540, May 2021. doi: 10.1609/aai. v3566. 16696. URL https://ojs..a.. aaai............................ orq/ index. php/ hhtp/AAA//artiill//ieee////
Wang. Z., Shen, W., and Zuo, S. Bayesian nash equilibrium in first-price auction with discrete value distributions. In Proceedings of the 19th International Conference on Au- tonomous Agents and MultiAgent Systems, AAMAS '20, pp. 1458-1466 Richland, SC, 2020. International Foun- dation for Autonomous Agents and Multiagent Systems.
Marshall, R. C., Meurer, M. J., Richard, J.-F. and Stromquist, W. Numerical analysis of asymmet- ric first price auctions. Games and Economic Behavior, 7(2):193-22,, 1994. ISSN 0899-8256. doi: https//bbioor//00.000//gmeee./ com/ URL https://ww..cienee ccc.anee/srrcccee//////999222221
ISBN 978 177814500 4553351
Milgrom, P. Putting auction theory to work: The simulta- neous ascending auction. Journal of Political Economy, 108(2):245-272, 2000. ISSN 00223808, 1537534X.
Milgrom, P. R. and Weber, R. J. A theory of auctions and competitive bidding. Econometrica, 108-)11089 1982. ISSN 00129682, 14680262.
Nash, J. F. Equilibrium points in n-person games. Proceed- ings of the National Academy of Sciences, 36(1):48-49, 1950. doi: 10.10773/pma.33.11.3 URL https: //ww.. pnas. mhas.oz. brgg/dbiaab//1..100
36. 48.
Nesterov, Y. Lectures on Convex Optimization. Springer Publishing Company, Incorporated, 2nd edition, 2018. ISBN 2319915770.
Salimans, T,, Ho, J., Chen, X., Sidor, S., and Sutskever, I. Evolution strategies as a scalable alternative to reinforce- ment learning, 2017. URL https: /ttp:://axxvvvvooo abs/1703. 03864.
Shen, J., Orten, B., Geyik, S. C., Liu, D., Shariat, S., Bian, F, and Dasdan, A. From 0.5 million to 2.5 million: Efficiently scaling up real-time bidding. In 2015 IEEE International Conference on Data Mining, pp. 973-978, Atlantic City, NJ, USA, 2015. IEEE, doi: 10.1 109/ICMM. 2015.72.
Tong, T., Ma, C., and Chi, Y. Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent. Journal of Machine Learning Research, 22(150):1- 63, 2021. URL http:/ / fmmr..rao. 20-1067. html.

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
A. Related Work
Our work is mainly related to methods for solving equilibrium in auction games, which has been addressed via various approaches.
Numerical Equilibrium Solver: Computing Nash Equilibrium (NE) is known for its computational complexity, with even the two-player (aka bidder) bi-matrix game problem being PPAD-complete (Chen et al., 2009). This complexity extends auction settings, where solving BNE is also PPAD>complete in both continuous (Filos-Ratsikas et al., 2021) and discrete value scenarios (Filos-Ratsikas et al., 2024; Chen & Peng, 2023). Despite this complexity, there have been positive developments in numerical methods for solving BNE in specific auction contexts. Marshall et al. (1994) proposed a numerical method for solving BNE in first-price auctions, named backward-shooting which has since been applied to both continuous (Bajari, 2001; Gayle & Richard, 2008) and discrete settings (Wang et al., 2020). Other numerical methods include polynomial approximations (Bajari, 2001; Hubbard & Paarsch, 2009) and best-response dynamics (Bosshard et al., 2020).
Learning BNE in Discrete Auction Games: Recent advancements have investigated the application of machine learning techniques to compute the BNE in both discrete and continuous auction games. In discrete value scenarios, initial approaches applied no-regret learning algorithms, known to converge to NE in zero-sum normal-fomn games (Freund & Schapire, 1999; Lei et al., 2021), to auction scenarios (Hartline et al., 2015). Theoretical results show that no-regret learning can converge to BNE in several simplified auction settings (Feng et al., 2021), while it might fail to converge in auctions with fixed values (Deng et al., 2022). Researchers have also introduced other agent-based learning methods (e.g. reinforcement learning) into discrete auctions (Feng et al., 2021; Kolumbus & Nisan, 2022; Banchio & Skrzypacz, 2022). More advanced methods include the application of online convex optimization techniques (Bichler et al., 2023a) and the development of unified frameworks to learn BNE across various auction mechanisms (Huang et al., 2024) via transformer architectures (Vaswani al., 2017).
Learning BNE in Continuous Auction Games: Our focus aligns with the continuous value setting, where solving BNE requires optimizing each bidder's bidding function, similar to optimizing differentiable games. Despite the success of gradient-based learning in differentiable games (Daskalakis al., 2018; Letcher et al., 2019), gradient methods face fundamental challenge of gradient computation in auction games, due to the non-smooth nature of utility function (Bichler et al., 2021). To address this issue, existing works have employed various gradient estimation methods through evolutionary strategies (ES) (Bichler et al., 2021; Li & Wellman, 2021; Bichler et al., 2023b), or approximating the utility function to allow for smooth gradient computation (Kohring et al., 2023). Theoretically, Bichler et al. (2023c) provided convergence analysis on gradient- based methods in symmetric auction games by formulating the BNE as a variational inequality (VT) problem. Our work follows this gradient-based learning paradigm in continuous auction games, with novel gradient estimation techniques and learning objectives to improve convergence rates.
B. Limitations and Future Directions
Theoretical Limitations: Our theoretical framework primarily focuses on the symmetric auction with a uniform prior following Feng et al. (2021), and employs a shared linear bidding strategy. Future research could extend these insights to more generalized settings that include a broader array of auction types and bidding strategies. Additionally, the theoretical results presented are based on exact gradients in their population form and do not incorporate empirical loss under different estimation scenarios, e-g., the KDE or histogram methods when estimating the pdf of the market price distribution. Future studies could address this limitation by deriving solutions using stochastic optimization approaches, which may offer more robust and practical insights.
Our work introduces a new gradient estimation method that utilizes the analytic gradient and proposes a new optimization approach, approximate BR gradient. However, the closed-form solution required by our gradient estimation method might not generalize across all possible scenarios, particularly in more complex auction settings where more sophisticated gradient estimation techniques might be necessary. Although our optimization objective operates independently of specific gradient estimation methods, its reliance second-orde gradients introduces additional complexity, necessitating differentiable estimated distribution.
Methodological Constraints:
12

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
C. Proofs
C.1. Gradient Estimation
Following previous work (Huang et al., 2024; Bichler et al., 2023c), the ex-post utility uy can be reformulated as the function di of competition with market price m, maxzşi by:
u (u, bi, b-i)= = ú, b5, m;) (m; := max
j
(18)
ū, (Ui, bi, m²) I(b; > m4),
where the u, (vs, bú, mz) is the utility when bidder wins. We present the results FP and SP, where ij (Ui, m.) = us -bb. in FP and uz (v,, by, m,) = V m, in SP respectively. Without loss of generality, we assume:
Assumption C.I. The market price distribution is atomless.
The ex-interim utility's gradient can be directly computed:
(1 B-i)
ab.
0
Ee_ [ui(ve, by. b-i(v=:)]
Zb.
0
Emilns [1t (1i, bs, mi) I[b; > m,)]
0b,
Uz b) I1(b, > x)dFm (x)
bb;
1/n ai (1t, b) fm, (z)dz
ab.
utt (vs, bi, b,) fm, (b,) + 1-' ①
(Us, b), fm, (x)dr.
In the case first-price (FP) and second-price (SP) auctions, the gradient is calculated by:
(t: - b.).fm. (b.) F'm (b:), FP (1: - (.).m.((.)).
ab: ūz (vi, bi, B_i)
SP
Moreover, the second-order gradient, which is used in the approximate BR method, is calculated by:
2² ū. (U;, br, B-1))=) = (w: be)5mn (bc) 2fm, (bi), FP (vs bo)Sm, (b.) (b:), SP
0b?
Notably, this gradient formula can be extended to other settings, such as risk aversion and reserve price. For example, consider a risk-averse utility (Krishna, 2010) such that the ex-post utility is extended as:
(ui by. b=:),, (e by, b-.) = (u b;, b-:), else
u 2
(19)
where un;, b,, b-i) is the original risk-neutral utility function defined in (2) and p E (0, is the risk-aversion weight. Take the first price auction as an example, the gradient of ex-interin utility in this risk-aversion setting can be computed as (denote ue (v, b,, (_,) with uf for simplicity):
0
(w: b.) 1.pmmm (bx) - plu: b,)0 Fm,
by S Us
uf
ab,
(v) - b,) (b,) Fm, (b.).
by > U/.
(U: b Pm, (b.) 2p(v;- b-) (bi)
0
of
+ p(p 1)(4; bb) 2i) (ba),
Fm
b, S U/
(vi b.) fmn (b.) 2m,, (bi),
b, U4
13

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
As for scenarios with reserve price r, the ex-iterim utility is modified as:
Ev_ [1; - b,) I[bb > max(3=(((-),r)))
FP,
bi, B_1)
Ry [1; (ax((3_(ve_)))) T(b; >
SP.
To estimate the gradients, we can replace the original market price m, m by with a reserved version: m. max (m;; r). We estimate the distribution of the reserved market price m by sampling bids b-i, and compute the pdf fmn and edf Pmn. Then the gradient with the reserve price can be estimated via Equation (11) by changing the distribution from m, to m..
C.2. Convergence Analysis on Utility Gradient
C.2.1. CONVERGENCE ABILITY
Here provide the convergence ability of different MC estimation methods under the symmetric uniform first-price auction setting of Assumption 3.1. We will prove that projected gradient ascent via our derived closed-form gradient (MC on distribution) converges to BNE while the MC on gradient converges to zero-bidding:
Proof of Proposition 3.2. The gradient of ū, calculated as:
0 bb,
ú. (wy, bi, 3-:) (v: b:). (b:) Fi, (b:)-
Assuming a linear bidding function B((o;) we + c. the market price distribution becomes:
- (x--) =""=
12 1
Fm, (I)
fm. (x)
thus, the gradient of ū, w.r.t. b, B,(v)) is:
ab; u. (v., (mi),
12W
n
By applying the chain rule, the derivatives of 0, = (w, T)T are
(, = v; u,(u, B,(0)),
V.l(D,,,(,,,, ab.
u. (,(1,),B_))
Given that UiBu, = Er, Vo. (v; (v:), we have:
V V.U.(B,,B.)) n2 - 1 NW
(n 1)c
(n + 1)w
TEW
(.U,BB,BB.))
nww
nww
W
Since the parameters are constrained to be non-negative, we utilize projected gradient ascent:
8/+11 +aVo,
where the projection operator is defined as:
(roj(O,) Proj(w, c) w w'2'20
min I|w' w/12 + ||c' c122
(max(w, 0}, max(c,
14

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
To prove that projected gradient ascent converges to the BNE strategy 02 (w* ,,u","') -m== O)T, seek show that:
VV, - -0,) 2 0.
This condition is sufficient for convergence since:
|10
0, |0 Proj
[|Proj(;; a oo;Ui) Proj(0,)11
S |10g + avouU 1/ (non (non-expansion)
O10 0, 20 V oo Ui, 0j 0:) + a VV
E |00 - 1;11 (when a is small)
Denoting ow n-1 then 1 nnow. and the gradient can be written as:
Vi Vell
nów (a+1) 1)e
(n-1)c
(-5w -c
VO =
=
-bw
0, 0: =
w
Considering the different cases for Sw:
When 8 The dot-product equals 22 2/w and the equality only occurs c 0, i.e. 0: 07.
When 8.. * 0: The dot-product is:
1
2n - cōw + c2
VuU cV.l;
8
W
1-3n Given that the discriminator (w..tt. c) A 82 (=(++1
< 0, the dot-product remains positive.
Thus, the gradient satisfies UV, 8- 02) 2 0, where the equality holds only when 0g = 0r ensuring convergence to 0
We've also provided a gradient flow of n Ug in Fig. 6, from which can observed that the gradient vector always has a positive part pointing to the BNE point.
For MC estimation gradient, the parameters update is given by:
(vi, bi, B-1) Prn(i = Fin (bs);
bb
vn - B,0,,,,,,((1:),811111 --
thus:
1
V=U,((, 12 7+
V.U,(3,,B..) n
The gradient is always negative, causing the parameters to converge w, c 0 with the projection operator. This results in the zero-bidding strategy (e(1,) 0.
We' ve also validated this phenomenon experimentally in the symmetric first-price auction setting with n = 2 bidders who share a 3-layer MLP network as their bidding function and employ stochastic gradient descent (SGD) to optimize the network. As illustrated in Fig. 7, the network employing our gradient estimation method in Eq. (11) successfully converges the BNE, contrast, the network trained using the MC estimation on gradient in Eq. (10) converges toward zero bidding.
15

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
Gradient Flow Map A
1.0
BNE Point (w", c*) Gradient Direction Optimum Direction
A
0.8
A
A
A
4
A
0.6
0.4
0.2
L
0.0
*
7
0.0
0.2
0.4
0.6
0.8
1,0
W
Figure 6. Gradient flow of Va, Us when
C.2.2. CONVERGENCE RATE
Upper bound. Here we prove the (n²2) condition number of U.'s Hessian matrix (Lemma 4.1) and O(n log 2) local convergence rate of projected gradient ascent under the symmetric uniform first-price auction setting of Assumption 3.1:
Proof of Lemma. 4.1 and Theorem. 4.2 (Part upper bound). Firstly we examine the Hessian matrix of Uz:
0²
θ u. Vo B.(z))
Vi. U. Ev,
U.
3r Vo,
O
ab;
With the second gradient of
8 28?
(vi, bi, B_ i) at bi Bo, (vi) being (assuming >> 2):
0²_
(n - 1) - 2 - nw) 1 n-2 (n 1)(n - 2) n-3
14
06
the Hessian matrix expressed as (Let S. = nw + 2 12):
(n-1)Sw.
c(n 1)(n
1)_1)
c(n-2)
H (w,c)
()+1)
(n (n-1)S
c(n 22)
S
cn 1)
For the local convergence rate, we define a neighbor region of the BNE point:
N(w e²) = [ww,, T)T R - w012 + |c - cs
where we ((2) radius: r 2n so that S.m E [2 3.. Now we analyze the property of the Hessian matrix within this
neighborhood, which satisfies:
Every element of H is positive and in the order of ((1), thus the max eigenvalue Amax O(1):
16

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
Leamed Bidding Stralegy B((x))
Leamed Bidding Strategy
1.0
1,0
BNE Strategy
BNE Strategy
Learned Strategy
Learndd Strategy
0.8
0.5
0.4
0.4
0.2
0.2
0.0
0.2
0.4
0.5
0.8
1.0
0.0
02
0.4
0.8
0.8
1.0
Value V.
Value V/
(a) MC on distribution (ours)
(b) MC on gradient
Figure Convergence results of different gradient estimation methods. The strategy converging to BNE in (a) is learned via the proposed MC estimation on distribution, while the zero-bidding strategy in (b) is learned via the MC estimation on gradient.
The determinant is positive:
1 wa
n n
2(n 1) n(n + 1)
n 2 +
Det(- H)
oe + (n + 1)n²
cS w
c²
0;
n
With the eigenvalues À satisfying:
2n.S (1 1)
2(n 1)2c) - A + H),
(- = X2 x
nw?
one can verify that the discriminator of this quadratic (w.r.t. A) is positive, that H has positive real eigenvalues, H is positive definite, and Amna
nSw [)w2
(n-1)*c
12(1);
The determinant Det (-H) is in the order of ( the max eigenvalue Amax is in the order of @(1) so that the condition number
Amaa
x
is
(m?²)
Amtn
Detl
Hj
Having examined the local property of H (w", c²), we can now prove the local convergence rate within N(w",, cc"). Since we've established in previous proof that:
100 - 0 < 10 1,
the gradient update will keep the parameter inside the neighbor region V(w",c") making the negative utility function always convex and the condition number x always being (nn²). Thus we can directly apply the results of general convex optimization problems: as established by Bubeck (2015) (Theorem 3.12), with stepsize Amaa Ami the projected
gradient ascent update 0f+1 Proj(0; aV,, satisfies:
11
2
110: 0,1 <
110
+
With x being ((n²), it will take On log
7) steps for |10g - 0:11 S d.
Lower Bound. Here we prove the convergence rate's lower bound the utility gradient method.
Proof of Theorem. 4.2 (Part II: lower bound). As previously stated, let p.n n=1 the utility gradient update (w..t. 8n and c) can be written as:
84+1
85 c²
nst n+1
(n-1)c²
c+1
8t
B-I
gt + pt w
n
17

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
We consider initial point 0
(==2 n
thus 80
-1.
Applying the update rule the initial point:
81 w
an
n F 71 +-
R2 2
7+
to ensure convergence, we need to make sure: (6 + (at)2 - (8 2 + (c))², resulting a < 2=2, We first claim that during optimization, & [- and ct (so that projected gradient ascent degrades the vanilla gradient ascent), which will be verified by induction later. Then we have:
E [0. 1].
For convergence analysis, we separate the update rule into two independently updating terms, denoted as at 8y + kic and b' 5 + k2d,, where kn, li2 two roots of the following quadratics:
nke
(n 1)e + k(-kc cc)
=)= =
k)
n
+
n +
n
12 +
n
This quadratics is derived by letting Vo, U = vV U and replace ow - kc. Without loss of generality, let 4 < k2, one may verify that:
12 1
n
k1
l2 < 1.
+ 1
n22
n
With the equally scaled gradient and parameter V U.V = 0w/c, we have:
gt+1 +kc 6%, ke!
+ k)
12 --- + k)(tt
(1
+ k)) (6t +ko',
5 + a-1
n ++11
n
5t + n-1
n
+
b*. Since the optimum of and are both a² 1²" the convergence of a' and b' can be directly examined via the multiplier -= n+I + k).
which means a++1_ = (1
k2) at and b
(1-
(441 + k2)
Given = 1, the convergence rates are follows:
For a with I+1 kn < =+1 x. we have I+1 + k1) E (0, 1 so a' converges to a" (2n2 log 2), with the lower bound obtained with some constant-order O(1)
nン For If with - < 2/2 < we have ( + +1) E (2 n+I n A+1 ), so be converges to 10 = O log h)
with the constant-order a.
For large n. the initial a - क while 60 - + + 2. so a > 69. This imbalance further expands due to then Q(n² log 4)) convergence rate for al while On log 2) rate for b², As a result, the distance to optimum dominated by a':
Ayya k2b²
2
( a -
||0e 1-112 ( + (ct)2
+
1/2 - h1
K1 - Kzz
1
[1i2
+ 1)(a²)2 -((1ik2 + 1)a't + (k) - 1)(())
(k1 k2)
h3 + 1
(ki k2) 2 (at)2.
1 )
2 log Resulting in an (n
convergence rate for 6.
Additionally, the condition 5t E [-2. 2. 0] can verified via induction (we consider a large n for simplicity):
Initially .w have 50
n: a and 10 n
18

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
With a a++1__ (1 " n+I + k1) a', the multiplier of a' is positive by induction, so the sign of a and a²
are the same. And a > b+ holds by the update rule. So 8 Roat-1 b
k
0. With a' converges
k2
to 0, the shrinking magnitudes ensures 1, still in [- - O]-
Similarly, the projected gradient ascent becomes the vanilla gradient ascent method since cf
2 0.
We provide illustrative examples for the constructed lower bound. Given the initial point 0 (n-2 x+11 ) we set the
learning rate a to 2=2, and the optimization trajectory in shown in Fig, 8. As predicted, the point quickly converges to around the line 0w + c = 0 (i.e., b' = 0) but takes much more steps to converge to the optimum due to the slow convergence of a².
Utility Gradient Dynamica w.r.1. + C (n*5, 20op
Utilly Gradient Dynamics w.r.t 6, + (m=10, step=600)
0.002
intaal Point
0.30
Intaal Point
BNE Puint
Puint
0, Ryf -0
6, + ky
Utllly Grad Trajectury
Utilly Grad Trajestury
0.05
100
0.075
0.01
0.000
6/025
0.002
0.03
3,200
-0.17
-0.35
-0.125
100
0775
-6.053
-0.225
-0.10
-0.55
-0.51
8,
(a) n
(b) n
Figure 8. An illustration of construction of utility gradient's lower bound. The figure illustrates the parameter quickly converges the vicinity of the line ō... + c 0, but slowly converges to optimum. We use 200 steps for the n = 5 case and employ 200 x 2 800 iterations for the 5 2 10 case show the quadratically growing complexity as n increases.
C.2.3. ACCELERATED METHODS
One may argue that the choice of projected gradient ascent rather than some accelerated gradient method, such as the Momentum or Nesterov method, might harm the convergence rate. However, it can be verified that even with Nesterov (or FISTA algorithm in the constrained optimization setting), which known to achieve the lower bound time complexity of first-order algorithm (Nesterov, 2018), the local convergence rate of the utility gradient is Onn log 4). This convergence rate can be directly derived via Theorem 3.15 from (Bubeck, 2015) like the previous results, we omit it here.
We've also included comparison with the Nesterov method in Fig. 9. As depicted in the figure, using fixed steps, the accelerated Nesterov method seems to alleviate the problem of slow convergence when = 10, but it still cannot converge the bidder number n increases further. In contrast, our proposed BR gradient methods successfully converge to the BNE point in both cases.
C.3. Convergence Analysis on BR Gradient
C. THE BR DISTANCE OBJECTIVE
Here we prove that the Best Response Distance objective is an upper bound of the approximation factor e in eBNNE, as stated in Lemma 4.3.
Proof of Lemma 4.3. Let the approximation factor e being:
e max Engo (v.(vs. br, (v,, B,,), - as (v,, (,,,), B..)
then 9 is an BBBNE by definition, For the BR distance, let (b.))) (,,,,, b,, 3_ and br, = (r.( for short, we
19

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
Dynamics Different Methods
Dynamics Different Methods
0.05
0,012
Point
BNE
Unilyy Grad
Nestarov Utiliyy Grad
Paramater c
0.03
Parameter
0.008
Approx BR Grad (Ours)
(Ours)
In tial Point
0.008
0.02
BNE Point
Utilly
Nesterov Crad
0,002
Grad (Ouns)
Approx-Bi BR Grad (Ours)
0.00
0.000
0.85
0.86
0.90
0.954
0.966
0,988
0.970
0.972
0.974
Parameter W
Parameter
(a) Dynamics when n 10
(b) Dynamics when n.
Figure 9. Learning dynamics of different methods in the setting of Proposition 3.2. The initial point 0/-0 is picked the vicinity of ((0)), such that 02 = 02 +
2n 2n ". All methods run 150 steps by default and we plot the best-performing results after learning-rate
-1
1
grid search.
have:
(3n
Σ Ee, [13:(1:))
1r
max Bys
[1,b:(vs) bral1]]
1
2 max
(Eu, (1)) -brill) (Jensen's 's inequality)
i
1
2
max
Ev.1 (+:()((v=)) (bbr))ll))
(L-Lipschitz)
2T.
Thus is bounded by v (3) L.
C.3.2. CONVERGENCE RATE
Here we prove the Ollog 2)) convergence rate of the projected gradient descent via the BR gradient (i.e., optimizing the BR distance objective), under the symmetric uniform first-price auction setting of Assumption 3.1:
Proof of Theorem 4.4. The BR gradient is defined as:
9br. = E,, [wwo; + c br;(e:)) Vo, So, (v:) where br:( = arg max ur b;, B-:)-
b,
Let 08,/0b; 0, the best-response can calculated as:
71
c
br;(v;)
Uj +
therefore the BR gradient can be calculated as:
(w n-1
Abr.
3
(w
n=
20

---

Thus will take Ollog 1 ) steps for |00 07 d. Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
So the update rule of the BR gradient be written as:
0,+1 Proj (0; agbr))
ww'
3 8
(n-
where ogor:
2n
c'
ain 10-11 1) c²
2 1/
To measure the distance to 8", let:
(1
)6t
(n 1)a
0f agh. - 0g =
3
2n
A(O; - 07)
onn
1)
5
n
where the matrix A is defined as:
1)a
A
2r
c2 1)
So the distance to f satisfies:
110
0g || = [|Proj (0) aghhr) (roj(
I ||0] agbr: 0,11
= || A(0 - 0?)1l
- |||||| |10] 1-
So the problem converts examine the spectral radius of A. Let the stepsize being or 2. we have:
5
(n
A =
By simple calculation, one can verify that:
The matrix is positive-definite;
2. The spectral radius of (i.e., max eigenvalue in the positive definite case) smaller than 39 40
Thus we have:
|10
01 S
||||| 110
0,
10 -1
0:1
40
39
11 11
40
C.4. Convergence Analysis on Approximate BR Gradient
Here we prove the local convergence results of the approximate BR gradient under Assumption 3.1:
Proof of Theorem 4.5, In a small neighbor region of 0; such as the previously defined N(w", ,c),, the ex-interim utility function is guaranteed be concave, thus the approximate BR gradient computed via the second-orde approximation (assuming 2):
8 (v;, bi, 3_e) Shg
br, B_i) B((v))
(v, bi, 3_.)
26?
wv; (nn nww) c(n 1)]
=B(():) (n 1)((n 2 - now) U/ c(n - 2)]
21

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
The gradient dynamics satisfies:
w ct+1
w - al (3: - br:]
c² aB (3:(1;) br.]
Assume the gradients can be locally approximated as linear function of 0 0z (which we will validate later), i.e,
Bes (v: - br:] E. (3:(1)) br.]
= A(0) - 0,).
Then the gradient dynamics be reformulated as:
0.+1 87 (I aA) (0) 6;).
Similarly, we need to examine the spectral radius of a.. Consider the convex case, i.e., A is positive-definite so that (A) > O, to make sure the spectral radius || a:A|| less than 1, we let 0 < < 2/ (mxmmx(A) (4). Then the minimal spectral radius is:
min
[max(| |1 - amx (A)). 1 a.minn (A))))
(E Xemaee
which is satisfied when a² Amina (A) (A)++Apull Amaz (4) (Note that this is the learning rate in the previous utility gradient's proof.) With this learning rate, we have (denote the condition number as x(A) = Amax (A)/ Amin (A)):
100
0, S || aAll
| 0,11
$ 1| a All 110_-1 0,1
Amax Amin -100 0:11
Amax + Amin
K -10--11 - -0
K K+1 1
4t
S exp
110P - 1:11-
K +
resulting in an (x{(A) log 4) convergence rate with optimal learning rate.
This explains the On log 2) local convergence rate for the utility gradient method since the gradient of the negative utility function can be locally approximated linearly by - -H (0) 07) and - H has an (nn)) condition number.
For the approximate BR gradient method, we now derive a similar linear system for the gradients. Consider a neighbor region with radius r:
(²) = {0, E 110, 0,1 s sr).
denote 6 = w 1=1, we have 8w,, c in the order of (r))
The gradient of is:
Ev, [3.(1;) - br:]
wT; (n1 1 - nw)e; - c(n 1)]
E., (n 1)[(n 2 - nw W c(n - 2)]
w
ni,,.; 0; + c(n - 1)
En, v2 (ndw. + 1)l; + c(n - 2)
n
w
ni + c(n 1)
(ndw, 1) + c(n v;dy;
Let = =ów O(nr), b= c(n - 1) = (nr), == ndw + +1 = 1 + 0 ) d = c(n 2) = -Onr).Thee integral can be computed as:
ac 2ad + 2be
d(be ad)
log( d
integral
2e
b
1
+
O(wr))
log
2e
e
nr
22

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
With some small r, such as (++,,, can omit the high-order infinitesimals and get:
B., [3,())) br,]
w
ndw
cnn-n1 100-11 1)
cnn
n 1
2
w
n1
8m
11 1)
n
1
2
Similarly, the gradient of w is:
Byg (.((((e)) -b,,]
ndw + c(n -1) n (now + 1)Us + c(n 2)
1i dvv
The integral is calculated as:
integral
[a(6d - 3ed + 26 + 3eble 2d)]
6e
d²
e (eb ad) log( d+c
((n))²))
3e
With small enough r we can omit the high-order infinitesimals and get:
nd
c(n- -
1)
Bu (,,,(((()s)) - br,] Rd
Y1
3
2
6w
3
Combining the 2 gradients produces linear gradient dynamics:
Be, (B,,(r)(B(vv:)) - br:] ER, (3:(1)) - br:]
A(0) 07),
where the matrix is defined as:
nEW
A
This is a scaled version of the previous BR gradient's 's matrix, which has been proven to be positive-definiae and the condition number is in the order of (11).
Therefore, the approximate BR gradient locally converges to BNE, at a speed of Olog 2
D. Additional Experiments
To illustrate our method's generalizing ability to general auction settings without known closed-form solutions, consider asymmetric first-price auctions with > 2 bidders, which generally lack closed-form solutions.
Here we reuse the setting of Figure 3 by replacing the second price with the first price, where bidders are equally divided into 2 types: the strong bidders with U[0, 1] and the weak bidders with U[0 0.5). In the context of n = 10, we conducted experiments to plot the learned strategies various methods across different random initializations in Figure 10.
As shown in the figures, the learned strategies of existing baselines (i.c., SM and Utility Grad) exhibit a classical slow- converging pattern: the strategies place positive bids b, > O even U; + 0. While the closed-fome BNE solutions under this setting, to our best knowledge, have not been derived, we can still infer that this bidding behavior surely deviates from BNE, as better utility could be achieved by bidding zero when = 0.
Conversely, strategies derived from our Approx BR method do not exhibit this issue. Furthermore, the learned strategy curves suggest that strong bidders with large values tend to bid more conservatively due to reduced competition, which aligns with the characteristics of the simplified 2-bidder setting's 's BNE solution (Kaplan & Zamir, 2012).
23

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
Learned Strategies across Different Initializations
Seed 0
Seed
See 2
Seed 3
0.7
Wesk didders Strong Bidders
Wesk Bidders
Weak Bidders
0.7
Wiok Biäders
Strong Bidderrs
String B Biolers
Strong Bilierr
0.5
0.5
0.5
0.5
Bids D1
0.4
0.3
0.3
0.3
0.2
0.0
0.0
0.0
0.0
Values
(a) Learned strategics using our Approx BR method.
Learned Strategles across Different Initialiiationns
Seed
Weat B.oders Strong Bidders
Wusk Bidders
0.7
Weak Biddus
Wick Biadurs
Strong Biöders
String B ddlers
Strong Bilders
0.6
0.6
0.6
0.5
B.05 D:
0.4
0.4
0.4
0.4
0.2
02
0.2
0.6
0.6
0.4
Values
Values
Values V)
Values Vi
(b) Learned strategies using the Utility Grad method.
Learned Strategies across Different Initializations
Seed Q
Seed
Seed 2
Seed
0.6
0.5
0.5
0.5
0.5
0.4
0.2
0.2
0.2
0.2
0.3
0.1
0.1
0.1
0.0
52
0.6
0.6
0.8
1.0
0.0
02
0.4
0.6 Values V)
3.5
1.0
3.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.5
0.8
10
Values V
Values v
Values VI
(c) Learned strategies using the SM method.
Figure 10. learned strategies of various methods across different random initialization under the asymmetric first price setting.
E. Implementation Details
E.1. Closed-Form BNE Solutions
Here we list the closed-form BNE solutions for the auction games considered in our experiments:
1. FP with symmetric uniform prior U(0, 1], risk-neutral bidders: (8 (1;) n 0/1
2. SP with symmetric uniform prior (0, 1), risk-neutral bidders: B (us) = V4g
3. FP with symmetric uniform prior U[0, 1], risk-averse bidders with utility defined in (19) and 0.5: 83 (vx) = 2n-2
4. SP with symmetric uniform prior U00, 1], risk-averse bidders: (vx) ti.
5. FP with asymmetric uniform prior U [0, 0.5) and (00 1), each type has risk-neutral bidder: 37(11)
1 (1
Jes
VI 3uf) for the weak bidder. 33 (12) 302
I + 303 1) for the strong bidder;
6. SP with asymmetric uniform prior U0, 0.5] and U0, 1), each type has m risk-neutral bidders (m 2 2): /87 (v:) Ui.
24

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
The solutions of (I), (2), (4), (5), and (6) can be directly found in (Krishna, 2010). As for the (3) case, can directly apply the ODE (Equation (4.3) in (Krishna, 2010)):
(w:) = u(u; 87 (vi) g(v))
ul; - (u;)) G(u;)
where u(x) = x², G()x) = 51 Fy(e) -ー and g(x) = G' (x) = (n 1)x"
Thus the BNE strategy satisfies:
(1s)s) 2(1s - 87 (v:))
U/
with the boundary condition (0) = 0, we have
2n 2
(1,)
2n Us.
Additionally, we illustrate the learned strategies using our Approx BR method for the FP asymmetric setting with two value priors: U0, 0.5) and 00, 1] (i.e. the No.5 setting above) in Fig. 11. The bidding strategies learned via our method closely align with the BNE solutions, confirming convergence even in this asymmetric setting.
Strategies of the Weak/Strong Bidders
0.30
Bids
0.15
BNE: Weak Bidder
0.10
BNE: Strong Bidder
Learned Weak Bidder
Learned Strong Bidder
0.4
Values V;
Figure I1. Theoretical BNE and the learned strategies with our Approx BR method in the asymmetric 2-player FP auction, which shows convergence this asymmetric setting.
E.2. Approximate BR Gradient Algorithm
The approximate BR gradient method is detailed in Algorithm 1.
F.3. Codes & Hyper-Parameters
Since official repository for the SM method (Kohring et al., 2023) does not provide instructions for reproducing their experiments, have implemented the SM method independently. In the original SM paper, the ex-post utility is modified
(A)(b:/A)
u. SM bi, b-s) (v; SM)
Σ cxp(b,/))
where = = Pj. In our implementation, we use D. by for FP and pi SM = maxy by for simplicity. Note that this modification doesn't change the smoothness and ability approximate the original utility function of u$M. Our results align closely with the ones reported in the SM paper: The L2 error of our results is around 3e-3 and the SM paper's L2 is ranged in 4e-3~-5e-3 when evaluated at the FP/SP symmetric uniform setting with 2 players. While improving the L2 result, the training time per iteration when n in our implementation is 0.012~0.013 seconds, which is comparable to the time range of 0.009~0.011 seconds reported SM's paper.
25

---

Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response
Algorithm Stochastic Approximate BR Gradient Method
Input: Bidders [1....n}. distributions F, each bidder's strategy: Peten learning rate a, parameter y, total steps
2: for = 0 to 7 do
3: for 1 to do
4: Sample K values: of ~ Fi.j = 1,..., K and corresponding bids b/ Bog(vg)
5: Estimate the gradients of u² via Eq. (11) and Eq. (15)
6:
if T2 /0b3 < O and O /bb; x 0 then
7:
Calculate the approximate best response via second-order gradient: br3 = 1/.
1800
-1
au ab.
8: else
9: Calculate the approximate best response via first-order gradient: br, = by + 2b.
end if
Update strategy:
0,+1
0:
1 K
BBg (u²) -br,) Vo, So.
12: end for
13:
end for
14:
Return: Learned bidding strategies: 3ge=T
For the estimation of pdf in the ex-interim utility's gradient (Eq. (11)), we utilize the kernel density estimation (KDE) approach with a Gaussian kernel:
N
m
fm. (x)
K
hN
j=1
where the mj.j j = 1,..., N are samples market prices, and (-)) the standard normal density function. The bandwidth in KDE is hyperparameter that controls the approximation quality. For comparison, the SM gradient estimation uses a soft-max approximation for the winning indicator in the ex-post utility function:
exp(b,/A)
[[bidder i wins) & E exp(b,/A)
where the À is also hyperparameter controlling the approximation quality. For the choices of these two parameters, we perform grid search in the main experiment (Tab. 2) and use tuned values for the rest experiments.
As for other asymmetric SP auction, where we increased the learning rate to 0.2 for better results. Since all experiments considered in this work are under the independent private value (IPV) setting, this allows us to individually sample the v; and u_, values. For all experiments, we sample 256 values for e; and 10,000 value samples for v- Since the value prior mainly uniform, we use 10,000 equally divided value samples for L2 evaluation to avoid random noise.
during the training stages, set the learning rate to 0.05 for all experiments except for the
Regarding the conditions for applying the second-order approximation in the approximate BR gradient method, we use the following criteria: 1. the 2nd-order approximation is not applied during the first 200 steps of training; 2. it's only enabled if uu /b; < -le-8 and |0,/ < 0.01 by default. These conditions ensure that the second-order approximation is used in the vicinity of local optimum. The parameter in first-order approximate best response is set to 1. Our code is open-sourced at: https: / github.. com wow//eeeseeeeeecce Heee//essee 7 Approx- BR- RR-aadd
26


Reviews:
[{"review_id": "Yh2J0MWv2m", "reviewer": "Reviewer_QBEq", "summary": "This paper introduces the Approximate Best Response Gradient method to efficiently learn Bayesian Nash Equilibrium (BNE) in auction games. It addresses the challenges of gradient computation and slow convergence in existing methods by using an analytic gradient solution and a novel Best Response Distance objective. The method achieves a local convergence rate independent of the number of bidders and demonstrates improved learning efficiency across several auction scenarios.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## General Settings with Unknown BNEs\n\nThank you for your valuable feedback.\n\nIndeed, the experimental evaluation in our paper primarily focuses on auctions with known BNEs. This choice was made deliberately to **allow for a clear and precise assessment of the learned strategies** by comparing them against analytically derived solutions. Specifically, it enables us to quantify the error of the learned strategies $\\beta_{\\theta_i}$ using the $l2$-distances to the analytic solution $\\beta_i^*$.\n\nHowever, we would like to emphasize that **this evaluation choice does not imply that our method cannot generalize to settings with unknown BNEs**. \nTo illustrate, let's consider asymmetric first-price auctions with $n>2$ bidders, which generally lack closed-form solutions.\nWe can reuse the setting of Figure 3 by eplacing the second price with first price, where bidders are equally divided into 2 types: the strong bidders with $U[0,1]$ and the weak bidders with $U[0,0.5]$.\n\nIn the context of $n=10$, we conducted experiments to plot the learned strategies of various methods across different random initializations. **The detailed results are available in this [anonymous link](https://anonymous.4open.science/r/Figures-1718/plot_strategies.md)**.\n\nAs shown in the figures, **the learned strategies of existing baselines (i.e., SM and UG) exhibit a classical slow-convergeing pattern**: the stratgies place positive bids $b_i > 0$ even as $v_i\\to0$.\nWhile exact BNE solutions are unknown in these cases, we can infer that this bidding behavior **surely deviates from BNE**, as better utility could be achieved by bidding zero when $v_i=0$.\n\nConversely, strategies derived from **our Approximate Best Response gradient method do not exhibit this issue**. Furthermore, the learned strategy curves suggest that strong bidders with large values tend to bid more conservatively due to reduced competition, which **aligns with the characteristics of the simplified 2-bidder setting's BNE solution [1]**.\n\nWe hope these explanations and supplementary results alleviate your concerns regarding the significance of our work and illustrate its broader applicability.\n\n---\n**Reference**\n\n[1] Kaplan, T. R. and Zamir, S. Asymmetric first-price auctions with uniform distributions: analytic solutions to the general case. Economic Theory, 50(2):269–302, 2012.", "claims_and_evidence": "The non-convergence of best response dynamics is a well-known challenge for computing (Bayesian) Nash equilibrium in general games. Even when limited to auction games, the BNE of first price auction was unsolved for many decades. This work is making a valuable contribution in finding a response dynamics with certain convergence guarantees.", "methods_and_evaluation_criteria": "The evaluation of the proposed methods, however, seems a little bit limited. Only second price auctions and first price auctions are evaluated in the experiment section, while the BNEs are solved theoretically for both symmetric and asymmetric settings (except the risk-aversion case). It seems to me that the method should work for broader settings where the BNE is theoretically unknown. But the current experiment does not show any advantage of the proposed method in finding BNEs. Leaving me to doubt why this is an important problem.", "theoretical_claims": "I didn’t verify all the details, but the theoretical part looks correct to me.", "experimental_designs_or_analyses": "See methods and evaluation criteria above.", "relation_to_broader_scientific_literature": "It might be relevant to finding BNE for more general cases.", "essential_references_not_discussed": "I don’t know any.", "other_strengths_and_weaknesses": "See Claims and Evidence above.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "No further questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uvVFpHHCtw", "reviewer": "Reviewer_7Vtz", "summary": "This paper presents the Approximate Best Response Gradient method for learning Bayesian Nash Equilibrium (BNE) in auction games. Auction plays a crucial role in many modern trading environments, including online advertising and public resource allocation, but computing BNE is computationally hard. Existing methods face challenges in gradient computation and optimization, especially in large-scale auctions.\n\nThis paper aims to address these challenges. First, they introduce an analytic solution for utility gradient estimation, avoiding the biased utility problem in existing methods. Second, they propose the Best Response Distance objective. By optimizing this objective, the proposed method achieves a local convergence rate of $O(\\log (1/d))$, while the traditional method has a rate of $O(n^2\\log (1/d))$. To reduce computational burdens, they further propose an approximate best response approach using local Taylor expansions.\n\nExtensive experiments across various auction scenarios, including different mechanisms, asymmetric value priors, risk-averse utilities, and alternative gradient estimation approaches, demonstrate that the proposed method significantly accelerates convergence and enhances learning efficiency.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Theoretical Assumptions\nThanks for highlighting this point!\n\nFirst, we acknowledge that achieving **convergence in learning algorithms under general game settings is a challenging problem**, which is further compounded by unknown BNE solutions for such settings.\n**The focus of this work is on accelerating convergence**, so we opted to establish our theoretical results within the simplified framework, **consistent with previous research** [1,2]. \n\nDespite the assumptions of asymmetric uniform prior and linear strategies for theoretical derivation, we've empirically verified the effectiveness of our method under **various auction scenarios with neural network strategies**, including different mechanisms, asymmetric value priors, risk-averse utilities, and alternative gradient estimation approaches, and demonstrated ***significantly accelerated convergence and enhanced learning efficiency*** as you've noted.\nWithin our rebuttal experiments, we also extend our evaluation to settings with unknown BNEs (please refer to our response to Reviewer QBEq), which further validates the acceleration capabilities of our method in general cases.\n\nMoreover, there are **two key theoretical advancements that have broader applicability** beyond the mentioned assumptions:\n1. **Gradient Estimation Technique**: We address the model bias issue in existing works through the analytic gradient based estimation. \nNotably, this method can be applied to general first-price (FP) and second-price (SP) auctions, **without relying on the mentioned uniform or symmetric assumptions**.\n2. **Best Response (BR) Distance Objective**: This objective provides an upper bound to the approximation factor of $\\epsilon$-BNE (Lemma 4.3), ensuring that optimizing this objective refines the BNE. \nImportantly, this result is **independent of uniform, symmetric, or specific FP/SP auction assumptions**, making it a viable objective for optimizing more general auction games. Furthermore, we have developed a practical approximation for the argmax operator in the BR-distance, proving its efficacy in the simplified auction setting, which could also inspire future research aimed at solving general auctions with similar approximations.\n\nWe hope these clarifications could highlight the significance and potential impact of our contributions.\n\n## Gradients & FP/SP\nFirst-price (FP) and second-price (SP) auctions are indeed prevalent in real-world applications. For instance, **Google Ads** employs **FP auctions** for their online advertisement services, having transitioned from **SP auctions** [3]. \nWe focus on these auctions due to their wide applications like exsting works [1,4].\n\nWhile it's true that real-world implementations of FP/SP auctions can include additional configurations, **such as reserve prices (bid floors), our gradient estimation approach is adaptable to such scenarios**.\n\nWhen introducing a reserve price $r$, the ex-iterim utility is modified as:\n- FP: $\\bar u_i(v_i,b_i,\\beta_{-i}) = \\mathbb E_{v_{-i}}[(v_i - b_i)\\cdot \\mathbb I(b_i>\\max\\\\{\\beta_{-i}(v_{-i}),r\\\\})]$\n- SP: $\\bar u_i(v_i,b_i,\\beta_{-i}) = \\mathbb E_{v_{-i}}[(v_i - \\max\\\\{\\beta_{-i}(v_{-i}),r\\\\})\\cdot \\mathbb I(b_i>\\max\\\\{\\beta_{-i}(v_{-i}),r\\\\})]$\n\nTo estimate the gradients, we can **replace the original market price $m_{i} = \\max_{j\\neq i}b_j$ with a reserved version**: $m_{i}^r = \\max\\\\{m_i, r\\\\} = \\max\\\\{\\beta_{-i}(v_{-i}),r\\\\}$. \nWe can estimate the distribution of the reserved market price $m_i^r$ by sampling bids $b_{-i}$, and compute the pdf/cdf $f_{m_i^r}$ and $F_{m_i^r}$.\n**Then the gradient under reserve price can be estimated via Equation (11) by changing the distribution from $m_i$ to $m_i^r$**.\n\nThis flexibility in gradient computation highlights its ability to generalize to more complex auction settings beyond pure FP/SP setups.\n\n## Explaination on Eq. (10)\nThanks for your valuable feedback, we will add explaination on Eq.(10) in our revised version:\\\nIn Eq. (10), the gradient is computed as $-\\text{Pr(i wins)}\\cdot \\nabla_{\\theta_i}\\beta_{\\theta_i}(v_i)$. \nHere $\\text{Pr(i wins)}$ is the winning probability of bidder $i$, which remains positive unless $b_i = 0$.\nSince the gradient' coefficient $-\\text{Pr(i wins)} < 0$ unless $b_i=0$, **the gradient for the bidder's bid $b_i=\\beta_{\\theta_i}(v_i)$ is consistently negative, unless $b_i=0$**.\nSo the optimization procedure will continuouly reduce the bid $b_i$, **until reaching the stationary point $b_i=0$**.\nThis is why the incorrect MC gradient estimation results in the zero-bidding problem.\n\n## Hyperparameters\nWe simply set $\\gamma$ to 1 in our experiments (Line 1354).\n\n## References\n[1] Convergence analysis of no-regret bidding algorithms in repeated auctions\n\n[2] On the convergence of learning algorithms in bayesian auction games\n\n[3] https://blog.google/products/admanager/update-first-price-auctions-google-ad-manager/\n\n[4] Enabling first-order gradient-based learning for equilibrium computation in markets", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes. No issues have been found so far.", "experimental_designs_or_analyses": "Yes. No issues have been found so far.", "relation_to_broader_scientific_literature": "This paper contributes to the BNE computation literature with a faster method. The result could be very useful for online advertising. However, since this paper focuses too much on first-price and second-price auctions only, it may lack of broader impact.", "essential_references_not_discussed": "No, to my knowledge.", "other_strengths_and_weaknesses": "Strengths\n1. The analytic gradient solution provides a more accurate way to estimate gradients compared to existing methods, which suffer from biased utility functions. This allows for more reliable learning of BNE strategies.\n2. The new optimization objective leads to a significantly faster local convergence rate.\n3. The paper provides a comprehensive theoretical analysis of the convergence rates of different methods.\n4. The extensive experiments on different auction scenarios validate the superiority of the proposed method in terms of convergence speed and accuracy.\n\nWeaknesses\n1. The theoretical framework is mainly based on symmetric auctions with a uniform prior and a shared linear bidding strategy. It may not be directly applicable to more complex auction types and bidding strategies.\n2. The closed-form solution for gradient estimation cannot generalize to other auction settings easily. Nowadays, most real-world online advertising scenarios do not use pure first-price or second-price auctions.\n3. The lack of clear expression around Equation (10). The text fails to explicitly convey the concept of exploring the consequences of incorrect gradient calculation, which could potentially confuse readers. The sentence \"the key issue...\" is hard to parse.", "other_comments_or_suggestions": "No.", "questions_for_authors": "How to determine a good \\gamma in Equation (16)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jfiYrv7G2A", "reviewer": "Reviewer_Be25", "summary": "This paper investigates the problem of learning approximate ex-ante BNE in auction games under a publicly known prior distribution of bidder values. It proposes three new algorithms:\n\n1. **Utility Grad**, which computes the gradient of bidders' utilities analytically using the CDF and PDF of the value distribution. However, as the authors point out, this method suffers from a low convergence rate that depends on the number of bidders.  \n2. **BR Gradient**, which optimizes the distance between bidders' current strategies and their best responses. Unlike Utility Grad, its convergence rate is independent of the number of bidders.  \n3. **Approximate BR Gradient**, which builds on BR Gradient by using a locally approximated best response.  \n\nTheoretical convergence rate analysis is conducted under the linear bidding assumption (Assumption 3.1). Empirically, the authors evaluate Utility Grad and Approximate BR Gradient when the bidding function is implemented using neural networks.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## More Settings with Unknown BNE\nWe acknowledge that the experimental evaluation in our paper primarily focuses on auctions with known BNEs. This choice was made deliberately to allow for a clear and precise assessment of the learned strategies by comparing them against analytically derived solutions. Specifically, it enables us to quantify the error of the learned strategies $\\beta_{\\theta_i}$ using the $l2$-distances to the analytic solution $\\beta_i^*$.\n\nTo evalute our method in more complex settings without known BNEs, let's consider asymmetric first-price auctions with $n>2$ bidders, which generally lack closed-form solutions.\nWe can reuse the setting of Figure 3 by eplacing the second price with first price, where bidders are equally divided into 2 types: the strong bidders with $U[0,1]$ and the weak bidders with $U[0,0.5]$.\n\nIn the context of $n=10$, we conducted experiments to plot the learned strategies of various methods across different random initializations. The detailed **results are available in this [anonymous link](https://anonymous.4open.science/r/Figures-1718/plot_strategies.md)**.\n\nAs shown in the figures, **the learned strategies of existing baselines (i.e., SM and UG) exhibit a classical slow-convergeing pattern**: the stratgies place positive bids $b_i > 0$ even as $v_i\\to0$.\nWhile exact BNE solutions are unknown in these cases, we can infer that this bidding behavior **surely deviates from BNE**, as better utility could be achieved by bidding zero when $v_i=0$.\n\nConversely, strategies derived from **our Approximate Best Response gradient method do not exhibit this issue**. Furthermore, the learned strategy curves suggest that strong bidders with large values tend to bid more conservatively due to reduced competition, which **aligns with the characteristics of 2-bidder setting's BNE solution [1]**.\n\nThis result verifies the effectiveness in accelerating convergence of our method under more complex settings.\n\n## Known Prior Assumption\nIn fact, the referenced paper [2] also assumes the distribution to be common knowledge (Page 5, line 5: *\"$f$ is assumed to be common knowledge\"*).\nThe assumption is basically a setting for auction game rules so that the bidders know how the values are sampled.\n\nIn our method, as demonstrated in Algorithm 1 (Appendix D.2), the optimization process begins with each bidder independently sampling their own values, followed by gradient updates. \nDuring this procedure, **our algorithm does not explicitly access the distribution**. \nInstead, **it leverages sampled values to drive game optimization**, which is consistent with most existing methodologies.\n\n## Sampling & Convergence Rates\nIn this paper, we mainly focus on the **optimization convergence rates**, which means we are interested in how many update steps are required by different algorithms to achieve a similar target approximation level.\n\nAs for the sampling complexity, the sampling process is a fundamental part of **both our gradient estimation, and and the existing ES or SM estimation methods**.\nImportantly, in our experiments, we ensured that all algorithms had access to **the same amount of data samples** for a fair comparison. \nThe results, as presented in Table 2, indicate that **the wall-clock time for our gradient estimation is significantly less than that of SM-based estimations**. \nThis efficiency gain is attributed to our analytic gradient computation, which alleviates the computational burden during backpropagation.\n\nThus, while sampling is an intrinsic requirement for all compared methodologies, our approach still demonstrates superior efficiency in wall-clock time without compromising the quality of gradient estimations.\n\nWe hope this clarification could addresses your concerns regarding the convergence rate and sampling impact.\n\n\n## Convergence to Local BNE\nThe Approximate BR (ABR) Gradient method **can indeed converge to the local approximate BNE**:\n\nAs discussed in lines 300-310, the ABR method simplifies to the Utility Gradient (UG) method when employing the first-order approximation, with the second-order approximation only activated in the vicinity of the BNE.\nTherefore, the **ABR method shares the same convergence ability of the UG method when analyzing if it can converge to a local approximate BNE**.\n\nAs established in **Proposition 3.2, the UG method can indeed converge to the BNE** under Assumption 3.1, substantiating the convergence capability of the ABR method as well.\n\nWe will include this explanation in our revised version to ensure clarity.\nThank you for emphasizing this issue!\n\n---\n**Reference**\n\n[1] Kaplan, T. R. and Zamir, S. Asymmetric first-price auctions with uniform distributions: analytic solutions to the general case. Economic Theory, 50(2):269–302, 2012.\n\n[2] Bichler, M., et. al. Learning equilibria in symmetric auction games using artificial neural networks. Nature machine intelligence, 3(8):687–695, 2021.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "The proofs are OK to me.", "experimental_designs_or_analyses": "In the experiment, the auction settings are restricted to cases with simple analytical solutions for BNE. More complex settings can be explored.", "relation_to_broader_scientific_literature": "The paper proposes a learning method to compute BNE of auction games, which is PPAD-hard.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "### Strengths:\n1. The authors provide a detailed discussion of existing gradient methods for learning BNE in games.  \n2. None of the proposed methods introduce bias to the utility function.  \n3. The convergence rates of both BR Gradient and Approximate BR Gradient are independent of the number of bidders.  \n\n### Weaknesses:\n1. The authors assume that the prior distribution is common knowledge, which is a stronger assumption than in previous works (e.g., Bichler et al., 2021), where only sampled data is available. A known prior distribution simplifies algorithm design.  \n2. While the CDF and PDF can be approximated from data, doing so requires additional samples. The paper does not discuss whether this approximation affects the convergence rate of the methods.  \n3. The theoretical results rely on Assumption 3.1, and the analysis of convergence to a locally approximate BNE is missing. This is particularly important for Approximate BR Gradient, as the algorithm is based on finding a locally approximate best response.", "other_comments_or_suggestions": "See the discussions above.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "D049E7Szqh", "reviewer": "Reviewer_RMDC", "summary": "This paper studies the problem of learning Bayesian Nash Equilibrium (BNE) in auction games as the number of bidders grows. The authors propose the Approximate Best Response Gradient method, including an analytic solution for gradient estimation to avoid the biased utility, and the Best Response Distance objective to address the slow convergence issue. A local convergence rate is proved to be independent of the number of bidders in symmetric auctions. Experiments across various auction formats, including different mechanisms, asymmetric value priors, and risk-averse utilities, show that the proposed method significantly accelerates convergence and enhances learning efficiency.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> There have been several works proposing gradient-based approach to solve NE of some classes of games, and the proposed metric, Best Response Distance, is commonly used. Nevertheless, the gradient estimation is novel for auction games.\n\nThank you for your positive feedback and for highlighting the innovative aspects of our work!\n\nRegarding the Best Response (BR) Distance metric, we would like to kindly point out that it differs from several existing metrics due to its focus on measuring **strategy-level** distance:\n$$\n\\\\|\\beta_i(v_i) - \\arg\\max_b\\bar u_i(v_i,b,\\beta_{-i})\\\\|^2,\n$$\nwhere $\\beta_i(\\cdot)$ is the bidding strategy.\n\nThis approach contrasts with other prevalent metrics, such as exploitability or the Nikado-Isoda function and its variants [1], which typically measure **utility-level** distance in a form like:\n$$\n\\max_b \\bar u_i(v_i,b,\\beta_{-i}) - \\bar u_i(v_i,\\beta_i(v_i),\\beta_{-i}),\n$$\nwhere $\\bar u_i$ is the bidder's ex-interim utility.\n\nThe strategy-level distance was chosen to mitigate slow local convergence issues associated with the **ill-conditioned utility function**, as detailed in Lemma 4.1. \nAnd we have proved that **BR-distance serves as an upper bound of the approximation factor $\\epsilon$ in $\\epsilon$-BNE** in Lemma 4.3, so optimizing it leads to a closer approximation to the BNE.\n\nHowever, if there are existing works that adopt a similar strategic approach akin to the BR-distance, we would be delighted to incorporate them into our references, as your suggestions are invaluable in ensuring comprehensive coverage of related research.\n\nThank you again for recognizing the contributions of our work and for your valuable insights.\n\n---\n**References**\n\n[1] Gemp, I., et. al. Approximating nash equilibria in normal-form games via stochastic op- timization. ICLR 2024", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense for the problem.", "theoretical_claims": "As far as I checked, the proofs are correct.", "experimental_designs_or_analyses": "The experimental designs and analysis sound.", "relation_to_broader_scientific_literature": "There have been several works proposing gradient-based approach to solve NE of some classes of games, and the proposed metric, Best Response Distance, is commonly used. Nevertheless, the gradient estimation is novel for auction games.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Overall this paper saw decent support from the reviewers (three weak rejects), I also think that the rebuttals clarified most of the reviewers' questions and concerns and augmented the papers contribution by presenting additional experiments. Given the interest in this topic in EC/ICML/NeurIPS recently, I think we can consider this paper for acceptance. If accepted the authors should address the reviewers' comments and incorporate the additional experiments from the discussion phase. There is also a very recent SODA 2025 paper by Ahunbay and Bichler, which the authors may want to discuss.
Decision: Accept (poster)