Simultaneous Gradient Learning in First-Price Auctions

Introduction

Learning in multi-agent systems fundamentally differs from single-agent learning: strategy updates are shaped by the adaptation of other agents. As a result, learning dynamics in games need not converge, may cycle, exhibit chaotic behavior, or converge to different outcomes depending on initial conditions. Understanding the subset of games where commonly used learning algorithms converge

Preprint. to meaningful equilibrium predictions remains a central challenge at the intersection of machine learning, optimization, and game theory.

Somewhat surprisingly, recent papers observe convergence close to the Bayes-Nash equilibria (BNE) in economically relevant Bayesian games [7, 6]. These methods build on gradient learning, and we will focus on its simplest variant, projected gradient ascent, in this paper.

We will deliberately restrict our attention to first-price single-item auctions. This game is a canonical example used in large-scale applications such as display advertisements. However, despite the uniqueness of the BNE, the empirical convergence of gradient-based algorithms has not yet been fully theoretically justified. Here, we aim to provide an explanation for the convergence of projected gradient ascent in first-price auctions under increasingly finer discretizations. The BSCCE, however, is a broader concept and can be applied to all games with private information.

Gradient Dynamics in Games. Motivated by their algorithmic simplicity, recent work studies gradient-based learning dynamics in games [19, 21, 10]. While it is known that Nash equilibria are equilibria of the resulting dynamical system, strong assumptions, including strict monotonicity, are usually needed to guarantee uniqueness and the convergence of the dynamics to such an equilibrium in last-iterate, independent of initial conditions [20, 23]. Similarly, Lyapunov-function-based arguments can be used to show stability [18]. In general, the dynamics of a game may also cycle, prohibiting last-iterate convergence statements in general.

Dynamical systems offer a powerful toolset, but the analysis is game-specific and often requires significant effort to use (see, e.g., Bichler et al. [8]). In Bayesian games with private information, the picture is even less well understood: equilibrium strategies are functions that map types to actions, which further complicates the analysis. In particular, Bichler et al. [8, 9] have shown that the first-price auction satisfies neither the monotonicity nor the (weaker) Minty condition, which rules out many of the related convergence statements.

No-regret Learning and Bayesian (Coarse) Correlated Equilibria. As an alternative to dynamical systems, we draw on no-regret learning theory, shifting the focus from last-iterate to time-average convergence. Indeed, it is well known that no-regret algorithms converge to (Bayesian) coarse correlated equilibria (BCCE) [16]. Similarly, no-internal-/no-swap-regret algorithms converge to (Bayesian) correlated equilibria (BCE) [14]. However, the BCCE can be a large superset of the BNEs of a game, and this result says little about the convergence of no-regret algorithms to a BNE. Meanwhile, no-internal regret algorithms are much more complex, and BCEs may be too strict to capture the behavior of gradient learning algorithms.

In the context of auctions, Ahunbay & Bichler [1] recently showed that the set of BCCEs collapses to the unique BNE in all-pay auctions with continuous types, which proves convergence of no-regret algorithms to an approximate BNE in discretized versions of the auction. However, the authors show that this explanation is insufficient in first-price auctions: the BCCE set remains large for non-concave priors even under arbitrarily fine discretizations and can contain outcomes far from the competitive equilibrium. Thus, standard no-regret guarantees do not explain why gradient-based learners consistently converge close to the BNE in this setting.

Our research relates to the work by Bergemann et al. [5] which analyzes BCEs under varying levels of information provided to the bidders. They find a subset relation for the BCEs as information quality increases (modeled as "information structures"), meaning that as information quality increases, the BCE set shrinks. Slightly different from our setup, their model assumes that bidders do not observe their private valuations directly, but instead receive a signal chosen by the auctioneer.

Contributions. The large support of BCCE warrants a closer inspection of gradient algorithms in first-price auctions. The central contribution of this paper is to refine the equilibrium notion used to analyze gradient-based learning in Bayesian games. We introduce the Bayesian Semicoarse Correlated Equilibrium (BSCCE), which captures the outcomes of gradient dynamics more precisely than prior concepts. BSCCE is motivated by the observation that gradient-based algorithms can realize only a restricted class of deviations, namely, tangential, probability-preserving transformations of mixed strategies, which correspond to gradients of potential functions.

BSCCE lies between BCE and BCCE as it restricts (expands) the class of deviations relative to BCE (BCCE). Figure 1 illustrates the maximal support across equilibrium concepts in a first-price auction.

