Scalable Neural Incentive Design with Parameterized Mean-Field Approximation
Authors: Nathan Corecco
Batuhan Yardim
Vinzenz Thoma
Zebang Shen
Niao He
Venue: NeurIPS 2025 poster ()
Keywords: Mean-Field Games
Equilibrium
Optimization
Mechanism Design
Auctions
Game Theory
Primary area: reinforcement_learning
TL;DR: We design a mean-field explicit differentiation method for incentive design in large-scale games with exchangeable agents.

Abstract: Designing incentives for a multi-agent system to induce a desirable Nash equilibrium is both a crucial and challenging problem appearing in many decision-making domains, especially for a large number of agents $N$.
Under the exchangeability assumption, we formalize this incentive design (ID) problem as a parameterized mean-field game (PMFG), aiming to reduce complexity via an infinite-population limit.
We first show that when dynamics and rewards are Lipschitz, the finite-$N$ ID objective is approximated by the PMFG at rate $\mathcal{O}(\frac{1}{\sqrt{N}})$.
Moreover, beyond the Lipschitz-continuous setting, we prove the same $\mathcal{O}(\frac{1}{\sqrt{N}})$ decay for the important special case of sequential auctions, despite discontinuities in dynamics, through a tailored auction-specific analysis.
Built on our novel approximation results, we further introduce our Adjoint Mean-Field Incentive Design (AMID) algorithm, which uses explicit differentiation of iterated equilibrium operators to compute gradients efficiently.
By uniting approximation bounds with optimization guarantees, AMID delivers a powerful, scalable algorithmic tool for many-agent (large $N$) ID.
Across diverse auction settings, the proposed AMID method substantially increases revenue over first-price formats and outperforms existing benchmark methods.

