Stackelberg games encompass a wide range of practical problems including incentive design, Bayesian persuasion, inverse optimization, bilevel optimization, cybersecurity, adversarial learning, to name a few. Stackelberg games are comprised of two type of players -leader and followers 1 . Mathematically, they are represented as follows: where X is the leader's strategy set, Y ⊆ R d is the followers' (joint) strategy set, f : X × Y -→ R is the utility of the leader, G : X × Y -→ R d is the game Jacobian of followers and SOL(Y, G(x, •)) is a variational inequality problem that denotes the equilibrium response of followers, given the strategy of leader be x ∈ X. Assuming that the set S(x) is singleton for every x ∈ X (commonly referred as lower-level singleton assumption), (I.1) is equivalent to optimizing the following hyper-objective:
Note that in general (I.2) is non-convex optimization problem. Thus, the goal in Stackelberg games is to find a stationary point / local optima of (I.2) ( [2]).
In numerous practical scenarios, it is unrealistic to presume that the leader possesses any information regarding the variational inequality problem at the lower-level, including the mapping G(x, •) and even their strategy set Y -information traditionally assumed in prior research on solving Stackelberg games. Thus, the key question we ask in this work is:
Q: Can we design efficient algorithms for Stackelberg games where the leader does not require any explicit knowledge of the game played between followers? In this work, we affirmatively answer the above question in the setting where the leader can only probe the followers with different strategies and receive estimates of their (approximated) equilibrium responses. This is in contrast to the common assumption in the literature on Stackelberg games, where it is assumed that the leader has access to an equilibrium or best-response of followers either by knowledge of the utility function of followers or through an oracle. In particular, we consider that followers are rational in the sense that they employ an adaptation/learning algorithm, which asymptotically converges to the equilibrium [3].
We propose a two-loop algorithm where, in the outer loop, the leader fixes its strategy (i.e., the value of x) and announces it to the followers. Between two updates of the leader's strategy, the followers employ an adaptation algorithm, for a finite number of steps, so that they converge to an approximate equilibrium (or best-response). Upon observing the followers' behavior, the leader constructs an approximate estimator of the gradient of the hyper-objective (I.2) and updates its strategy via gradient descent using the estimator.
We show that the proposed algorithm converges to a stationary point of (I.2) at a rate O(T -1/2 ). Moreover, we show that if the hyper-objective satisfies the strict-saddle property, i.e. the minimum eigenvalue at any saddle point is strictly negative, then the iterates asymptotically avoid saddle points (which include local maxima) and converge to a local minima of the hyper-objective (aka local Stackelberg equilibrium [2]).
We corroborate the theoretical results by conducting a simulated study of the proposed algorithm to design tolls over the Sioux Falls (South Dakota, US) transportation network. In this setup, we assume that the leader does not know the origin-destination (o-d) demand of travelers moving between different o-d pairs, which is sensitive information.
Learning in Stackelberg games: Learning in Stackelberg games with finite actions is an active area of research ( [4]- [8]), where the leader has access to either a noisy or exact best response oracle. Furthermore, a dominant paradigm in this literature is to consider two-player games with finite strategy sets or linearly parametrized utility functions, with the exception of [2], [9]- [11]. In [2], the authors study the convergence of a two-timescale algorithm to the Stackelberg equilibrium, requiring knowledge of the Hessian of followers' utility functions for leader updates. In [9], [10], the authors require the followers to follow a specific (i.e. gradient type) learning algorithm in order to ensure convergence. Finally, in [11], the authors impose strong convexity assumption on the hyper-objective which is restrictive (as shown in [12]). In this work, we aim to design followeragnostic learning in a general-sum Stackelberg game in continuous spaces with no knowledge of the followers' utility functions or learning algorithms and not imposing restrictive assumptions about convexity of hyper-objective.
Bilevel optimzation. Bilevel optimization, a subset of problem (I.1), is extensively studied in literature, resembling a Stackelberg game with a single leader and follower. Existing research on bilevel optimization pursues three main approaches. The first utilizes a value function-based approach, converting the problem into a constrained singlelevel optimization problem with convergence guarantees to approximate Karush-Kuhn-Tucker (KKT) points [13], [14]. However, such points may not capture locally optimal solutions [15]. Another line of research focuses on asymptotic convergence of solutions of simpler bilevel problems than (I.1) under various assumptions on the lower-level objective function structure [16]- [18]. The third line explores solving the non-convex optimization problem (I.2) using gradient descent, requiring the computation of the gradient of the solution mapping, denoted as ∇S(x). While many methods exist for approximating ∇S(x), including Automatic Implicit Differentiation (AID) ( [19]- [23]), or Iterative Differentiation ( [20], [24]- [26]), our work is closely related to zerothorder methods, specifically avoiding the computation of the Hessian ( [15]). Our proposed algorithm shares similarities with [15], but we eliminate the need for oracle access to a lower-level optimal solution, leveraging two-timescale stochastic approximation to analyze accumulated errors [15].
Consider the following Stackelberg game
where
Under mild conditions on the monotonicity of G(x, •), it is ensured that S(x) is non-empty and convex ( [27]).
In what follows, we call a continuously differentiable function f :
Next, we introduce the main assumptions on the parameters of (SG) made throughtout this paper Assumption 1. (1) For every y ∈ Y , the function f (•, y) is L 1 -Lipschitz. Additionally, for every x ∈ X, the function f (x, •) is L 2 -Lipschitz and ℓ 2 -smooth.
(2) For every x ∈ X, the set S(x) is singleton and function
Assumption 1-( 1) is a common assumption employed in literature to derive rates of convergence [10], [11]. Assumption 1-( 2), which requires that the set S(x) exists, is singleton and Lipscthiz continuous for every x, holds for strongly monotone games at lower level [28]. Furthermore, it also applies to the incentive design problem in routing games, as discussed in Section III. Assumption 1-( 3) is a technical condition we impose on the hyper-objective to use Taylor's series expansion in the proof of convergence. Notably, this assumption is less restrictive than those imposed on the hyper-objective in [11]. We believe this assumption can be further relaxed, but we leave this as an interesting direction for future work.
Under the setting presented in this section, it can be verified that the set S(x) exists, is singleton, and is Lipschitz continuous mapping [28].
The goal of social planner is to minimize the overall congestion on the network while also minimizing the tolls levied on travelers. More formally, the planner's objective function is given by f (x, y) = e∈E w e (y)ℓ e (w e (y))+λ∥x∥ 2 , where the first term corresponds to the average congestion on the network and second term is a regularization term with parameter λ > 0, which ensures low values of tolls 3 . Thus, the problem of toll design is as follows
which is an instantiation of (SG).
Remark 1. In order to compute S(x) in (III.3) the planner needs to know the set Y that requires knowledge of the demand of travelers between various o-d pairs, which is a sensitive information. In Section V, we use the proposed approach to solve (III.4) where the designer does not know the demand of travelers and can only observe the congestion levels (w e ) e∈E on the network in response to the set tolls.
In this section, we present a follower agnostic algorithm for solving (SG). Following which, we present the convergence guarantees of the proposed algorithm to a stationary point. Additionally, we show that the algorithm will eventually converge to a local optima by avoiding the saddle points and local maximum.
The algorithm is based on alternatively moving towards solution to the variational inequality at lower level and descending along the upper-level objective function. Specifically, between two updates of leader (upper-level), the followers (lower level) employ an iterative adaptive rule, aimed to solve the variational inequality SOL(•), for a fixed number of steps. Following which, the upper level iterates descend where F (x; δ, v) denotes a gradient estimator of function f (•) := f (•, S(•)), evaluated at x with parameters δ, v. We shall describe the estimator in detail below.
b) Gradient estimator: In order to compute the gradient of f (x), we need to compute the derivative through the solution to the variational inequality in (SG), i.e. S(x), which may involve higher order gradient computations and at times is not computable in closed form due to constraints. In this work, we consider a gradient estimator inspired from [30], [31]. Specifically, we consider the following estimator
such that (i) x = x + δv, where v ∈ S(R d ) := {z ∈ R d : ∥z∥ 2 = 1} and δ > 0, are referred as perturbation and perturbation radius respectively; (ii) K is a positive integer capturing the number of rounds of adaptation rule employed by followers between two updates of leader's strategy; (iii) for any x ∈ X, k ∈ [K -1] consider a iterative solver for variational inequality denoted by H such that
where y (0) is some initialization for the iterative solver of variational inequality. For example, when the lower level problem is just a convex optimization problem with objective function g(x, •), a typical choice of H k is projected gradient descent, i.e. H k (y; x) = P Y (y -γ k ∇ y g(x, y)), where P Y denotes the orthogonal projection on Y and γ k is the step size. Note that, in order to construct the gradient estimator in (IV.1), the leader need not know the exact description of update rule H k . For most of the paper, we shall concisely denote y (k) (x) and y (k) (x) as ỹ(k) and y (k) respectively.
Remark 2. Direct application of zeroth-order gradient estimator from [30], [31] would result in following estimator
where f is defined in (I.2). Observe that the gradient estimators F and F differ because in (IV.1) we evaluate f (x, •) at y (K) (x) while in (IV.2) we evaluated it at S(x) for any x ∈ R d . This induces additional bias in the gradient estimator that needs to be appropriately accounted while establishing convergence results.
c) Algorithm: The algorithms runs for T rounds. In every round t ∈ [T -1] the leader queries the followers with two strategies x t and xt = x t +δ t v t where v t ∼ Unif(S(R d )) is a vector sampled uniformly randomly from the unit sphere in R d and δ t is the perturbation radius (refer line 2-3 in Algorithm 1). The followers respond to the leader's Algorithm 1: Follower Agnostic Stackelberg Optimization Algorithm Data: Time horizon T , Initial conditions y
t 10 end strategies by using an iterative variational inequality solver for K steps to obtain ỹ(K) t and y (K) t respectively (refer line 4 and 7 in Algorithm 1). After observing ỹ(K) t and y (K) t
, the leader computes a gradient estimator as per (IV.1). The leader updates its strategy for next time as per (UL) (refer line 8 in Algorithm 1). The followers initialize their strategies as per line 9 in Algorithm 1.
We now study the convergence properties of Algorithm 1.
Assumption 2. For any x, x ∈ X, the updates in (LL) are such that ∥y (K) (x)-y (K) (x)∥ ≤ C∥x-x∥, for some C > 0.
Assumption 2 posits that the adaptation rule employed by followers is stable with respect to perturbations in the leader's strategy. This assumption is typically satisfied by many algorithms, including gradient-based algorithms.
Assumption 3. Atleast one of the following holds:
(1a) For any x ∈ X, the iterates (LL) converge to equilibrium at a polynomial rate. That is, for any initial point
where λ, C are positive scalars. (1b) For any x ∈ X, the iterates (LL) converge to equilibrium at a exponential rate. That is, for any initial point y (0) , ∥y (K) (x) -S(x)∥ ≤ Cρ K ∥y (0) -S(x)∥, where C is a positive scalar and ρ ∈ [0, 1).
Remark 3. Convergence of lower-level problem is extensively studied in literature, e.g. [32], [33], and is not the focus of this article. Assumption 3(1a) holds for gradient descent updates for convex functions that satisfy quadratic growth condition [34]. Meanwhile, Assumption 3(1b) holds for gradient descent on strongly convex functions.
Then the updates (x t ) t∈[T ] in Algorithm 1 are such that
where α = CK -λ if Assumption 3(1a) hold, or α = ρ K if Assumption 3(1b) hold.
Intuitively, the theorem states that if we want to converge closer to a stationary point then we need to run the Algorithm 1 with larger T or smaller α (i.e. larger K). Crucially, the term αd 3 in the bound is due to error accumulation between time steps due to non-convergence of lower-level to exact solution of variational inequality S(x). Owing to such precise characterization of error accumulation across time steps, our rate is informative of the computational complexity of solving the bi-level problem while in other contemporary work, namely [15], it resembles iteration complexity of the oracle. Since α is a function of K, the number of lower level iterations in every round, we can choose K to be large enough to make sure that the algorithm converges closer to the stationary point.
Remark 4. We know that for non-convex smooth functions, gradient descent converges to a stationary point (at a rate of O(1/ √ T )). However, the key point of departure of (UL) from standard gradient descent is the presence of bias in the gradient estimator. Consequently, the key component of the proof is to bound the error in the gradient estimator (IV.1). This is because the estimator can be decomposed as
denotes the bias introduced due to the difference between standard zeroth-order gradient estimator, as per (IV.2), and the true gradient. The term E
(2) t denotes the randomness introduced if we were to use the standard zeroth-order gradient estimator (IV.2). Finally, the term E
(3) t denotes the bias introduced due to difference between our gradient estimator (IV.1) and the standard zeroth-order gradient estimator (cf. Remark 2). a) Proof of Theorem 1: The proof of Theorem 1 follows by noting that f approximately decreases along the trajectory (UL) (Lemma 1). Note that the decrease is said to be "approximate" because of the bias introduced by (IV.1) in comparison to actual gradient ∇ f (•). We then proceed to individually bound the bias terms (Lemma 2). The convergence rate follows by using the step size and perturbation radius stated in the statement of Theorem 1.
Proof of Theorem 1. From Lemma 1 we know that f (•) approximately decreases along the trajectory of (UL). That is,
Using the bounds on error terms from Lemma 2, we obtain
Re-arranging the terms and adding and substracting the term f (x * ) = min x∈X f (x), we obtain
Summing the previous equation over time step t we obtain
Setting η t = η(t+1) -1/2 d -1 and δ t = δ(t+1) -1/4 d -1/2 , as per the statement of Theorem 1, and dividing both sides by t∈[T ] η t , we obtain
, where C is a positive scalar. Next, we bound Term E + Term F as follows
where in second equality
), and we have appropriately adjusted the constant C to account for additinal constants. Thus, combining (IV.4) and (IV.5), we obtain
To conclude, we obtain
This concludes the proof. Now, we formally state the Lemmas used in the proof.
The proof of Lemma 1 follows in two steps: First, we use second-order Taylor series expansion of f along the iterate values. Second, we use (UL) and complete the squares using algebraic manipulations. A detailed proof is provided in the extended version of this paper [1].
Lemma 2. The errors E ∥E (i) t ∥ 2 for i ∈ {1, 2, 3} are bounded as follows:
where C is a scalar and e 0 = ∥y
The stated bounds on E ∥E
t ∥ 2 and E ∥E
t ∥ 2 are inspired by the literature on two-point zeroth-order gradient estimators [30], [31]. We use the Lipschitz property of f (x, •) to bound
.
Following which, Term A and Term B are recursively bounded. A detailed proof is provided in the extended version of this paper [1].
In this section, we show that the updates in (UL) does not converge to a saddle point. Towards that goal, we make the following assumption that posits that the function f (•) satisfy the strict saddle property. Assumption 4. For any saddle point x * of f , it holds that λ min (∇ 2 f (x * )) < 0.
In the following theorem, we formally state the nonconvergence result.
Theorem 2. Let Assumption 1-4 hold. For ϵ > 0 there exists a time T ϵ such that for any saddle point x * of f it holds that E ∥x t -x * ∥ 2 ≥ ϵ, ∀ t ≥ T ϵ .
To prove Theorem 2, an asymptotic pseudo-trajectory of (UL) is constructed. We then show that the asymptotic pseudo-trajectory almost surely avoids saddle point.
a) Proof of Theorem 2: The proof follows by contradiction. Suppose there exists a saddle point x * such that lim t-→∞ E ∥x t -x * ∥ 2 = 0. This implies that for any ϵ > 0 there exists an integer T ϵ such that for all t ≥ T ϵ it holds that E ∥x t+s -x * ∥ 2 ≤ ϵ/4 ∀s ≥ 0.
(IV.8)
Next, for any arbitrary point x t along the trajectory (UL), we define a dynamics parametrized by xt = x t + δ t v t , as follows z s+1 (x t ) := z s (x t ) -η t+s ∇ f (z s (x t )), where z 0 (x t ) = xt . From Lemma 3, we know that for any ϵ > 0 and positive integer S there exists Tϵ,S such that
Next, note that ∥z s (x t ) -x * ∥ 2 ≤ 2∥z s (x t ) -x t+s ∥ 2 + 2∥x t+s -x * ∥ 2 . Therefore, combining (IV.8)-(IV.9), we observe that for every t
But from [35] we know that for gradient descent with random initialization almost surely avoids converging to saddle pointfoot_3 there exists S ϵ such that for all s ≥ S ϵ it holds that ∥z s (x t ) -x * ∥ 2 ≥ 2ϵ. This establishes contradiction. Lemma 3. Let x t be an arbitrary point along the trajectory (UL). Define a dynamics parametrized by xt = x t + δ t v t , such that z s+1 (x t ) := z s (x t ) -η t+s ∇ f (z s (x t )), where z 0 (x t ) = xt and it holds that for any positive integer L, we have
A detailed proof of Lemma 3 is provided in the online version of this article [1].
We numerically study the Algorithm 1 in the context of incentive design in routing games (described in Section III). We consider the Sioux Falls transportation network, as depicted in Figure 1(a). The latency function and network topology are inherited from http://tinyurl. com/y4fm4nvt. We consider a synthetic demand of (1, 2, 3, 2, 2, 1) units, respectively, between o-d pairs Z = ((1, 20), (13, 2), (20, 1), (10,13), (11,20), (4,21)). The incentive designer can set tolls on each edge of the network. In response, unknown to the planner, the travelers alter their route selection as per a gradient rule. More formally, given a toll x ∈ R |E| , we consider that the route choices made by the travelers are updated by descending along the gradient of the potential function Φ(•, x) (cf. (III.3)). Note that, for any x ∈ R |E| , z ∈ Z, r ∈ R z , the gradient is ∂Φ(y,x) ∂yrz = e∈E ℓ e (w e (y)) ∂we(y) ∂yrz + x e ∂we(y) ∂yrz = (i) e∈E ℓ e (w e (y))1(e ∈ r) + x e 1(e ∈ r) = (ii) c r (y, x),
where (i) is due to (III.1) and (ii) follows from (III.2). Consequently, the gradient update takes the following form: for every z ∈ Z, y (k+1) z = P Yz (y
rz -γc r (q k , p)) r∈Rz . We simulate 12 runs of Algorithm 1 with T = 1000 and K = 3. The initial route flow vector y (0) 0 and ỹ(0) 0 are randomly initialized. We set initial tolls uniformly randomly between [0, 0.1]. We set the step size η t = 6(t + 1) -1/2 , δ t = 0.3 • (t + 1) -1/4 , γ = 0.005 and λ = 0.01. In Figure 1(b), we show the leader's objective value as function of time iterates t ∈ [T ]. We observe that all trajectories converge to same objective value even with random initializations. This shows that the convergent point is perhaps a global optimizer.
We propose an efficient algorithm for Stackelberg games which converges to a stationary point at a rate of O(T -1/2 ) and asymptotically reaches a local Stackelberg equilibrium. The algorithm is designed so that the leader does not need to know any information about the game structure at lower-level and updates its strategies by only querying for the followers response to its strategy. However, in this work we assume that follower's equilibrium strategy is singleton, Lipschitz and the leader's hyper-objective is differentiable. An interesting direction of future work is to relax this assumption.
Here, we allow for tolls to take negative values. Such tolling scheme can be implemented by considering revenue-refunding schemes.
Authorized licensed use limited to: CALIFORNIA INSTITUTE OF TECHNOLOGY. Downloaded on March 06,2025 at 21:01:56 UTC from IEEE Xplore. Restrictions apply.
Note that λ can in-general be zero, i.e. we do not require strong convexity of leader's objective function in its decision variable for our theoretical results to hold. We choose λ > 0 to impose a "soft-constraint" on the amount of tolls.along an "approximated" gradient estimator, inspired from zeroth-order optimization ([30],[31]), evaluated at the lower-level iteration in current round.a) Leader's strategy update: The leader's update rule is as follows:x t+1 = x t -η t F (x t ; δ t , v t ), (UL)
More specifically, we use the results from[35, Proposition 8]. Even though the results in[35, Proposition 8] hold for gradient descent update with constant step-size, we can use this result for decaying step size in our context as well. This is because the proof of[35, Proposition 8] only requires each step of the gradient update to be diffeomorphism, which holds in our setting as the step-sizes are always non-negative and decaying.