Formally, BSCCE extends the notion of Semicoarse Correlated Equilibrium (SCCE), originally developed for complete-information games [2], to Bayesian settings. However, this extension must be handled carefully, as the strategic normal form of a Bayesian game is exponential in the number of types. Thus, applying the SCCE to the strategic normal form is computationally infeasible. In contrast, our approach is based on the partial Bayesian approach [13], which allows a polynomial characterization of BSCCE in terms of the game size and thus makes BSCCE tractable in discretized games.

BSCCE is defined via linear incentive constraints against a class of deviations, restricted to affine, symmetric, probability-preserving deviations that capture the geometry of projected gradient ascent. This approach relates to the concept of $\Phi$-equilibria, as introduced by Greenwald & Jafari [15] and Lugosi & Stoltz [17]. Another related variant of $\Phi$-equilibria are linear correlated equilibria (LCE), for which Daskalakis et al. [12] provide a polynomial algorithm that has no-$\Phi$-regret in convex games. The deviations leading to LCEs include those considered in this paper. Therefore, LCEs are a stricter notion of equilibrium (LCE $\subseteq$ SCCE). We focus on (B)SCCE because of its relation to gradient learners, which has been established by Ahunbay, Mete (2025); Ahunbay & Bichler [2].

We apply BSCCEs to discrete first-price auctions with different priors. Our results show convergence of gradient-based algorithms in many first-price auctions as the discretization is refined. This includes auctions with non-concave priors where the BCCE set remains large (Ahunbay, Mete, 2025).

Taken together, these results justify the empirical success of gradient-based learning in discretized Bayesian games, selecting a smaller equilibrium set than standard no-regret theory predicts. A full theory for the convergence of gradient algorithms remains an open task, but our proposed concept provides important insights on the convergence of gradient-based learning algorithms.

The Model

We consider strategic interactions under incomplete information. We begin by defining the standard game-theoretic concepts for an incomplete information setting. Let $\Delta(\mathcal{H})$ denote the set of probability distributions over a measurable space $(\mathcal{H}, \mathcal{B}(\mathcal{H}))$, where $\mathcal{B}(\mathcal{H})$ is the Borel $\sigma$-algebra associated with the metric space $\mathcal{H}$.

When discussing distributions such as $\sigma(\theta, a)$, we denote the marginal distributions by omitting the marginalized variables. For example, $\sigma(a)$ denotes the marginal distribution over actions. We denote conditional distributions and expectations with vertical bars; for instance, $\sigma(a_{-i} \mid\theta_i, a_i)$ is the conditional probability of the opponents’ actions $a_{-i}$ given player $i$’s action $a_i$ and type $\theta_i$.

A pure strategy for player $i$ is a mapping $s_i:\Theta_i \to\mathcal{A}_i$. A mixed strategy $x_i:\Theta_i \to\Delta(\mathcal{A}_i)$ maps types to distributions over actions.

The expected utility of player $i$ given a strategy profile $x$ and type $\theta_i$ (interim utility) is $u_i(x_i,x_{-i}\mid\theta_i)$:

This definition can be extended to infinite type- and action spaces by replacing the corresponding sums with integrals. Observe that the interim utility is linear in $x_i$, the player’s own action distribution.

There are multiple approaches to define Bayesian correlated equilibria (BCEs) [13]. We will rely on the "partial Bayesian approach", which assumes that all players observe their types and a recommendation for a corresponding action. In contrast to the "strategic form" and "agentic form" approaches, recommendations are correlated on the level of individual actions and may depend on the realized types of all players. For this, we need the following concepts. Let $\sigma\in\Delta(\Theta\times\mathcal{A})$ denote a distribution over types and actions.

This condition ensures that a player’s recommendation does not reveal information about opponents.

Single-Item, First-Price Auctions. We focus on the standard symmetric Independent Private Values (IPV) model. The set of bidders is $\mathcal{N} = \{1,\ldots,n\}$. Each bidder $i$ draws a private valuation $\theta_i$ independently from a probability mass function (or density) $\pi$ with corresponding cumulative distribution function $F$ with support on $[0,\bar{\theta}]$. W.l.o.g. we can set $\bar{\theta}=1$. Bidders submit bids $a_i \in\mathcal{A}_i = [0,1]$. The restriction $\mathcal{A}_i = [0,1]$ is w.l.o.g. as rational bidders never overbid.

The auction is defined by an allocation rule $q_i(a)$. The utility of bidder $i$ with valuation $\theta_i$ is:

We assume a standard highest-wins allocation rule with uniform tie-breaking:

In the first-price auction, the winner pays their bid.

Under regularity assumptions [11], the first-price auction has a unique BNE $\beta^{\mathrm{FP}}$ in the symmetric IPV model, which is given by the expectation of the second-highest valuation conditioned on the bidder having the highest valuation (i.e., the highest of the others):

