Paper deep dive
Incentive Design without Hypergradients: A Social-Gradient Method
Georgios Vasileiou, Lantian Zhang, Silun Zhang
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 92%
Last extracted: 4/14/2026, 1:39:02 AM
Summary
The paper introduces the 'social-gradient flow', a hypergradient-free incentive design method for steering self-interested agents toward a socially optimal Nash equilibrium. It proves that the social cost gradient is a descent direction for the planner's objective, enabling convergence to the social optimum without requiring knowledge of equilibrium sensitivities or agent cost functions. The method is validated as a two-timescale learning process where agents adapt strategies on a fast timescale and the planner updates incentives on a slow timescale.
Entities (5)
Relation Signals (3)
Social-gradient flow → optimizes → Incentive design
confidence 95% · we propose a hypergradient-free incentive law, called the social-gradient flow, for incentive design
Social-gradient flow → convergesto → Social optimum
confidence 90% · the joint strategy-incentive dynamics converge to the social optimum
System Planner → steers → Nash Equilibrium
confidence 90% · system planner who steers self-interested agents toward a socially optimal Nash equilibrium
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Incentive design problems consider a system planner who steers self-interested agents toward a socially optimal Nash equilibrium by issuing incentives in the presence of information asymmetry, that is, uncertainty about the agents' cost functions. A common approach formulates the problem as a Mathematical Program with Equilibrium Constraints (MPEC) and optimizes incentives using hypergradients-the total derivatives of the planner's objective with respect to incentives. However, computing or approximating the hypergradients typically requires full or partial knowledge of equilibrium sensitivities to incentives, which is generally unavailable under information asymmetry. In this paper, we propose a hypergradient-free incentive law, called the social-gradient flow, for incentive design when the planner's social cost depends on the agents' joint actions. We prove that the social cost gradient is always a descent direction for the planner's objective, irrespective of the agent cost landscape. In the idealized setting where equilibrium responses are observable, the social-gradient flow converges to the unique socially optimal incentive. When equilibria are not directly observable, the social-gradient flow emerges as the slow-timescale limit of a two-timescale interaction, in which agents' strategies evolve on a faster timescale. It is established that the joint strategy-incentive dynamics converge to the social optimum for any agent learning rule that asymptotically tracks the equilibrium. Theoretical results are also validated via numerical experiments.
Tags
Links
- Source: https://arxiv.org/abs/2604.11346v1
- Canonical: https://arxiv.org/abs/2604.11346v1
Trouble viewing inline? Open PDF directly →
Full Text
57,654 characters extracted from source content.
Expand or collapse full text
Incentive Design without Hypergradients: A Social-Gradient Method Georgios Vasileiou†, Lantian Zhang†, and Silun Zhang† This work has been partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP), funded by the Knut and Alice Wallenberg Foundation.† Georgios Vasileiou , Lantian Zhang and Silun Zhang are with the Dep. of Mathematics at the KTH Royal Institute of Technology, Stockholm, 10044, Sweden. geovas, lantian, silunz@kth.se Abstract Incentive design problems consider a system planner who steers self-interested agents toward a socially optimal Nash equilibrium by issuing incentives in the presence of information asymmetry, that is, uncertainty about the agents’ cost functions. A common approach formulates the problem as a Mathematical Program with Equilibrium Constraints (MPEC) and optimizes incentives using hypergradients—the total derivatives of the planner’s objective with respect to incentives. However, computing or approximating the hypergradients typically requires full or partial knowledge of equilibrium sensitivities to incentives, which is generally unavailable under information asymmetry. In this paper, we propose a hypergradient-free incentive law, called the social-gradient flow, for incentive design when the planner’s social cost depends on the agents’ joint actions. We prove that the social cost gradient is always a descent direction for the planner’s objective, irrespective of the agent cost landscape. In the idealized setting where equilibrium responses are observable, the social-gradient flow converges to the unique socially-optimal incentive. When equilibria are not directly observable, the social-gradient flow emerges as the slow-timescale limit of a two-timescale interaction, in which agents’ strategies evolve on a faster timescale. It is established that the joint strategy-incentive dynamics converge to the social optimum for any agent learning rule that asymptotically tracks the equilibrium. Theoretical results are also validated via numerical experiments. I Introduction Incentive design addresses the problem of a system planner who seeks to steer the collective behavior of self-interested agents toward a socially desirable outcome by publicly committing to a reward (penalty) scheme. This hierarchical decision-making structure is often encountered in a broad class of engineered systems, including demand response in energy markets [19, 9], congestion-aware tolling [24, 3], and data crowdsourcing markets [13]. The planner’s incentive map can be viewed as a feedback mechanism between contracted parties [15], with the aim of aligning agents’ preferences with a target equilibrium [25]. A central difficulty in incentive design is the information asymmetry, where the leader typically lacks complete information about the agents’ cost functions. Therefore, incentive design can be regarded as a reverse (or inverse) Stackelberg game with partial or no information on agents’ costs [14, 25, 30]. As a standard formulation, Stackelberg games can be cast into Mathematical Programs with Equilibrium Constraints (MPECs) [21, 6], in which the planner solves a minimization of social cost subject to the constraint that agents respond with a Nash equilibrium (NE). A prevalent approach to solving MPECs treats the constraint as a differentiable layer and updates the planner’s action by hypergradient descent[10, 17, 16, 12]. The hypergradient is the total derivative of the social objective with respect to incentives, through the agents’ equilibrium response. Gradient-based approaches to solving MPEC for incentive design have been studied from both continuous- and discrete-time perspectives. In continuous-time, recent work has utilized full- or partial- information hypergradient-decent to solve Stackelberg games, under varying low-level cost structures and dynamics [23, 2, 1]. Population games are considered in [23], with agents that follow replicator dynamics over a probability simplex, and a slow-timescale gradient flow that utilizes the potential structure of the lower level is proven to guarantee convergence. [1] examines game design under both full and partial information assumptions. In the partial information case, the unavailable hypergradient is reconstructed from equilibrium trajectories, utilizing local utility gradients at the current equilibrium. Likewise, in discrete time, Liu et al. [20] develop a two-timescale scheme where agents evolve their strategies via mirror descent and the planner’s knowledge of local costs is leveraged to asymptotically estimate the unavailable hypergradient. A related relaxation is proposed in [11], where an approximate NE and its sensitivity are computed in a distributed manner and subsequently utilized for a projected hypergradient step. In addition, current work in [22] presents an incentive design method that does not rely on hypergradients. Instead, it requires observing the externality, defined as the marginal difference between the social objective and the agents’ costs. In the present work, we propose the social-gradient flow, a hypergradient-free incentive law applicable whenever the planner’s social cost is a function of the agents’ collective action profile. The proposed scheme utilizes only the gradient of social cost (without differentiating through the equilibrium). We establish that the social cost gradient constitutes a descent direction for the planner’s objective, regardless of the unknown agent cost landscape. Under an idealized equilibrium observation model in which the planner can observe the equilibrium responses, we prove global convergence of the social-gradient flow to the unique socially optimal incentive from any feasible initial condition. In the relaxed setting where equilibrium responses are unobservable, the proposed law represents the slow-timescale limit of a two-timescale learning dynamics in which agents adapt their strategies on a fast timescale and the planner responds to the observed trajectory on the slow one. Under standard assumptions on agents’ learning process (i.e., that it asymptotically tracks Nash equilibria), we prove the joint two-timescale dynamics converge to the social optimum. Notation. For a real-valued map f:ℝn→ℝf:R^n , denote by ∇f(x)∇ f(x) its gradient at x. We say that f is μ-strongly convex on ⊂ℝnX ^n if f(y)≥f(x)+⟨∇f(x),y−x⟩+μ2‖y−x‖2,f(y)≥ f(x)+ ∇ f(x),\,y-x + μ2\|y-x\|^2, for all x,y∈x,y . For a vector-valued map F:ℝn→ℝmF:R^n ^m, denote by DF(x)∈ℝm×nD\!F(x) ^m× n its Jacobian at x. For a matrix A, define Sym(A)=12(A+A⊤) *Sym(A)= 12(A+A ) the symmetrization of A. Denote by f(t)=O(g(t))f(t)=O(g(t)) the existence of c>0c>0 and t0t_0 so that |f(t)|≤c|g(t)||f(t)|≤ c|g(t)| for all t≥t0t≥ t_0. Write f(t)=o(g(t))f(t)=o(g(t)) if limt→∞f(t)/g(t)=0 _t→∞f(t)/g(t)=0. In addition, CkC^k denotes the class of k-order continuously differentiable functions. I Problem Formulation We consider a set of =1,…,nN=\1,…,n\ non-cooperative agents that interact in a game influenced by a single system planner. Each agent i∈i seeks to minimize its own cost by choosing a strategy xi∈ix_i _i, with i⊂ℝX_i a compact, convex set. 111We present the scalar case for notational simplicity; the results extend to higher-dimensional strategy spaces. Let =∏i∈iX= _i X_i be the joint strategy space. Agent i is equipped with a private nominal cost ℓi:→ℝ _i:X , where ℓi _i is C2C^2, and also receives an incentive γi:→ℝ _i:X issued by the system planner, acting as a penalty on action x∈x if γi(x)≥0 _i(x)≥ 0 and as a reward otherwise. The literature has extensively investigated affine linear incentives [4, 31, 22, 18], due to their sufficiency to influence agent behavior by modifying marginal costs. For this reason, we consider the total cost of each agent to be ciγ(x)=ℓi(x)+γi(x)=ℓi(x)+pixi,x∈,c_i^γ(x)= _i(x)+ _i(x)= _i(x)+p_ix_i, x∈ X, (1) where pi∈ℝp_i is an incentive parameter. We refer to p=(pi)i∈ℝnp=(p_i)_i ^n as the incentive issued to agents. Given the costs (ciγ)i∈(c_i^γ)_i , define the pseudo-gradient of the incentivized and nominal games, respectively, as Gγ(x)=[∂x1c1γ⋮∂xncnγ], and G0(x)=[∂x1ℓ1⋮∂xnℓn].G_γ(x)= bmatrix ∂ x_1c_1^γ\\ \\ ∂ x_nc_n^γ\\ bmatrix, and G_0(x)= bmatrix ∂ x_1 _1\\ \\ ∂ x_n _n\\ bmatrix. Observe that by the above definition and (1), p acts as an additive shift to the pseudo-gradient with Gγ(x)=G0(x)+pG_γ(x)=G_0(x)+p. Following the equivalence between NE and variational inequality (VI) problems (see, e.g., [7, 8]), for any given incentive p and costs (ciγ)i∈(c_i^γ)_i , we define an incentivized Nash equilibrium (INE) of the game to be any x∗(p)∈x^*(p) satisfying Gγ(x∗(p))⊤(x−x∗(p))≥0,∀x∈.G_γ(x^*(p)) (x-x^*(p))≥ 0, ∀ x . (2) Assumption 1. DG0D\!G_0 is L1L_1-Lipschitz in X, and there exists a positive scalar m>0m>0, such that G0G_0 satisfies Sym(DG0(x))⪰m2,∀x∈. *Sym(D\!G_0(x)) m2I,\,∀ x . (3) The strong monotonicity assumption on G0G_0 is sufficient for the existence and uniqueness of the INE for all p∈ℝnp ^n [7, Theorem 2.3.3]. Assumption 1 can be relaxed to Rosen’s diagonal strict convexity (concavity) condition [27], though doing so would require an additional diagonal matrix known in the proposed incentive-seeking dynamics. We call any map p↦x∗(p)p x^*(p) that satisfies (2) a response map for the incentivized game. Define the set =−G0(int)⊂ℝnP=-G_0( *intX) ^n. The result that follows characterizes a response map. Lemma 1. Suppose Assumption 1 holds. Over the open set P, the response map x∗(⋅)x^*(·) is unique, and x∗:→intx^*:P→ *intX is a C1C^1 diffeomorphism. Proof. Presented in Appendix A. ∎ P is bounded and simply connected (hence path connected), since x∗:→intx^*:P→ *intX is a diffeomorphism and int *intX is an open hyperrectangle in ℝnR^n. However, P need not be convex. The following lemma presents properties of the map x∗(⋅)x^*(·). Lemma 2. Under Assumption 1, it holds that, for any p∈p , (i) the response x∗(p)x^*(p) satisfies Gγ(x∗(p))=0,G_γ(x^*(p))=0, and is 2m 2m-Lipschitz ; (i) the response map Jacobian Dx∗(p)D\!x^*(p) is non-singular and satisfies Sym(Dx∗(p))≺0 *Sym(D\!x^*(p)) 0; (i) there exist positive constants σ1 _1 and σ2 _2 such that σ1‖w‖2≤‖Dx∗(p)w‖2≤σ2‖w‖2,∀w∈ℝn, _1\|w\|_2≤\|D\!x^*(p)w\|_2≤ _2\|w\|_2,\,∀ w ^n, where σ1=(maxx∈‖DG0(x)‖2)−1 _1\!=\! ( _x \!\|D\!G_0(x)\|_2 )^-1 and σ2=2m _2= 2m; and (iv) the Jacobian Dx∗(p)D\!x^*(p) is 8L1m3 8L_1m^3-Lipschitz in P. Proof. Presented in Appendix A. ∎ The system planner’s objective is to steer the agents toward the minimizer of a strongly convex function Φ:→ℝ :X by selecting an appropriate incentive p. Hence, the planner attempts to solve the MPEC problem minp∈ℝn _p ^n Φ(x∗) (x^*) (4) s.t. Gγ(x∗)⊤(x−x∗)≥0,∀x∈. G_γ(x^*) (x-x^* )≥ 0,\,∀ x . Assumption 2. The social cost function Φ:→ℝ :X is μΦ _ -strongly convex in X and has a L2L_2-Lipschitz gradient. Further, the unique social optimum x†=argminx∈Φ(x)x = *arg\,min_x (x) is in int *intX. Denote by p†=−G0(x†)∈p =-G_0(x ) the unique incentive satisfying x∗(p†)=x†x^*(p )=x , i.e., the incentive under which the agents’ INE is aligned with the social optimum. When restricted to the domain P, the bilevel program (4) then reduces to an implicit minimization of Φ∗:→ℝ _*:P , where Φ∗(p)=Φ(x∗(p)) _*(p)= (x^*(p)) is the objective and its (hyper)gradient with respect to p is ∇Φ∗(p)=Dx∗(p)⊤∇Φ(x)|x=x∗(p).∇ _*(p)=D\!x^*(p) ∇ (x) |_x=x^*(p). The key challenge in solving (4) is that both the domain P and the response map x∗x^* depend on the private cost functions of the agents. Moreover, the hypergradient ∇Φ∗(p)∇ _*(p) is not computable due to its dependence on the INE sensitivity Dx∗(p)D\!x^*(p). In the sections that follow, we design an incentive adaptation law that asymptotically solves the planner’s minimization without requiring agents’ private information. I Social-Gradient Incentive Adaptation This section considers a continuous-time incentive-seeking dynamics, which we refer to as the social-gradient flow. Under an equilibrium observation model [26, 18] that assumes that the induced equilibrium response x∗(p)x^*(p) is directly observable to the planner, we prove that these dynamics asymptotically converge to the incentive p†p that induces the socially optimal response. We define the social-gradient flow as p˙(t)=g∗(p(t))=∇Φ(x)|x=x∗(p(t)),p(0)∈. p(t)=g_*(p(t))=∇ (x) |_x=x^*(p(t)), p(0) . (5) The social-gradient flow (5) utilizes the negative definiteness of Sym(Dx∗(p)) *Sym(D\!x^*(p)), to ensure that ∇Φ(x∗(p))∇ (x^*(p)) is a descent direction for Φ∗ _* at p. For c≥0c≥ 0, define the sublevel sets c=p∈:Φ(x∗(p))−Φ(x†)≤c.P_c=\p : (x^*(p))- (x )≤ c\. (6) Let c∗=minx∈∂Φ(x)−Φ(x†)>0.c^*= _x∈ (x)- (x )>0. We show that each cP_c, with c<c∗c<c^*, is forward invariant under (5), and constitutes a domain of attraction for the optimal incentive p†p . Theorem 1. Suppose Assumptions 1 and 2 hold. For any c<c∗c<c^*, the set cP_c is compact and forward invariant under dynamics (5). Moreover, cP_c contains a unique asymptotically stable equilibrium at p†p . In particular, for any p(0)∈cp(0) _c, the trajectory of dynamics (5) satisfies limt→∞p(t)=p† _t→∞p(t)=p . Proof. First, we show that for any c<c∗c<c^*, the sublevel set cP_c is compact. Observe that c⊂¯=−G0()P_c⊂ P=-G_0(X) is bounded. Consider (pk)k⊂c(p_k)_k _c that converges to p∞∈¯p_∞∈ P. If p∞∈∂¯p_∞∈∂ P, then limk→∞(Φ(x∗(pk))−Φ(x†))≥c∗. _k→∞ ( (x^*(p_k))- (x ) )≥ c^*. However, since Φ(x∗(pk))−Φ(x†)≤c<c∗ (x^*(p_k))- (x )≤ c<c^* for all k, we have a contradiction. Therefore p∞∈p_∞ , and by the continuity of Φ∘x∗ x^* on P, it holds that Φ(x∗(p∞))=limk→∞Φ(x∗(pk))≤c+Φ(x†), (x^*(p_∞))= _k→∞ (x^*(p_k))≤ c+ (x ), which implies p∞∈cp_∞ _c. Second, we show that cP_c is forward invariant and contains a unique asymptotically stable equilibrium at p†p . Define the Lyapunov function V(p)=Φ∗(p)−Φ(x†)V(p)= _*(p)- (x ) with the sublevel set c=p∈:V(p)≤c.P_c=\p :V(p)≤ c\. By Assumption 2, V(p)>0V(p)>0 for all p∈c∖p†p _c \p \. Moreover, V is non-increasing along all trajectories of (5), since V˙(p) V(p) =∇V(p)⊤g∗(p) =∇ V(p) g_*(p) (7) =∇Φ(x∗)⊤Sym(Dx∗(p))∇Φ(x∗)≤(a)0, =∇ (x^*) \! *Sym(D\!x^*(p))∇ (x^*) (a)≤0, where x∗=x∗(p)x^*=x^*(p), and (a)(a) follows from Lemma 2-(i). The equality in (7) holds only for p=p†p=p , and the result follows. ∎ The implementation of (5) requires exact observations of equilibrium response x∗(p)x^*(p), which requires that agents instantly compute and play the INE. A more practical observation model, a learning-agent model, assumes that the planner observes an evolving trajectory of agent responses given pkp_k, which asymptotically converges to x∗(pk)x^*(p_k) on a faster timescale. In this case, law (5) emerges as the limiting dynamics of an associated two-timescale iteration. IV Incentive Adaptation under Equilibrium Tracking Dynamics In this section, we generalize the equilibrium observation requirement and model the planner-agent interaction as a two-timescale learning process. Formally, in response to the incentive pkp_k issued by the planner, the agents update their strategy xkx_k according to a private learning dynamics, which is only required to guarantee asymptotic convergence to the equilibrium response for any fixed incentive. Meanwhile, the planner observes the trajectory of xkx_k and updates the incentive on a slower timescale using the social-gradient flow. Given an initial strategy-incentive pair (x0,p0)(x_0,p_0), the overall strategy-incentive update dynamics are given by xk+1 x_k+1 =xk+ak(f(xk,pk)−xk), =x_k+a_k (f(x_k,p_k)-x_k ), (8a) pk+1 p_k+1 =pk+βk∇Φ(xk)pk+βk∇Φ(xk)∈c, =p_k+ _k∇ (x_k)1 \p_k+ _k∇ (x_k) _c \, (8b) where ak∈(0,1]a_k∈(0,1] and βk>0 _k>0. In (8), f(⋅,pk)f(·,p_k) represents the agents’ (unknown) learning dynamics for the Nash equilibrium x∗(pk)x^*(p_k) and cP_c is a known compact sublevel set of P with 0<c<c∗0<c<c^*. Since the set PcP_c is generally nonconvex, the projection operation onto PcP_c is intractable. We therefore adopt an indicator-based update in (8b). Our objective is to show that, even when the Nash response map x∗(pk)x^*(p_k) is unobservable, the incentive pkp_k designed using the agents’ learning-dynamics responses xkx_k, as given in (8a)-(8b), guarantees global convergence of both the players’ and the planner’s strategies to the socially optimal pair. Assumption 3. The map f:×c→f:X×P_c is jointly LfL_f-Lipschitz. Moreover, there exists a class-ℒKL function ϕφ, such that every solution x(t)x(t) of dynamics x˙=f(x,p)−x x=f(x,p)-x satisfies ‖x(t)−x∗(p)‖2≤ϕ(‖x(0)−x∗(p)‖2,t),\|x(t)-x^*(p)\|_2≤φ (\|x(0)-x^*(p)\|_2,t ), for any t≥0t≥ 0, x(0)∈x(0) , and p∈cp _c. Assumption 3 holds under a broad class of learning dynamics f studied in the literature, such as the Nash equilibrium (NE) update [26], the projected gradient (PG) update [29], and the best-response (BR) update [7, 28]. We revisit these learning rules in Section V. Assumption 4. The sequences (ak)k(a_k)_k and (βk)k( _k)_k satisfy ∑k=0∞ak=∑k=0∞βk=∞,∑t=0∞(ak2+βk2)<∞,andβk=o(ak). _k=0^∞a_k= _k=0^∞ _k=∞,\, _t=0^∞(a_k^2+ _k^2)<∞,\,and\, _k=o(a_k). By Lemma 1 and Theorem 1, the pair (x†,p†)(x ,p ) is the unique fixed point of (8) in ×cX×P_c. The theorem that follows establishes that iteration (8) converges to the socially optimal pair (x†,p†)(x ,p ) from any initial condition in ×cX×P_c. Theorem 2. Suppose Assumptions 1-4 hold. Then, for any initial condition (x0,p0)∈×c(x_0,p_0) ×P_c, the sequence (xk,pk)k≥0(x_k,p_k)_k≥ 0 generated by iteration (8) satisfies limk→∞‖xk−x∗(pk)‖2 _k→∞\|x_k-x^*(p_k)\|_2 =0, and limk→∞pk=p†. =0, and _k→∞p_k=p . (9) Consequently, (xk,pk)→(x†,p†)(x_k,p_k)→(x ,p ), as k→∞k→∞. Remark 1. Under Assumptions 3 and 4, iteration (8) can be viewed as a two-timescale stochastic approximation (TTSA) scheme [5]. However, its convergence cannot be established by a direct application of standard arguments due to the non-convexity of cP_c and the use of the indicator function in (8b). We preface the proof of Theorem 2 with three auxiliary lemmas. First, Lemma 3 proves that iteration (8a) follows the slow-moving equilibria (x∗(pk))k(x^*(p_k))_k on a faster timescale, satisfying ‖xk−x∗(pk)‖2→0\|x_k-x^*(p_k)\|_2→ 0, even when PcP_c is nonconvex. Second, Lemma 4 establishes that the indicator function in (8b) is activated infinitely often for any initial condition (x0,p0)∈×c(x_0,p_0) ×P_c, so the indicator is asymptotically negligible. Finally, Lemma 5 establishes that standard asymptotic pseudo-trajectory results of stochastic approximation extend to approximation schemes over compact forward-invariant domains, without requiring convexity. Lemma 3. Suppose Assumptions 1–4 hold. Let (xk,pk)k≥0(x_k,p_k)_k≥ 0 be generated by dynamics (8) with (x0,p0)∈×c(x_0,p_0) ×P_c. Then ‖xk−x∗(pk)‖2→0,\|x_k-x^*(p_k)\|_2→ 0, as k→∞k→∞. Proof. Let δk=βkpk+βk∇Φ(xk)∈c _k= _k1\p_k+ _k∇ (x_k) _c\. Define h(x,p)=f(x,p)−xh(x,p)=f(x,p)-x so (8) can be written as xk+1 x_k+1 =xk+akh(xk,pk), =x_k+a_kh(x_k,p_k), (10a) pk+1 p_k+1 =pk+δk∇Φ(xk). =p_k+ _k∇ (x_k). (10b) If cP_c is convex, (10) corresponds to a TTSA scheme and the result follows from established techniques (see e.g. [5, p. 66, Lemma 1]). We show that the result holds if cP_c is nonconvex. Due to space limitations, we provide only a sketch of the proof here. Let M=supx∈‖∇Φ(x)‖2M= _x \|∇ (x)\|_2, B=sup×c‖h(x,p)‖2,B= _X×P_c\|h(x,p)\|_2, and m(n,T)=maxk≥n:∑j=nk−1aj≤T.m(n,T)= \k≥ n: _j=n^k-1a_j≤ T\. The proof will proceed in three steps. Step 1: Since δk≤βk=o(ak) _k≤ _k=o(a_k), there exists some NεN_ such that δk≤εak _k≤ a_k, k≥Nεk≥ N_ . For n≥Nεn≥ N_ and k∈[n,m(n,T)]k∈[n,\,m(n,T)], ‖pk−pn‖2≤M∑j=nk−1δj≤εM∑j=nk−1aj≤εMT.\|p_k-p_n\|_2\;≤\;M _j=n^k-1 _j\;≤\; M _j=n^k-1a_j\;≤\; MT. (11) By (11), it holds that supn≤k≤m(n,T)‖pk−pn‖2→0 _n≤ k≤ m(n,T)\|p_k-p_n\|_2→ 0 as n→∞n→∞ for each T fixed. Step 2: Let sk=∑j=0k−1ajs_k= _j=0^k-1a_j and denote with x¯(s) x(s) the piecewise-linear interpolation of (xk)k(x_k)_k on [sk,sk+1][s_k,s_k+1] and the convex X . Let xn(s)x^n(s), s≥ns≥ n be the trajectory of x˙=h(x,pn) x=h(x,p_n) with xn(0)=xnx^n(0)=x_n. By arguments similar to those presented in [5, p. 12, Lemma 1], it follows that sup0≤s≤T‖x¯(sn+s)−xn(s)‖2→0, as n→∞. _0≤ s≤ T\| x(s_n+s)-x^n(s)\|_2→ 0, as n→∞. (12) Step 3: Finally, we leverage the uniform ℒ−KL-bound ϕφ of Assumption 3, property (12) and the Lipshitzness of the x∗x^* map to conclude that ‖xk−x∗(pk)‖2≤ak−1B+ϵ+2mω(n,2Tϵ),\|x_k-x^*(p_k)\|_2≤ a_k-1B+ε+ 2mω(n,2T_ε), for any ϵ>0ε>0 and appropriate TϵT_ε. The result follows. ∎ Lemma 4. Suppose Assumptions 1-4 hold. Let (xk,pk)k≥0(x_k,p_k)_k≥ 0 be a sequence generated by iteration (8) with initial condition (x0,p0)∈×c(x_0,p_0) ×P_c. It then holds that ∑t=0∞βkpk+βk∇Φ(xk)∈c=∞. _t=0^∞ _k1\p_k+ _k∇ (x_k) _c\=∞. Proof. At each k, denote p^k=pk+βk∇Φ(xk) p_k=p_k+ _k∇ (x_k). Suppose for some initial condition the sequence (xk,pk)k≥0 (x_k,p_k )_k≥ 0 satisfies ∑k=0∞βkp^k∈c<∞. _k=0^∞ _k1\ p_k _c\<∞. (13) Then (8b) implies ∑k=0∞‖pk+1−pk‖2<∞, _k=0^∞\|p_k+1\!-\!p_k\|_2<\!∞, so pk→p∞p_k→ p_∞, where p∞∈cp_∞ _c is dependent on (x0,p0) (x_0,p_0 ). First, we show that (13) implies a contradiction if p∞∈intcp_∞∈ *intP_c. Let r>0r>0 be such that Br(p∞)⊂cB_r(p_∞) _c. We have that ‖p^k−p∞‖2≤‖pk−p∞‖2+βkM,\| p_k-p_∞\|_2≤\|p_k-p_∞\|_2+ _kM, M=supx∈‖∇Φ(x)‖2M= _x \|∇ (x)\|_2, so there exists a T such that ‖p^T−p∞‖2<r\| p_T-p_∞\|_2<r, and hence p^k∈c=11\ p_k _c\=1 for all k≥Tk≥ T, which contradicts (13). Second, (13) also implies a contradiction when p∞∈∂cp_∞∈ _c. Let V(p)=Φ∗(p)−Φ(x†)V(p)= _*(p)- (x ). For sufficiently large k, p^k=pk+βk∇Φ(xk)∈ p_k=p_k+ _k∇ (x_k) since pk∈cp_k _c, so by a Taylor expansion V(p^k)=V(pk)+O(βk2) V( p_k)=V(p_k)+O( _k^2) +βk∇Φ(x∗(pk))⊤Dx∗(pk)∇Φ(x∗(pk)) + _k∇ (x^*(p_k)) \!D\!x^*(p_k)∇ (x^*(p_k)) (i) +βk∇Φ(x∗(pk))⊤Dx∗(pk)(∇Φ(xk)−∇Φ(x∗(pk))). + _k∇ (x^*(p_k)) \!D\!x^*(p_k) (∇ (x_k)\!-\!∇ (x^*(p_k)) ). (i) Observe the following regarding the RHS above. For term (i), by Assumption 1 we have that for any w∈ℝnw ^n, w⊤Sym(Dx∗(pk))w w *Sym (D\!x^*(p_k) )w =(a)−v⊤Sym(DG0(x∗(pk)))v (a)=-v *Sym (D\!G_0(x^*(p_k)) )v ≤(b)−m2‖v‖22≤(c)−m2σ12‖w‖22, (b)≤- m2\|v\|_2^2 (c)≤- m2 _1^2\|w\|_2^2, where we denote v=DG0(x∗(pk))−1wv=D\!G_0(x^*(p_k))^-1w, (a)(a) is due to the fact that Dx∗(pk)=−DG0(x∗(pk))Dx^*(p_k)=-DG_0(x^*(p_k)), (b)(b) is due to Assumption 1, and (c)(c) follows from the observation that ‖w‖2=‖DG0(x∗(pk))v‖2≤1σ1‖v‖2.\|w\|_2=\|DG_0(x^*(p_k))v\|_2≤ 1 _1\|v\|_2. By Lemma 2 and Assumption 2, term (i) satisfies (i)≤βk‖∇Φ(x∗(pk))‖2σ2L2‖xk−x∗(pk)‖2. eq:lemmaPE_3≤ _k\|∇ (x^*(p_k))\|_2 _2L_2\|x_k-x^*(p_k)\|_2. Conclude that V(p^k)≤V(pk) V( p_k)≤ V(p_k) +O(βk2)−βkm2σ12‖∇Φ(x∗(pk))‖22 +O( _k^2)- _k m2 _1^2\|∇ (x^*(p_k))\|_2^2 +βkσ2L2‖∇Φ(x∗(pk))‖2‖xk−x∗(pk)‖2. + _k _2L_2\|∇ (x^*(p_k))\|_2\|x_k-x^*(p_k)\|_2. We have by Lemma 3 that ‖xk−x∗(pk)‖2→0\|x_k-x^*(p_k)\|_2→ 0 and ‖∇Φ(x∗(pk))‖2→‖∇Φ(x∗(p∞))‖2>0\|∇ (x^*(p_k))\|_2→\|∇ (x^*(p_∞))\|_2>0, since p∞∈∂cp_∞∈ _c. For sufficiently large k, the negative quadratic dominates both the O(βk2)O( _k^2) term and the cross-term, implying V(p^k)<V(pk)≤c.V( p_k)<V(p_k)≤ c. Hence, ∑k=0∞βkpk+βk∇Φ(xk)∈c=∞, _k=0^∞ _k1\p_k+ _k∇ (x_k) _c\=∞, which contradicts (13). ∎ Lemma 5. Let cP_c be a compact (nonconvex) subset of an open U⊂ℝnU ^n, and let g:U→ℝng:U ^n be Lg−L_g-Lipschitz. Suppose cP_c is forward invariant for dynamics p˙=g(p) p=g(p) and contains a unique globally asymptotically stable equilibrium p†∈int(c).p ∈ *int(P_c). Let (pk)k≥0⊂c(p_k)_k≥ 0 _c satisfy pk+1=pk+akg(pk)p_k+1=p_k+a_kg(p_k), where ∑k=0∞ak=∞ _k=0^∞a_k=∞, ∑k=0∞ak2<∞ _k=0^∞a_k^2<∞. Then limk→∞pk=p† _k→∞p_k=p . Proof. Define tk=∑j=0k−1ajt_k= _j=0^k-1a_j and let p¯(t):[0,∞)→ℝn p(t):[0,∞) ^n be the linear interpolation of (pk)k(p_k)_k on t∈[tk,tk+1]t∈[t_k,t_k+1], that is, p¯(t)=pk+t−tkak(pk+1−pk),t∈[tk,tk+1]. p(t)=p_k+ t-t_ka_k(p_k+1-p_k), t∈[t_k,t_k+1]. (14) Since cP_c is non-convex, p¯(t) p(t) belongs in the convex hull co(c)co(P_c) and satisfies p¯(tk)∈c p(t_k) _c. Let B=supp∈c‖g(p)‖2B= _p _c\|g(p)\|_2, so ‖p¯(t)−pk‖2≤akB,t∈[tk,tk+1].\| p(t)-p_k\|_2≤ a_kB, t∈[t_k,t_k+1]. (15) Let ϵ>0ε>0 be such that cϵ=p:dist(p,c)≤ϵ⊂U.P_c^ε=\p: *dist(p,P_c)≤ε\⊂ U. Since ak→0a_k→ 0, there exists some K so that akB≤ϵa_kB≤ε for all k≥Kk≥ K, so (15) implies p¯(t)∈cϵ p(t) _c^ε for all t≥tKt≥ t_K. Hence g(p¯(t))g( p(t)) is well-defined for t≥tKt≥ t_K. For each n≥Kn≥ K, let pn(t)p^n(t) be the trajectory of p˙=g(p) p=g(p) with pn(0)=pnp^n(0)=p_n. The error ep(t)=p¯(tn+t)−pn(t)e_p(t)= p(t_n+t)-p^n(t) satisfies ‖ep(t)‖2≤Lg∫0t‖ep(τ)‖2τ+Lgmaxk≥nakBt.\|e_p(t)\|_2≤ L_g _0^t\|e_p(τ)\|_2\,dτ+L_g _k≥ na_kBt. By a similar Grönwall inequality argument as in [5, p. 12, Lemma 1], it follows that for all T>0T>0, supt∈[0,T]‖p¯(tn+t)−pn(t)‖2→0, as n→∞. _t∈[0,T]\| p(t_n+t)-p^n(t)\|_2→ 0, as n→∞. The result follows from the pseudotrajectory convergence to a compact connected internally chain transitive invariant set of p˙=g(p) p=g(p) (see e.g. [5, p. 15, Theorem 2]). ∎ The proof of Theorem 2 is finalized below. Proof of Theorem 2. Let δk=βkpk+βk∇Φ(xk)∈c _k= _k1\p_k+ _k∇ (x_k) _c\. By Lemma 3 it holds that ‖xk−x∗(pk)‖2→0\|x_k-x^*(p_k)\|_2→ 0, so it remains to show pk→p†p_k→ p . Denote g∗(p)=∇Φ(x∗(p))g_*(p)=∇ (x^*(p)) as in (5), so (8b) becomes pt+1 p_t+1 =pk+δk(g∗(pk)+ξk), =p_k+ _k (g_*(p_k)+ _k ), ξk _k =∇Φ(xk)−∇Φ(x∗(pk)), =∇ (x_k)-∇ (x^*(p_k)), where ‖ξk‖2≤L2‖xk−x∗(pk)‖2\| _k\|_2≤ L_2\,\|x_k-x^*(p_k)\|_2 is an o(1)o(1) term, and g∗g_* is L3L_3-Lipschitz on P, with L3=2L2/mL_3=2L_2/m. Define tk=∑j=0k−1δjt_k= _j=0^k-1 _j, so limk→∞tk=∞ _k→∞t_k=∞ by Lemma 4. Let p¯(t) p(t) be the interpolation of (pk)k(p_k)_k, as in (14), so ‖p¯(t)−pk‖2 \| p(t)-p_k\|_2 ≤δk‖g∗(pk)+ξk‖2≤δk(B+‖ξk‖2), ≤ _k\|g_*(p_k)+ _k\|_2≤ _k(B+\| _k\|_2), where B=supp∈c‖g∗(p)‖2B= _p _c\|g_*(p)\|_2 and ‖ξk‖2=o(1)\| _k\|_2=o(1) perturbation. Since the perturbation vanishes asymptotically, p¯(t) p(t) therefore remains an asymptotic pseudotrajectory for dynamics p˙=g∗(p) p=g_*(p), and the result follows from by Lemma 5. ∎ V Numerical Examples This section presents two illustrative examples that validate the convergence result given in Theorems 1 and 2. In both examples, the planner’s social cost is Φ:→ℝ :X , Φ(x)=12‖x−x†‖22 (x)= 12\|x-x \|_2^2, and x†∈intx ∈ *intX. V-A Aggregative Game over a Directed Network We consider n=5n=5 players competing in an aggregative game over a directed network. Each has a private cost ℓi(x)=12(qixi2+a∑j=1nwijxixj), _i(x)= 12 (q_ix_i^2+a _j=1^nw_ijx_ix_j ), (16) where x∈=[−2,2]nx =[-2,2]^n. The parameters qi>0q_i>0 represent an agent-specific preference, the matrix W=[wij]i,j=1nW=[w_ij]_i,j=1^n is a stochastic (non-symmetric) adjacency matrix with zero diagonal, and scalar a>0a>0 is the coupling strength between agents. The nominal pseudo-gradient is a linear map G0(x)=MxG_0(x)=Mx, where M=Q+aWM=Q+aW and Q=Diag(qi)Q= *Diag(q_i). Assumption 1 is satisfied for appropriate a (details given in Appendix B), so the response map is x∗(p)=−M−1px^*(p)=-M^-1p. We first verify Theorem 1 for 100100 initial conditions, sampled uniformly at random from intc∗ *intP_c^*. Figure 1 reports the evolution of the social cost Φ(x∗(p(t))) (x^*(p(t))) and the incentive error ‖p(t)−p†‖2\|p(t)-p \|_2 for two initial conditions, corresponding to the smallest and largest sublevel sets among the sampled initial conditions. It is evident that each sublevel set is forward invariant and all trajectories converge to p†p . Figure 1: Φ(x∗(p(t))) (x^*(p(t))) and ‖p(t)−p†‖2\|p(t)-p \|_2, under (5) with initial condition in intc∗ *intP_c^*. Trajectories depicted correspond to flows from the maximal and minimal sublevel sets across 100 initial conditions. Moreover, we verify Theorem 2 under two choices of the agent dynamics (8a). We consider agents who adapt their strategies according to the Nash-equilibrium and best-response learning rules, defined as fNE(x,p)=x∗(p)f NE(x,p)=x^*(p) and fBR(x,p)=−Q−1(p+aWx)f BR(x,p)=-Q^-1(p+aWx), respectively. Appendix B gives a detailed description of each rule, and illustrates that Assumption 3 holds. Figure 2 presents the evolution of the two-timescale discretization error ‖xk−x∗(pk)‖2\|x_k-x^*(p_k)\|_2 and the incentive error ‖pk−p†‖2\|p_k-p \|_2, comparing the two adaptations. The results have been computed for 100 initial conditions sampled uniformly in ×cX×P_c with c=0.8c∗c=0.8c^*. Figure 2: Median (solid) and min–max envelope (shaded) of ‖xk−x∗(pk)‖2\|x_k-x^*(p_k)\|_2 (top row) and ‖pk−p†‖2\|p_k-p \|_2 (bottom row) under iteration (8), with f=fNEf=f NE (left column) and f=fBRf=f BR (right column). Results represent 100 initial conditions sampled from int×c *intX×P_c, with c=0.8c∗c=0.8c^*. V-B Coupled Oscillator Game We further investigate a two-player coupled oscillator game adapted from [26]. Each player has a private cost ℓi(x)=−θicos(xi)+cos(x1−x2), _i(x)=- _i (x_i)+ (x_1-x_2), (17) where x∈=[−π3,π3]2x =[- π3, π3]^2 and θi>0 _i>0 are scalars. We select parameters θ1=4.2 _1=4.2 and θ2=5 _2=5, for which Assumption 1 holds (see Appendix B). In this game, the nominal pseudo-gradient is the nonlinear map G0(x)=[θ1sin(x1)−sin(x1−x2)θ2sin(x2)+sin(x1−x2)].G_0(x)= bmatrix _1 (x_1)- (x_1-x_2)\\ _2 (x_2)+ (x_1-x_2) bmatrix. For given p, the response x∗(p)x^*(p) can be solved numerically via an associated convex minimization problem (see Appendix B). Agents adapt their own strategies according to (8a), using a local projected gradient (PG) descent rule, fPG(x,p)=Π(x−ηGγ(x)),f PG(x,p)= _X (x-η G_γ(x) ), where η>0η>0 is a small constant, and Π _X is the projection onto the convex set X. Figure 3 illustrates the trajectories of (xk,pk)k≥0(x_k,p_k)_k≥ 0 for the two-timescale dynamics (8) in the strategy and incentive spaces, for the given initial condition and stepsizes ak=O(k−0.6)a_k=O(k^-0.6) and βk=O(k−0.9) _k=O(k^-0.9). Observe that the forward invariance of c0P_c_0 is not guaranteed in the transient regime, where c0=Φ∗(p0)−Φ(x†)c_0= _*(p_0)- (x ), due to the tracking bias introduced by the discretization error. Nevertheless, incentive iterates remain in cP_c, with c=0.95c∗c=0.95c^*, and converge to p†p . The indicator rejects no updates after the initial transient, as predicted by Lemma 4. Finally, Figure 4 presents the discretization error ‖xk−x∗(pk)‖2\|x_k-x^*(p_k)\|_2 and incentive error ‖pk−p†‖2\|p_k-p \|_2 for iteration (8) while varying the degree of timescale separation βk/ak=O(k−γ) _k/a_k=O(k^-γ) for different values of γ>0γ>0. Smaller γ values introduce a more pronounced tracking bias in the incentive, and larger γ values result in diminished finite-time incentive performance. Figure 3: Iterates (xk,pk)k(x_k,p_k)_k satisfying (8), from the initial condition x0=(0,−0.5)⊤x_0=(0,-0.5) and p0=(−3,−3)⊤p_0=(-3,-3) , and stepsize sequences ak=O(k−0.6)a_k=O(k^-0.6) and βk=O(k−0.9) _k=O(k^-0.9). Solid lines indicate the boundaries ∂ and ∂c _c, with c=0.95c∗c=0.95c^*. Dashed line indicates ∂c0 _c_0 with c0=0.62c∗c_0=0.62c^*, which corresponds to the sublevel set on which p0p_0 lies. Figure 4: ‖xk−x∗(pk)‖2\|x_k-x^*(p_k)\|_2 and ‖pk−p†‖2\|p_k-p \|_2 under iteration (8), with initial condition x0=(0,−0.5)⊤x_0=(0,-0.5) and p0=(−3,−3)⊤p_0=(-3,-3) . Lines depict variations of the timescale separation degree βk/ak=O(k−γ) _k/a_k=O(k^-γ) for different γ>0γ>0. VI Concluding Remarks This work studies adaptive incentive design under information asymmetry, where the planner observes either the Nash equilibrium response or an evolving response trajectory that asymptotically tracks the induced Nash equilibrium. Our first contribution is to establish a social-gradient dynamics in continuous time for seeking the optimal incentive which does not require the equilibrium sensitivity information and still yields a descent direction for the planner’s objective. Our second contribution is to establish the two-timescale implementation of the proposed social-gradient dynamics, in which agents endowed with learning dynamics respond on a faster timescale than the planner. Its convergence to the socially optimal pair is proven for any agent learning dynamics that converges uniformly. We consider two open questions as natural extensions of the present analysis. First, if agents’ local costs are C0C^0 only, the pseudo-gradient extends to a set-valued subdifferential, and the first-order optimality condition corresponds to a generalized variational inequality. Second, the proposed two-timescale method operates with knowledge of the feasible set cP_c. It would be interesting to investigate whether this requirement can be relaxed to knowledge of the set X alone. A natural extension would be an algorithm that incrementally refines the operating domain from an initial conservative estimate of the safe set using observations that approach ∂ . References [1] T. Alpcan, L. Pavel, and N. Stefanovic (2009) A control theoretic approach to noncooperative game design. In Proc. 48th IEEE Conference on Decision and Control (CDC) held Jointly with 2009 28th Chinese Control Conference, Shanghai, China, p. 8575–8580. External Links: ISSN 0191-2216, Document, Link Cited by: §I. [2] T. Alpcan and L. Pavel (2009) Nash equilibrium design and optimization. In Proc. 2009 International Conference on Game Theory for Networks, Istanbul, Turkey, p. 164–170. External Links: Document, Link, ISBN 978-1-4244-4176-1 Cited by: §I. [3] J. Barrera and A. Garcia (2015) Dynamic incentives for congestion control. IEEE Transactions on Automatic Control 60 (2), p. 299–310. External Links: Document Cited by: §I. [4] T. Başar (1984-03) Affine Incentive Schemes for Stochastic Systems with Dynamic Information. SIAM Journal on Control and Optimization 22 (2), p. 199–210. External Links: ISSN 0363-0129, 1095-7138, Document Cited by: §I. [5] V. S. Borkar (2008) Stochastic Approximation: A Dynamical Systems Viewpoint. Texts and Readings in Mathematics, Vol. 48, Hindustan Book Agency, Gurgaon. External Links: Document, Link, ISBN 978-81-85931-85-2 978-93-86279-38-5 Cited by: §IV, §IV, §IV, §IV, Remark 1. [6] B. Colson, P. Marcotte, and G. Savard (2007) An overview of bilevel optimization. Annals of Operations Research 153 (1), p. 235–256. External Links: ISSN 1572-9338, Document Cited by: §I. [7] F. Facchinei and J. Pang (Eds.) (2004) Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer New York. External Links: Document, ISBN 978-0-387-95580-3 Cited by: §A-A, §B-B, §I, §I, §IV. [8] F. Facchinei and J. Pang (2009) Nash equilibria: the variational approach. In Convex Optimization in Signal Processing and Communications, D. P. Palomar and Y. C. Eldar (Eds.), p. 443–493. External Links: Document, Link, ISBN 978-0-521-76222-9 978-0-511-80445-8 Cited by: §I. [9] M. Fochesato, C. Cenedese, and J. Lygeros (2022-12) A Stackelberg game for incentive-based demand response in energy markets. In Proc. 61st Conference on Decision and Control (CDC), Cancun, Mexico, p. 2487–2492. External Links: Document, ISBN 978-1-6654-6761-2 Cited by: §I. [10] T. L. Friesz, R. L. Tobin, H. Cho, and N. J. Mehta (1990) Sensitivity analysis based heuristic algorithms for mathematical programs with variational inequality constraints. Mathematical Programming 48 (1–3), p. 265–284. External Links: ISSN 0025-5610, 1436-4646, Document Cited by: §I. [11] P. D. Grontas, G. Belgioioso, C. Cenedese, M. Fochesato, J. Lygeros, and F. Dörfler (2024-12) BIG Hype: Best Intervention in Games via Distributed Hypergradient Descent. IEEE Transactions on Automatic Control 69 (12), p. 8338 – 8353. External Links: ISSN 0018-9286, 1558-2523, 2334-3303, Document Cited by: §I. [12] A. Hauswirth, S. Bolognani, G. Hug, and F. Dorfler (2021-02) Timescale Separation in Autonomous Optimization. IEEE Transactions on Automatic Control 66 (2), p. 611–624. External Links: ISSN 0018-9286, 1558-2523, 2334-3303, Document Cited by: §I. [13] C. Ho, A. Slivkins, and J. W. Vaughan (2014) Adaptive contract design for crowdsourcing markets: bandit algorithmsfor repeated principal-agent problems. In Proc. 15th ACM Conference on Economics and Computation, New York, NY, USA, p. 359–376. External Links: Document Cited by: §I. [14] Y. Ho, P. Luh, and R. Muralidharan (1981) Information structure, stackelberg games, and incentive controllability. IEEE Transactions on Automatic Control 26 (2), p. 454–460. External Links: Document Cited by: §I. [15] Y. Ho, P. Luh, and G. Olsder (1980-12) A control-theoretic view on incentives. In Proc. 19th Conference on Decision and Control, Albuquerque, NM, USA, p. 1160–1170. External Links: Document Cited by: §I. [16] Y. Kim, S. Leyffer, and T. Munson (2020) MPEC Methods for Bilevel Optimization Problems. In Bilevel Optimization, S. Dempe and A. Zemkoho (Eds.), Vol. 161, p. 335–360. External Links: Document Cited by: §I. [17] J. Li, J. Yu, Y. (. Nie, and Z. Wang (2020) End-to-end learning and intervention in games. In Proc. 34th International Conference on Neural Information Processing Systems, Vancouver, Canada, p. 16653–16665. External Links: ISBN 978-1-7138-2954-6 Cited by: §I. [18] J. Li, M. Motoki, and B. Zhang (2024-10) Socially optimal energy usage via adaptive pricing. Electric Power Systems Research 235, p. 110640. External Links: ISSN 03787796, Document Cited by: §I, §I. [19] P. Li, H. Wang, and B. Zhang (2019) A distributed online pricing strategy for demand response programs. IEEE Transactions on Smart Grid 10 (1), p. 350–360. External Links: Document Cited by: §I. [20] B. Liu, J. Li, Z. Yang, H. Wai, M. Hong, Y. (. Nie, and Z. Wang (2022) Inducing equilibria via incentives: simultaneous design-and-play ensures global convergence. In Proc. 36th International Conference on Neural Information Processing Systems (NIPS), New Orleans, LA, USA, p. 29001 – 29013. External Links: ISBN 978-1-7138-7108-8 Cited by: §I. [21] Z. Luo, J. Pang, and D. Ralph (1996) Mathematical programs with equilibrium constraints. Cambridge University Press. Cited by: §I. [22] C. Maheshwari, K. Kulkarni, M. Wu, and S. Sastry (2024) Adaptive Incentive Design with Learning Agents. arXiv. Note: Preprint arXiv:2405.16716 External Links: Document Cited by: §I, §I. [23] E. Mojica-Nava, J. I. Poveda, and N. Quijano (2022) Stackelberg Population Learning Dynamics. In Proc. 2022 IEEE 61st Conference on Decision and Control (CDC), Cancun, Mexico, p. 6395–6400. External Links: Document, Link, ISBN 978-1-6654-6761-2 Cited by: §I. [24] J. I. Poveda, P. N. Brown, J. R. Marden, and A. R. Teel (2017) A class of distributed adaptive pricing mechanisms for societal systems with limited information. In Proc. 56th Annual Conference on Decision and Control (CDC), Vol. , p. 1490–1495. External Links: Document Cited by: §I. [25] L. J. Ratliff, R. Dong, S. Sekar, and T. Fiez (2019-05) A Perspective on Incentive Design: Challenges and Opportunities. Annual Review of Control, Robotics, and Autonomous Systems 2 (1), p. 305–338. External Links: ISSN 2573-5144, 2573-5144, Document Cited by: §I, §I. [26] L. J. Ratliff and T. Fiez (2021-08) Adaptive Incentive Design. IEEE Transactions on Automatic Control 66 (8), p. 3871–3878. External Links: ISSN 0018-9286, 1558-2523, 2334-3303, Document Cited by: §I, §IV, §V-B. [27] J. B. Rosen (1965-07) Existence and Uniqueness of Equilibrium Points for Concave N-Person Games. Econometrica 33 (3), p. 520–534. External Links: 1911749, ISSN 00129682, Document Cited by: §I. [28] G. Scutari, D. Palomar, F. Facchinei, and J. Pang (2010) Convex Optimization, Game Theory, and Variational Inequality Theory. IEEE Signal Processing Magazine 27 (3), p. 35–49. Cited by: §IV. [29] T. Tatarenko, W. Shi, and A. Nedić (2021) Geometric Convergence of Gradient Play Algorithms for Distributed Nash Equilibrium Seeking. IEEE Transactions on Automatic Control 66 (11), p. 5342–5353. External Links: ISSN 1558-2523, Document, Link Cited by: §IV. [30] R. K. Velicheti, S. Bose, and T. Başar (2025-09) Harnessing Information in Incentive Design. arXiv. External Links: 2509.02493, Document Cited by: §I. [31] Y. Zheng and T. Basar (1982-06) Existence and derivation of optimal affine incentive schemes for Stackelberg games with partial information: a geometric approach. International Journal of Control 35 (6), p. 997–1011. External Links: ISSN 0020-7179, 1366-5820, Document Cited by: §I. Appendix A Proofs of Supporting Lemmas A-A Proof of Lemma 1 Proof. We prove the lemma in two steps: Step 1. We show that x∗(⋅)x^*(·) is uniquely defined on ℝnR^n. For any x,y∈x,y , denote v=x−yv=x-y. Since X is convex, xt=y+tv∈x_t=y+tv for all t∈[0,1]t∈[0,1]. Under Assumption 1, v⊤(G0(x)−G0(y))=∫01v⊤DG0(xt)vt≥m2‖v‖22.v (G_0(x)-G_0(y))= _0^1v D\!G_0(x_t)v\,dt≥ m2\|v\|_2^2. Therefore G0(x)G_0(x) is m2− m2-strongly monotone on X, and so is Gγ(x)G_γ(x) for any p. This implies that (2) has a unique solution x∗(p)∈x^*(p) (see [7, Theorem 2.3.3]), so the response map is uniquely defined. Step 2. We show that the map x∗(⋅)x^*(·) restricted to P is a diffeomorphism. By Assumption 1, DG0(x)D\!G_0(x) is nonsingular for every x∈intx∈ *intX and G0G_0 is injective by strong monotonicity. It follows that G0:int→G0(int)G_0: *intX→ G_0( *intX) is a diffeomorphism from int *intX to −=G0(int)-P=G_0( *intX). Since G0G_0 is an open map, P is open, and x∗(p)=G0−1(−p)x^*(p)=G_0^-1(-p) defines a 1C^1 diffeomorphism x∗:→intx^*:P→ *intX. ∎ A-B Proof of Lemma 2 Proof. Claim (i). Since x∗∈intx^*∈ *intX, x=x∗+td∈x=x^*+td for all small t>0t>0 and d∈ℝnd ^n. By (2), we have Gγ(x∗)⊤d≥0G_γ(x^*) d≥ 0 for all d∈ℝnd ^n, which implies Gγ(x∗)=0G_γ(x^*)=0. Further, by Assumption 1, G0G_0 is m2 m2-strongly monotone on X, therefore, for any p1,p2∈p_1,p_2 , we have m2‖x∗(p1)−x∗(p2)‖22 m2\|x^*(p_1)-x^*(p_2)\|_2^2 ≤(G0(x∗(p1))−G0(x∗(p2)))⊤(x∗(p1)−x∗(p2)) ≤ (G_0(x^*(p_1))-G_0(x^*(p_2)) ) (x^*(p_1)-x^*(p_2) ) ≤(a)‖p1−p2‖2‖x∗(p1)−x∗(p2)‖2, (a)≤\|p_1-p_2\|_2\,\|x^*(p_1)-x^*(p_2)\|_2, where (a)(a) uses Gγ(x∗(p1))=Gγ(x∗(p2))=0G_γ(x^*(p_1))=G_γ(x^*(p_2))=0. By Lemma 1 and Claim (i), we have that for all p∈p , x∗=G0−1(−p)x^*=G_0^-1(-p) and Dx∗(p)=−(DG0(x∗))−1D\!x^*(p)=-(D\!G_0(x^*))^-1. Claims (i) and (i). For any w∈ℝn∖0w ^n \0\, setting v=DG0(x∗)−1wv=D\!G_0(x^*)^-1w, w⊤Sym(Dx∗)w=−v⊤Sym(DG0(x∗))v<0, and w *Sym(D\!x^*)w=-v *Sym(D\!G_0(x^*))v<0, and m2‖w‖22≤w⊤Sym(DG0(x∗))w≤‖w‖2‖DG0(x∗)w‖2. m2\|w\|_2^2≤ w *Sym(D\!G_0(x^*))w≤\|w\|_2\|D\!G_0(x^*)w\|_2. It follows that σmax(Dx∗)=σmin(DG0(x∗))−1≤2m _ (D\!x^*)= _ (D\!G_0(x^*))^-1≤ 2m, and σmin(Dx∗)≥(maxx∈Xσmax(DG0(x)))−1. _ (D\!x^*)≥( _x∈ X _ (D\!G_0(x)))^-1. Claim (iv). Given p1,p2∈p_1,p_2 , let Ai=DG0(x∗(pi))A_i=D\!G_0(x^*(p_i)). We have that Dx∗(p1)−Dx∗(p2)=A2−1(A1−A2)A1−1, aligned D\!x^*(p_1)-D\!x^*(p_2)=A_2^-1 (A_1-A_2 )A_1^-1, aligned so with Claims (i) and (i) we conclude ‖Dx∗(p1)−Dx∗(p2)‖2≤‖A2−1‖2‖A1−A2‖2‖A1−1‖2 \|D\!x^*(p_1)-D\!x^*(p_2)\|_2≤\|A_2^-1\|_2\|A_1-A_2\|_2\|A_1^-1\|_2 ≤4L1m2‖x∗(p1)−x∗(p2)‖2≤8L1m3‖p1−p2‖2. ≤ 4L_1m^2\|x^*(p_1)-x^*(p_2)\|_2≤ 8L_1m^3\|p_1-p_2\|_2. ∎ Appendix B Supplement on Numerical Examples B-A Aggregative Game over a Directed Network We first give a sufficient condition such that Assumption 1 is satisfied. Observe that Sym(M) *Sym(M) =Q+aSym(W) =Q+a *Sym(W) (18) ⪰(λmin(Q)−a‖Sym(W)‖2)≻0, ( _ (Q)-a\| *Sym(W)\|_2 )I 0, so, Assumption 1 holds when a<λmin(Q)/‖Sym(W)‖2a< _ (Q)/\| *Sym(W)\|_2. It follows that M is nonsingular, and the linearity of G0G_0 yields a closed-form response map x∗(p)=−M−1px^*(p)=-M^-1p. Moreover, we verify Assumption 3 holds for each of the learning dynamics in the example. In the NE-update learning rule agents utilize fNE(x,p)=x∗(p)f NE(x,p)=x^*(p) in (8a). Assumption 3 is satisfied since dynamics x˙=x∗(p)−x x=x^*(p)-x are linear and admit the solution x(t)=x∗(p)+(x(0)−x∗(p))e−t.x(t)=x^*(p)+(x(0)-x^*(p))e^-t. In the BR-update learning rule each agent minimizes its incentivized cost against the joint strategy of other agents, which yields fiBR(x,p)=argminyi∈icγ(yi,x−i).f_i BR(x,p)= *arg\,min_y_i _ic^γ(y_i,x_-i). Since ciγ(x)c_i^γ(x) are strictly convex with respect to xix_i, each minimizer xi∈intix_i∈ *intX_i satisfies the first-order condition qixi+a∑j=1nwijxj+pi=0q_ix_i+a _j=1^nw_ijx_j+p_i=0, which can be expressed fBR(x,p)=−Q−1(p+aWx).f BR(x,p)=-Q^-1(p+aWx). To verify Assumption 3, consider the error e=x−x∗(p)e=x-x^*(p). When x˙=fBR(x,p)−x x=f BR(x,p)-x, it follows that e˙=−Q−1Me e=-Q^-1Me. Since Q is diagonal and (18) holds, it follows that Sym(Q−1M)⪰m/(2λmax(Q))≻0 *Sym(Q^-1M) m/(2 _ (Q))I 0. Therefore, Q−1MQ^-1M is anti-Hurwitz and ‖x(t)−x∗(p)‖2 \|x(t)-x^*(p)\|_2 ≤‖e(0)‖2‖exp(−Q−1Mt)‖2 ≤\|e(0)\|_2\| (-Q^-1Mt)\|_2 ≤‖e(0)‖2exp(−μ2(Q−1M)t), ≤\|e(0)\|_2 (- _2(Q^-1M)t), where μ2(A)=λmax(Sym(A)) _2(A)= _ ( *Sym(A)) denotes the logarithmic norm induced by ∥⋅∥2\|·\|_2. The exponential convergence of x(t)−x∗(p)x(t)-x^*(p), uniform over p∈cp _c, follows. B-B Coupled Oscillator Game We first present a sufficient condition for Assumption 1 to hold. The Jacobian of G0G_0 can be computed DG0(x)=[θ1cos(x1)−cos(Δx)cos(Δx)cos(Δx)θ2cos(x2)−cos(Δx)],D\!G_0(x)= bmatrix _1 (x_1)\!-\! ( x)& ( x)\\ ( x)& _2 (x_2)\!-\! ( x) bmatrix, where Δx=x1−x2 x=x_1-x_2. By Gershgorin’s circle theorem, λmin(DG0(x))≥miniθicos(xi)−cos(Δx)−|cos(Δx)|. _ (D\!G_0(x))≥ _i\! \ _i (x_i)- ( x)-| ( x)| \. Since |cos(Δx)|≤1| ( x)|≤ 1 and cos(xi)≥cos(π/3) (x_i)≥ (π/3) for all x∈x , Assumption 1 holds whenever θi>2/cos(π/3) _i>2/ (π/3) for i=1,2i=1,2. Regarding the numerical computation of the map x∗x^*, observe that DG0(x)D\!G_0(x) is symmetric and hence, for every p, there exists a Ψp:→ℝ _p:X such that ∇Ψp(x)=G0(x)+p∇ _p(x)=G_0(x)+p over X (see [7, p.14, Theorem 1.3.1]). One can verify that Ψp(x)=−θ1cos(x1)−θ2cos(x2)+cos(Δx)+p⊤x. _p(x)=- _1 (x_1)- _2 (x_2)+ ( x)+p x. Therefore, computing the solution x∗(p)x^*(p) to (2) is equivalent to solving the convex program x∗(p)∈argminx∈Ψp(x)x^*(p)∈ *arg\,min_x _p(x). Finally, the example implements the projected-gradient learning dynamics fPGf PG, in which fiPG(x,p)=Πi(xi−η∂cγ∂xi(x)),f_i PG(x,p)= _X_i (x_i-η ∂ c^γ∂ x_i(x) ), where η>0η>0 is a constant and Πi _X_i is the projection on iX_i. To show that fPGf PG satisfies Assumption 3, observe that the fixed point condition x∗(p)=Π(x∗(p)−ηGγ(x∗(p)))x^*(p)= _X (x^*(p)-η G_γ(x^*(p)) ) holds. By the non-expansiveness of Π _X and strong monotonicity of GγG_γ, ‖fPG(x,p)−x∗(p)‖22≤(1−ηm+η2L2)‖x−x∗(p)‖22, \|f PG(x,p)-x^*(p)\|_2^2≤(1-η m+η^2L^2)\|x-x^*(p)\|_2^2, where L=maxx∈‖DG0(x)‖2L= _x \|D\!G_0(x)\|_2. Let ρ=(1−ηm+η2L2)12ρ=(1-η m+η^2L^2) 12. When η∈(0,mL2)η∈(0, mL^2), it holds that ρ∈(0,1)ρ∈(0,1). Applying Grönwall’s inequality on dt12‖e‖22≤−(1−ρ)‖e‖22 ddt 12\|e\|_2^2≤-(1-ρ)\|e\|_2^2 yields the required ℒKL bound, which is uniform in cP_c.