Scalable Neural Incentive Design with Parameterized Mean-Field Approximation
Nathan Corecco'
Batuhan Yardim
Department of Computer Science ETH Zurich
Department of Computer Science
ETH Zurich yardima@inf etzz. ch
nathan www.ccoeinn ethz. ch
Vinzenz Thoma
Zebang Shen
Department of Computer Science ETH Zurich & ETH AI Center vinzenz. thoma@ai ethz. ch
Department of Computer Science
ETH Zurich
Bebang.seendule ethz. ch
Niao He
Department of Computer Science ETH Zurich a..o.he@inf.ethhe..
Abstract
Designing incentives for multi- system to induce a desirable Nash equilib- rium is both crucial and challenging problem appearing in many decision-makern domains, especially for large number of agents N. Under the exchangeability assumption, we formalize this incentive design (ID) problem as parameterized mean-field game (PMFG), aiming to reduce complexity via an infinite- population limit. We first show that when dynamies and rewards are Lipschitz, the finite-N N ID objective is approximated by the PMFG rate O(I//N) Moreover, beyond the Lipschitz-continuuu setting, we prove the same O(1//N) decay for the important special case of sequential auctions, despite discontinuities in dynamics, through a tailored auction-specific analysis. Built on our novel approximation results, we further introduce Adjoint Mean-Field Incentive Design (AMID) algorithm, which uses explicit differentiation of iterated equilibrium operators to compute gra- dients efficiently. By uniting approximation bounds with optimization guarantees, AMID delivers a powerful, scalable algorithmic tool for many-agent (large N) ID. Across diverse auction settings, the proposed AMID method substantially increases revenue over first-price formats and outperforms existing benchmark methods.
1
Introduction
Setting the right incentives in game with many participants is challenging and high-staker problem. Policymakers must frequently make choices that affect millions, for instance, planners must design rules for curtailing city traffic [46), set pricing maximize effective bandwidth in telecommunications networks 3. design spectrum auctions between telecom operators [1 or manage supply and demand energy grids [52]
We study the incentive design (ID) problem. Given an objective G, a parameterized N-player game G. and player strategies ,I,...,77 ID solves the equilibrium constrained optimization problem:
"quaal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Maximize G(O, ......, nN) such that Fi....,TTy E Nashg(O)
(ID)
where Nashg (0) denotes the set of Nash equilibria (NE) of game for the incentive parameter
0 (which is to be learned). (ID) is also referred to in the literature as mathematical programming
with equilibrium constraints (MPEC) [51]. Despite their relevance, MPECs are notoriously
computationally challenging and in the general case NP-hard [3 [5]] Simply computing a Nash cquilibrium for a fixed incentive parameter 0 is also PPAD-complete [22], even for 2 players [17] For games with many players, as in many real-world problems, the so-called curse of many agents M becomes an added challenge. In such cases, computing (0) becomes prohibitively expensive, let alone tackling (ID).
In this work, we take the approach of mean-field approximation for games with agent exchangeability (i.e., symmetry) to tackle this problem. Instead of solving (ID) directly, we construct an appropriate mean-field game (MFG) approximation M to & and solve the mean-field ID (MID) problem:
Maximize G(O, TMFG) such that TMFG E Nash,MO)..
(MID)
For the mean-field approximation (MID) to be meaningful, its solution should closely match that of the original N-player incentive design problem (ID), with the approximation error vanishing as N + co. We formalize this requirement in the following desideratum.
Desideratum D1 (Approximation) The solution of (MI) should be a good (approximate) solution for (ID), in particular when N is large, with explicit guarantees.
MFGs are known to approximate finite thiite NEs with explicit bounds for large N 63
14
19
75
Under Lipschitz continuity, a non-asymptotic bound of O(1/VN) in exploitability is obtained with propagation- ioppagatiinnof-chiee of-chaos type argument. By contrast, problem (MID) not only contains the classical MFG as a subproblem but also an incentive objective, accordingly, we must show that the
approximation error still vanishes as N co. Establishing this result is our first contribution.
Contribution 1: Lipschitz PMFGs and Approximation. We formalize (MI) as a parameterized MFG (PMFG), and show that for Lipschitz PMFGs the (MID) problem approximates (ID) with rate of O1//NN, both in exploitability and optimality of the design objective.
While Lipschitz continuous MFGs cover a broad class of real-world games and are well-studied, they exclude many important applications, notably large-scale auction design, where the transition dynamics are inherently correlated and non- -on-hipschitz. Motivated by the ubiquity and impact of auctions, we analyze (D1) beyond Lipschitz. PMFGs, which our second contribution.
Contribution 2: Approximation beyond Lipschitz. We identify a PMFG for sequential batched auctions (BA-MFG) with many bidders, and establish (DT) with O(//N) approximation rate, by identifying a set of "well-behaved" policies that is dense in the set of Nash equilibria.
Although D guarantees that the mean-field approximation captures the fundamental solution structure of the N- N-player incentive design problem, realizing practical benefits from this framework requires the following desideratum.
Desideratum D2 (Optimization) We would like (MID) to be computationally tractable or easier to solve than II)), specifically, admit an efficient first-order oracle that be used for optimization.
Our algorithmic contribution is to satisfy this desideratum in both settings: (i) PMFGs under Lipschitz continuity assumptions, and (ii) mean-field auction design.
Contribution Algorithmic Contribution. We formulate our adjoint mean-field incentive design (AMID) algorithm for solving (MI) efficiently. AMID is modification of backpropagation based on the adjoint method for computing (approximate) derivatives with Nash equilibrium constraints. While naive autodiff-basee approaches incur a large ( memory footprint, reformulation of the gradient computations reduces the memory footprint to (VTT), with up 80% savings in practice.
Contribution 4: Experimental Contribution. Finally, we use AMID to (i) solve congestion pricing in the classical beach bar MFG, and (ii) design revenue-optimal mechanisms across a variety of sequential auctions with neural network parameterization. Our method consistently outperforms standard first-price mechanisms used in practice and other optimization approaches to solve (MID).

---

Table 1: Comparison of selected works ID in literature. Large N: results scale to many-agem (symmetric) G. Dynamic: solves ID on games with dynamics, Explicit diff.: explicit differentiation for first-order information, Approx.: finite-agent approximation in N, Auctions: applies to auctions.
Work
Model
Large N
Dynamic
Approx.
Explicit diff.
Auctions
48
VI VI
x
X
50
/
x
X
23
Cont, time
/
/
54
LQ
/
/
X
Maj.-min.
/
X
Ours
PMFG
/
T-hhorem
/Seection 2.2
V- Section
1.1 Related Works
We present the works most relevant to this paper, complemented by the discussion in Appendix B
Mathematical Programming with Equilibrium Constraints (MPEC). Several works have stud- Some of these assume that the equilibrium problem satisfies strong monotonicity to compute the gradients. Others use explicit differentiation, an approach we also follow in this work. Motivated by the success of reinforcement learning (RL), many works have focused on the optimal design of (mulli-agent) RL environments 69 An important instance of designing games with desirable outcomes is
ied gradient- gradient-based approaches for MPEC 48 50
47
26
67
28
automated mechanism design, capturing many real-world economic problems [18 20 49].
Steering and Equilibrium Selection. Complementary to ID problems, a related strand of work has focused on steering and equilibrium selection. For mean-fiel field games, (3 considers a problem of choosing equilibria with high social welfare. Steering learning dynamics towards desirable equilibria for Markovian and no-regret learners and extended to MFGs by (72).
was studied by [35 11 78
Mean-Field Games (MFG). MFGs, first formulated in the seminal works of Lasry & Lions
and Huang et [3 analyze symmetric competitive agents at the many-agent limit. Recently, many works have studied RL in mean-field settings, such as stationary MFGs [32 77 73 19] monotone MFGs 158
56 57 76,, static MFGs (74), and mean-field control 1S While general MFGs remain
theoretical challenge (75), under structured settings, they have shown empirical and algorithmic
45 MFGs have also been studied in Stackelberg equilibria, closer to our setting B 23 23 While these works have similar objectives ours, rather than letting a leader influence a population through interactions with a static environment, we aim to design parameterized MFGs directly by explicit differentiation. In this sense, (MID) can be seen to differ in objective from these works. Moreover, these results do not readily apply to auction design, a foundational problem for incentive design. In Table 1 provide comparison with selected works and our results.
efficiency 119
15
2 Designing Games for Large Populations: Lipschitz Case
We first formalize parameterized N-player dynamic games and the corresponding ID problem.
Notation. We use S, A to denote (finite) state-actions spaces. For the horizon H, define policy space 1I = { [M] x S + A abbreviate Tx (a]s) := [h, sa) and also treat 11 as a subspace of [ For finite set X' define the "empirical distribution" a (x) 1/N EN also provide a full reference table for our notation in Appendix A
Lr,=r' We
Definition (Parameterized Dynamic Games) A funite-horizon parameterized dynamic game (PDG) is tuple G :=
H. po, θ, (Pr,o) 1 H-1 _B of players N E N>1, discrete state actions sets S, A. parameter space θ parameterized transition dynamics Ph.e S x A AgN, parameterized reward functions R,,9 SN N - j0, 11 starting distribution μo As. and time horizon H E Ny For strategy profile π E II 2 0 and some 0 θ, the expected
3

---

rentrapy-regularized) sum of rewards of player E [N] is defined as
H
gsn,, an) + + ( (s))) Vs Vi Mo of
(T(() = E
Σ
8h 8
Define (T((0 == [ ( where (TT() ea Sg (( : 11 (T|(). the exploitability. If (0) = 0 for π² E Ell we call H Nash equilibrium (DG-NE) with respect to parameter 0. The set of all Nash equilibria for 0 E @ is denoted Nashğ (0). One is typically interested in maximizing a function of the aggregated population behavior (e.g., revenue, negative congestion):
N
() = ([ |T, 0), where La
1 N
(ID Objective)
SxA + R. with the constraint that л E TT is an (approximate) Nash equilibrium under (ignoring multiplicities). The parameter space Q and the parameterizations of Ph.o, Rs will dictate the implicit constraints the design, such the available information time For such parameterizations, optimizing G will be nontrivial and incorporate an intractable many-agent NE computation lower-dimensional MFG (i.e. of size independent of N) and propose tractable alternatives.
given by some θ x H
subproblem. In the following, we reduce this problem to
2.1 Parameterized Mean Field Game Design
Below, we formalize PMFGs. Definition generalizes genniaainnnnnerraliiieee the standard definition of MFGs to parametric family of MFGs, and approximates Definition on a continuum of infinitely many players.
Definition 2 (Parameterized Mean-Field Games) hinie-ooorizon parameterized mean-field game (PMFG) is tuple M : AS,A, H, no, θ (r p
-1 h== 0: {Rn a ) of discrete state actions sets S.A. parumeterized transition dynamics Pr.o -S x AsxA + Ass parameterized reward functions Ra,0 S x A x ASxA
0. initial distribution pa As, and horizon H E E. M8, Pn.o a, L) (a'ls") and H-1 called population operator For
No Define operators Th. as (T, (s's
A(T(0) = (Tn-2(-- Iı TTooooo Tu, T1 T1(0)]0) -hh
10- 1=0
E MT T 2 and L (LA 1== S the total expected (entropy regularized) reward is
H
Vī (L. - 10) = E
Rs an, LN) + (H((T((NN)
50mMa: ag mo (#k) Ph
h=
We define mean-field exploitability as ET (m := en (A(T), T' (A(T)) TO)) If ( O for π² E ll, we call MFG Nash equilibrium (MFG-NE) with respect to parameter 6. The set of all Nash equilibria for 0 E θ is denoted Nash
In this section, we will make the following (standard) assumption on Po a, L), Ro(s, a, L). which holds in many relevant applications.
Assumption (Lipschitz continuity) For all s, s S,a E A, the functions Phoo( a, L). R a, L), and g(, L) are Lipschitz continuous in L.
Theorem below demonstrates that by optimizing the objective g(8, A(r*)), one can obtain approxi- mation guarantees (up to bias of O(///N) on the performance of the PDG that has independent and symmetric state transitions. We have therefore established (II for PMFGs.
Theorem Let M be a PMFG, Assumption 1 hold. and G be the PDG such that Ps. a) = X [EIN) Pn.o(s",a", a,ss a)) and Ri,,o(s, = Rs, a' (s, a)) for all i. Let n E Nash (0)
and π = (n² ,-..,,")) E ITN Then:
1. ET 0) S O(//N)) that is, " is a O(1/N)-NE of under
Note that define A(m(0)o .40

---

2.
-
Theorem D mirrors bounds MFGs without ID 775 and Stackelberg MFGs in other settings [54] For clarity, the theorem is stated as approximation result for a PDG G that exactly satisfies agent exchangeability, which might not always be the case. In some applications, finding the mean-field formulation M given PDF G might be nontrivial. The converse problem of constructing an appropriate PMFG M that approximates a given G was studied in [76), and this work can be trivially generalized to this case with an additional approximation bias due to asymmetries in G. The case of auction design, which also does not satisfy Assumption and the assumption of Ph.o being product measure, will require specific treatment Section
2.2
Approximating the First Order Derivatives
Having satisfied (DI) for ID with Lipschitz dynamics in the previous section, we turn to (D2) formulating algorithmic methods solve (MID). We state the standard definitions of value and g-functions for PMFGs, which will be important for learning NEs:
Ro(sw, aa Iwc) + TH(TT on ou (ent) x, Σ
( v, Ro a, LA) E Vi+ (sh+1 n. snmaan aa Po .a Lone)
We define the commonly used online mirror descent update rule Ford θ IT Nh with F amaa (9, (h, 8) == arg max (s, [A(T), n, 4), + +H(u) 17 1 (n)) (u(u)((s)). 4
for some given learning rate 1) > 0 and entropy regularization r 2 0. F and has received particular attention in MFG literature due to its theoretical and empirical properties. Abbreviating Fird (6,5) ()
F (0 F Foma (O,....... amd (0, <) .). i.e., F' (0,-)(0,-) applied 7 times, the repeated iterations F [T()) for T > are known to convert NE for monotone MFGs theoretically [56] 79 37), and empirically find good approximations to NE [19 for general MFGs. Furthermore, any x E Nashi is guaranteed to be a fixed point of the map (0, .) for some learning rate 1). We formulate an explicit differentiation scheme for the PMFG using these properties of F Fomd- Defining the softmax transform softmax R [ - I1 as softmax(()(h,,,,)
omd
explCt...ol En exp exprSt.... the above OMD
update rule can reformulated terms of log probabilities:
(0, (h, s, a) == (1 Sy) + 79% (s, a c/A(softmax(()) softmax((), 0).
For fixed 0, the repeated iterations Food will converge (under technical conditions) to log nr where n² is an NE of the MFG induced by With this motivation, we reformulate the PMFG design problem MID) as maximization of the T-step approximate objective
TT approx : + g (0, A(softmaxx( (P!T)) (0, (o))
(I (T'aapprx.)
appeox in general is a well-defined differentiable function (see Lemma Appendix Dj. In particular, standard autograd tools can be used to compute VG While the behavior of V VGT approx when T + oo is not immediate, Lemma I below shows that under technical conditions Giiprox meaningful objective function to maximize, and produces low-bias estimates of the derivatives of the true NE with respect to 0 for sufficiently large T'.
Lemma (Differentiability of F Let Ç RIXSSA 0 θ be such that the following hold:
1. (f',
. .C) = 10 ( for 0' E U for a neighborhood of
2. For 5" such that 5* = Fo (0,S). S). Tf is C in a neighborhood of (0,5*), and p(oca (..1A(softmax((")) softmax(("") ),0)))) < t for all h (H) ",ottaax""))sssstmxx("""""
Then, softmax( P (0', (C) Nash (0")) on 0' E U, F partially differentiable in @ at (0, S).
and lim7-+x FgF a (0,5) Free ( (0, (0,G) C).
5

---

Lemma justifies the use of G approx (and subsequently the explicit differentiation scheme) as an objective function under mild technical conditions. If G is also C², VG Girproo converges to the derivative of map 0' - G( x²) where x" is a function of 0' such that x E NashjMl (6') locally, that is, for all 0' in some neighborhood of 0. Moreover, Lemma I provides intuition on how to tune the parameters 7), T, and characterizes their impact on the quality of explicit differentiation.
One major challenge from computational point of view of backpropagating -apprrox. will be the size of the computational graph, growing with (T)). In many MFGs, finding a good approximate MFG-NE will require a large T. which will incur large computational overhead.
Algorithm| D which we call adjoint mean-field incentive design (AMID), reduces the poten- tially memory-intensive backpropagation through complex computational graph simple for- ward and backward pass in t. Crucially, the up- date operator F is typically quite complicated for PMFGs: for instance, Fond itself involves solving forward (A) and backward equations (gf) in h. Therefore, for large T, naive autograd will be in- efficient due the storage of many intermediate values and large graph.
Algorithm 1 AMID
Input: Update rule F, objective G. T.n, T, T, Forward pass
for E O..... .., T
2: G+1 = (1- a + (0(())))
3: end for
4: ST+1 OgG((, (T,1),(+)),)))).)))))).)). ar -0,G((r+1)
for t E T. T..., do
Backward pass
6: at = (1 n7 aa
) + F
7:
#:-1 = 8: no F(0, Cb)
8: end for
9: return 80
Lemma 2 (Adjoint method) Let O
RRd' be an open set and F θ Rd + Rd and G x Rd - Rd be difserentiable functions. Assume Algorithm is run with inputs F, G, and T N 00 n, C, E Rd. Then its return value 8o is equal to V VoG(O, (0
Remark In Algorithm 7 {Ge)e will need to be stored for the backward pass in memory, however, the memory footprint can be reduced O( by caching every O( timesteps of the forward process and recomputing Se as required, maintaining time complexity of O(T). Furthermore, Algorithm 7 can be generalized to arbitrary Bregman divergences, which permits a variety of inner loop operators to be used (Appendix(D. D.6).
3 Beyond Lipschitz: Mechanism Design for Large-Scale Auctions
Auction design a ubiquitous and well-studied problem of extraordinary economic interest [43 To analyze auctions at the mean-field regime, we move beyond the Lipschitz PMFG assumptions. Designing auctions with maximum revenue in the resulting equilibrium can be framed as an instance of (ID) (see our discussion in Appendix C and with an appropriate PMFG, tackled using AMID. Specifically, we consider the following sequential batched auction setting motivated by real-world formats used for selling government debt, broadcast licenses, mineral rights, art, fish, timber (27] and including transactions in mined Ethereum blocks (62)
(Parameterized) batched auctions. An H-round N N-player batched auction with incentive parame- ter is a PDG Gane with state space S = V {+} (where the value space := {(O..., (IV) 11/lv1 represents possible valuations and 1. denotes non-partici in the current round) and action space A {0.... (1-AI 1)/1A1} (possible bids). Each bidder i E [N] at round h E [H] has a private state si S not revealed to the auctioneer other bidders. Overall, the auctioneer sells at most [amax goods (for some Qmax E 1)) and chooses 0, parameterizing the allocations and payments as outlined below. The auction evolves for h [H] follows:
1. Initial states at h = 0 are independently sampled from distribution 140 E Av. 2. At every round h [H), bidders for which s), #L submit their bids aj, E A. Observing the bid distributions i7 1
N EiE[M] ea; 4o #1 the mechanism decides on a ratio of goods be sold this round, af (2) Items are allocated to the highest [af (2/ |)N] bidders, with ties broken uniformly at random.
Each bidder i who receives an item, makes a payment pi. = ph (at, D E R2o- winning bidder receives utility un (* pi.) R and transitions to state 1,, while non non-winning and non- participating bidders receive zero utility.

---

5. Before proceeding to round h+ 1, each bidder transitions independently to a new state according to dynamics function Wh, : x As + As. which maps the agent's current state and the empirical population distribution (after the allocation at round h)) to distribution over next states.
To ensure the mechanism can not sell more goods than are available (Ommxx) ) we assume that the parameterizations of of, are such that Σn af (0)+)) S mmax almost surely. This is can be ensured, for example, by parameterizing of, complex valuation dynamics, such as single-minded bidders (who stay in 1), time-dependent or population-dependent evolving valuations, as well as super and subadditive valuations over bundles of goods. Under these dynamics, we denote the expected utility of player i and exploitability as Jase , E.. respectively, as defined in Definition
fraction of remaining goods at every h. Gane allows for
We note that parameterizing a Pl fully captures the intuition of reserve prices in the BA-MFG setting. In many auction formats, a reserve price, i.e., a minimum price that bidders have to bid and pay win, has been shown increase revenue (55). A reserve price Th. A at round h can be implemented for example with Or (v) = Ee'zn. 2n. v(a') and ph (a, V) = a.
3.1 Auctions at the Mean-Field Regime
From the above description, Gauc clearly has exchangeable agents. However, the corresponding one-step state evolutions are not independent, making Theorem iinapplicable here. Motivated by the relevance of large-scale auction design, we show that PMFGs are still relevant and (DI) holds with refined analysis of batched auctions in the following. We begin by defining the correct MFG that characterizes the batch auction at the limit N- + co. While the definition is symbol-laden, we state it for completeness.
Definition 3 (BA-MFG) A Batched-Auction MFG (BA-MFG) is the PMFG Mmja (S, H, po, θ, ( pmmfay H-1 y H-1) ). where Hggh. Poth are given by:
0 h== {
gighh (s, a, L) = Pwin (s, a, L, a (L)))wn(s') 1, 11
(s. (L)))
(s' as,a, L) == Pwin s,,, a, L, a (v (L) (4))
8,h
+ (1 - (s, L, (L))== (,,00
where (D) EetID(s, [(s,)), gl.0
As such that (1,)(1) L(L)
(L, La (1)-(()))))))))))))))))) and ((s) = (,sm(()) (L,a,((-((L))) and pwin defined a
a, L.) = 1sy1 max 0. min { a- -'VEV, L(s',a') V (L)
Pwin as
We use Vi E to denote expected reward and exploitability in Mmia. as Definition 2
The intuition behind Definition B relies on the fact that the function Pwin approximately characterizes the marginal winning probability of agent when N is large. In fact, Theorem 2 below shows that BA-MFG is indeed the correct model for auctions with large N. Existing approximation results (such incompatible with this setting due (1) the fact that transitions in (finite-player) auctions are not independent, and (2) due to the inherent jump discontinuities in both paue Regte No zero-dominance (NZD) policies, defined below, identify subset of policy space II where this difficulty can be circumvented.
63 75
well as Theorem TD fundamentally
Definition 4 (No zero-dominance (NZD)) Let Mmja be a BA-MFG and A E e. π E II is said to satisfy the NZD property for 0 if at induced L {L, (H-))--1 ( there exist A, [H] such that Eeev Ln a) 0 and Exev,a'a (n = af (v-1 (L)).
While NZD is a technical condition, it is for instance satisfied by any entropy regularized MFG-NE of Mmia if r > O, therefore, contains e-NE for arbitrarily small E > O. With this property, BA-MFGs satisfy (DT) as shown below, making it relevant model for auction design.
In this definition take 5/o c0, for any >> 0 and % 0, for convenience.
7

---

Theorem (Approximation for BA-MFG) Let Mmja be BA-MFG with tipschiz-continnnn Wh, Wh, 0h Ph, and let g O x A - R. be Lipschitz. Let ग E Th be policy that satisfies the no zero-dominance property with respect to 0 O. Then, for ( ) II
any T 2 0, 1. Euu ( (T S Enja (TT 0) + O (1/N)) anr
2. g(, Amtu (0)) G( (() - (0/N).
Proof sketch: The proof builds on (1) special handling of the correlated evolution of st at any round h and (2) showing that for non-zero dominant policies the dynamics locally Lipschitz continuous. The two conclusions are proved separately in Appendices E.3 and E.4
Theorem 2 demonstrates convergence for broad class of policies and relates to large strand of work on equilibrium computation for auctions, which we discuss Appendix B While true MF-NE does not necessarily satisfy the pero-dominance property, entropy-rege regularized arized MF-NE does. In this regard, the results above show that the BA-MFG essentially characterizes the limiting behavior of batched auctions.
Remark In general, Theorem 2 incorporates a standard worsi-case exponential bound in H, depending Why However, in certain cases, such non-expansive or population-independee Wh. and x with full support, the bound becomes polynomial in H, (S), |A] (see Appendix E.3 We
later verify the quality of the bound in real-world experiments.
Finally, we state the following differentiability result of F thus satisfying (D2) when combined with the adjoint method described Section 2.2 This result permits mechanism design by backprop- agation for any entropy regularization T > 0, completing the motivation for BA-MFG.
Lemma (Differentiability on Ganc) Let Musa be a BA-MFG on an open parameter space O C R. with Lipschitz Uh, Whs oh ph then Fomd is almost everywhere differentiable on || x θ.
Equipped with algorithmic tool to solve large-scale ID problems, move to empirical demon- stration on applications.
4 Experimental Results
We evaluate our methodology on numerical examples of increasing complexity, using AMID obtain gradient estimates and ADAM (40) as an update rule on parameters 0. All experiment details, including computational resources, can be found in Appendix We also provide reference implementations JAX and Py
First, we demonstrate the effectiveness of our approach the prototypical MFG of the beach bar game [8]. We formulate the PMFG Mas. where a large population of beachgoers starting from move left, stay, move right (A 1, 1}) beach (S == [K]) over H steps, while trying to minimize their distance to the bar located at Shar = K/2 and avoiding busy spots. We parameterize a pricing mechanism 0 E (the softmax of population flow):
H4 Uniform(S)
[0, 1/2]S for spots on the beach to minimize congestion
R (s, a. L, 0) := d(s, Sbar)
aal K
log Ln(s) 6s, L)
L)
Σ [x)((()
K
We report the training curves and induced flows in Figure along with 0* in Appendix
'The PoToh implementation adapted from MFGLib 31

---

2.4
10-1.6
10-1.8
101
001
10
0
0.2
0.4
U.6 0.8
Dtention (10*)
Dew
Figure I: Payment design with AMID in Map- Left: objective and exploitability throughout training iterations. Middle-right: population flow time before and after learning payments.
Dynamic auction settings. We move to the more challenging but relevant setting of designing neural network mechanisms BA-MFGs. We focus risk bidders (un, linear in payments) and on direct revelation mechanisms, i.e. S = A We set [S] 100, and maximize the revenue objective:
Frev (0 :
Σ
Σ
Ln(s, a Pin In, a (((v=~((A))))) (a,v~((Ln))
A=0 (s.))EVXA
The exact settings, labeled (AT)-(A3)
follows:
(A1) = 4. μI = Uniform(S (S). mmax = 0.8, and single- bidders (after winning stay at state 1) with evolution in valuations s), otherwise.
(A2) = 4, amax = 0.8, (s))) x 7* for 7 = 0.9, dynamic values with w=s' o exp( (3s -200/200 for = 0.2, bidders are single-minded.
(A3) 5, He uniformly sampled from As, Qmax Uniform( (00formm(006.2. 1.2)), participants re-enter with probability 0.3 each round
We parameterize Ph: af with residual neural network (architecture clarified in Appendix F contain- ing = x 10y parameters, with inputs Ch, 2/ and remaining unsold goods at round h, guaranteeing by parameterization that more than Ommx goods sold in total.
Baselines. We evaluate AMID against several benchmarks. First, we compare against the results of rumning simple first-price auction (FIRSTPRICE), i.c., the highest bidders win and pay what they bid, to see how much more revenue we can achieve from optimizing over af and ph- Second, we contrast with various methods without gradient information: two methods using two-point gradient estimators (0-ADAM and (-SGD respectively), and a 0-order annealing strategy (ANNEAL. using random perturbations of 0. We use 10-3 10 and T = 400 for computing objective G Gxppoxx We report the training curves in Figure 2 where we evaluate GT...
approx throughout training Tea 500 for robustness. The results indicate the effectiveness of our method against zeroth-order methods across different auctions. Evaluations on a larger variety of settings and parameterizations (longer horizons H, nonlinear utilities, static mechanisms, other g) are also reported in Appendix
Empirically Testing DI
D2
Figure illustrates that we fulfill (T) & D2 Notably,
the actual revenue in the N player auction is very close to the optimized frev even for N s 100. Furthermore, the exploitability curve of OMD iterates the optimized 0* also suggests that the iterates are good approximation of ME-NE, and empirically, the assumptions of Lemma are valid. Namely, OMD iterations produce valid approximate Nash equilibrium after the end-to-end optimization process with AMID, empirically verifying that the revenue at Nash is indeed optimized.
We further provide empirical evidence supporting (D2) by comparing the computational footprint of AMID against naive backpropagation through the full computational graph induced by OMD. In
'The latter choice is motivated by the conceptual simplicity, widespread use in practice, and does not represent significant restriction given the revelation principle (43).
'The setting more challenging for two reasons. First, the neural mechanism must generalize over Oraax. which it can observe. Second, it must generalize over all which it does not observe, but potentially infer from - -LL) This is also referred to prior-free mechanism design (29 34

---

0.25
0.4
0.4
Revenue
0.2
0.35
0.2
0.15
0.3
0.1
0.25
6
0.2 0.4 0.6 0.8
0.2 0.4 0.6 0.8
Iteration (102)
Iteration (10%)
Iteration (10
AMID
O-ADAM
O-SGD
ANNEAL
FIRSTPRICE
Figure 2: frev throughout iterations of AMID and baseline algorithms in settings (A1-3), left to right.
Table 2
we report the time and memory usage of the two methods when solving (A1) with increasing time horizons H single H100. The results reported for single backpropagation step. The modest growth in memory and computation time observed for AMID as H increases highlights the scalability and practical suitability of our methodology for solving large-scale ID problems.
109
10-1
Mean bid (a)
10-1
mnf
0.5
10-2
10
10-3
10-3
0
100
102 Agents (N)
10a
103
10
10t
102
0.2 0.4 0.6 0.8
Iteration (7)
Valuation (s)
Figure 3: Left: deviation in revenue in Mmia N-player gase at 0" as functions of N, and middle:
exploitability curve of OMD iterations F(T) (8",.) at optimized 6* in (AI), (A2), (A3). Right: mean bids of NE computed by F'lT) for [4] before and after optimization with AMID in (A1).
Table 2: Empirical compute time and memory usage for single-step naive backpropagation single- step AMID across different problem horizons, in setting (A1). The rows with "n/a" indicate the method did not run single H100.
Horizon
Naive (time, s)
Naive (memory)
AMID (time, s)
AMID (memory)
H=5
0.19 0.02 s
2760 MiB
0.09 1 0.01
560 MiB
H=10
0.25 + 0.10
8746 MiB
0.21 + 0.08
586 MiB
H-25
0.71 0.15
16960 MiB
0.67 : 0.12s
826 MiB
H-50
n/a
n/a
1.72 0.41s
1076 MiB
5
Conclusion
In this work, we presented novel method for ID relying on PMFGs. In particular, we set forth two desiderata in order to use scalable first-order optimization to approximately solve problems. Through new analyses, we demonstrated that these conditions hold in both classical Mean Field Game (MFG) settings and batched auction environments. For both settings, we presented a unified algorithm, called AMID, which can solve span of ID problems, such as congestion pricing or optimal auction design. Overall, the AMID framework offers a flexible foundation for diverse incentive design applications, paving the way for future extensions.
10

---

Acknowledgments and Disclosure of Funding
This project was supported by Swiss National Science Foundation (SNSF) under the framework of NCCR Automation and SNSF Starting Grant. V. Thoma acknowledges funding from the Swiss National Science Foundation (SNSF) Project Funding No. 200021-207344 and supported by an ETH AI Center Doctoral Fellowship.
References
[1] Alexander Aurell, Rene Carmona, Gokce Dayanikli, and Mathieu Lauriere. Optimal incentives to mitigate epidemics: stackelberg mean field game approach. SIAM Journal on Control and Optimization, 40(2):824-S3222 2022.
[2] Santiago R. Balseiro, Omar Besbes, and Gabriel Y. Weintraub. Repeated auctions with budgets in ad exchanges: Approximations and design. Management Science, 01(4):664-888 2015.
[3] Tamer Basar and Rayadurgam Srikant. Revenue-maximizin pricing and capacity expansion in a many-user regime. In Proceedings. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, volume 1, pages 294-301 301. IEEE, 2002.
[4] Alain Bensoussan, Michael HM Chau, and Sheung Chi Phillip Yam. Mean field stackelberg games: Aggregation of delayed instructions. SIAM Journal on Control and Optimization, 53(4):2237 2266, 2015.
[5] Alain Bensoussan, Jens Frehse, Phillip Yam, et al. Mean field games and mean field type control theory, volume 101. Springer, 2013.
[6] Martin Bichler, Maximilian Fichtl, Stefan Heidekrüger, Nils Kohring, and Paul Sutterer. Learn- ing equilibria in symmetric auction games using artificial neural networks. Nature Machine Intelligence, 388)6677-695, August 2021.
[7] Martin Bichler, Maximilian Fichtl, and Matthias Oberlechner. Computing bayes nash equilib- rium strategies in auction games via simultancous online dual averaging. In Proceedings of the 24th ACM Conference on Economics and Computation, EC '23, page 294, New York, NY, USA, 2023. Association for Computing Machinery.
[8] Vitor Bosshard, Benedikt Bünz, Benjamin Lubin, and Sven Seuken. Computing Bayes-Nash equilibria in combinatorial auctions with continuous value and action spaces. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (ICCAI), Melbourne, Australia, August 2017.
[9] Vitor Bosshard, Benedikt Bünz, Benjamin Lubin, and Sven Seuken. Computing bayes-nash equilibria in combinatorial auctions with verification. Journal of Artificial Intelligence Research, 69:531-570, 2020.
[10] Yang Cai and Christos Papadimitriou. Simultaneous bayesian auctions and computational complexity. In Proceedings of the Fifteenth ACM Conference on Economics and Computation, EC 14, page 895-910, New York, NY, USA, 2014. Association for Computing Machinery.
[11] Ilayda Canyakmaz, Iosif Sakos, Wayne Lin, Antonios Varvitsiotis, and Georgios Piliouras. Learning and steering game dynamics towards desirable outcomes. In Proceedings of the 7th Annual Learning for Dynamics & Control Conference, volume 283 of Proceedings of Machine Learning Research, pages 1512-1524. PMLR, 04-06 Jun 2025.
[12] René Carmona and Gökçe Dayanıh. Mean field game model for an advertising competition in a duopoly. International Game Theory Review, 23(04):1100044 2021.
[13] René Carmona, Gökçe Dayamıkı, and Mathieu Laurière. Mean field models to regulate carbon emissions in electricity production. Dynamic Games and Applications, 12(3):897-922 2022.
[14] René Carmona and François Delarue. Probabilistic analysis of mean-field games. SIAM Journal on Control and Optimization, 51(4):2705-7734,2 2013.

---

[15] René Carmona, Mathieu Laurière, and Zongjun Tan. Model-free hean-field reinforcement learning: mean-field mdp and mean-fiell q-learning. The Annals of Applied Probability. 33(66))5334-5388 5381, 2023.
[16] Siyu Chen, Donglin Yang. Jiayang Li, Senmiao Wang, Zhuoran Yang, and Zhaoran Wang. Adaptive model design for Markov decision process. In Kamalika Chaudhuri. Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th Inter- national Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 3679-3700. PMLR, 17-23 Jul 2022.
[17] Xi Chen, Xiaotie Deng, and Shang- Hua Teng. Settling the complexity of computing two-player nash equilibria. Journal of the ACM (JACM), 56(3):1-57, 2009.
[18] Vincent Conitzer and Tuomas Sandholm. Self-interested automated mechanism design and implications for optimal combinatorial auctions. In Proceedings of the 5th ACM Conference on Electronic Commerce, EC '04, page 132-141, New York, NY, USA, 2004. Association for Computing Machinery.
[19] Kai Cui and Heinz Koeppl. Approximately solving mean field games via entropy- regularrzed deep reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 1909-1917. PMLR, 2021.
[20] Michael Curry, Vinzenz Thoma, Darshan Chakrabarti, Stephen McAleer, Christian Kroer, Tuomas Sandholm, Niao He, and Sven Seuken. Automated design of affine maximizer mech- anisms in dynamic settings. Proceedings of the AAAI Conference on Artificial Intelligence. 38(9):922-99335, March 2024.
[21] Michael Curry, Alexander R Trott, Soham Phade, Yu Bai, and Stephan Zheng. Finding general equilibria in many-agent economic simulations using deep reinforcement learning, 2022.
[22] Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a nash equilibrium. Communications of the ACM, 52(2):89-97, 2009.
[23] Gokce Dayanikli and Mathieu Lauriere. A machine learning method for stackelberg mean field games. arXiv preprint ar Xi2:23022.1044000 2023.
[24] Greg d' EoEn, Neil Newman, and Kevin Leyton- Brown. Understanding iterative combinatorial auction designs via multi-agent reinforcement learning. In Proceedings of the 25th ACM Conference on Economics and Computation, EC '24, page 1102-1130, New York, NY, USA, 2024. Association for Computing Machinery.
[25] Stylianos Despotakis, R. Ravi, and Amin Sayedi. First-price auctions in online display advertis- ing. Journal of Marketing Research, 58(5):888-9))) 0878907, October 2021.
[26] Tanner Fiez, Benjamin Chasnov, and Lillian Ratliff. Implicit learning dynamics in stackelberg games:
Equilibria characterization, convergence analysis, and empirical study. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 3133-3144. PMLR, 13-18 Jul 2020.
[27] Ian Gale and Mark Stegeman. Sequential auctions endogenously valued objects. Games and Economic Behavior, 36:74-103, 07 2001.
[28] Matthias Gerstgrasser and David C. Parkes. Oracles & followers: Stackelberg equilibria in deep multi-agent reinforcement learning. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Searlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 11213111266 PMLR, 23-29 Jul 2023.
[29] Andrew V. Goldberg, Jason D. Hartline, and Andrew Wright. Competitive auctions and digital goods. page 735 744, 2001. Cited by: 199.
12

---

[30] Amy Greenwald, Jiacui Li, and Eric Sodomka. Approximating equilibria in sequential auctions with incomplete information and multi-unit demand. In Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
[31] X. Guo, A. Hu, M. Santamaria, M. Tajrobehkar, and J. Zhang. MFGLib: A library for mean field games. arXiv preprint arXiv:2304.0888 2023.
[32] Xin Guo, Anran Hu, Renyuan Xu, and Junzi Zhang. Learning mean-field games. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[33] Xin Guo, Lihong Li, Sareh Nabi, Rabih Salhab, and Junzi Zhang. Mesob: Balancing equilibria & social optimality, 2023.
[34] Jason D. Hartline and Tim Roughgarden. Optimal mechanism design and money burning. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC '08, page 75-84, New York, NY, USA, 2008. Association for Computing Machinery.
[35] Jiawei Huang, Vinzenz Thoma, Zehang Shen, Heinrich H. Nax, and Niao He. Learning steer markovian agents under model uncertainty. In The Thirteenth International Conference on Learning Representations, 2025.
[36] Minyi Huang, Roland P Malhamé, and Peter Caines. Large population stochastic dynamic games: closed-loop mckean- vlasov systems and the nash certainty equivalence principle. Com- munications in Information & Systems, 6(3):221 2006.
[37] Noboru Isobe, Kenshi Abe, and Kaito Ariu. Last iterate convergence in monotone mean field games. arXiv preprini 24.00::40005:/// 2024.
[38] Krishnamurthy Iyer, Ramesh Johari, and Mukund Sundararajan. Mean field equilibria of dynamic auctions with learning. Management Science, 60(12):2949-22 2970, dec 2014.
[39] Robert G. Jeroslow. The polynomial hierarchy and a simple model for competitive analysis. Mathematical Programming, 3262):146-164, June 1985.
[40] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings. 2015.
[41] Paul Klemperer. How (not) to run auctions: The curopean 3g telecom auctions. European Economic Review, 46(4-5):829-844 845, May 2002.
[42] Nils Kohring, Fabian Raoul Pieroth, and Martin Bichler. Enabling first-order gradient-based learning for equilibrium computation in markets. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 17327-17342. PMLR, 23-29 Jul 2023.
[43] Vijay Krishna. Auction Theory. Academic Press, 2002.
[44] Jean-Michel Lasry and Pierre-Louis Lions. Mean field games. Japanese journal of mathematics, 2(1):229-260, 2007.
[45] Mathieu Laurière, Sarah Perrin, Julien Pérolat, Sertan Girgin, Paul Muller, Romuald Élie, Matthieu Geist, and Olivier Pietquin. Learning in mean field games: A survey. arXiv preprint 2xXv:22055.12944 2022.
[46] Ana Ley, Winnie Hu, and Keith Collins. Less traffic, faster buses: Congestion pricing's first week. The New York Times, January 2025. Accessed: 2025-15-01.
[47] Jiayang Li, Jing Yu, Boyi Liu, Yu Nie, and Zhaoran Wang. Achieving hierarchy-free approxima- tion for bilevel programs with equilibrium constraints. In Proceedings of the 40th International Conference Machine Learning, ICML'23, Honolulu, Hawaï, USA, 2023. AMLR.org
13

---

[48] Jiayang Li, Jing Yu. Yu Nie, and Zhaoran Wang. End-to-end learning and intervention in games. In H. Larochelle, M. Ranzato, Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 16653-16660 Curran Associates, Inc., 2020.
[49] Anton Likhodedov and Tuomas Sandholm. Methods for boosting revenue in combinatorial auctions. In Proceedings of the 19th National Conference on Artifical Intelligence, AAAI'04, page 232-237, San Jose, California, 2004. AAAI Press.
[50] Boyi Liu, Jiayang Li, Zhuoran Yang, Hoi-To Wai, Mingyi Hong. Yu Nie, and Zhaoran Wang. Inducing equilibria via incentives: Simultaneous design-and-play ensures global convergence. In S. Koyejo. S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 29001-29013, Curran Associates, Inc., 2022.
[51] Zhi-Quan Luo, Jong-Shi Pang, and Daniel Ralph. Mathematical Programs with Equilibrium Constraints. Cambridge University Press, nov 1996.
[52] Sabita Maharjan, Quanyan Zhu, Yan Zhang, Stein Gjessing, and Tamer Basar. Dependable de- mand response management in the smart grid: A stackelberg game approach. IEEE Transactions on Smart Grid, (1):12201332 2013.
[53] Carlos Martin and Tuomas Sandholm. Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks. In Edith Elkind, editor, Proceedings of the Thirty-Second International Joint Conference Artificial Intelligence. IJCAI-23, pages 2844-2852. International Joint Conferences on Artificial Intelligence Organization, 8 2023. Main Track.
[54] Jun Moon and Tamer Başar. Linear quadratic mean field stackelberg differential games. Auto- matica, 97:200-213 2018.
[55] Roger B. Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58-73, 1981.
[56] Julien Pérolat, Sarah Perrin, Romuald Elie, Mathieu Laurière, Georgios Piliouras, Matthieu Geist, Karl Tuyls, and Olivier Pictquin. Scaling mean field games by online mirror descent. In Proceedings of the 21st International Conference Autonomous Agents and Multiagent Systems, pages 1028-1037, 2022.
[57] Sarah Perrin, Mathieu Laurière, Julien Pérolat, Romuald Élie, Matthieu Geist, and Olivier Pietquin. Generalization in mean field games by learning master policies. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 9413-9421, 2022.
[58) Sarah Perrin, Julien Pérolat, Mathieu Laurière, Matthieu Geist, Romuald Elie, and Olivier Pietquin. Fictitious play for mean field games: Continuous time analysis and applications. Advances in Neural Information Processing Systems, 33:13199-13213, 2020.
[59] Fabian R. Pieroth, Nils Kohring, and Martin Bichler. Equilibrium computation in multi-stage auctions and contests. ArXiv, abs/2312. 11751, 2023.
[60] Zinovi Rabinovich, Victor Naroditskiy, Enrico H. Gerding, and Nicholas R. Jennings. Comput- ing pure nash equilibria in games with finite actions and continuous types. Artificial Intelligence,
February 2013.
[61] Daniel M. Reeves and Michael P. Wellman. Computing best-response strategies in infinite games of incomplete information. In Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence, UAI '04, page 470-478, Arlington, Virginia, USA, 2004. AUAI Press.
[62] Tim Roughgarden. Transaction fee mechanism design. In Proceedings of the 22nd ACM Conference on Economics and Computation, EC '21, page 792, New York, NY, USA, 2021. Association for Computing Machinery.
[63] Naci Saldi, Tamer Basar, and Maxim Raginsky. Markov-nash equilibria in mean-field games with discounted cost. SIAM Journal on Control and Optimization, 56(6))4256-4255 2018.
14

---

[64] Sina Sanjari. Subhonmesh Bose, and Tamer Başar. Incentive designs for stackelberg games with large number of followers and their mean-field limits. Dynamic Games and Applications. 15(1):238-277 278, 2025.
[65] Vinzenz Thoma, Vitor Bosshard, and Sven Seuken. Computing perfect bayesian equilibria in sequential auctions with verification. Proceedings of the AAAI Conference on Artificial Intelligence, 14111:141188-14 14166, April 2025.
[66] Vinzenz Thoma, Michael Curry, Niao He, and Sven Seuken. Learning best response policies in dynamic auctions via deep reinforcement learning, 2023.
[67] Vinzenz Thoma, Barna Pasztor, Andreas Krause, Giorgia Ramponi, and Yifan Hu. Contextual bilevel reinforcement learning for incentive alignment. In Advances in Neural Information Processing Systems, volume 37, pages 227369-127435 2024.
[68] Yevgeniy Vorobeychik and Michael P. Wellman. Stochastic search methods for nash equilibrium approximation in simulation-based games. In Proceedings of the 7th International Joint Confer- ence on Autonomous Agents and Multiagent Systems- Volume 2, AAMAS '08, page 1055-1062. Richland, SC, 2008. International Foundation for Autonomous Agents and Multiagent Systems.
[69] Jing Wang, Meichen Song, Feng Gao, Boyi Liu, Zhaoran Wang, and Yi Wu. Differentiable arbitrating in zero-sum markov games. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, AAMAS '23, page 1034-1043, Richland, SC, 2023. International Foundation for Autonomous Agents and Multiagent Systems.
[70] Kai Wang, Lily Xu, Andrew Perrault, Michael K. Reiter, and Milind Tambe. Coordinat- ing followers to reach better equilibria: End-to-end gradient descent for stackelberg games. Proceedings of the AAAI Conference on Artificial Intelligence. 36(5):5219-5277, June 2022.
[71] Lingxiao Wang, Zhuoran Yang, and Zhaoran Wang. Breaking the curse of many agents: Provable mean embedding q-iteration for mean-field reinforcement learning. In International conference on machine learning, pages 10092-10103. PMLR, 2020.
[72] Leo Widmer, Jiawei Huang, and Niao He. Steering no-regret agents in mfgs under model uncertainty, 2025.
[73] Batuhan Yardim, Semih Cayci, Matthicu Geist, and Niao He. Policy mirror ascent for efficient and independent learning in mean field games. In International Conference on Machine Learning, pages
PMLR, 2023.
[74] Batuhan Yardim, Semih Cayci, and Niao He. A variational incquality approach to independent learning in static mean-field games. ACM/ / IMS Journal of Data Science, 2(2), July 2025.
[75] Batuhan Yardim, Artur Goldman, and Niao He. When mean-field reinforcement learning tractable and relevant? In Proceedings of the 23rd International Conference Autonomous Agents and Multiagent Systems, AAMAS '24, page 2038-2046, Richland, SC, 2024. Interna- tional Foundation for Autonomous Agents and Multiagent Systems.
[76] Batuhan Yardim and Niao He. Exploiting approximate symmetry for efficient multi-agent reinforcement learning. In Proceedings of the 7th Annual Learning for Dynamics & Control Conference, volume 283 of Proceedings of Machine Leurning Reseurch, pages 31-44. PMLR, (4-066 Jun 2025.
[77] Muhammad Aneeq Uz Zaman, Alec Koppel, Sujay Bhatt, and Tamer Basar. Oracle-free reinforcement learning in mean-field games along a single sample path. In International Conference on Artificial Intelligence and Statisticy, pages 10178-10206. PMLR, 2023.
[78] Brian Hu Zhang, Gabriele Farina, Ioannis Anagnostides, Federico Cacciamani, Stephen McAleer, Andreas Haupt, Andrea Celli, Nicola Gatti, Vincent Conitzer, and Tuomas Sandholm. Steering no-regret learners to desired equilibrium. In Proceedings of the 25th ACM Conference on Economics and Computation, EC '24, page 73-74, New York, NY, USA, 2024, Association for Computing Machinery.
15

---

[79] Fengzhuo Zhang, Vincent YF Tan, Zhaoran Wang, and Zhuoran Yang. Learning regularized monotone graphon mean-field games. arXiv preprint arXiv:2310.08089 2023.
[80] Stephan Zheng, Alexander Trott, Sunil Srinivasa, David C. Parkes, and Richard Socher. The ai economist: Taxation policy design via two-level deep multiagent reinforcement learning. Science Advances, 8(18), May 2022.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The claimed convergence rate is proven in the paper and the experimental results are accurately described.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We state our assumptions in Section 2.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
17

---

Justification:
See Assumption 2 and Assumption 1 and the extensive appendix with all
proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We introduce and formally define our approximation framework in Definition and describe the algorithmic procedure using pseudocode in Algorithm The experimental setting (Batched Auction MFG) (Definition 3) and objectives precisely specified. The various experiments where we apply our framework are clearly defined in Section 4 and full details are presented in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
18

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We provide code with both JAX and PyTorch implementations, along with instructions to execute the experiments. All experiments are seeded to ensure reproducibility. The main experiments implemented using the JAX codebase.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
ltiiss.cc/publc///gee
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All experimental settings documented in Section Details the hyperpa- rameters and experimental setup are provided in Appendix and the accompanying code includes the full configuration used for each experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: All experiments include error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
19

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide detailed information about computing resources in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: http::::////uuriii nww.npsu...../. wtcplpp..cccpuubbe cccppublc//thicccctieelllll
Answer: [Yes]
Justification: We use neither human subjects nor sensitive data, and we do not foresee dual use of our work.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Not applicable, immediate social impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
20

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We used JAX, PyTorch, and adapted code from MFGLib. No additional third-party datasets or pretrained models were used. Everything is properly cited.
Guidelines:
The answer NA means that the paper does
existing assets. The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
21

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
22

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy bettts://neurre CcCCCoofeeeeecccs///2////// for what should or should be described.
23

---

Contents
Introduction
1.1
Related Works
2
Designing Games for Large Populations: Lipschitz Case
2.1
Parameterized Mean Field Game Design
2.2
Approximating the First Order Derivatives
3
Beyond Lipschitz: Mechanism Design for Large-Scale Auctions
3.1
Auctions at the Mean-Field Regime
4
Experimental Results
Conclusion
10
Frequentl--Used Notation
25
Extended Related Works
26
Automated Mechanism Design II)
26
Mean-Field Mechanism Design
27
D.I
Preliminary Lemmas
27
D.2
Proof of Theorem
28
D.3 Proof of Lemmal)
28
D.4
Discussion of Assumptions of Lemma
29
D55
Proof of Lemma
29
D.6
Extension of Lemma to General Mirror Descent
Results on Batched Auctions
31
Extended Definitions
Preliminary Lemmas
................................
E.3
Proof of Theorem
part (Approximation in Exploitability)
................................
37
Proof of Theorem part 2 (Approximation in Objective)
49
Proof of Lemma
50
Experiment Details
54
Additional Results the Beach Bar Process
55
Additional Results on Auctions
57
24

---

A Frequently-Used Notation
General Notation
H(u)
E. u(x) ) log u(z), entropy
(2)
Ite-a. sigmoid function
Vf
E Rdixdd xd2 Jacobian function f 12 - RR
Sp-1
fx R |||| = 1], (D dimeeension unit sphere in D
Bp
| 1 D-dimensiionl unit closed ball in IR
Var
variance of random variable
e;
standard unit vector with i-th entry 1.
Ax
E - Nz= 2 0}. probability simplex on X.
Da(ulo)
= = u(x) log /o=)) Kullback Leibler divergence
(5-)
dot product.
indicator function.
& norm (on Euclidean space IR D)
1-
l norm (on Euclidean space IR D)
DiE[N] m
product measure
(xx)
empirical counts of entries of some x E X.N. o(xx 1/N E Cx.
((A)
spectral radius of matrix A E RDD
(argy(d)
== LvEx d(x, E Ay. for E Axxy.
||
=
sup 11
|| gl operator of A with norms
||
1pp
Generic PMFGs
parameterized MFG
H
horizon (number of rounds) of auction
(finite) state space (finite) action space number of players/agents ID objective
A
N
G
Eig(0, D) true ID objective in N N-player game set of r-regularized Nash equilibria parameter space
Nash"(9) (9)
θ
A
E θ, ID design parameter
II
( (H) S - AA), set of finite-horfs horizon Markovian policies. initial state distribution
po
Ph.e
parameterized state transition dynamics in N N-llayer DG
R
parameterized reward functions in N N-player DG E IR entropy regularization magnitude E II N-tuples of policies
J
expected reward of player in dynamic game G (see Definition
exploitability of player in dynamic game & (see Definition I maximum exploitability in dynamic game G (see Definition parameterized mean-field game (PMFG) parameterized state transition dynamics in PMFG parameterized reward functions PMFG one-step MFG forward flow (see Definition 2
CG
M
Ph.
R
TA
maps policies in II to H-step mean-field population flow in A (see Definition
Adjoint method:
state value function in the PMFG
%
q-value value function (on state-action pairs) in the PMFG
F
[ θ - [ [x generic policy update operator for computing NE, defined in log policy space
F Fond
mirror descent update, policy space
Fond
mirror descent update, in log-policy space
25

---

For auctions:
Gane
batched Auction
inactive state for agent not participating in the current round value space
V
amax
parameter for maximal amount of goods
parametrized item allocation function parametrized payment function utility function of bidders
Ph
Up
valuation dynamics function transition dynamics in batched auction reward functions
h.8
ra
entropy regularized (r) sum of rewards for agent i E [N]
era
entropy regularized (7) exploitability for agent i [N]
aac
Mmta
batched auction MFG
pmita
BA-MFG transition dynamics
&
Rmila
BA-MFG reward functions
action marginal of active (non-1) states; maps state-action distributions to sub-probability distributions over actions
Pwin
winning probability function, given a bid a, sold goods a and population bid distribution yー
cL,6
post allocation state distribution
mfa
entropy regularized sum of rewards for BA-MFG
Emfa
entropy regularized exploitability of rewards for BA-MFG population operator for BA-MFG revenue objective
Amta
grev
B Extended Related Works
Related works on Equilibrium Computation in Auctions. As outlined Appendix C many real- world auctions are not strategyproof. It is thus important to evaluate them at equilibrium bottbriium-bhhhh from a predictive (how bidders will likely behave), as well as from a normative (bidding recommendations) standpoint. While some simple formats have been solved analytically (43), existing hardness results for computing exact equilibria auctions [10] motivate approximate computational approaches. In single-round auctions, strand of work has used iterated best-response computations calculate equilibria [6]
68 60) g 9. Other approaches rely on gradient descent 42] or deep learning 16.55 53 For multi-round auctions,
(65] compute e-perfect Bayesian equilibria, using best response
dynamics. Others have used (deep) RL to find approximate Nash equilibria [30 559 24
66]
In our
work, by using mean-field approximations, we circumvent the curse of dimensionality inherent to these multi-agent RL approaches. Using mean-field approaches to solve auctions has been explored previously some extent. 2 32) study specific repeated ad auctions with budget constraints, and
38 studies dynamic auctions, where bidders iteratively learn about their own type.
Other MFG works. Stackelberg equilibria for MFGs have also been studied in the particular case of linear-quadratic models [54 4]. Another relevant model in this setting mean-field incentive design with major and minor players (64), where designing incentives for leader is studied for the purpose of influencing population. In continuous time, Stackelberg MPGs have been studied in applications such as regulating carbon markets [3 epidemics [1] and advertising markets [12].
C Automated Mechanism Design as ID
We note that in contrast to our approach many works on automated mechanism design focus on designing strategyproof auctions, i.e. auctions which bidders bid truthful in equilibrium, relying on the so-called revelation principle 20
The revelation principle states that any non- strategyproof equilibrium an auction can implemented an outcome equivalent strategyproof equilibrium of an adapted auction 43). Restricting strategyproof mechanisms bypasses the need
18 49
26

---

to differentiate through an equilibrium. Instead of problem like (ID) where the outer objective depends on an inner equilibrium solution, the inner solution already known-bid truthfully-aan instead the problem becomes one of constrained optimization problem, where the so-called incentive compatibility (IC) constraints ensure that bidding truthfully in fact an equilibrium [8].
While restricting to strategyproof mechanisms foregoes the need to differentiate through an equilib- rium, many real-world auctions not strategyproof. In fact, in 2019 Google for example deliberately changed towards non-strategyprod first price auctions for selling ads, citing the increased trans- parency simple, non-strategyproof format for the bidders [25]. In such cases without IC constraints, the question is how bidders will respond in equilibrium and in turn designing revenue-optimal
auctions becomes instance of (ID). which tackle in Sections Bamoonsssnnn andd
D Mean-Field Mechanism Design
D.I Preliminary Lemmas
Theorem (Rademacher) Let U CR" be an open set and f : U - R be Lipschitz continuous map. Then, f is almost everywhere differentiable on U, that is, the points on which f is not differentiable on U for a measure O.
In some cases, an explicit differentiability assumption might be useful for PMFG dynamics, which state below.
Assumption (Differentiabilityy) For all 8, E S, E the functions Pa(s'(s, a, L), Ro a, L) are differentiable on 0, L. Furthermore, g(0, L) is differentiable 0, L with bounded derivatives.
In partieular, the following simple result is useful for the derivation of AMID.
Lemma 4 (Differentiaaiiliyy of operators) The maps I, A, 9h Vi Fond as well as the map 0, π - g(0, ATT) are almost everywhere differentiable under Assumption 7 and differentiable everywhere under Assumption 2
This result is a straightforward result of the definitions of the mentioned operators, in particular, when Assumption 2 is taken, the mentioned operators are also differentiable as they the compositions of differentiable functions. In the case where only Assumption [T holds, the above-mentioned functions are also Lipschitz on every bounded domain, which implies by Theorem that they are almost everywhere differentiable.
Proof:
Finally, we state the following standard lemma from past work on the approximation of MFG dynamics by finite player games.
Lemma Assume that the conditions of Theorem 7 hool for the PMFG M and DG G, let let T. lH be two arbitrary policies, and let 0 θ be fixed. Let L ) A(=|0) be the population flow induced by æ on the PMFG with fixed parameter Take the trajectories sh ai P.,, induced by the DG with parameter A and policy profile (IT, ......
E IIN. Then,
EIIL., - 11
Lpop.ts
hh+1 pp
(SII
(S)
V
2 N
+
N
1
Σ
h-1
pop.ja
hh-i-
An.
1=
where Dn == sup, (+(s) Tn(-1s)]l,, and Leop, y is uniform bound the Lipschitz moduli of Tú, in L. Furthermore, denoting the random variables 8h, as the distributions of state-action pairs in the PMFG dynamics with population flow L and policy n,
h
|| Pls = -, -. = -1 -. = =I1l Kr.
Σ ElILA LX
N==0
where KL is the Lipschitz modulus of transition dynamics Po., in L.
Proof: The proof is straightforward extension of the approximation results due to 77 to the case where transition dynamics and rewards also depend on the mean-field flow over actions. See in particular Theorem 3.2 in (75).
27

---

D.2 Proof of Theorem 1
First, we present the bound on exploitability. As in the setting of Lemma 5 let L (L,, = A be the population flow induced by म on the PMFG with fixed parameter B. Take the trajectories
si af La induced by the DG with parameter 0 and policy profile π := (π, ........ T) Similarly, denote the random variables 5h, ag as the distributions of state-action pairs in the PMFG dynamics with population flow - and policy n.
11
V L T0) - (x())
Σ
P(sh- 0, a| (R +0
h,s,a
Σ
P(sh- 0, = a, In =
h,s,a.
p = 3, an = a, Ln = L) (, s, s,000) - R al0))
h,s,a.L
+ (F(s) s, a = a] - P(s = s. a, = a))) a +(
h,8,0
Since RL,, a0) + TH( T (+)) S + log [A], and Ra. is Lipschitz in (say with modulus
K), it holds that
IV LL x00) JG (T|))
< K Σ BlI[an - [h] + Σ
P( a, = P(s/ = a, = -II (1 log [AD < O(LVN),
+
h
The corresponding bound on (TT (TT is obtained by maximizing h as the best response to the population strategy profile in the DG, and setting ı to be MFG-NE n² for the parameter 0.
by an application of Lemma 5
We also prove similar bound for the objective value. Assume now that all N players play policy x in the DG. Then, since g is Lipschitz continuous,
|G(0, x g(0, A(T (0)) S E ((0 [La - g(0, (2
Kr 1,
where we denote the Lipschitz modulus of g with La as K₁ (with respect to norm || . Ih). An application of the technical lemma Lemma 5 yields then the ((1//))) upper bound.
D.3 Proof of Lemma 1
We first prove that if limn- Fll (0',5) () exists and (0', 5*, the softmax((")) Nashjy (0'). Since Food is a continuous function, it must hold that
Foma (on.(())"* Foma( (0', lim Fold (f', ()) Foral (6' .() <("
T
therefore Fond (0', = -- Denoting (.1(s)) == softmax (h, :)), we then have the relations F0, (h, 5, (1- (h, 8, a) + a|AA(a), 0),
Fond (0, (h,, arg max (g (s, | ((T)) 0), + - 17 '(1 ((1-T)) Du(uT(()))
HEDA
Then, for any h, holds that (", 8, a) = - (1, alA(T=/ We show that n* is then the best response to A(x²) by backward induction. Denote for convenience L = {LAh, A(x*).
R a, Iij-1) and (4]1() = Rx ..I- therefore, by first order optimality conditions, (+1)(+)s) maxi- mizes (uniquely) the strongly concave function (u, Rn, a, Lig-)) + rH(u) the
At time H - 1, (H - 1,8,a)
exp(f-IRn,ole [
28

---

simplex As. Hence, at every state at time H - 1, the policy 1-1s( is optimal. Assume now Tz. (-Is) is optimal for all h' > h for some h E f0..... H 2}. Then, by the inductive assumption, (5, a (ATr), ) π 0) is the optimal regularized q function for all h' 2 h. Since (", s, - 0% (s, (l(((T)) TT, 0), once again by first order optimality conditions, Ti is also the optimal policy at time h.
We move to the convergence of derivatives. Firstly, since qi. is given to be C* in a neighborhood of softmax((*))
(0) and p(Ocy? (-- (.-IA(softmax((())) ssoltaa) (()), < T, there exists an open neighborhood of (0, (*) where p(0,q. (., [Asofftmax(("), softmax((") 0)) < T - 81 for all (0', E for some 61 > 0. Then, since
FO, () s, a) = (1- (h, + nat alsss.aAAAssssaaa (ssottmax(()) (oftammaxx))))))smm(()))))
on U it also holds that defined by (0,a(0, Foma( (0, ()) = ama (0, c). therefore by the implicit function theorem Fond is
(),())
82 for some 82 >> O. On U, the map Famm is implicitly
differentiable in O and
Vo Food (0, () (I 0g Foma (0, Fomd (R) Foma E.
Fixing some direction E θ, define inductively the iterates
So = C' S++1 (0, St)
3o = 0, T+41 = Fomu (1) + 3o Fona(0, C))o.
Note that by the chain rule, 21+1 V. (F (0, ('))u, therefore, if show that lime-+oo 24 (a(F ond (0, (')) for any choice of v, we are done. Firstly, by the assumptions of the lemma, for sufficiently large To, it holds that Çe E U for all > To. and (* = lim St. Detining x² == de F (0,, (*)) -100) (0, (e)u, which satisfies x²' = Therefore.
)x)x + 0g (0, (.)..
|| - 2² =1 Fomd amd (0, Gt) Fc (0, (0, ())==)== + Fg 10, ()) Og Foma )00ll < a Fomal (0,Ge) ..) 0g omaal (0("))rre + 110g F (fma 5*) )are 0g F Forna (f,, )²a=²)) )=*1l
+ 110 Fo omal (0, l Og F amd (0,ll)
< || 0 Fomul (0, (t) 0g F Fmaal (,, <* )=ell + (1 52)11.r x111
+ 1100 F Foma( (f, ( Og F om (0, )ull,
which proves that x, + xx as both 0g F omd Og are continuous in Ç for Ç E U and Go + C", By the implicit function theorem, x² is the gradient of p(aa). concluding the proof.
D.4 Discussion of Assumptions of Lemma
We briefly discuss the ramifications of Lemma Firstly, the result is useful only assuming that the OMD iterates converge to NE of the MFG. NE computation in MFGs is well-studied research topic on its own, and several positive results are known for various classes MFGs. We take this for granted in this lemma, NE computation is not the main goal.
Next, we note that the lemma suggests that the derivative of (T-approx.) a valid first-order oracle provided that the Jacobian of Food has bounded spectral radius around the NE induced by 0. Importantly, for any PMFG, T-tepp objective approximates the fixed-point gradient provided that is sufficiently large. For more structured settings, the result can be strengthened to permit 7 = 0, for instance, the derivations in (48) readily extend to the case where H 1, |S| = 1, and the reward function R. is monotone in population distribution. We leave future work to generalize this for monotone PMFGs with dynamics (i.c., for PMFGs with > 1).
D.5 Proof of Lemma
Let θ = D. Z = RD and assume the functions F 0:0x + Z and g e x Z + R are differentiable. We define é + R
((0) = g(0 (6++((0)) (4) == (1 - =FF(C.))))(
v= O.....
(1)
29

---

for some So constant. Clearly {(O) is differentiable; our goal is to efficiently compute Vol(o).
Define for any sequence of (row) vectors (ar Ji for a, + the function
L(0, (ax)]_m) 9 (0, (r))(())
Σ a. (0)+1 ())) 7 (0,)c(0))
1=
T
a (0, (.)) =g (0,(TT++00) ar (T+1 (1 ar) Co(0) - 1) Σ
T
+ Se 1a--1-(1 1 nzr)at)
Σ
Since for any (ar)zzo holds that L(0, (a)) {(O), we have the identities
(0, {ar) ) = Vol(O), dn. L0, {a = 0 Therefore, for any sequence of functions ar (0) that depend 0, have
= 0
(a)) (0)
+ Σ v (aa)) da.
L(O, L0 (a)) = 0gL(0, (at))
We will therefore compute 0gL(0, fa ) with suitable choice of a, By simple derivation:
0gL(0, (ar)=o)) =0:9(0, (0)) + 0g (r))
ar V - 17) vo (0)
a 0g,
Σ
(0,
aa. -1-1-(1- (1=))
Since VoCo 0, Co is constant, rearranging the terms yields:
LgL (a)) = =(V5o((r+220)) V
F(, 0og(0, (r+1(0)
t=
a (1-1))a
177 (aa00((0
Therefore, we pick
aT = (Vg((T++1
8 = (1 - 17) + 0 F (.))),
we obtain the equality
Vol(O) = T0, (ar) = 1) a,00 (0, ((()) (r)))))))
(2)
Most importantly, Equation permits the computation of Vgl with T with only caching the variables G. Namely, the forward system Equation (I) can used to iteratively compute CT+1, and the backward system only requires evaluating Jacobians at the current step, meaning other than G. the memory requirements are kept constant.
In case memory bottleneck, & can be cached during the forward step every 3VT steps for some constant 8, meaning only ((VT) memory needed. In this case, during the backward step, G. will need be recomputed every ((VT) steps for ((vT) OMD iterations, maintaining the (TT) time complexity. will introduce tradeoff between time and space complexity.
30

---

D.6 Extension of Lemma 2 General Mirror Descent
Lemma analyzes the adjoint method under the specific entropy regularization scheme. Let h : R be a strongly convex distance generating function, and Vh. RP - RD the corresponding mirror map. Then, the generalized mirror descent update rule can be written (in policy space 11 C ())xXAA;
Vh(m++1) = (1 TT) Vh(m) + 17 T. (0)), == ......? T.
Defining the iterates G == ( we obtain the similar update rule
((0) == g(0, (Vh) (Vh) (0)))
(+) = (1 (. F0, (Vh) =-= 0....,
which reduces to the case analyzed in Appendix [D5 by the definitions
F(0, ((()) = F(0, (Vh) (Vh)- g(t, (r+1(0)) = 9(0, (Vh) (Vh) ((++1(())))
E Results on Batched Auctions
This section presents the formal analysis of parameterized batched auctions introduced in the main text. We also provide rigorous statements and complete the proofs left out in the main text.
Appendix E. provides formal definitions of the settings omitted in the main text and useful auxiliary constructions to assist the proofs. Appendix F.2 presents a collection of auxiliary lemmas that support the subsequent analysis. In Appendix F.3 we prove the first part of Theorem 2 establishing an upper bound on the exploitability mean field policies under the no zero-dominance condition. The second part of the theorem, which addresses convergence of the mechanism-leve objective, is proved in Appendix E.4 Finally, Appendix [E.5 provides the proof of Lemma 3 which establishes the Lipschitz continuity of the (entropy regularized) q values under full-support policies.
E.1 Extended Definitions
Additional useful notation. To streamline the proofs, also introduce useful notation. For any arbitrary finite set X' and scalar & E R>o define the sets:
8 x = {deRs RxERR VEE X: d(x) 2 0, Σ -
=
ZEX
A = (deR' Ve X: d(x) 2 0, B <
Σ d(z) $ 1}}
ZEX
A = (dER* X d(x) 2 0, Σ d(x) $)
zeX
For R.Y. where X' has total order, denote the cumulative mass function Sz(d) = Ex'ze d(z'). For some d E Axxy, define the marginal distribution
Marg (d) == Σ d(x,)) E Ay.
xEX
For E [0, 1]. define the threshold bid operator Th. : A - Aas
(d) == max ( {a A: Sd(d) a, d(a) > 0) U (ao)),
where ag is the smallest element of A. For d A also define Th, (d) The (Margs(()))))
We define the operator E. A A + VXA, which maps a matrix state-action distribution L to a matrix T,' where each entry L' T'(s, a) represents the expected probability mass of agents in state s
who chose action and did not win an item this round, given that goods are allocated. Formally:
if Th(d), 0
E. Ev d(d Te d(s, (d)) if = Th(d),
Ea(d)(s,
d(s,a)
otherwise
31

---

Sa is well-defined as Evev d(s', (d) 0 whenever >> by definition.
Using the operator Ea, define the post allocation operator T.. A Av. which maps sub-probability distribution d over active state-action pairs to the post allocation state distribution. That
(L)(s)) = (D.())).))
REA
The operator a. which governs the transition of the population state distribution after item allocation, can be expressed in terms of Y, by explicitly accounting for the inactive state I. Specifically, let e AsxA be a state-action distribution and assume alv- (d) < 11-+(d) Then I' AsxA + As defined as
(a) (d) if E V, i
(d) = -EEeAd di a)) a
where d_1 denotes the restriction of dl to active states V.
The BA-MFG is parametrized PMFG, where both the payment function and the allocation threshold function are parameterized as og and ph. Throughout this section, we assume these parameters are fixed and omit them, writing without loss of generality or, Ph instead.
Definition 5 (Batched Auction MFG (BA-MFG)) A Batched-Auction MFG (BA-MFG) is MFG defined by the tuple Mmsa (S, A, H, no: [P H-1
Th=0 {R ( ) of discrete state space S [U[L}, discrete action space A, horizon H Noo. initial distribution μi E S, transition dynamics piu S x A x ASxA - As and reward functions 12% : x Ax ASxA + [0, 1]. The transition dynamics poda and the reward functions Remla depend from the allocation functions {0x h==
H-- the
dynamic functions {wa (ukJ-=n 0 the payment functions (pa3n-0 Define the "winning probability" as
H-1 and the utility functions {un
H
if if E. Lis,
L(S
Pwin( (8, L, 1,41
a Edd E Eo' al).aa) End L(s.a)
otherwise
For the allocation and valuation transition define the operators Pa ASxA + As, As x As as
(L()(s)) = E. (1,,a)(1= - - (8, 0, a, L, aly
if #1
[((1) + Es Evs Ins Dwin (8, a. L. (L))) otherwise
Tw(()= = Σ ((2)w(-12.)) (),
2ES
Define also T Amja as
T Ta ()) T (Tar, (s))))),
Amji(T)) = (T.- To, m.), T2).., m))
The transition probability and rewards can be written as:
pmfa (s' (s'1s, a,, L) = Pwin a, L, an (v- ww 1, L,n (L)
+ (1 - Puii a, L, an (v w)) I (L))
17 (s, a, L) (8 a, L, anly (L)))ul(s,p (D))).
For π E IH, 2 and L [L M the total expected (entropy regularized) reward
V (L, TT) = EE
Σ R (s,a, Ln) +HH(MT(sN))
sn 1~ppte an
NNote that this way of writing 1',, Amta consistent with the MFG definition.
32

---

For policy т E HH we denote with L = (T) the induced state-action distribution, with yt' the induced state distribution and with 5 the induced hidden state distribution, with &% Fos (LT)- Additionally, we define with Pa the transition probabilities associated with the item allocation dynamics
(win a, L, a(u -()
if if s' =
a, = (1 Pwin a, L, a(v (L))))
otherwise
Then, the total expected (entropy regularized) reward can also be expressed
H
V L. π =
E
R (s,a, LA) + TH(TT((A))
900-100 Compoennaa(en.eee Pay as Lb)) $nt T (ba))
hm0
Definition (N-player Batched Auction (N-BA)) N- player batched auction (N (N-BA) a dy- H-1 namic game Game = SN, A, H, Ho: { {P [ {R H-1 of discrete state space VU {1}. discrete action space A, horizon H E Noo. starting distribution Po E S, transition dynamics Ph: SNN A - A and rewards functions Ry, SN A - 10, The transition 111 the 1H-1 Let (a'...., a²) E A the joint
fulnctoiinfuunccionn dynamics Prt and the reward functions Rig depend from the allocation functions {am]
h=0 dynamic functions functions {wn)) HH-1 the payment functions {ph H-1 )= and the utility functions {un)
s = (s) ......Nj E S denote the joint state of all agents, and action profile. Assume items are allocated to the top bidders according to the submitted actions, with uniform random tie bre-bieaknng at the allocation threshold. This induces a joint allocation probability kernel PN,a SN A - ASN formally defined as
ViE Mu S =1}, x' =L. U E T : 2 = (a(v) .N [W/.
PNa(z(ssa) = ((N1--
ViE C, - ='=
otherwise
where v E, Eni a maxfa A: ΣSE[N] Laiza,si11 2 [a(r) T (j [N] a' a", *1}. W = {j : a² > a", s² FL} and L = fi E [N] a² < a st *1}. The marginal winning probability and the rewards, similar as its corresponding MFG can be expressed as
Pk (1 a) =: =: Σ (2)(s al) (s" a², o(, (olu-)(((saa)))
N
Rg (ss = (s a', as, [Nan(v +(o(s.a))ll ) (s', (a(sa)
N
We define with H.,, the N-player discretization of Rathe
R (8, a, L) == Pwin(8, (8,,0, a, L., [Nou(u N
vo v-
Note that if L(s a) = 0, the reward nemla (8, a, L) is not defined. Additionally, observe that
R Rame: a) R (s', af as)
For a strategy profile n E IIW, T 2 the (entropy regularized) sum of rewards of player i E [N] is defined as
#-1
VjElM af wOyh (x()) Za ~ PN (Bn an), -x= ΣSEINi 24 math En) ESEIM 9//.
auc
(T))
= E
Σ
mlde (sh, oh, En) + (H(TT((s))
NNN
h=o
exploitability E ETT = max J ( +T
(TT)
33

---

E.2 Preliminary Lemmas
We present several important lemmas that will be used later to prove the main convergence theorem.
Lemma (Sensitivity of Ea to the Population) Let a E [0, 1] and let d, d' E A VxA Then E. is Lipschitz-confimuuus with respect the Enoormm, with constant I:
[d) =. (d))lz S I|d - d' 111
Proof: It is straightforward verify that E,, is continuous. We verify that it is also Lipschitz continuous with modulus 1. Assume a > 0, as otherwise (d) the identity map and the claim is trivial. Denote the bids by A = (1,-... A), and let (d) = Es Ea'z d(s', a') with
SA+1(d) and (d(d) Eeev d('s a). For fl............................ 1}. define the regions
Ra {d E A (a 2 Sa+1(d)
On the region Ra the map (d) is differentiable, in fact, for d E Ra it holds that ā = The (d) and
if
(d)(s,,)))
Sa(d) d(s, a) (a(
if a = à otherwise
d(s.a)
We calculate the Jacobian of Ea and upper bound its operator norm ||VEa||1-> given by the max column sum | 11Eal11>11 maxe,0 Eera aal We upper bound the column sums corresponding to 8, a.
Case 1. If a then 8E, (d)('',) for any (s',a') # (s, and 8E (d)(s.o 8d.a
1, therefore the
8d.a
column sum is
0E a a))
(d)(s)
=1 1.
Ddsa
Od
Case 2. If a then
e (d)l''
O a' # a, therefore
Odsa
0 (d)
F (d)) a)
8 (d)
FE, (d)(
+ Σ
Odea
Adsa
Od.r
Od
x¹
s'
Sa(d) + +d(s,a) ra(d) ra()) Sa(d) +
ra(d)
ra rd(2)
d(s' a) rald) (d(() + 1,
[d
since all terms in the absolute values are nonnegative if ā Tha (d).
Case 3. If a then only the rows corresponding the active action à has nonzero gradient, and
(d)
(E, (d)
Σ Eee
d(s",a) d(s. a) =
ad
Ōd.a
To conclude, it holds that on any arbitrary region Ra.
0E (d)
|V = max 5,a
Σ
=
adaa
s'.0!
Therefore, /V < 1 on all regions Ra, and E. is non-expansive in the & norm.
Lemma (Sensitivity of E., to the Allocation Parameter) Let d E A arbitrary, let 01 02 S [|d]] arhitrary. Then
[E., (d) (d)ll < Jai -2g.
34

---

Proof: As in Lemma 6 let A = (l)...,A, and let Sa(d) = Ev Ea'oa ((s',a') with
SA+1(d) 0, and Ta (d) Evev des'
For a E {1...., + 1) such that ra(d) > 0, define the partition of the interval [0, [|d[[a] into the
intervals
R4 = {a E [0, [|d]]]] Sa(d) 2 a S2+1(d)).
On the interval Ra, the map E. (d) differentiable a, and holds that Th, (d) and
if a a = a otherwise
(d)((s,)))
ra(d) Sa(d) d(s,a) a)
d(s.a)
Then, again, we upper bound the operator norm of the Jacobian (in this case, gradient):
(d) aa)
V.E.(d)) Σ
Σ
d(s', d(s'sa)==) 11
da
ra(d)
So V [.=a(d))2-1 I 1, implying the claim of the lemma.
For completeness, we state the simple corollaries of the above two sensitivity analyses the following.
Corollary (Lipschitz Continuity 3) Let d, d' E A A [d]]l),,,, and a' E [0, (dd)l))) arbitrary, then
[Ea(d) - E (dd))l)) & I|d d'I12 +aa-aa
Proof:
Let d, d' E A E [0, [d and E [0, ||d' [I1) arbitrary. Without loss generality
assume |dd]a 2 |dd' then by applying triangular inequality we have
(d) - E. (d')ll < (d) - -.) (d)ll + || (d) (. s la a'l l|d d'11,, where the last step follows from Lemmas 6 and 7
Corollary 2 (Lipschitz Continuity of Y Let d, d' ADx [d]]]), and a' e 10, [Id"|1)) arbitrary, then Ta is non-expansive in the l norm, that
(d) (d'('") I laa-dl d' + ||d d' [
Proof:
de d' E A1 a E [0, [|]]l1), and a' E [0, (1'1l))))) arbitrary, then
- (dd")
Σ E. (d) Σ Ed
aed
Σ E (d)
(d) ((E (d')l")
aEA
The upper bound follows by the result of Corollary !
Corollary (Lipschitz Continuity of T.) Let d, d' E ASxA and suppose the threshold function
a: A + [0, 1] Lipschitz continuous with constant Ka and satisfies the feasibility condition a(v) < ||lla for all v E A Then,
(d) - [a(d')l & (Ka 1) d''11-
Proof: By Corollary 2 and the Lipschitz continuity of it follows that:
(d) - (dd' s la(v (((v=((d)) a(v ((((=~(('))) (d')) + ||d d'Il2
< Kalld d' ( + [|d |||
In the next sequence of results, we deal with the stability of winning probabilities given by the function Pwin- general, Pwin easily seen to have discontinuous jumps, however, local stability result can be shown if the NZD condition holds.
35

---

Lemma 8 (Stability of Winning Probabilities) Let A = fai, ag...., ..k be a finite set of actions ag, and let E A =1 For any [0, 11, define the winning
with total order aı < 02 <
probability for action a E A as
Ea'sa uaa)) 2 ar if E Ea'za u(a') S a and a >
Pwin (a,
a La'sa v(a')
otherwise.
v(a)
Assume that o, satisfy the no zero-dominance property (ie. for any a E A. v(a) = +
Ea v(d') < a(v)) and ||l|l > 0. Then for all v E SAA a' E [0, 1), E A, Pwin satisfies
Puin (a, v, a) - Pwic (a, a S Cv.a 1/111 + Cr aa - a').
where:
if==0 =0
minf
if Ana 0, #1, >
min(p(a"), ).d..a)
Cua
if An, 0,a =1,0>
min(u(a" min(u(a-).A...)
if An. =0,a #1,a>0
min(v(a").v(a
if Ara =,a==1,a>>
min(F(a")}
and where a² == Th, (v) is the threshold action, a is the action just below the threshold (a = ak-1 if a = O3 for some k and a =I if a1), and Au, == -iimagg a
Ea'za u(a'))
Importantly, Co.a is finite in each case if v, L satisfies the NZD condition. The proof, while notionally dense, works on a simple idea: in general, Pwin incorporates discontinuities where the winning probability of action below the threshold might jump from 0 to 1. However, this does not happen locally when there is some probability mass on a just below the threshold action. Note that when ||/|| &f and NZD holds, it holds that v(a") 0, and v(a ) > 0f a" * ai and > O. Furthermore, by NZD, if a = 0, must hold that v(ax) > and a = ag by definition. Define the useful constant
Proof:
Avaar max(+/ut" 1/(a-)), 1/vla"),
if A a 0, An, = 0, a #1
Ara = 0, =1
which will be the radius of the open set around which there are no discontinuities of Pwin-
First, we show that [a,in 14, a) (a, a')l < Cuaaa a' for any a'. Without loss of
generality, we can assume that a S [| a < ||r| as Pwin(a, (a, (.) pwin (a, 1, min(a', ||]||
for any a' by definition, and minfa, ||<[|]] min(a', [| la a'). If la a'l then a' E (a - 5, 0, a 8) since
(RRR) R On the interval (a - 8,a + 8) Rzo, Pwin is continuous for any
(a, For a < a", a a a=: Pwi (a, v. v') = =0,
For a a" Pwin (a, U. v.) = 1,
if Eo'za v(a)) S a', otherwise.
Pwin (a", ,,,) For a d'
a' En'ra v(a')
v(a))
if Ed'sa u(a') 2 a', otherwise.
For a = = a if #L: Pwin v, ,,,a)
a - v(e
v(a))
Moreover, from above, Pwin is almost everywhere differenniable in a' in this interval with Opwin (a, v, a))
< (max(1/u(a>) !/(a")); , if a" # #0,ax> 0
8a
[Lu(a"), otherwise
as in this interval the "active" threshold action will always be either a" of a Therefore,
Pwin (a, a)
Pwin (win(a, a'll Cyaaa - a').
36

---

If on the other hand la a²l 2 8, then
[Pwin V, a) (aa))-Pwnnae u, v, 1155515551 d'I S C2 So in both cases it holds that [pwin u, a)) - Pwin(a, U, v,)')l S Cuaaaa - d'|.
Next, we show the stability in v. Once again, assume that ||2/ - vII2 < 6. On the open set
{v/: 1|l'' ~ < of the function (win(a,,,a) is once again continuous in v' for any a, and almost everywhere differentiable with
Öpwin (a, v.,,),)) Ov (a')
a =1 or ara=
p(aa)
min(a(a"))v(a-) if 31,
for almost every v'. Therefore, it holds that
|Pwin (a, v', a) - Pwin (a, U, a)) S Cuallu v' 11-
On the other hand, if 1| v/ll 2 then
Pwii aa, 1/ a)) (a, v. $1 1/
To complete the proof, we use the triangle inequality: [Pwin(a, (a, v/, a') - Pwin(a, v, a)l S (a, v.a') Pwin va, + P (o,na, - pwinla, a')l
The proof of Lemma 8 can be adapted to handle action distributions with full support. In this case, a refined version of the first part of the argument shows that the winning probability is Sopschizz-continooe with a constant bounded by mintula ),ma") where a" a aat are actions around the threshold. Consequently, for policies with full support, i.e. nn 2 c all E V. a E A, and some e > O, the deviation in winning probability is bounded by [I-Ommsae
Remark
v/Il
Lemma 9 Let n' E As be two arbitrary state distributions, and let n, E IT be two arbitrary policies. Define the corresponding state-action distributions L, IL' ASxA as
L(s, a) == (())T(als).
L((s,a)= =z)))
Then, it holds that
- [ S sup | - (-1s)]l | 1l
Proof:
We compute the total variation distance:
L'Il
Σ Ip(s)=(als) p (a)s))
Σ (m(s))(als)) (())=(((l)) (())) - -1 (1))) (als))
s,a
Σ m(s) (als)) - <'{ass)| + Σ (m(s) - n²(ss) Σ क (a|s)
= sup || ا (-1s) n' (-1s)]1 + ||I 1'1,,,
where the last line uses that Σ. n' (als) = for all s.
E,3 Proof of Theorem part (Approximation in Exploitability)
The theorem considers BA-MFGs with Lipschitz-continee
reward, dynamics, and utility functions. Let K,, [0, 2) denote the Lipschitz modulus of the state dynamics W/. K, the Lipschitz modulus of the payment function Ph. K2 the Lipschitz modulus of the utility function 24 with respect to its second argument, and K2 be the Lipschitz modulus of the allocation funciton ay, That is, for any E V. E V, E P.P.P' E Rg0-
(s, un (s. S Kn. lp -p'l, Ipa(a, v) - (n KG 11 l/11, (an(v) an((v)) < K, -1l 1|vvvv/1l v'11-
37

---

The composed function (s Pa v)) then is also Lipschitz with modulus KuK, Kp as
[n, pm (a, v)) - (, (n (a,() - K. lp,(a, - pn v/1 KuKp 111 v/ 1/111.
for all v, E E
Additionally, let Bp be an upper bound on the absolute value of payments, i.e., (a, 2) I By. and let B, be an upper bound on the absolute value of utilities, i.e., |u (s. p) I Bu. for all s, a, h. Such upper bound always exists if U/ Ph are continuous in since A is compact set.
The argument proceeds three steps:
1. First, we bound the expected deviation between the empirical distributions and their mean field counterparts. That is, show upper bound the deviation EE | [alla
2. Second, we show that for policies satisfying the no zero-dominance property, the expected transition probabilities associated with item allocation, under both the mean field and finite-population settings, differ proportionally to the deviation in population distributions.
3. Finally, we bound the exploitability of a single agent when all other agents follow a policy that satisfies the zero-dominance property with respect the mechanism.
In our analysis, we also make use of the population distribution & after item allocation at round In the mean field setting, this is defined as & == a. (La), where LA E A is the state-action distribution at round h, and the operator aa,, captures the expected post-allocation state distribution under the mechanism (e.g,, by marking winners as inactive). This quantity serves as the input to the state transition function W/ in the MFG dynamics. In the finite-agent setting, we denote the analogous empirical quantity by fu. representing the empirical distribution over states immediately after allocation. We also define the random variables (2)) } 2 =1 if agent not active in round l (i.e. s = agent i won the the auction in round h, and z), s) otherwise. With this definition,
N
+ As
Finally, we define the constants used in our convergence analysis as follows. Define
K, = sup [wss {) wisss Kg = Kw + K.. 8,8'
E.3.1 Step 1: Expected Deviation of Empirical Distributions
We derive explicit bounds on the expected deviation between the empirical distributions and their mean field counterparts. particular, we bound the deviations for the state distribution and the state-action distribution.
Lemma Let Mmja = (S,A, H, po, (Pmfaa corresponding finite-agent Butched Auction model with N agents, Gases which is approximated by Mmga Let ग (=A))=-....HHL..eN)) E IT denote the joint policy of the population. Denote by Ph E As the empirical state distribution and by Lm ASxA the empirical state-action distribution at round h.
Jh=0 (Rer (emfarH-] H-1) define BA-MFG. Consider the
Let E Th arbitrary, and define the associated mean field state-action distribution flow I. Amta (T), with corresponding marginal state distribution p. = En (.),.a)) Then, for all h.
(0. H- -1}, 1}, the following bound holds:
S N
E 1 --Talll] SBI 1mlll]
TT
+
N
[E[N]
38

---

Proof: We decompose the deviation:
E L Tnlli (oNten) S
1 E[In how +B [|
(n)
(6)
We bound the two terms separately. For ( define I. E ASXA as L(8,a) (a(s) =
N EiEN 1 (a)s). We (almost surely) have:
| B.Ln b, I 1
LII [ LI11
Σ
(+((ta((al))) - (n(+) (B(LaN - Lll
sESaEA
I || Pulli + N
E [t(as))) (a(as)))
iE(N aEA
| Pulla
Σ
-
VE(N
For the second term (4), by applying Jensen's 's inequality, we have:
Ln E(Znl(sh,
[shha
= ΣΣ
[[n(s,a) - (s
#ES AEA
Σ Σ
Var an (shhtn
aEA
Σ
(1 (als))
SESREA
Applying Cauchy-Sehwarz's inequality, get for any S:
Σ aEA
Σ
- -1)s)(11x((aas)))
Σ
Σ
(d]ss)([ (a)sss))
iE(N]
aEA iEN
IN
A
Σ
Σ
(clss)
aEA
S
(s).
By integrating this result into the previous computation and using Cauchy-Schwarz's inequality, we get:
E
|| Ln - ELZn
ΣΣ sESaEd
Σ
(1 - (als))
N sES
SE(N].8i
A N
A N
Σ (s)
S
#E8
#ES
Combining the upper bounds derived for terms (L) and (D), obtain the desired result, as E [1 Lnlla]] = E
I L L, 11 (s
Lemma 11 (Deviation Between Empirical and Mean Field Population) Let Mmja (S,A, H. Pos (P" H-1 ( be BA-MFG. Let (an)H-1 H-1 1H-1, and H--1 denote the allocation thresholds, transition dynamics, payment, and utility functions, respectively, from which {P ( H-1
{wiJn=o {
H-1
H-1 are derived. Assume these functions are 1h=0 and {R Th=0
Lipschitz continuous, with respective Lipschitz constants Ko, Km, Ky, and K,,
Consider the corresponding finite-agent Batched Auction model with N agents Ganes which approxi- mated by Musa Let ( H11, 11 denote the joint policy of the population. For
39

---

each round h, denote by Ln E ASxA the empirical state-action distribution and by Pr E As the corresponding empirical state distribution.
Let π E IT be an arbitrary policy, and define the associated mean field state-action distribution flow L, = ( with corresponding marginal state distribution 1o, = =L 1.7 a).
;,),,,))) Then, for
all h E {O..... H - 13, 5 it holds that
(K&(1 + Ko)) visI
E I1lu% - Pn]l1]] S
1 - Kę(1 + Ka) VN
+ Kg (Kę(1 + +aa))
S
1
SIIA
+ (1+ K
Ke Kaa)
2
N
N
+ Σ (Ke (Ka + -1))=
1
Σ
112
W cch
EE[N]
if KT + Ka) # 1, and
S
SSA
VIS
1
[lleR - [mlli]] S (h + 1)
+ hKg
VN
VN
2VN
N
IT
Thell1.
N
R<h
iE[M]
if (5 + Ka) 1.
Let [sh]n= h=o.... {at, - and {=f (=:))=o....fHI..ee as in Defini- tion We prove the lemma inductively over h. For h = 0 we have 14 = Mu = E[ Let X, Eie[N] 1 (s)==)) which by definition X, binomial random variable with parame- ters N and (s))). Since it is a sum of independent Bernoulli random variables, its variance is Var Var[X,] [X,] (1) po(s)). By using Jensen's, we upper bound the expected absolute deviation for each state 8 EV
Proof:
B[(mo(s) ( S v [Vrr[[o(s]] (o(s) - [o(s))
( N
N By summing over all states V and applying Cauchy-Schwarze inequality, we get:
Po(s) C.S. VM
Billoo [1]
Σ (s) م=){))]
Σ
VN
SEV
SEV
Next, for h O, we compute upper bound for the deviation at step h 1. In particular, we analyze the conditional expectation
E. [11/2+1 1 (1
s E [1lpT+1 B Bis+ H
| + [llĀn+ E H [
(A)
almost surely, where [ We upper bound the two terms (n) and (A) separately. For (D) we have:
v= are the states of agents after the item allocation in round h before.
(0)
Σ E (1))+1()) - Elpa+ 1 (s) [EH
<
Σ
v Var (x)+
SES
For arbitrary E S, noting that En {2/) measurable,
Var [Tn+ 1 (s) [+
1
Σ
- (ssss( (s) -1)
N E
Enlo'usssssss Ew)
N2
S'ES
s'ES
By the Cauchy-Schward inequality, we have
Σ
Σ
Σ Σ (n(s')uus)s'' (1))))) |S] =|S]-
NES
S'ES
SES ''ES
40

---

Therefore, we (almost surely) have
Σ (n(s))())ss( vss
(0)
N
VN
e'ES
For (A) it holds that
(A) = E. [11 Bl
[ = 11 1
= = ( - rr(
Kw
K.
|1 - EA
2
where in the last step we applied Lemma 2.2 from 775. and taking expectations, we obtain
Merging the upper bounds for (4) and (D)
VIS VN
K₂ 2
[ll - mhttlh]] S
+
Kw
|15 [1l11]]
Next, we bound the expected deviation between the post-allocation state distribution in the mean field model and empirical counterpart the finite-agent system. Specifically, we consider
| Ex ||| where 57 oo, (47) is the mean field post-allocation distribution induced by
policy म. and En is the corresponding empirical distribution in the finite-agent auction, computed from realized allocations rather than the operator I a.. Denote the o-algebra induced by {s) af as Fr. for simplicity, then
|KeT 111 &
E
Fulll
F
+ [IG. E F
(0)
:
We upper-bound the two terms separately once again. For (V) we have:
(9) = [1 -
= E
En (8) (+)
Fr
L
E
(n(s)) (+)
[rn
.EV
We establish an upper bound on the absolute deviation for each state 8 E V. Let E V be arbitrary. Given the empirical state-action distribution LA E ASxA, the corresponding empirical state distribution is given by marginalizing over actions: Ay EeEA a)). By definition of Thn there are (s) agents in state at round h. Denoting these agents as i,,..., (N)x we can express (s) as:
(s)
Σ
N
Two key observations can be made regarding these indicator variables:
1. The indicators are negatively correlated due to the structure of the auction. To illustrate this, assume without loss of generality that the first M agents have not won yet, i.e., sf, # for all i [M]. Since the number of items in each round fixed, when conditioning on T.p, we have
Σ 1
which implies that the indicator variables 1 - are negatively correlated. Consequently, their complements 1 = = - 1= are also negatively correlated. This implies that any subset of these indicator variables retains this negative correlation property. Specifically, for every state the random variables = j [N (s)], are negatively correlated.
41

---

2. Since these are Bernoulli random variables, their variance is at most 1/4.
It follows from the two observations above that the variance of fa conditioned on Fr, can be upper bounded almost surely as follows:
Var (1()s) Fr
Var
Fh
Var
Fh
N
N
2 =8
JElNTA( (o))
LIEENTA (+)
Th (s)
War
Fh
S
N2
2 =s
4N
Using Jensen's inequality, bound the absolute deviation using the variance:
(
E [a(ss) - (+)
- Var
(n))
Fr
4N
Using this result, together with
inequality, we can further bound (9):
(V) = ΣE [n(()) - (+) -
Fr
(s(s)
C.S.
v
4N
2VN
.EV
sEV
For the term (4), applying the result of Corollary 3 yields:
(0) = E
ElG [ullll|FA
||Tan an (IR) Tan (f+))l + [B[[.]] T Ta, (Tn)lla
< lan(u -1 (L,)) -nn( ((EN)) + +1,,, - -Inllt 11 + N
1
s -Kal(v--(LL - -v -v-- (w=+([n)ll: + 114 La +
1 s (Ka, + 1) La + N'
where the second to last step follows from the Lipschitz continuity of an while the last step follows
from [1 (L)) (v- ([n)il | - L, 1I Additionally, [[B[Ex - Ta, (In))la N comes
from Lemma 7 as [a
Nov -v-) $ 1.
Combining the upper bounds for (9) and (4) we get:
[[IIsT [[]]]
V 1
$ (Ka 1))
|1 Inlla]
2
N
A .
| N
VD 2vN
SKa + +1)
E
[III [all]]
+
Σ
||
milla
N
N
sE|N]
where the last step follows from Corollary
Combining this result with the bound on B[l fi+ 1h1], we apply induction on to conclude the proof of the lemma.
Corollary (Deviation Between Empirical and Mean Field State-Action Population) Under
the conditions of Lemma 11 for all .O...., H - 1}, holds that:
| - Lalls] < (K₃(1 + k4))++1
VIS
SIA
E
Ke(1 + Ko)
VN
VN
(Ke(1 Ka))*
V
1
+ Kg 1 Kg(1 Ka)
+
2/N
N
Σ (Kg (Ka 1
1
Σ
|
m 11,
N
NSh
42

---

if KK + Ka) # L. and
E L Talli]
s (1 11)
VIS
VSIA
+ hkk
v
S
+
1 N
VN
2V
Σ WSh
Σ
T
-
[E|N]
if jf(g(1+ + Ka)= 1.
Proof:
The upper bound is obtained easily from Lemmas 10 and
11
E.3.2
Step 2:
Expected Deviation of Winning probabilities
We derive explicit upper bound the expected deviation in winning distributions between the mean field auction and its finite-agent counterpart, under a single-agent deviation from a common policy.
Lemma 12 (Expected Deviation in Allocation Dynamics) Let
Mmja
(8,A, H, Ho: (Prii H-1 H-1 {Ri ) be a BA-MFG. Let H-
{Wi)H-1 \H-1 {ph)
and {un)h=o H-1 denote the allocation thresholds, transition dynamics, payment, and utility functions, respectively, from which [P Jh=0
(P H-1 and {R H-1 are derived. Assume these functions are Th=0
Lipschitz continuous, with respective Lipschitz moduli Ka, Kw,, Ky, and Ku. Consider the corresponding finite-agent Batched Auction model with N agents approximated by Mmsa. Let
= (=0.),==....HHI11.. E I denote the joint policy of the population, and let Top As be the empirical state-action distribution at round h.
Let 1h arbitrary, and define the associated mean field state-action distribution flow L Amjo (7). Then, for all h E {0,..., .....,H H - 13, the following bounds hold:
E [P (6 oh, L (LT)) Pwin(sh, ahe Ln, INv INv--(( (wn-+ [(b))))] {
N
S Ciaan E | Tall]] + Cry.n 1 Ka +1 N
and
E [1Po, (8hs aho LR) - on (Sn, an)
< 2C Ly,oo E | -Eulli]
20,
+ Cr 1 K. + N
where for arbitrary state-action distribution L ASxA and a: 4 10, 1]. the constant Ct. is defined as in Lemma
Proof: For the first inequality, we have
Pwin sh, oh, LT,, 2- (LT)) - (hin(sh oh, Ln, INn [(En))]]]
N
P. Pl o/ = Iin I.] Pwin (sho a/. L,, v (IxR) - Pwin (sh ar Ian INW-+(In))
N
8.0.L
CLy.on
< Σ Pfs)) s, of, = a, Ln 1|O2y,an 11,%% L1l1 +
Ka +1
8.0.I
CLy.a + K2 + N
SCI. E. | Rnall]]
where in the second-to-last step used Lemma
43

---

Additionally, for the allocation dynamics .N... since each state E V can transition only either to itself or the inactive state 1, it follows that:
Pa (sh, ai. LR) P (sh, an)lla] = D [1] (s|s), ag. L,) Pi.an (s|Sn, a 1l1]
SES
E [I (s aii Li) Piv (s), (sh: [n]lla]
[I] Pan 18); an [,n Piv ( |sh a [1a]
2E [] Pa.. (1 18), aj (7) - Pi (1 Ssh |n)]l1]
Since the marginal probability transitioning to the state corresponds to the winning probability, the bound follows directly from the first inequality.
E.3.3 Step 3: Exploitability Deviation for BA-MFG
Finally we prove the absolute difference in expected reward due to single-side policy deviation.
Theorem 4 Let Maja (S,A, H, no: [P ) Jh-0 (1e ( ) be Batched Auction Mean Field H-1 {pm) and (ux ) denote the allocation thresh- olds, transition dynamics, payment, and utility functions, respectively, from which {Ph H H-1 and H-1 (T% Th=0 are derived. Assume these functions are Lipschitz continuous, with respective Lipschitz constants Keo. Kw, Kp. and Kw.
H-1
Game (BA-MFG). Let {am))=0 {whSh=0)
Th=0
Consider the corresponding finite-agent Batched Auction Gaue with N agents, which is approximated by Mmju. Let II an arbitrary policy satisfying the no-zero dominance property. Then, for any policy π E II it holds
Vija (Amga -
1T ane
(TT, H. ,...., 7
VN
N - rimes
Define the random variables {sh oh 2/, [e(N) (I.... along with [- (Pt ) and ( as in the definition of the N N-player Batched Auction (see Definition 6 Here, sj denotes the state of agent at round h, aj. its action, and 2/, its hidden state following the al- location step. The random variables Ln. Ar, and &n represent, respectively, the empirical state-action distribution, the empirical state distribution, and the empirical post-allocation state distribution at round h.
Proof:
For the Mean-Field Batched Auction, define (sa, an 2n ) and action of representative agent at round h, and zı. denotes its post-allocation hidden state. These evolve deterministically according to the mean-field population flows 1, ,,",, 8 induced by the population policy म.
HH-1 where 8 and an represent the state
We divide the proof into three steps:
1. We show that for every E {O..... H 1} we have:
|[(5 = - 1PP ( -111
501,, L, (Ka + 1)N
Σ IE [1
Inilli] (Ki +)+ +2C22,an)
VIST
1
hK,,
2VN N
2. We show that for every E {O...., ... H - 1} we have:
E [ (e (Sh, L,,) 12 ( (s), og. Ew]l
Cry.n Bu
(K₂ K, + B, P,C ..
on |1 Lulls]
K2 + N
+ Bu PP(s P(s -111.
44

---

3. In the last step we combine the results of the previous steps to prove the man claim of the theorem.
Step 1: We prove the inequality by induction on h. For the base case h = 0, we have [[|ss Pish = IIIl1 = O, since both distributions are equal to the initial distribution Noo Now, assuming the bound holds for some h 2 O, we show that it also holds for round h + 1.
[[P[s = ] - Pish+1 1111
Σ 2i6
Plzz = =, E))n(Z) -
Σ Plan 2|wa (2,
22 Eh)
By adding and subtracting Σx,e P(zh = 2, En g/wn (z, (7) = E. PP = 2]wn(z, (2, 5%), and
applying triangular inequality, we get
[P(sh+1 -] 13-PP -P(s -II1 S
Σ
Plz = E, E) (wn(z;{) - ww wn xmi
Σ (F(z =] P(z 2) =)) (2,
+
S
BIIET [1] + ||PÍz -] - P|z -]112
The term FF[IET [.
using the same derivation as in the inductive step of Lemma further upper bounded as
can be
E I<T
Gulls] s (Ko + 1)E | - Eulla]
[
vMM 2 +
1
N
Finally applying a similar reasoning we can upper bound [|P[z] = - P(z --1l1- ||p(zn = 1 - 1P(= = -]1l
Σ pls = s. a = al alPN. N.a (s, - Σ P(sn = =, = a. a] (s, a, 1%)
s.a
6.0
By adding and subtracting Em. P(ss = s, s,a al Pon. (s) a., 11,) Σs, P(s = 8, 8.05
Pon (s, a, L and applying triangular inequality, we get
|P|Ez = -1 - Piz = -ll1 S
Σ
P(sa = s. = alI||P (s, - -aa , ,
8.8
+ Σ Pan (s, 17)11PP(s = 04 al -P(s) s, a = a]]
S ||| P IIPNNau Naw (Sh, an) - -Pa (0/, ah, 1N)l
+ [8h 8) - -P(s = =|1 Σ Tn(a|s)]| Pa,, (8, a, 17)l-
Applying Lemma 12 it follows
||p|2
Plz
-11/2
Cry,n |[[[s, 1 P[s). -111
S $20 10
E
| L. 11
+2 K, + 1N
By combining the two bounds, we obtain
| [P = 1 - IP(s/+1 = -II1 S Km (Kn + 1)B [|LA - -Lalli]
+ VI
1
+ N
2VN
2C17.on
+ 2C LT E [112% - -Eulla]
(Ka 1)N
+ |P[(s = - - = -111--
45

---

Applying the induction hypothesis completes the proof for round h + 1.
Step 2: We prove the inequality by using the result obtained in step 1. Let h {0...., H 1511 13 arbitrary, then
[ ( (sh, ahh L Re (3/, a/,, Ln>ll
E El (sh, on, L%) 12 (sh, an BRDl + BiRg (6): a/. L7)
RNN, (8/. u/ Ln)l
(M)
(6)
The first term (L) can be upper bounded by
Σ (P(sh s) -0 Pist
sl) Σ Ra Rh (s,
L.) s Bulli[ss = 1 -Pist. -111..
For the second term (4) we have:
(A)
Σ
P(sh 8, a = a, L |1 (s, a, LT) Re (s,
,,a.L
Σ
Pis = 8, a} = a, I un|uu (s. v - - un ph un,
s,a.L
|win [pwin(s)s (0h ai 17, 2 ((,T) Pwin (8/- a/s Lai IN ((all
BaE
S Kukp Σ Pl1) =,,0 = a, T = L111 B1l1
8,0.
+ BaCLo on E -[122--Enn - -Eulla] + CLy,an Bu Ka + N
CLa.an B₁
I + on )E - +
K1+1N
where in the second to last step we used the Lipschitz continuity of u p and Lemma 12 Combining both results we get:
CIT. Bu Ka + 1 N
Rmla (Sh, Oh: 1 RNN. (5), an Ln]ll S (KaKp + B. BBC .0. )B 1 Emllz]
B,, . P[s) -ll1--
Step 3: We now combine the results from the previous steps to establish the final bound stated in the theorem.
Miaal (Amiia T)
J (ST, ...... T)
H
Rmfaa (sh, an, LR) + TH((T((SH)) N, (s}, o/. Inn - +H(TT())))
E pmffa (sh, an LT,) + +H(TAA
R H oh Lx) -T
We proceed by bounding each term individually for every round h. Leth (0.... H 1} arbitrary, then
E pemal (sh, ab, (T) 7 H((T(()))) remaa (5), 1 Ln. 7HL( (+)))
< (s (sh, ah. L%) Riffa
(s) ah. In)] + E [H())()s)) H( (st)))
The first term is bounded using the result from Step 2, while the second term can be handled as follows:
E [H(T)((s) - 7((TA( -
IP P[sh s) - P(s = s)
< [P(SAA = 1 - P( = 111 log(lA4))
46

---

Therefore the (entropy regularized) absolute difference in rewards at round h can be upper bounded by
E
Ri (Sh. Oh,
R.N, W.,h(55 (s/ az Inn +H((T((s)))
CI...n Ba
I (KuK, B,
1, cap )L | - -Ealla]
+
Ka N
+ (Bu + t log( (o)(((A)))][PPP))
PP(s) -IIl..
By applying the bound on [P[sh = P(s) = -111 derived in Step 1, and summing the per-round deviations over h, it follows:
mf (Amfa (Amfa(T), Jmic (T,, nr ,,..., गT
N times
H-1
CiT.on By Ko + N
Kg + BaCI
17.n Ton )
1 Inlls]
A=0
#-1
20 1. (Ko + 1)
+ (Bu + (og(((A)))
E
|1 - -Lw (Ka + 1) 20 (3,a) +
h=0 &hhh
(H
S
+ (B, +og(((A)))
Kw
2
2/N
N
In particular, Corollary implies that the total (entropyyreegularized) reward difference is of order
O
Conclusion and Statement of Result. Let Mmia be a BA-MFG with Lipschitz-continuous -H-1 {w>, [
H-1 ) {on) /== (pa )= Let wy E πH be a policy that satisfy the no zero- dominance property. Let further assume my is 6--MG-NE, namely
HH-1
M max Vi x') VITi (A 18).
x'elT
Then, for π (Io...., TT8,, we have:
max (T'''TT', n T - auc (TT)
x' x'Elli
max J (T' , -i)- - J (T)
d'lll
+ VT (Amta(TT)) ( x²) - ViT (Amfa (T6), x') Vinaa (Amta( mT) - ViT (Amia( (TT) TT)
max VTT (Amia (T6), n²) Vitta (Amta (TT), T8)
"Elll
+ VIITa (Amia ( n²) - J ( . [ + Vinaa (Amita (6ss)TT5' σT) J (xr)
C2
C2 = 5
5 8 +
N
N
47

---

In case Kę(Ka + 1) # 1, the constants C₁ and C2 are given by
H-1 C =
K + +BBCI and) 1 (Ke(1 + Ka)) h+1
(VIS) + VISILAi)
- Kg(1 + Ka)
h=0
H
(KuKp + Brp on )E 1 - (Ke + +Ka)a
1 Ke(1 Kn.) visl
h=0
H-1
Kw (Ka +1) + 22220,2..0 aw))
Mich
(Ke(1 + Ka)) 2 Bu + +og (AAl)
(VIs) + VISIIAA)
1 Kę(1 + Ka)
(Kş(1 + Ka))*
+ +Bu + + log|
V(S)
1 - (1 + Ka)
K VI81
(Bn + (ogg(LA))HH(HH
1)
H-1
(Ke(1 + Ka))at1 1 (Kç(1 + Ka))
+ Kg 1- - (Kg(1 + Ka))² 1 (Kç(1 + K())
C2 = 2 Σ
(K Kp + B.orra and
h=0
Bu C1.s5,00 ,nk
+2
Ka +1
h=0
H-1
(Kç + Ka))
+ 2(B, + T log (A))
Σ
Σ
(Ka + +1)+20 an
(Ke(1 + +Ka))
h=0 Wich
H-1
1 (K((1+Ka)))
+ +2(B, + + |Al)
Σ
Σ
(Kw + 1) +1)+20r,57 20 an
1 (Ke(1 + Ka))
4=0 h'
H-1
20 1.ggaa
+ +((B, + tog [Al)
Σ
Ka +1
h= Wich
+ (Bn + - log AA) H(H-1) 1).
In case (K(Ka + 1) = 1, the constants C₁ and C2 are given by
#-1
C = Σ
(h + 1) (KaKp + BaC ON and (VIST v
0=
#
Σ h=D
h (KuKp + BaCry on )
H-1
+(B + log (A)
Σ
Σ
(h'+1)
(Ku(Ka 1) +
20 aaw) (V1ST + v(S|IAA)
A=0 Mich
H-1
+ +(B, + ++Tlog/AA
Σ
Σ n'
(Ko +1)+ 20 20 (7 K KEVIs)
h=0 hich
K Vis
+ (B, + +Tlog((A)))((
2
48

---

H-1 C2 Σ h=0
C
(KuKp + Bu ni .on
) + 1 Keh) + Bu Ko +1
H
+ 2(B + log((-A)))
(io + + 20 20, Inn an (h +1 + Kehl)
h=0 Mich
H-1
20 15..0 saw
+ 2(B. + + +=lgg((AAA)
Σ Σ
Ka K1
A=0
+ (Bu + H 1).
Remark 4 For policies with full support, the Lipschitz conslant associated with the winning prob- ability is of order 2, as discussed in Remark Consequently, the constants C₁ and C2 scale as
1-(Kg(K,, O I I-Ke(Ka+1]
when Kg(Ka + 1) & 1, and as O H$) when Kg(Ka + +1) =1
Explanation of Constants. In the above expression, the constants represent key components of the BA-MFG dynamies:
By and K2 are the bound and Lipschitz constant of the utility function u respectively.
Bp and Kp the bound and Lipschitz constant of the payment function p respectively.
K denotes the Lipschitz constant of the transition function w.
Ka the Lipschitz constant of the allocation threshold function a.
K2 sup,, (s, w(s', {)
Kg Kw + 2 K,
CL. is the Lipschitz constant of the winning probability function evaluated at the distribu- tion L. assuming L satisfies the no zero-dominance property. For its precise definition, see Lemma 8
T is the entropy regularization parameter.
E.4 Proof of Theorem part 2 (Approximation in Objective)
We show that, under Lipschitz conditions, the objective computed under the mean field approximation closely matches its expected value under finite population of agents.
Theorem (Convergence of the Mechanism Objective) Let Sx + R. be a Lipschitz- continuous objective defined over the class of Batched Auction Mean Field Games (BA-MFGs). } h=n
Let Mmja be BA-MFG with Lipschite-comtinuuus {un},
H- {wa, hh0 (o1) H-1 H Let
πt) π (
be the joint population policy for some π E 11 Then:
(Q(Ama((T)
G(T)) = O
VN
where G(TT) = Elg(( EEl((tn))
Proof: We use a decompasition over the support of È and apply the triangle inequality:
[9(Amta G(T)) =
Σ P L/TT] (g(Am - -(())))))L)))
L
Σ P = L|r] [1T]lg(Amtaa ((
Σ ppL [lm] Lll1
K2 ([) +
where K2 is the Lipschitz constant of g. The result follows by applying the bound from Corollary
49

---

Lemma 13 (Lipschitz Continuity of Expected Revenue) Let 9rev denote the expected revenue ob- payment functions {p=J 1H-1 and allo- H-1 be two arbitrary state-action 1H-1 Let L = {L, HH-1 and L' he0 )=
jective. Let Mmia be BA-MFG with cation functions {arA h-=0
distribation trajectories over H rounds. Then,
Brev grev (L) 9rev (L)) S (B, K.) + -
1-LL-1I
where Bp is a uniform bound on the absolute value of the payment functions, K2 is their Lipschitz constant, and Ko. is the Lipschitz constant of the allocation threshold functions.
Proof:
The expected revenue, for L [Th H= can be rewritten using the operator =
H-1
Ire LD) = Σ Σ
(Ln(s,a) - -o Ph (a.v)
h== 8,0
To simplify notation, we define
(L) = L E.()),
representing the residual (unallocated) mass at each state-action pair. Applying the triangle inequality:
19rev (L)
Shev (L')
S
Σ
Ean (c. a)) pn(a,v-t(Ln))
((n))
h=0
(1)))
H
Ban(v (Ln))))
- Ean(u sagn)( (Ln)))
h=0
8,4
Σ h=0
Σ
Using the boundedness of the payment function and the Lipschitz continuity of the allocation operator E., the first term can be bounded by (2 Ka) EiE || 4/ For the second term, the Lipschitz property of p implies a bound -H K, T. 1l Combining these, we conclude that the revenue objective 9vev is Lipschitz continuous with constant B, + Ka) + Kp. and satisfics the bound
1shev (L) - 9sev (B,(2 (aa)) + K2) L'll2
Corollary (Convergence of Expected Revenue) Let geev the expected revenue objective. Let H-1 H-1 [an) [Pi)
Mmja be BA-MFG with Lipschitz-continuoxr {up J h=0 {wn] (TT ...... x) be the joint population policy for some E TT. Then:
H-1
Let
Irevv (Amgia Ann(((TT) Gre =
VN
Proof:
The result follows by combining Theorem 5 and lemma
13
E.5 Proof of Lemma
In this section, we prove that the (entropy regularized) f-functions are Lipschitz continuous with respect to the population policy, assuming full support. begin by showing that population flow is Lipschitz in the policy. Next, we establish that both the transition dynamics and the reward function are Lipschitz continuous with respect to the population distribution. Finally, we combine these results to derive bound on the Lipschitz constant of the (entropy regularized) q-functions.
50

---

Lemma 14 (Lipschitz Continuity of Population Operator) Let
Mmja
(S, A, HI po, (1 H-1
{ (Re J be Batched Auction Mean Field Game (BA-MFG). 0h
Let {an)h=o, {wa) H-- {pa)a=0 1H-1 and {wn)h=o denote the allocation thresholds, transition ( R-1
{ H-1 and {Kg Th=0 dynamics, payment, and utility functions, respectively, from which {Ppt Ti20
are derived. Assume these functions are Lipschitz continuous. Consider two arbitrary policies n, aT' E HI. then
||Amfa (T) Ammta (T)) S Σ
Cee(1 Ka))* | T//
N'sh
We prove the bound inductively. Let L := Amfa( (T) and L == Amta(aa) denote the population flows induced by policies x and n', respectively. Similarly, let μM and n denote the corresponding marginal state distributions.
Proof:
For h 0 we have μg Mg 14o. Therefore by Lemma 9 we have 1|45 - LØ 111 S II Tollı.
For >> 0 by applying the result of Lemma
we have
| L 11 S Th+1 + 11 - 1h-1ll1.
We then bound the variational difference in state distribution:
1 1 |11 (5P) - (5% 1l1 s Kellsh - 5% llz
Kgl[To. o.. (L)) - T,,, (L, Il S Kg(1 + K.)1I LØ 1l,
where in the last step we used Corollary By induction over h the claim follows.
Lemma (Lipschitz Continuity Transitions and Rewards under Full-Support Policies)
Let Mmsa be BA-MFG with utility functions {wkth=) transition dynamics H payment H-1 all of which are Lipschitz-continuuu with
HH-1 functions {ph) } h=00 and allocation thresholds
constants Ku, Kw: Kp. and Ka respectively. Consider policies n, x' II with full support:
that is. for all s E S, a E A. and h E O...... 1, we have (a(a)s) > E and oí (a ()) > e for some
constant 0. Then
[R (s, a, I.7) RRh (s, a, [
Bu
+ Kukg))
E(Ke(t (KE(I+ Ka)) || - T/1l11.
(1 Oemax)e
Ngh
and
||ppof (8, 1.7 -
(s, a, I. )l
2
Ka +
Σ h
(Ke(1 + Ka)))~a(11 Thell.
Ommax)
Proof: Let n. T E TH be two arbitrary policies with full support Let L = A and L Am)) We then bound separately the rewards and the transition probabilities.
We first bound bound the absolute difference in rewards, let s E S, E AA arbitrary, assume fL. else the claim holds trivially, then, by applying triangular inequality we have:
pape (s, a, LT Te (s, L%
< Bu (win a, L7 an (v-1 (LR)) - Pwin(s, a, an ((W (L m))
(n (n (-(,v--([T)))) un (8, (-(x,
Bn,
ma [ L || K,K,,lI IA
where the last step follows by Remark and the Lipschitz continuity and u. By Lemma 14 the bound for the rewards follows.
51

---

Similarly for the transition probabilities we have:
Ph (s, LT) Prolic (s, a, L7 I
(=| on (1.7 1)l Pas (2|8, 1.7 Pan (z18, a, 1.7))
Σ Pan (2|8, a, 1x) 100 (2, Tan (a)))) - wh(2 aan (I.h )
(11
Pa,, (s, a, LR) Pan (s, a, LJ)l1 Kw Tan a (IT) - Ian (I,). Ill1.
From Remark 3 and Corollary B follows
| (s 1.,)
( a, I. 11/2 a1-xmmx)e
Ka +1) 1 12,11, 11,,
by Lemma 14 the bound follows.
Lemma (Lipschitz Continuity Regularized Value Functions) Let Mmja be a BA-MFG with
H-1 and alloca- utility functions {un h= transition dynamics [wn)h=o 18-1 payment functions {ph F
H-1
tion thresholds {ar [o all of which are Lipschitz-cominnous with conslants K K Ky. and Ka, respectively.
H-1
Let n, T' E II be two policies with fill support, i.e., for some > 0, TT(als), (als) > for all h, s.a. Let VT [s|L", x) and Vī (s) T²) policies x and n', defined recursively as
denote the entropy-regularized value functions under
(s T) = (T( Σ (n(as))
(s, as) + PM L
aEA
where (LT) =
Amfu is the population distribution induced by policy n.
Then, there exists constant C > O such that for all h and all S, the following bound holds:
(s L" Vi (s| x²) S C1| x/111-
where C= HH2 when Kę(1 Ka) = 1, and C 0 1- 1-(((--KK) when Kg Ka) #
Proof: We prove a stronger inductive bound that implies the result of the lemma. To simplify notation, we introduce the following constants:
B = Kg(1 + Ka).
== B, + T log((AI).
= Je + K2 KnKp.
B.
91 = (B, + rlog((AA))
[I-amae]e Ka + 1).
We also define the following h-dependent quantities, which will be used in the inductive argument:
A == (log((5) + 1) (H B,
G := 9o 9i (H h-1), 1),
A Im -m/1l1-
We proceed by backward induction on the round h, and show that the following bound holds:
H
H-1
(s I IF,,) m) V/ LT
xx
Σ
An Ar
GN Σ gh- K"CW
52

---

For h = H by definition, the value function at round H is zero for all states, i.e.
(s = V (s|L*, T)
Assume that for value function at time h + 1, V the upper bound holds. We now prove the same for V The regularized value function is:
Vi (*] , = r H()m(())
Σ (A(als)) ( _
Then,
(i Tt (s|L" I
<THH(T((S)) H(() (s))
Σ ma Σ (4 ,T)
For the entropy term
()) we have
- [H((=(()) - H( (+)) < (log(2) + 1) 1| (s) 7/ (+)1l
By applying triangular inequality we can upper bound (4) as follows:
(A) Σ Ta(ass) (als) (s, a L" ,-)l Σ ((s (s, a r')l
The first term can be bounded as function of H and the maximal absolute utility B.:
Σ (als)) x' (als) 9 (s, alL", x) S H h) (B, + + rlo(([A)) [| - n/ (s)ll
where the term F llA(( comes from the maximal additional reward from the entropy regularizers For the second term we bound the absolute difference in functions:
19 (s, a|L", T) 4% (s, alL= ,T))
< Rm (s, a, [T)= - (s I
Pm (8|1s,,, a,, LT) - pm (5'1s, LI L
pmfffa (s'ls, a, LW VIT (s'ILT Vi ,t))
< [a (s, a, LN) - R (s, L
+ (H B) + T log( (I]) Phula (s, a, LT) Prul a, 27)31b
max
T) Vi++1 (s L m')).
By combining all intermediate bounds and applying Lemma 15 we have
LL - L" ,T') An + GA
gh-W A
h Sih
max
V
(s'
L TT)
Vi 7'),,
by induction the bound holds. As next we compute the global Lipschitz constant.
#-1
H-1
(i LT m) (8 1.T
m3)
Σ
An An
Σ Gw
G
Σ
gh h" AN
W=h
M'=h
R"Sk"
(A)
53

---

For ( we have:
H-1
H-1
#-1
Σ
Ap AR S Σ
An S Ao
Σ
A
N/=h
h=0
4=0
For (A) we have:
Σ
Gn
Σ
Bhh't
gh'-K" AN"
Σ
Gh Σ
gh-h
Do
W=h
N"SM
h=0
WS
H
H-1-N
AN
Σ
Gw++y3
H - 1-K
H 1 1-
AN
GR
Σ
3 91
Σ
1=0
3=0
H-1-M
GR
Σ
9
k==0
Using the definition of the geometric sum, and observing that the constants G₁ as well the nested geometric sum decrease as h increases, we can further simplify the bound by pulling out the leading terms. For * 1:
H 1
H-1-k Σ 5=0
1- 1-3"
H H-1
GN
B s 1 - 3
(go + gi(H - 1))
Σ A
M==
h=0
while for B = 1:
H-1
H-1-h
H
Σ
GN
Σ
3 S H(g + (H - 1))
Σ
An
h'=0
1=0
h=0
Combining the results (for 1) of (D) and (A) we have:
Vi7 L", Vi L 7 (T(og( + +1) HB 1- 3"
#-1
1- 3 (go + g1 (H 1)))
Σ A..
For 8 1 the geometric term is replaced by И. By the definitions of B, go and 91 the claim follows.
F Experiment Details
Implementation Details. The experiments were implemented in JAX and PyTorch, the code is provided in the supplementary material. We implement the adjoint method in JAX. For the PyTorch implementation, some code was adapted from (31] All error bars in experiments are one standard deviation away from the mean.
Hardware and Compute Time. We run our experiments single NVIDIA H100 GPU with an AMD EPYC 16-core CPU. One run of AMID for 1000 iterations takes 6 minutes, apart from the experiment (A8) described below with long time horizon Il 100, which takes 20 minutes for 1000 iterations. The beach bar process experiments take roughly 3 minutes for 1000 iterations.
Parameterizing 0 in MM- For the beach bar process, we parameterize the per state payments as 0, = Pmax sigmoid(Es). where Pmax is the maximum per state payment and the unconstrained parameters & E S are learned via AMID.
54

---

f Parameterizing 8 in Mmta- We parameterize Pf. and sold goods a as residual neural networks sharing a base. The base network, J has dn = - |A| imputs consisting of one-hot encoded time vector ex. | vector of bid distribution =ー and remaining goods at round ====0 ). For the input vector Zin R the base residual network
denoted rh. (given by amax defined as
Σx h-1
C/2 Fin -ー
E
R
1g#+d+1
rh
( = ReLU (W Tin + +b
h (2) ReLU (eLU(((())) (1) 1) + b(2) V(2) Fin + x) R dhidden.
Ybuse
The goods to be sold this round are then computed by:
aA = r x ow Ybase + bb). bg). E. R.
and the payments functions for bids is computed then by:
(3) = ReLU ybase + b(0)) + Ubase: (4
A - o (((1)) E ERA-1
i-1
paymentt, 0,
paymennt,
Σ //g i= 2.....
Note that this parameterization ensures that the payment rule ph is a monotonic increasing function of bids W(1), (22 Reliiddon (II+d11), (222, W7(3) E Rdhidden xchiddon W e R(1-1)xduaeew and
The parameters 0 of the mechanism overall
8(1), ((2), c22), 6(3), Wg E Rduiaden, b(4) RA- A-1 by E.R.
Baseline algorithms. For zeroth-order baseline algorithms 0-SGD and O-Adam, we use the standard 2-point (biased) gradient estimator
Gampooxe (0 + Unero2) Cipprrox (0 U2ero 2)
D2,
2uzero
where 0 E DR. is uniformly distributed on the sphere Sp-1, and Uzero is tunable hyperparameter. This estimator satisfies the well-known property
E E = V E E
Sppeox (0 + u))
2 Uniform(Bp).
That Va is unbiased estimator of the gradient of smoothed version of the function GT approx The bias tunable by the parameter M2rro- with smaller values corresponding to less bias but potentially higher variance in estimates. Since single evaluation of this gradient estimator takes 2 forward passes over GT spproxx its run time is comparable to that of AMID per iteration. For the baseline sample a perturbation from the D-dimensional standard normal approx
ANNEAL, each iteration, distribution. After evaluating Oppprox (f), Gipprox (9 + ())meal)) GT (0 a.) for the tunable
hyperparameter Ganneal O. ANNEAL updates 0 to be the best among 0, 0 ammeaal 8 ammeall
Hyperparameters. All hyperparameters for the baselines as well as AMID are presented in Table For a fair comparison, perform grid search range of values for the parameters for all baselines and take the best run after 10 repetitions. In our experiments, AMID robust to hyperparameter choices while zeroth order methods require some tuning.
F.1 Additional Results on the Beach Bar Process
As mentioned in the main body of the paper, we first present the payment function 02 learnt AMID after 1000 iterations. As before, we report these by using a slightly higher OMD iteration step Te 500 than used for training, to demonstrate the robustness of our method.
55

---

Parameter
Explanation
Values
"
Adam/SGD learning rate
3e-5, 1e-4, 3e-4, 1e-3,
le-3, le-2
U Zero
Noise magnitude for evaluating zeroth-order gradi- ent estimator Vo. for O-SGD and 0-ADAM Perturbation magnitude for ANNEAL
le-3, le 1,-2, 3e-2
anncall
le-6, 6, 1e-5, le-4, le-3.
1e-2. 3e-2
Entropy regularization
le-3
ROMD T
OMD learning rate
10
OMD iterations in (7-approx.
400
Teal
OMD iterations for validation
500
dhadden
Hidden dimension residual network parameter-
256
izing payments and sold goods
Table Hyperparameters for experiments on auctions.
100
State (S)
Figure 4: Payment function s + 0, learned after training with AMID, where payments are bounded
on [0, 1/2].
A bottleneck in the beach bar experiment is the magnitude of payments 0., which is restricted be bounded [0, 1/2]. We also report the experiment when E [0, 4/s}s below (i.c., when Pmax 0.8), in Figure 5 As expected, the population distributions L,, are smoother and closer to uniform in this case. both cases, AMID behaves as expected: the exploitability of T'' iterates of OMD is consistently low throughout training, suggesting that the T step approximation objective remains close a NE throughout training iterations (with exploitability exploitability of the policy induced by the T repeated iterations of OMD is due to the fact that in the beach bar experiments, tuning payments yields NE distribution closer to uniform, which is also the initialization of OMD iterates.
0.02). The fact that the
56

---

10-1.0 1.8
2.5
10 10-1.8
600
10-2
500
0.2 0.4
0.6
Itenatoon (10
State (S)
32
Figure 5: Payment design with AMID in Mab with larger payments. Left: objective and exploitability throughout training iterations. Middle: learned payment rule after training with AMID. Right: population flow in time after learning payments.
F.2 Additional Results on Auctions
We first analyze 3 further auctions with nonlinear utility functions for bidders. Namely, we take (A1) presented in the main body of the paper where 4, Ao Uniform(S)) Omax 0.8. |S] = |A| = 100 and bidders are single-minded with no evolution in valuations s) other than to transitions to I.
(A4) Risk-averse utilities formulated by
up(s.p) 1 cxp( B(s p)}
1 exexp
exp
where take 1. (A5) Risk-seeking utilities formulated by
un(s,p) expl p)} -1
expx
where we take ==1 1. (A6) Hyperbolic time discounting, which discounts future rewards, where the utility at time h is given by:
P Uy u p) 1 Ah"
where take À the time discount factor.
Across utility functions, AMID manages to beat all baselines. In our experiments, we also observed significant qualitative changes in both the mean-field Nash equilibrium and the payment rule when nonlinear utility functions are used. We show NE payment rules suggested by the neural mechanism NE in Figure 7
Experiments regarding the impact of horizon. We report the impact of agent regeneration and time horizon by evaluating AMID on the following auction setups:
(A7) H 6, agents regenerate with probability (that is, they never transition to 1 even when they win a round), linear utilities for bidders, Qmaa = 0.8, Mo(s) oc x for = 0.9, dynamic values with w(s'ls (s) expf (1.2s = "2>²/2z²) for 0.2.
(A8) Long horizon H 100, Qmax = 5, linear utilities for bidders, agents regenerate with probability 0.015, (s) x 7 for 7 0.9, dynamic values with w(s'(s) (s) exp (1.2s = / for
σ 0.01.
The results reported on Figure
57

---

0.3
0.2
0.2
Revenue
Revenue
0.25
0.2
0.1
0.15
0.1
0.2 0.4 0.6 0.8
1
0.2 0.4 0.6 0.8
0
0.2
0.4
0.6 0.8
Iteration (10*)
Iteration (10*)
Iteration (10*)
AMID
0-ADAM
0-SGD
ANNEAL
FIRSTPRICE
Figure Irev throughout iterations of AMID and baseline algorithms in settings with nonlinear
utilities for bidders (A4-6), left to right.
Mean bid (a)
Peyment (P)
Mean bid
0.5
0.5
0.5
0
0.2 0.4 0.6 0.8
0
0.2 0.4 0.6 0.8
0.2
0.4 0.6 0.8
1
Valuation (s)
Valuation (s)
Bid (a)
Figure Left: mean bids NE H" after training with AMID on the risk-seeking utility experiment (A5) for h E 2, Middle: mean bids at NE at 6* after training with AMID on the hyperbolic time discounting utility experiment (A6) for {0, 1, 2,2.3). Right: payment function in setting (A5) at the bids induced by the NE policy at 0* for h E (0, 1,
General objectives. Finally, we explore the impact of optimizing over more general objectives other than revenue. We define the objective
Jmnx (0, L) = grev (8, L) + Jefficiency (0, L),
where we define Jefficiency as:
H-1
Jefticiency (6, (),
Σ Σ
au(s,a)pwn(s, Lns (z (Ln)))u (a,v-1(Ln)
hm0 (s.a)EVXA
We modify experiment (A1) and evaluate our AMID on the following setting.
(A9) H nl Uniform(S), Ommx 0.8, and single-minded bidders (after winning stay 1) with no evolution in valuations s), otherwise. The objective function is fmix-
The results reported on Figure g
Experiments with static on and payment rules. Finally, to verify the impact of the mecha- nism having access to bids on at round h, we run final experiment where the mechanism is independent of bids, which call static mechanism. In this case, we simply parameterize (a) sigmoid
(xp(0
and (a(
ensure no more than Omax hoods Omax En ("
are sold and the payments never exceed the bid. The parameter space is then = (0()), ,(2)) for g(1) R[H]xA g(2) E R!H), For static mechanisms, we observe much less significant improvement over the first price mechanism in general, which most likely originates from better allocation of goods over time when there are dynamics such as regeneration.
(A10) H static mechanism parameterization (independent of +), each agent regenerates with probability 0.3 at the end of every round, and has a linear utility function.
The results in this setting reported in Figure g
58

---

1.2
0.4
0.8
Objective Jaix
Reventi
0.3
Revenue
0.6
0.8
0.2
0.4
0.6
0.1
0.4
0.2
0.2 0.4 0.6 0.8
1
0
0.2
0.4 0.6 0.8
0
0.2 0.4 0.6 0.8 1
Iteration (10*)
Iteration (10*)
Iteration (10%)
AMID
O-ADAM
0-SGD
ANNEAL
FIRSTPRICE
Figure 8: Left-middle: Ivev throughout iterations of AMID and baseline algorithms in settings
(A7-8). Right: Imix throughout iterations of AMID and baseline algorithms, in setting (A9).
Experiments on approximating exploitability. We also report our attempts to measure the true N player exploitability gap suggested by Theorem when N is finite. For the first price mechanism, we compute the MFG-NE on the auction setting (A1) introduced in the main paper. Then, fixing N 1000, simulate trajectories in the batched auction by setting the policies of 999 agents the MFG-NE, and train PPO on the last bidder. In this setting, we were not able to achieve a better mean reward for the last bidder than the MFG-NE. This suggests the exploitability is close to 0, we report the expected reward achieved by PPO throughout training in Figure g
0.4
0.4
Revenue
0.3
Reward
0.2
0.2
0.1
0.2 0.4 0.6 0.8 Iteration
20
40 60
Sampled games (10²)
Figure 9: Left: Revenue throughout training in the static mechanism setting (A10). Right: PPO episodic rewards trained on the batched auction (AI) with N = 1000 agents, all but one playing NE. Blue is the MFG best response expected reward, red PPOs expected reward throughout training.
59


Reviews:
[{"review_id": "eNc8XOqpi0", "reviewer": "Reviewer_MR4R", "summary": "This paper proposes a method for incentive design in multi-agent systems. The authors introduce the Adjoint Mean-Field Incentive Design algorithm, which combines parameterized mean-field games and adjoint differentiation to compute gradients and optimize incentive design at scale efficiently. Experimental results validate the theoretical findings, showing that AMID outperforms first-price auctions and existing benchmark methods across various auction settings.", "questions": "It would be helpful to include numerical comparisons of the optimization efficiency between AMID and baseline methods, such as the optimization time for different numbers of agents.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths：\n- The writing is clear \n- The combination of mean-field approximation and the adjoint method enables the optimization of complex incentive design problems.\n- The paper provides strong theoretical contributions by proving that under Lipschitz continuity assumptions, the mean-field approximation for incentive design converges with a rate of O(1/N). The authors extend this result to non-Lipschitz continuous settings, particularly focusing on sequential auction settings.\n\nWeakness：\n- It would be helpful to include a comparison of the convergence speed between AMID and the baseline algorithms, especially as the number of agents increases.\n- There are still some formatting issues, such as inconsistent spacing in lines 295-299.", "was_revised": true, "final_justification": "The additional experiments provided by the author addressed my concerns. Considering the opinions of other reviewers, I maintain my score.", "rebuttal": "We thank the reviewer for recognizing the strengths of the work and the insightful questions. We respond to the weaknesses and questions in order.\n\n## Weakness 1 and Question: \nThe PMFG framework makes it possible to solve the incentive design (ID) problem independently of the number of agents. Without the MFG approximation, the problem **quickly becomes intractable even for moderate $N$**, due to the high computational complexity of computing and differentiating through Nash equilibria. The PMFG construction helps handle this complexity while still providing theoretical guarantees. For the bias-efficiency trade-off due to the PMFG approximation and corresponding AMID algorithm, we refer the reviewer to Figure 2 and Figure 3 (left plot) in our submission.\n\nAll the methods compared in the experimental section are built on the PMFG framework to address the ID problem. The per-iteration cost of AMID is similar to that of the other methods, as AMID requires one forward and one backward pass, both of which have similar computational cost. In contrast, zero-order methods require at least two forward passes to approximate the gradient. As a result, while the per-iteration cost is comparable, AMID converges faster because it uses the exact gradient rather than approximating it.\n\nThat said, we agree that a numerical comparison of optimization efficiency would be helpful to have in the main paper. In the camera-ready version, we will update the appendix to include actual optimization runtimes for each algorithm, giving a clearer picture of their practical performance.\n\nTo illustrate the effectiveness of AMID, we provide the following measurements on **single iteration time and memory usage** of naive backpropagation and AMID using the JAX implementation (on the setting (A2)). The results indicate clearly that naive backpropagation has intractable growth in memory and time as a function of $H$, and in fact becomes prohibitively expensive on a single GPU for moderate $H$. Here, ❌ indicates that we were not able to run the naive algorithm.\n\n| Horizon $H$ | Naive (time, seconds) | Naive (memory) | AMID (time, seconds) | AMID (memory) |\n|-|-|-|-|-|\n| $H=5$ | 0.19 ± 0.02 s | 2760 MiB | **0.09 ± 0.01 s** | **560 MiB** | \n| $H=10$ | 0.25 ± 0.10 s| 8746MiB | **0.208 ± 0.08 s** | **586 MiB** ||\n| $H=25$ | 0.71 ± 0.15 s | 16960MiB  | **0.67 ± 0.12 s** | **826 MiB** |\n| $H=50$ | ❌ | ❌| **1.72 ± 0.41s** | **1076 MiB**  |\n\n\n## Weakness 2: \nWe thank the reviewer for pointing this out. While we are not sure which specific spacing inconsistency was referred to between lines 295–299, we will carefully review this section and ensure that any formatting issues, including spacing and alignment, are corrected in the camera-ready version."}, {"review_id": "xem7AOv7HP", "reviewer": "Reviewer_DFyx", "summary": "This paper studies the incentive design (ID) problem in multi-agent systems. The paper approximates the finite-player game with a parameterized mean-field game (PMFG) and subsequently optimizes the incentives in the PMFG. The authors show that under Lipschitzness, the PMFG objective well-approximates the original problem with rate O(1/sqrt(N)). The authors then propose an algorithm (adjoint mean-field incentive design), which differentiates through the iterated equilibrium operators. They then show empirical results on auction settings.", "questions": "See weaknesses.", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n* The theory that bridges PDG with PMFG is interesting an provides a useful tool for solving incentive design problems for large numbers of agents.\n* The contributions of the paper allow for scalable first-order optimization methods to solve this challenging problem, which I believe to be of importance to the field.\n* The introduction of the paper (with clear desiderata) is well-written and clear.\n* The large-scale auction examples are well-developed and deeper than typical empirical examples in ML papers.\n* The authors provide PyTorch and JAX implementations.\n\nWeaknesses:\n* The notation can be hard to digest and could use some explanation to improve the readability of the paper. One example is in Defn 2, L isn't really defined in words. Also, the concept of mean field exploitability could also be explained in words instead of just the equation. In general, I felt that the notation in the paper is often hard to comprehend and some rethinking or additional explanations may significantly improve the paper, especially for non-experts.\n* In Theorem 1, is there anything novel about the analysis compared to similar results in MFGs without ID?\n* Is NZD realistic for real-world auction equilibriums?\n* The paper uses discrete S, A, but real bidding is continuous. What would be necessary to extend this paper to function approximation settings?\n* I would be curious to see what the compute/memory requirements are when using naive back-prop compared to the adjoint method. This would better justify the approach.", "was_revised": true, "final_justification": "The author gave convincing responses to each of my concerns. The additional measurements concerning backprop are especially useful.", "rebuttal": "We thank the reviewer for recognizing the strengths of the work and the insightful questions. We summarize our responses below, by numbering the weaknesses suggested by the reviewer W1 to W5.\n\n**(W1):** To support readers unfamiliar with our notation, we included a full table of symbols in Appendix A. Due to space constraints, this was placed in the appendix, but we hope it to assist the reading of our paper. An explicit reference to Appendix A (which was missing in our submission) will be added in the camera-ready, before the start of Section 2. \n\nIn particular, the quantity $L$ is the *idealised, infinite player* distribution of the population over states and actions in time, at the infinite-player limit. Mean-field exploitability can be considered an infinite-player extension of exploitability in classical game theory, which quantifies how much each player is incentivised to deviate from a strategy profile (which must be 0 for exact Nash). We will incorporate the corresponding explanations in our final version to assist the understanding of our work.\n\n**(W2):** Theorem 1 builds on previous results to prove the convergence result for our setting: it relies on two extensions to handle exploitability analysis in the entropy-regularized objective function and the approximation in terms of the design objective $G$. A detailed proof is provided in Appendix E. While Theorem 1 is an extension of existing analysis, our key contribution is Theorem 2, which relies on an entirely novel analysis going beyond the Lipschitz continuous case.\n\n**(W3):** The NZD (No zero-dominance) property is realistic in auction settings. When optimizing with entropy regularization, NZD is guaranteed: every entropy-regularized MFG-NE $\\pi^*$ assigns non-zero probability to all actions (see lines 253-255).\nEven without entropy regularization, the NZD property can naturally arise in auction MFGs due to the structure of the reward and transition dynamics. When the item allocation function depends only on time, all losing actions yield the same immediate reward, zero, and the next state depends solely on the bidder’s valuation, not on the specific action taken. As a result, all losing actions are indistinguishable in value: for all states $s$ and all losing actions $a, a'$, it holds that $q_h(s, a | L, \\pi, \\theta) = q_h(s, a' | L, \\pi, \\theta)$, and any MFG-NE can be perturbed into an equivalent equilibrium that assigns non-zero probability to the highest losing action, satisfying NZD.\n\nThis is also reflected in the behavior of Online Mirror Descent (OMD) when used to approximate MFG-NEs. Since all losing actions have equal expected rewards, OMD assigns equal probability among them, including the highest losing action. Thus, if OMD converges to an MFG-NE, the resulting policy satisfies NZD.\nThe same reasoning extends to many auction settings where allocation depends on the bid distribution. For instance, in reserve-price auctions where goods are allocated proportionally to the number of agents bidding above a threshold, the learned MFG-NE still satisfies NZD due to the equal treatment of losing actions in the optimization dynamics.\n\nMoreover, in our experimental setting, we observed that the NZD property consistently holds across the learned policies. In particular, the policies obtained by AMID and the other baselines assign non-zero probability to the highest losing actions, consistent with the theoretical argument above. To support this, we will include plots in the camera-ready version that illustrate the action distributions and confirm that NZD is satisfied in all experiments.\n\n**(W4):** We would like to emphasize that in many auctions, a discrete action space is natural, either due to the discrete nature of currency or due to technical limitations, particularly in online auctions. As such, discrete auctions have been a topic of study in literature (e.g. [1,2]), and in fact, can introduce unique theoretical difficulty compared to the continuous setting. \nIn order to encapsulate realistic discrete bid auctions, in our experiments, we take a relatively fine discretization ($|\\mathcal{S}| = 100$).\n\nSeparately, it is possible to extend our work into the continuous action setting by replacing the discrete state-action MFG formalism standard in e.g. [3], which we leave for future work.\n\n**(W5):**\nTo illustrate the effectiveness of AMID, we provide the following measurements on **single iteration time and memory usage** of naive backpropagation and AMID using the JAX implementation (on the setting (A2)). The results indicate clearly that naive backpropagation has intractable growth in memory and time as a function of $H$, and in fact becomes prohibitively expensive on a single GPU for $H$ as small as $H=25$. Here, ❌ indicates that we were not able to run the naive algorithm.\n\n| Horizon $H$ | Naive (time, seconds) | Naive (memory) | AMID (time, seconds) | AMID (memory) |\n|-|-|-|-|-|\n| $H=5$ | 0.19 ± 0.02 s | 2760 MiB | **0.09 ± 0.01 s** | **560 MiB** | \n| $H=10$ | 0.25 ± 0.10 s| 8746MiB | **0.208 ± 0.08 s** | **586 MiB** ||\n| $H=25$ | 0.71 ± 0.15 s | 16960MiB  | **0.67 ± 0.12 s** | **826 MiB** |\n| $H=50$ | ❌ | ❌| **1.72 ± 0.41s** | **1076 MiB**  |\n\nWe agree that these figures will contribute to the paper significantly, and plan to incorporate these measurements in our final submission, in Section 4. Currently, the computational benefits of AMID are highlighted in the main paper, specifically in Contribution 3 (line 65) and in Remark 1 (line 189). In fact, the experimental results in the paper are already in the regime where the improvement due to AMID is significant.\n\n**References:**\n\n[1] David et al., 2011. Optimal design of english auctions with discrete bid levels, ACM Transactions on Internet Technology.\n\n[2] Chwe, 1989. \"The discrete bid first auction.\" Economics Letters.\n\n[3] Saldi et al., 2018. Markov--Nash equilibria in mean-field games with discounted cost. SIAM Journal on Control and Optimization."}, {"review_id": "Hj0aEVkPWr", "reviewer": "Reviewer_Pav3", "summary": "This paper reframes the study of incentive design (ID) as a mean-field game (MFG) under a exchangeability assumption across agents. It establishes non-asymptotic guarantees between the finite-agent ID problem and its mean-field counterpart, covering both Lipschitz-continuous settings and non-Lipschitz cases such as sequential auctions. To solve the resulting mean-field ID problem efficiently, it also proposes an adjoint-based gradient estimation algorithm (AMID) that reduces memory overhead during optimization. The proposed algorithm is tested on classical congestion pricing and various large-scale auction design tasks.", "questions": "- The theoretical results rely on several assumptions, such as Lipschitz continuity or the no-zero-dominance property for auctions. Could the authors provide more justification or empirical evidence on how often these assumptions hold in real-world scenarios?", "limitations": "- The paper does not provide a discussion on how strong its assumptions are.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- The paper is well-motivated from a practical perspective. Setting the right incentives in large multi-agent systems is a crucial real-world problem with applications in traffic management, auctions, and resource allocation.\n\n- The paper frames the problem from an innovative perspective by leveraging mean-field games (MFGs) with a exchangeability assumption to approximate and solve the original incentive design problem at scale.\n\n- The proposed method outperforms the selected baseline methods.\n\nWeaknesses:\n\n- It is not entirely clear how strong or restrictive the key assumptions are. For example, the theoretical guarantees depend on Lipschitz continuity (or specific structural properties like no-zero-dominance for auctions).", "was_revised": true, "final_justification": "The authors' response helped me understand the assumptions. After reading the rebuttal and the reviews from other reviewers, I decide to maintain my current rating.", "rebuttal": "We thank the reviewer for recognizing the strengths of the work and the insightful questions. We summarize our responses below.\n\n**W1, Q1, and the discussion of our limitations:**\n\nIn the main paper, the assumptions (in particular, NZD) as well as their consequences have been discussed (see for instance lines 253-255, lines 245-246, 264-266, and Remark 2). Here, we provide further commentary that will be incorporated into the paper.\n\n**Lipschitz continuity** is natural in many settings, as it implies that small changes in population behaviour does not cause major changes in game dynamics. It is is a **standard and minimal assumption** in MFG literature, as it ensures the existence and stability of solutions. In fact, without Lipschitz continuity, even basic properties such as approximation of finite-player Nash equilibria with explicit bounds might not hold (see Yardim et al., 2024). Theorem 1 could be considered therefore as stated under the most relaxed conditions.\n\nThat said, a key contribution of our work is showing that such assumptions can be relaxed in structured settings. Specifically, we performed a dedicated analysis for the auction setting, which is inherently non-Lipschitz due to discontinuities in the reward and allocation functions. Despite this, we were able to prove the same approximation results without relying on Lipschitz continuity (**Theorem 2**). This demonstrates that our framework can handle important real-world cases where standard assumptions do not hold.\n\n**The NZD (No zero-dominance) property** is realistic in auction settings. When optimizing with entropy regularization, NZD is guaranteed: every entropy-regularized MFG-NE $\\pi^*$ assigns non-zero probability to all actions (see lines 253-255).\n\nEven without entropy regularization, the NZD property can naturally arise in auction MFGs due to the structure of the reward and transition dynamics. When the item allocation function depends only on time, all losing actions yield the same immediate reward, zero, and the next state depends solely on the bidder’s valuation, not on the specific action taken.  As a result, all losing actions are indistinguishable in value: for all states $s$ and all losing actions $a, a', q_h(s, a | L, \\pi, \\theta) = q_h(s, a' | L, \\pi, \\theta)$, and any MFG-NE can be perturbed into an equivalent equilibrium that assigns non-zero probability to the highest losing action, satisfying NZD.\n\nThis is also reflected in the behavior of Online Mirror Descent (OMD) when used to approximate MFG-NEs. Since all losing actions have equal expected rewards, OMD assigns equal probability among them, including the highest losing action. Thus, if OMD converges to a MFG-NE, the resulting policy satisfies NZD.\nThe same reasoning extends to many auction settings where allocation depends on the bid distribution. For instance, in reserve-price auctions where goods are allocated proportionally to the number of agents bidding above a threshold, the learned MFG-NE still satisfies NZD due to the equal treatment of losing actions in the optimization dynamics.\n\nMoreover, in our experimental setting, we observed that the NZD property consistently holds across the learned policies. In particular, the policies obtained by AMID and the other baselines assign non-zero probability to the highest losing actions, consistent with the theoretical argument above. To support this, we will include plots in the camera-ready version that illustrate the action distributions and confirm that NZD is satisfied in all experiments."}, {"review_id": "HmuasnKg5R", "reviewer": "Reviewer_XDLE", "summary": "The paper aims to solve the incentive design (ID) problem for general N-player dynamic games, which is intractable. To make it tractable, the authors propose to construct mean-field game (MFG) approximations to general dynamic games. The authors develop such methods for games parameterized with Lipschitz continuity and for auction design where the Lipschitz assumptions do not hold.", "questions": "In addition to the questions in the Strengths And Weaknesses section:\n\nQ1. In the (ID) objective below Line 24, is the maximization over both $\\theta$ and $\\pi$? If pi is also an maximization variable, how does this paper (and other works) address this Nash selection problem? \n\nQ2. How does the Lipshcisnt constant in Assumption 1 affect the bounds in Theorem 1?\n\nQ3. In Section 2, isn't that we are given a PDG $\\mathcal{G}$ first and seek an PMFG $\\mathcal{M}$ approximation? If so, why does Theorem 1 state it the other way around (i.e., Given $\\mathcal{M}$  first…let $\\mathcal{G}$  be such that…)?\n\nQ4. At Line 165, $q^\\tau_h$ is required to be $C^1$ regarding $(\\theta, \\zeta^*)$. How about its continuity in $L$, the population density?\n\nQ5. At Line 170, what do you mean by “locally”?", "limitations": "No, the authors did not discuss limitations.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**     \nThe paper is overall well-written with clarity and technical formality that meets the expectation from such work.\nThis review will emphasize more on the weaknesses to justify the rating.\n\n**Weaknesses**     \nW1. The paper lacks context for readers unfamiliar with the topic to appreciate the significance of the key contributions in Sections 2 and 3. Here we take Section 2 as an example but similar concerns might apply to Section 3.\n- Theorem 1 extends prior results on the quality of the MFG approximation (i.e. unparameterized or with a single theta) to the parameterized setting for ID. It’s unclear how straightforward such an extension is. What are the key challenges in extending the prior results, if it is not straightforward?\n- Lemma 1’s formality is appreciated but it is unsurprising by itself nor does it help the method in any algorithmical manner.\n- The significance of the AMID algorithm is unclear. Lemma 2 confirms the soundness of AMID, but what's the key innovative techniques that make it more efficient than standard methods? What is the intuition and key idea behind those techniques? Are those techniques specific to MID or general enough to apply to other T-step approximate update functions? Is there any prior work or existing techniques to address the efficiency problem?\n\nW2. Some key points regarding the problem formulation are under-explained. Please refer to Questions.\n\nW3. Notation and clarity is overall good but can be further improved. To name a few,\n- In the ID objective (Line 108), $\\mathbf{e}$ is not defined.\n- At Line 145, it should be $\\to \\Pi_H$.\n- Inconsistent usage of $F_{omd}$ vs $\\bar{F}^\\tau_{omd}$. It seems $F_{omd}$ should be reserved for the update in the log prob space (Line 153) but first appears at Line 145.\n- At Line 166, $\\rho$ is not defined.", "was_revised": true, "final_justification": "The rebuttal is comprehensive so I have raised my score to the postive side.\n\nHowever, I am not an expert in this field and cannot confidently evalute the technical aspects. Therefore, I have decreased my confidence.", "rebuttal": "We thank the reviewer for recognizing the strengths of the work and the insightful questions. We summarize our responses below.\n\n# W1:\n\nWe respond to the concerns of the reviewer for Sections 2-3 jointly.\n\n**Theorems 1 and 2:** Theorem 1 uses the proof techniques developed for Lipschitz continuous MFGs (as acknowledged in Appendix D.2) with modifications to handle entropy regularization and the incentive function $g$. The theorem justifies our PMFG approximation for $N$-player ID in the first place. However, our **main contribution to MFG approximation** comes from **Theorem 2**, which incorporates non-Lipschitz (in fact, not continuous) dynamics and requires special use of the properties of auctions. To the best of our knowledge, no existing approximation result applies to this case (see our discussion on related works between lines 83-93). Critically, both theorems are required to justify our overall framework and demonstrate the well-posedness of incentive design via MFGs.\n\n**Lemma 1:** We disagree that the lemma is not relevant for the algorithm, as it provides two important conclusions. First, it justifies the use of our explicit differentiation scheme by showing that the scheme approximates $\\partial_\\theta F_{omd}^{\\infty}$ under reasonable assumptions, which is not clear a priori. Second, it provides **intuition on how to tune the parameters $T,\\eta,\\tau$ and their impact on the quality of explicit differentiation**. Lemma 1 also provides two conditions that can be evaluated empirically: while $\\partial_\\theta F_{omd}^{\\infty}$ is difficult to evaluate, one can easily verify the requirements 1 and 2 of the lemma.\n\n**Significance of AMID:** The main significance of AMID in our context is that it reduces an expensive (in fact, intractable) computation into an equivalent but tractable one. The key innovations associated with it are presented in Theorems 1 and 3 **(showing that PMFGs form a low-bias approximation to ID)** and Lemmas 1 and 2 **(showing that PMFGs are also efficiently solvable)**. Without the PMFG model, many-player incentive design will be intractable.\n\nIn principle, apart from the PMFG approximation that is specific to the incentive design problem, the technique could be applied to other settings where there are repeated evaluations of an operator. However, PMFG incentive design can be considered unique since the operator $F_{omd}^\\tau$ itself is quite complicated and involves forward-backward iterations on the MFG. For instance, the explicit differentiation scheme of [2] does not require our adjoint optimization, since the iterated operator is much simpler. Our technique permits explicit differentiation of Nash of MFGs, to the best of our knowledge, for the first time. We have seen tangential ideas employed in Neural ODEs [1] with possible applications to recurrent neural networks, although the works do not consider incentive design for MFGs and diverge from our goals and unique challenges of ID. \n\nWe also refer to our explicit measurements on various sizes of auctions (see the Table below) in our response to reviewer DFyx, copied for reference. The measurements were conducted in the setting (A2) and demonstrate the effectiveness of AMID even for small problem sizes: in all cases, AMID requires less memory and computational time than a naive gradient backpropagation. Here, ❌ indicates that the naive backprop method was not able to run on a single GPU, and the time ranges indicate one standard deviation. The table (which will be incorporated in the form of a plot in the paper) demonstrates that for explicit differentiation of PMFGs, the AMID approximation is crucial.\n\n| Horizon $H$ | Naive (time, seconds) | Naive (memory) | AMID (time, seconds) | AMID (memory) |\n|-|-|-|-|-|\n| $H=5$ | 0.19 ± 0.02 s | 2760 MiB | **0.09 ± 0.01 s** | **560 MiB** | \n| $H=10$ | 0.25 ± 0.10 s| 8746MiB | **0.208 ± 0.08 s** | **586 MiB** ||\n| $H=25$ | 0.71 ± 0.15 s | 16960MiB  | **0.67 ± 0.12 s** | **826 MiB** |\n| $H=50$ | ❌ | ❌| **1.72 ± 0.41s** | **1076 MiB**  |\n\n# W2 and relevant questions:\nWe thank the reviewer for the questions. We address these below, and will incorporate additional explanations in the final version using our extra page.\n\n## Q1 \nThere is no standard formulation to the best of our knowledge when there are multiple equilibria. Most works implicitly or explicitly assume uniqueness [2,3] and incorporate regularization when it does not hold [3]. Some works sidestep the issue by adopting a Nash oracle [4] or restriction to the local implicit map [5]. Our approach is similar to [5], where we differentiate with respect to the implicit map induced by $F_{omd}^\\tau$, under the conditions of Lemma 1.\n\n## Q2 \nThese were already alluded to in Remark 2, which will be expanded and clarified. In the structured setting of auctions, for many relevant cases, the Lipschitz constant $L$ is upper bounded by 1, therefore, the dependence on the time horizon $H$ scales with $O(H^2)$ with no explicit dependence on $L$ arising. For instance, if the valuations of agents are fixed across rounds (or evolve with a Markov kernel), our results imply $L\\leq 1$, see Appendix E.\n\nOur framework is general enough to incorporate complex models where valuations of the bidders can evolve depending on the valuations of others. In this case, the Lipschitz constant $L$ of the valuation dynamics $\\omega$ in $\\mu$ will incur an $O(\\frac{L^H}{\\sqrt{N}})$ approximation error, which is the best possible upper bound matching the lower bound of (Yardim et al., 2024). \n\n## Q3\nWe agree with the reviewer that $\\mathcal{G}$ is precursive and $\\mathcal{M}$ is a useful algorithmic construct. The reason the theorem is stated in the mentioned way is the fact that it holds true for all $\\mathcal{G}$ with $N$ players with asymptotic rates on $N$, and the mathematical statement of the inverse problem could obfuscate the main message (cf. [4]). However, for the theorem to be useful, an appropriate MFG formulation $\\mathcal{M}$ must be provided, as the reviewer has noticed.\n\nThis becomes clearer in Section 3: Definition 3 (of BA-MFGs) provides the heavy-lifting of defining the appropriate MFG, consequently, Theorem 2 provides the approximation guarantees for all relevant $N$-player auctions. More generally, our work is easily compatible with “inverse” problem designs in MFG (e.g. [6,7]), however, we leave the formal development of this as future work.\n\n## Q4\nFor the purpose of the lemma, it is sufficient that the “composite” map $(\\theta, \\zeta) \\rightarrow q^\\tau_h(\\cdot, \\cdot | \\Lambda(\\operatorname{softmax}(\\zeta)), \\operatorname{softmax}(\\zeta), \\theta)$ must be $C^1$ in the neighborhood of $(\\theta, \\zeta^*)$. This holds true in the specific case $\\Lambda$ is $C^1$ and $q_h^\\tau$ is $C^1$ in $L, \\pi, \\theta$, but for the composition to be $C^1$, this is not a necessary condition, hence the current statement of the lemma.\n\nWe have noticed that the statement of the lemma (in particular, $q_h^\\tau$ being $C^1$ in the neighborhood) could be improved for legibility, which will be done in the final submission.\n\n## Q5 \nFor the gradient computation at some $\\theta$, $\\theta’ \\rightarrow \\pi^{\\theta’}$ must be a map that such that $\\pi^{\\theta’}$ is the Nash corresponding to design $\\theta’$ whenever $\\theta’ \\in U$ for some open set containing the point of differentiation. The current statement is to ensure clear distinction between computing gradients (which is a local operation) and computing Nash for all $\\theta$: Computing a Nash equilibrium for all $\\theta$ might be intractable, but a map that locally computes Nash is sufficient for first-order information.\n\n# W3: \nTo assist reading our paper and help readers who are used to other conventions, we have provided a full notation table in Appendix A. This table was moved to the appendix due to space limitations. For the notation on $\\rho$ and $\\mathbb{e}$ and potentially others, we refer the reviewer to the appendix.\n\nWe thank the reviewer for pointing out the typos on lines 146 and the usage of $\\bar{F}_{omd}$. These will be fixed in the final submission.\n\n## References:\n\n[1] Chen, et al. Neural ordinary differential equations. NeurIPS 2018.\n\n[2] Li et al. End-to-end learning and intervention in games. NeurIPS 2020.\n\n[3] Liu et al. Inducing Equilibria via Incentives: Simultaneous Design-and-Play Ensures Global Convergence. NeurIPS 2022.\n\n[4] Wang, el al. Coordinating followers to reach better equilibria: End-to-end gradient descent for Stackelberg games. AAAI 2022.\n\n[5] Fiez, el al. Implicit Learning Dynamics in Stackelberg Games: Equilibria Characterization, Convergence Analysis, and Empirical Study. ICML 2020.\n\n[6] Yardim et al., Exploiting Approximate Symmetry for Efficient Multi-Agent Reinforcement Learning. L4DC 2025.\n\n[7] Chen at al., Individual-Level Inverse Reinforcement Learning for Mean Field Games. AAMAS 2022"}]

Author rebuttal:

Meta-review: The paper proposes Adjoint Mean-Field Incentive Design algorithm for incentive design in multiagent systems.  Experimental results are provided to validate the theoretical findings. Overall the reviewers all seem to be positive about the paper and the paper is definitely worth publishing at Neurips. Please incorporate the discussion/rebuttal response as appropriate in to the paper.
Decision: Accept (poster)