where $Y_1$ is the highest order statistic of the $n-1$ other bidders’ valuations. For example, if valuations are uniformly distributed ($\theta_i \sim U[0,1]$), this simplifies $\beta_i^{\mathrm{FP}}(\theta_i) = \frac{n-1}{n}\theta_i$.

Equilibria in the Discretized First-Price Auction. To find equilibria in more general settings, where theoretical predictions are unavailable, learning algorithms discretize the game. However, this discretization alters the game already in the symmetric IPV model and breaks the existence of the unique pure symmetric BNE [22]. Consequently, learning algorithms are no longer expected to converge to a singleton but rather to a set of mixed strategies. Figure 1 illustrates the set of possible BNEs and BCEs for an example. We are interested in how the limit set of the learning dynamics, in particular the projected gradient dynamics, changes as the discretization becomes finer.

Bayesian Semicoarse Correlated Equilibrium

Most learning dynamics are not guaranteed to converge to BNEs but only to relaxed notions thereof. On the one hand, BCEs are a relatively tight superset of BNEs, but they lack convergence guarantees for gradient-type algorithms. On the other hand, the set of BCCEs is too large in the case of First Price auctions to derive meaningful convergence statements [1]. Therefore, we need to move on to another, relaxed notion of equilibrium. We propose the Bayesian Semicoarse Correlated Equilibrium (BSCCE) for this purpose, which lies between BCE and BCCE.

Semicoarse Correlated Equilibrium (SCCE)

SCCEs were introduced by Ahunbay & Bichler [2] to capture the convergence set of gradient-based learners in complete-information games while maintaining computational feasibility. It can be understood as a specific instance of $\Phi$-equilibria [15, 17] that includes CEs but is (sometimes) strictly smaller than the CCE polytope. Ahunbay & Bichler [2] already applied this solution concept to complete-information versions of Bertrand competition and first-price auctions.

Let us recall the definition of SCCEs and provide an intuitive explanation. Gradient-based dynamics satisfy no-regret guarantees with respect to a restricted class of deviations that correspond to gradient fields of potential functions (Ahunbay, Mete, 2025). By restricting to gradients of quadratic functions, we obtain a solution concept that is representable as an LP and thus computationally tractable, and it is a superset of the outcomes of gradient dynamics.

A probability distribution $\sigma\in\Delta(\mathcal{A})$ is an SCCE if it is stable against infinitesimal deviations in the direction $Q_i x_i + q_i$ defined by a pair $(Q_i,q_i)$ for each player $i$, where

• $Q_i \in\mathbb{R}^{|A_i|\times|A_i|}$ is a symmetric matrix defining probability flow between actions, and

• $q_i \in\mathbb{R}^{|A_i|}$ is a vector providing an offset.

Since the utility function $u_i$ is linear in player $i$’s action, restricting attention to infinitesimally small deviations entails no loss of generality, as any local deviation can be extended globally by linearity.

These deviations capture the form of update directions that arise under gradient steps which are projected back into the simplex. Furthermore, to avoid projections in the analysis and to tailor the solution concept to mixed extensions of normal-form games, Ahunbay & Bichler [2] restrict the $(Q_i,q_i)$ according to three conditions:

1. Tangency: $\sum_{a_i'\in A_i}(Q_i(a_i',a_i)+q_i(a_i'))=0$ for all $a_i$. This ensures probability is merely reallocated between actions, not created or destroyed.

2. Non-negativity: $Q_i(a_i',a_i)+q_i(a_i')\ge0$ for all $a_i'\ne a_i$. This condition ensures that, at pure strategies, admissible deviation directions lie within the tangent cone of the probability simplex, so that infinitesimal deviations preserve feasibility.

3. Symmetry: $Q_i=Q_i^\top$. This ensures that deviations are gradient fields of quadratic functions. Projected gradient ascent can only move along gradients of scalar functions. Without symmetry, the deviation direction of $Q_i x_i+q_i$ can exhibit rotational flow, which is impossible for gradient fields.

The incentive constraints are infinitesimal deviations in the direction $Q_i x_i+q_i$ evaluated for pure strategies (i.e., $x_i$ is a canonical basis vector). Thus, the pairs $(Q_i,q_i)$ define deviations $d_i(a_i',a_i)=Q_i(a_i',a_i)+q_i(a_i')$ on actions $a_i',a_i\in A_i$. We denote the set of admissible deviations, i.e., where $d_i$ satisfies the conditions above, by $D$.

In summary, we get the following definition of SCCEs.

Although there are uncountably many incentive compatibility constraints as the set of pairs $(Q_i,q_i)$ forms a polyhedral cone, this cone admits a finite representation via its extreme rays. This yields a finite set of constraints, as detailed in Section A. Moreover, the resulting linear program has size polynomial in the cardinalities of the type and action spaces and thus is computationally tractable.

Extension to Bayesian Games

For the extension of SCCEs to Bayesian games, we adopt the partial Bayesian framework in line with the above definition of BCEs. This choice is motivated by the structure of learning dynamics in auction games: gradient-based algorithms operate on type-contingent mixed actions $x_i(\cdot\mid\theta_i)$ and update them using local, interim utility gradients. They do not optimize over or maintain distributions over complete strategy functions $s_i:\Theta_i\to A_i$. The partial Bayesian formulation mirrors this behavior by defining equilibrium objects directly as joint distributions over types and actions.

A Bayesian Semicoarse Correlated Equilibrium (BSCCE) is therefore defined as a joint distribution $\sigma\in\Delta(\Theta\times A)$. The definition inherits the structural conditions of Bayesian correlated equilibrium (Definition 2.5), such as prior consistency and conditional independence, but replaces the standard incentive constraints with semicoarse incentive constraints tailored to gradient-based deviations.

We build on the SCCE framework and allow for admissible deviations that are type-specific: for each player $i$ and type $\theta_i\in\Theta_i$, deviations are generated by a pair $(Q_i^{\theta_i},q_i^{\theta_i})$ defining a tangential, probability-preserving transformation of the action simplex. For notational simplicity, we denote such deviations by $d_i^{\theta_i}(a_i',a_i)=Q_i^{\theta_i}(a_i',a_i)+q_i^{\theta_i}(a_i')$.

2. Conditional independence.

3. Semicoarse incentive compatibility. No player can gain by admissible deviations. Formally, we require that, for every player $i$, every type $\theta_i \in\Theta_i$, and every deviation $d^{\theta_i} \in D$

The conditioning of expectations affects the player’s beliefs about other players and their actions.

The BSCCE constraints are all linear. We will add a linear objective that measures the distance to a given distribution (the BNE strategy) and obtain a linear program, which we provide in Section A.

Relation to other equilibrium concepts. Equilibrium notions can be ordered by the class of admissible deviations they allow. Allowing a richer class of deviations induces more incentive constraints and therefore yields a smaller equilibrium set. The Bayes-Nash equilibrium (BNE) is the most restrictive notion, as it allows all unilateral deviations at the level of complete strategies and requires that the actions be sampled independently for each player. Bayesian correlated equilibrium (BCE) relaxes this requirement by allowing players to condition deviations on correlated action recommendations, while still enforcing obedience to all such deviations. BSCCE further relaxes the equilibrium notion by restricting attention to a proper subset of deviations. Bayesian coarse correlated equilibrium (BCCE) imposes the weakest incentive constraints by allowing only unconditional deviations, and therefore yields the largest equilibrium set. Accordingly, the equilibrium concepts satisfy the inclusion chain

Bayesian Gradient Ascent Learners

To relate BSCCE to learning dynamics, we study gradient-based algorithms in discretized Bayesian games. Our goal is not to model all possible feedback mechanisms, but to identify a class of learning dynamics whose limiting behavior can be characterized by semicoarse incentive constraints.

Expected-Utility Formulation. A key modeling choice is how learning agents process private information. Rather than modeling stochastic type realizations and noisy gradient feedback, we adopt an expected-utility formulation that treats the Bayesian game as a deterministic, high-dimensional game over type-contingent mixed actions. Specifically, each player $i$ maintains a mixed action $x_i(\cdot\mid\theta_i)\in\Delta(A_i)$ for every type $\theta_i\in\Theta_i$. The player’s decision variable is therefore the vector

and payoffs are given by the ex-ante expected utility

Under this formulation, the Bayesian game can be viewed as a complete-information normal-form game with a structured action space $X_i$. The utility functions are smooth and multilinear in the mixed actions, and gradients with respect to $x_i(\cdot\mid\theta_i)$ are well defined.

Bayesian Projected Gradient Ascent. We consider players who apply projected gradient ascent to maximize their ex-ante expected utility. Given a step size sequence $(\eta_t)_{t\ge1}$, the update rule for player $i$ is

where $\Pi_{X_i}$ denotes Euclidean projection. Because the feasible set $X_i$ is a Cartesian product of simplices, the projection decomposes across types. We assume that step-sizes satisfy $\eta_t=\omega(1/t)$ and $\sum_{t=1}^{T}\eta_t=o(T)$.²

This deterministic gradient dynamic avoids stochasticity from sampled type realizations and allows us to directly apply no-regret and stability arguments developed for gradient-based learning in complete-information games.

Connection to Semicoarse Equilibria. The expected-utility view of our Bayesian game allows us to extend the convergence result of Ahunbay & Bichler [2], which shows that projected gradient ascent converges to the set of SCCEs in time-average under complete information, to our incomplete-information setting.

We provide a proof in Section B. This establishes BSCCE as a natural equilibrium concept for characterizing the long-run behavior of gradient-based learners in discretized Bayesian games.

Stochastic learning and sampled feedback. The BPGA dynamics studied above should be understood as an analytical proxy for the stochastic learning algorithms commonly used in practice. In typical auction-learning implementations, agents observe batched realized types and payoffs and update their mixed strategies using stochastic gradient estimates rather than exact interim gradients. Under standard assumptions, such stochastic updates track the corresponding expected-utility gradient dynamics in the limit (Benveniste et al. [4]). This suggests that BSCCE remains the correct limiting object for stochastic gradient dynamics. However, we do not claim that the stochastic case is fully resolved here. A full stochastic-gradient analysis of auction games is an important next step, but it is beyond the scope of this paper.

Convergence Analysis

In this section, we characterize the size of the Equilibrium sets for first-price auctions with two players in the IPV model. Since we study discretized auctions which have an ordered action space, we are not only interested in how much probability can be shifted between two feasible equilibria, but also how far this probability can be shifted.

Metrics. Given a possibly mixed strategy $\sigma\in\Delta(\Theta\times\mathcal{A})$ and a pure strategy $\beta^* : \Theta\to\mathcal{A}$, their squared Wasserstein-2 distance is

In the following, we will simply refer to this metric as the Wasserstein distance. We consider the squared Wasserstein-2 distance between the buyers’ marginal bid distributions and the equilibrium as a suitable objective for our analysis: This metric captures deviations in the probability mass assigned to different type–action pairs and weighs these based on the distance to the canonical equilibrium $\beta^*$. Furthermore, it provides a natural upper bound on the size of equilibrium polytopes $(\mathcal{P})$:

As shown by Ahunbay & Bichler [1], the BCCE in first-price auctions is unique whenever the prior cumulative distribution function (CDF) is strictly concave. As BSCCE $\subseteq$ BCCE, their contraction result immediately carries over to BSCCE. Thus, the theoretically interesting case for our analysis is when the conditions guaranteeing BCCE contraction are violated.

Their numerical experiments indicate that even under a uniform prior, which does not satisfy strict concavity, the BCCE that maximizes Wasserstein distance to the canonical equilibrium approaches that equilibrium as the discretization is refined. At the same time, they provide counterexamples in which this distance increases when the prior is no longer concave. In particular, such behavior arises for Beta$(\alpha,1)$ priors, whose CDFs are strictly convex for $\alpha> 1$.

These findings motivate a closer investigation of whether BSCCE provides a sharper prediction in precisely these regimes. Specifically, we examine whether the Wasserstein distance between BSCCEs and the canonical equilibrium decreases as the discretization becomes finer even when the prior CDF is convex and BCCE need not concentrate.

Discretization. We discretize the type and action space uniformly as $\{0,1/\xi,\ldots,1\}$, with a size of $\xi+1$. The probability of a discrete type $\theta_i=\frac{k}{\xi}$ is $F\left(\frac{k+1}{\xi+1}\right)-F\left(\frac{k}{\xi+1}\right)$. For a Beta$(\alpha,1)$ prior, the resulting type probabilities become increasingly imbalanced as $\alpha$ grows. In particular, the prior mass concentrates near the highest valuation, leading to $\pi_i(1)\gg\pi_i(0)$ for large $\alpha$. Similarly, the probability mass concentrates around $\frac{1}{2}$ for a Beta$(\alpha,\alpha)$ prior. This imbalance induces numerical instabilities in equilibrium computation and makes experiments for larger discretizations challenging.

Results. As the discretization refines, the BSCCE polytope contracts. In particular, its diameter, bounded by the maximal Wasserstein distance to the canonical equilibrium, converges to zero, indicating that all BSCCEs approach the unique continuous BNE. This contraction implies that any equilibrium selected by gradient-based learning dynamics in discretized auctions must lie close to the canonical equilibrium, providing strong numerical evidence for convergence in the continuous limit. The decrease in squared Wasserstein distance is illustrated in Figure 2 for a Beta$(2,1)$ prior. In this case, the Wasserstein distance decreases roughly as $\frac{1}{10\xi}$.

Figure 1 from our introduction visualizes the maximal conditional probability assigned to each type–action pair under different solution concepts for this prior. Specifically, each tile $(\theta_i,a_i)$ displays $\max_{\sigma\in P}\sigma(a_i\mid\theta_i)$. The figures illustrate the inclusion relationship $BNE\subseteq BCE\subseteq BSCCE\subseteq BCCE$. While all solution concepts are centered around the canonical equilibrium $\beta_i^*(\theta_i)=\frac{2}{3}\theta_i$, both BSCCE and BCE are substantially more concentrated around $\beta_i^*$ than BCCE.

The speed of the concentration depends on the priors (see Section C). When the game is close to a complete-information game, or the CDF is too convex, the size of the BSCCE polytope shrinks slowly. We observe that the BSCCE is more robust to the non-concavity of the CDF than the BCCE, but for large values of $\alpha$ (where the convexity strengthens), it is not able to track the BCE convergence.

Complexity

An implementation of the general BSCCE linear program for a discretization of $1/\xi$ involves $O(\xi^4)$ variables and $O(\xi^3)$ constraints, with a relatively dense constraint matrix. Several model reductions are available when players are symmetric, and additional reductions apply to first-price auctions, where rational players never bid above their type. This allows us to reduce the number of non-zeros in the LP by approximately an order of magnitude. Even after these optimizations and despite the polynomial scaling, the LPs become challenging to solve for very fine discretizations.

For a discretization of $\xi=20$, the BSCCE LP contains approximately 45k variables, 8k constraints, one million non-zeros, and requires about 20 seconds to compute the Wasserstein-distance-maximizing BSCCE using the Gurobi Optimizer version 12.1. By comparison, without model reductions, the same instance requires 30 minutes. For $\xi=30$, the BSCCE LP grows to roughly 180k variables, 25k constraints, and 7 million non-zeros, with a solution time of about 11 minutes.

While we can ensure a theoretically well-behaved complexity bound, this does not always imply practical tractability. Due to the increasingly numerical instability and increasing computational burden, we did not pursue even finer discretizations. We still believe that our study here is informative, as it points towards a theoretically justified convergence of gradient-based algorithms.

Limitations

Our results have some limitations. First, while BSCCE is defined for general finite Bayesian games, our numerical analysis focuses on discretized symmetric first-price auctions. In particular, the contraction of BSCCE toward the continuous-game BNE outside regimes already covered by existing BCCE results is supported numerically rather than established theoretically. When existing results imply that BCCE contracts to the BNE, the inclusion BCE ⊆ BSCCE ⊆ BCCE immediately yields the same conclusion for BSCCE. Beyond these regimes, however, deriving conditions under which BSCCE contracts to the BNE remains an open theoretical question.

Second, our formal learning result concerns time averages of deterministic Bayesian projected gradient ascent using expected-utility gradients. It therefore does not establish convergence guarantees for stochastic gradient updates based on sampled auction outcomes. While stochastic-approximation arguments motivate a connection between these settings, a formal treatment of stochastic BPGA requires additional assumptions and is beyond the scope of this paper.

Third, our numerical evidence is necessarily limited by the computational cost of optimizing over the BSCCE polytope. This constrains the discretization sizes that can be studied. Moreover, uniform discretizations can generate grid-alignment effects because the continuous BNE may lie closer to the action grid for some grid sizes than for others. We therefore interpret individual finite-grid results with caution and focus on the behavior across increasingly fine discretizations.

Finally, the auction experiments considered here use symmetric priors. Extending the analysis to asymmetric priors is nontrivial because the corresponding equilibrium is asymmetric and generally does not admit the same closed-form benchmark. Similarly, although the definition of BSCCE and its connection to BPGA apply to finite Bayesian games more generally, whether BSCCE provides a comparably sharp equilibrium prediction in other Bayesian games remains an open empirical and theoretical question.

Conclusion

This paper revisits a recurring empirical observation in auction learning: gradient-based algorithms applied to discretized Bayesian auctions reliably converge to outcomes that are close to the unique Bayes–Nash equilibrium (BNE) of the underlying continuous game, even in settings where standard theoretical guarantees fail. While existing no-regret arguments based on Bayesian coarse correlated equilibrium (BCCE) explain convergence in all-pay auctions, they are insufficient for first-price auctions, where the BCCE set can remain large and include outcomes far from the BNE.

To address this gap, we introduced the Bayesian semicoarse correlated equilibrium (BSCCE), a refinement of BCCE that restricts admissible deviations to tangential, probability-preserving transformations consistent with projected gradient dynamics. This equilibrium concept admits a linear programming characterization that enables systematic numerical analysis. While the focus of this paper is first-price auctions with independent private values, the solution concept BSCCE is defined for all Bayesian games.

Our main finding is that, in symmetric first-price auctions, the BSCCE set contracts as the discretization is refined. Across a range of priors, including cases where BCCE fails to concentrate, the diameter of the BSCCE polytope shrinks to zero, indicating convergence to the unique continuous BNE. This shrinkage property provides a stability certificate for gradient-based learning dynamics. However, shrinkage is limited when the priors are degenerate, i.e., when the game is close to a complete-information game, or when the CDF is highly convex. While the proposed equilibrium concept, BSCCE, sharpens predictions about the outcome of gradient dynamics, it remains open whether there is an even smaller, tractable solution concept that captures that outcome better.

Overall, our results suggest that equilibrium concepts tailored to the structure of learning dynamics can offer sharper and more robust predictions than generic no-regret notions in Bayesian games. The BSCCE framework provides a principled bridge between gradient-based optimization and equilibrium analysis, and it is applicable beyond auctions to other multi-agent learning problems with private information and high-dimensional strategy spaces.

Acknowledgments and Disclosure of Funding

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon Europe research and innovation programme (grant agreement No 101198689).

This project was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - GRK 2201/2 - Project Number 277991500.

The work of Mete Şeref Ahunbay was funded by a Walter Benjamin Fellowship from the German Research Foundation (Deutsche Forschungsgemeinschaft), project nr. 558988238.

This project has received funding from the French National Research Agency (ANR) through the PEPR IA FOUNDRY project (ANR-23-PEIA-0003).

LP Formulations

BSCCE LP

We state BSCCEs as a linear program over the joint distribution $\sigma\in\Delta(\Theta\times A)$ where the constraints enforce the conditions in Definition 3.2 (prior consistency, conditional independence, incentive compatibility). Note that $\pi(\theta)$ represents the probability density of the type distribution.

For the conditional independence, we write it explicitly in terms of the joint distribution and already assume prior consistency

Besides Prior Consistency

it must hold for each player $i \in\mathcal{N}$ and all corresponding types $\theta_i \in\Theta_i$ that

(Conditional Independence)

(Semicoarse incentive compatibility)

The suitable BSCCE deviations $d_i(\theta_i,a'_i,a_i)=Q_i(\theta_i,a'_i,a_i)+q_i(\theta_i,a'_i)\in D_i$ are defined as follows: for all players $i\in\mathcal{N}$ and for all corresponding types $\theta_i\in\Theta_i$ it must hold

(probability preservation, $\mu_i(\theta_i,a_i)$)

(non-negativity, $\gamma_i(a_i,a'_i)$)

(symmetry, $\rho_i(a_i,a'_i)$)

Tractable BSCCE LP

As there are infinitely many ’suitable’ deviations, the primal before is numerically unsolvable. We use the approach from Theorem 3.4 in Ahunbay & Bichler [2] to get a tractable version. The idea is to consider the ’worst-case’ deviations, which correspond to the extreme rays of the deviation polyhedral cone, and incorporate them into the objective. This results in an inner and outer problem. Then we consider the dual of the inner maximization problem, with the dual variables $\mu$, $\rho$ and $\gamma\geq0$ as introduced before. The dual is a feasibility problem as the right-hand sides are $0$, and the constraints can be incorporated into the outer problem. As $\mu_i(\theta_i,a_i)$ will only appear in one equality constraint, it can be eliminated from the resulting LP by fixing its value suitably. The Semicoarse incentive compatibility constraint is then replaced by the following two types of tractable constraints (for each player and type)

where

Note that if $\rho=0$, then the constraints reduce to the BCE incentive constraints.

If all players have identical type and action spaces, i.e. $|\Theta_i|=|\Theta_j|$ and $|A_i|=|A_j|$ for all $i\ne j\in\mathcal{N}$, the resulting LP has $O((|\Theta_i||A_i|)^{|N|})$ variables and $O(|N||\Theta_i|^{|N|}|A_i|+|N||\Theta_i||A_i|^2)$ constraints, where the first term comes from the prior-consistency and conditional-independence constraints, and the second term from the tractable semicoarse incentive-compatibility constraints.

Proof of Theorem 4.1

Proof. We show that the distribution

satisfies the constraints in Definition 3.2.

Prior consistency. We must show that the marginal of $\sigma_T$ over actions equals the prior $\pi$: $\sigma_T(\theta)=\pi(\theta)$. It holds that,

The second-to last step follows, as $x_{j,t}(\cdot\mid\theta_j)$ are a probability distribution over $A$, hence the inner sum equals 1.

Conditional independence. We first show that $\sigma_T(a_i\mid\theta_i)=\frac{1}{T}\sum_{t=1}^{T}x_{i,t}(a_i\mid\theta_i)$ (*). As a first step, we use Bayes’ rule and the definition of $\sigma_T$. Afterwards, we rearrange terms to obtain

The last step is a result of prior consistency and the insight that $\pi(\theta_{-i}\mid\theta_i)$ is a distribution over $\Theta_{-i}$ and $\prod_{j\ne i}x_j(\cdot\mid\theta_j)$ is a distribution over $A_{-i}$, so they sum up to one.

We now apply this to show conditional independence.

Incentive compatibility. We need to show that for every player $i$, every type $\theta_i\in\Theta_i$, and every deviation $d^{\theta_i}\in D$

Remember that the players play the strategy game in expected-utility formulation as described in Section 4. In particular, the ex-ante utility for playing a vector $x_i\in X_i:=\prod_{\theta_i\in\Theta_i}\Delta(A_i)$ is

This is essentially a complete-information game, and we can apply Proposition 2.1 from Ahunbay & Bichler [2]. The proposition states that, for any tangential $h : X \to\mathbb{R}$ with bounded, Lipschitz continuous gradients, the following inequality holds, assuming all players implement projected gradient ascent with suitably chosen step sizes.

The constant depends on the game and the function $h$. We choose

with pairs $(Q_i^{\theta_i},q_i^{\theta_i})$ that satisfy the tangency, non-negativity, and symmetry conditions. $x_i[\theta_i]\in\Delta(\mathcal{A}_i)$ is the probability vector that player $i$ assigns upon observing $\theta_i$. With this $h$, we now show that BSCCE incentive compatibility follows. We can assume that $\pi(\theta_i)>0$ without loss of generality because if this were not the case, we could remove the type from the game.

Let us first describe the gradients $\nabla_i h(x)$ and $\nabla_i u_i(x)$. They both are vectors in $\mathbb{R}^{|\Theta_i|\cdot|\mathcal{A}_i|}$, and, like the strategy vectors $x_i$, they have a block-wise structure: There are $|\Theta_i|$ blocks with $|\mathcal{A}_i|$ entries, corresponding to the gradients with respect to $x_i(a_i\mid\theta_i)$. In particular, we find

where the indices refer to the position in the vector corresponding to the respective type and action. The utility $u_i(a_i',x_{-i}\mid\theta_i)$ is the interim utility of a player that observes type $\theta_i$ and plays action $a_i'$ while the opponents commit to playing $x_{-i}$:

In what follows, we derive the equality

which allows us to apply the bound from the proposition to our distribution $\sigma_T$.

We start with the scalar product of $\nabla_i u_i$ and $\nabla_i h$:

In the second step, we used our gradients and note that the $\pi(\theta_i)$ terms cancel. We also moved from the vector-based notation for the players’ strategies to a conditional-probability notation. In the second step, we applied the identity $\sum_{a_i}x_{i,t}[\theta_i,a_i]=1$.

We expand the interim utility terms to obtain

where we moved the order of summation and regrouped the player strategies $x_{j,t}$ to one product.

When we average over time, we can identify $\frac{1}{T}\sum_{t=1}^{T}\pi(\theta_{-i}\mid\theta_i)\prod_{j\in\mathcal{N}}x_{j,t}(a_j\mid\theta_j)$ with $\sigma_T(a,\theta_{-i}\mid\theta_i)$:

By summing over all players, this establishes the equivalence, so we get

Note that this holds for any choice of matrices $Q_i^{\theta_i}$ and vectors $q_i^{\theta_i}$ ($i\in\mathcal{N},\theta_i\in\Theta_i$) that satisfy symmetry, tangency, and non-negativity. We can thus set all of them to zero aside for one player $i$ and one of its types $\theta_i$. This implies

which in turn concludes the proof. □

Numerical experiments

Hardware Information

We ran our experiments on a small-scale server with an Intel(R) Xeon(R) Silver 4116 CPU with 48 cores (2.10 GHz) and 192 GiB of RAM. Our experiments are based on Python 3.12 and Gurobi 12.1. We left the CPU usage to Gurobi. Each experiment took between several seconds and several minutes (see "Complexity" in § 5).

Wasserstein Distances in the Incomplete-Information game

The convergence curves for the squared Wasserstein-2 distance exhibit a periodic "zig-zag" pattern for the uniform prior (Figure 3a). This is an artifact of the uniform discretization grid aligning perfectly with the canonical continuous BNE actions ($1/2\theta_i$). Thus, the oscillation is a predictable effect rather than an algorithmic or numerical instability.

Equilibrium Polytopes in the Complete-Information Case

As the previous results suggest that the tightness of the BSCCE concept decreases as priors become degenerate, we investigate the limiting complete-information case. Figure 4 illustrates the different equilibrium polytopes for a first-price auction with two players, who both have type $\theta_i = 1$. In this case, the only possible CEs are that both players perfectly coordinate to play the exact same action out of the top three, whereas the SCCE and CCE sets are much larger. This implies that, although the SCCE set is smaller than the CCE set, an even stronger equilibrium refinement might be necessary.