Differentiable Equilibrium Computation with Decision Diagrams for Stackelberg Models of Combinatorial Congestion Games
Authors: Shinsaku Sakaue
Kengo Nakamura
Venue: NeurIPS 2021 Poster (2021)
Keywords: differentiable optimization
decision diagrams
combinatorial congestion game
Stackelberg game

Abstract: We address Stackelberg models of combinatorial congestion games (CCGs); we aim to optimize the parameters of CCGs so that the selfish behavior of non-atomic players attains desirable equilibria. This model is essential for designing such social infrastructures as traffic and communication networks. Nevertheless, computational approaches to the model have not been thoroughly studied due to two difficulties: (I) bilevel-programming structures and (II) the combinatorial nature of CCGs. We tackle them by carefully combining (I) the idea of \textit{differentiable} optimization and (II) data structures called \textit{zero-suppressed binary decision diagrams} (ZDDs), which can compactly represent sets of combinatorial strategies. Our algorithm numerically approximates the equilibria of CCGs, which we can differentiate with respect to parameters of CCGs by automatic differentiation. With the resulting derivatives, we can apply gradient-based methods to Stackelberg models of CCGs. Our method is tailored to induce Nesterov's acceleration and can fully utilize the empirical compactness of ZDDs. These technical advantages enable us to deal with CCGs with a vast number of combinatorial strategies. Experiments on real-world network design instances demonstrate the practicality of our method.

Differentiable Equilibrium Computation with Decision Diagrams for Stackelberg Models of Combinatorial Congestion Games
Shinsaku Sakaue The University of Tokyo
Kengo Nakamura
NTT Communication Science Laboratories Kyoto, Japan
Tokyo, Japan sakaueGmist. u.taaueellitt...oooooooo. Jc.
kengo. nak.nnaa. ntt.co. co.
Abstract
We address Stackelberg models of combinatorial congestion games (CCGs); we aim to optimize the parameters of CCGs so that the selfish behavior of non-atomic players attains desirable equilibria. This model essential for designing such social infrastructures as traffic and communication networks. Nevertheless, computational approaches the model have not been thoroughly studied due to difficulties: (I) bilevel-programming structures and (II) the combinatorial nature of CCGs. We tackle them by carefully combining (I) the idea of differentiable optimization and (II) data structures called tero-suppressed binary decision diagrams (ZDDs), which can compactly represent sets of combinatorial strategies. Our algorithm numerically approximates the equilibria of CCGs, which we can differentiate with respect to parameters CCGs by automatic differentiation. With the resulting derivatives, we can apply gradient-based methods to Stackelberg models of CCGs. Our method tailored to induce Nesterov's 's acceleration and can fully utilize the empirical compactness of ZDDs. These technical advantages enable us to deal with CCGs with a vast number combinatorial strategies. Experiments on real-worle network design instances demonstrate the practicality of our method.
Introduction
Congestion games (CGs) [49] form an important class of non-cooperative games and appear in various resource allocation scenarios. Combinatorial CGs (CCGs) can model more complex situations where each strategy is combination of resources. A well-known example of a CCG is selfish routing [50], where each player traffic network chooses origin-destination path, which is strategy given by a combination of some roads with limited width (resources). Computing the outcomes players' selfish behaviors (or equilibria) is essential when designing social infrastructures such traffic networks. Therefore, how to compute equilibria of CCGs has been widely studied [5, 12, 57, 42].
In this paper, we are interested in the perspective of the leader who designs non-atomic CCGs. For example, the leader aims to optimize some traffic-network parameters (e.g., road width values) so that players can spend less traveling time at equilibrium. An equilibrium of non-atomic CCGs is characterized by an optimum potential function minimization [41, 53). Thus, designing CCGs can be seen as Stackelberg game; the leader optimizes the parameters of CCGs minimize objective function (typically, the social-cost function) while the follower, who represents the population of selfish non-atomic players, minimizes the potential function. This mathematical formulation is called the Stackelberg model in the context of traffic management [46]. Therefore, we call our model with general combinatorial strategies a Stackelberg model of CCGs.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Stackelberg models of CCGs have been studied for cases where the potential function minimization has desirable properties. For example, Patriksson and Rockafellar [46] proposed a descent algorithm for traffic management using the fact that projections onto flow polyhedra can be done efficiently. However, many practical CCGs have more complicated structures. For example, in communication network design, each strategy is given by Steiner tree (see [24, 42] and Section 1.1), and thus the projection (and even optimizing linear functions) is NP-hard. How to address such computationally challenging Stackelberg models of CCGs has not been well studied, despite its practical importance.
Inspired by a recent equilibrium computation method [42], we tackle the combinatorial nature of CCGs by representing their strategy sets with supo-supeeeseed binary decision diagrams (ZDDs) [39, 32], which are well-established data structures that provide empirically compact representations of combinatorial objects (c.g., Steiner trees and Hamiltonian paths). Although the previous method [42] can efficiently approximate equilibria with Trank-Wolfe-see procedures break the differentiability of the outputs in the CCG parameters (the leader's 's variables), preventing us from obtaining gradient information required for optimizing leader's objective functions.
algorithm [18], its computation
Our contribution is to develop differentiable pipeline from leader's variables to equilibria of CCGs, thus enabling application of gradient-based methods to the Stackelberg models of CCGs. We smooth the Frank-Wolfe iterations using softmin, thereby making computed equilibria differentiable with respect the leader's variables by automatic differentiation (or backpropagation), Although the idea of smoothing with softmin is prevalent [29, 38], our method has the following technical novelty:
Our algorithm is tailored to induce Nesterov's acceleration, making both equilibrium com- putation and backpropagation more efficient. To the best of our knowledge, the idea of simultancously making iterative optimization methods both differentiable and faster is new.
Our method consists of simple arithmetic operations performed with ZDDs as in Algorithm 2. This is essential for making our equilibrium computation accept automatic differentiation. The per-iteration complexity of our method is linear in the ZDD size.
Armed with these advantages, our method can work with CCGs that have enormous number of combinatorial strategies. We experimentally demonstrate its practical usefulness in real-world network design instances. Our method brings benefits by improving the designs of social infrastructures.
Notation. Let [n] == (1.....,))
.n.. For any S S [*]. 1s E (0, 13" denotes a binary vector whose i-th entry is 1 if and only if S. Let be the fo-norm.
1.1 Problem setting
We introduce the problem setting and some assumptions. For simplicity, we describe the symmetric setting, although our method can be extended to an asymmetric setting, as explained in Appendix A.
Combinatorial congestion games (CCGs). Suppose that there is an infinite amount of players with an infinitesimal mass (i.e., non-atomic). We assume the total mass is without loss of generality. Let [n]] be a set of resources and let C 2 be set of all feasible strategies. We define d [S], which is generally exponential in n. Each player selects strategy S E S. Let E [0, 1J" be a vector whose i-th entry indicates the total mass of players using resource E [m]. In other words, if we let Ad be a vector whose entry 2g (S E S) indicates the total mass of players choosing S, we have = Eses 2glg E R.. Therefore, y is included in convex hull C == { (Eess 251g z E Ad) J. where A = {x Rd 2 0, Eses SES zs = 1} is the (d - 1)-dimensional probability simplex. A player choosing 5 incurs cost cs (t) = Eies (yys), where each c; : R + TR. is assumed to be strictly increasing; this corresponds to a natural situation where cost e; increases as i E [r|] becomes more congested. Each player selfishly selects strategy to minimize his/her own cost.
Equilibrium and potential functions. We say 2 E Ad attains a (Wardrop) equilibrium for every S E S such that 2ş > 0, it holds that cs(y) I minsres Cs (y). where y = E SEs 2g That is, no one has an incentive to deviate unilaterally. Let f R -> R be potential function defined as f() = Eie(n J cu(u)du. From the first-order optimality condition, it holds that z attains an equilibrium iff y = Eses 25 satisfies y = argminuee (w,) Note that minimizer y unique since c; is strictly increasing, which means f is strictly convex (not necessarily strongly convex).
2

---

Stackelberg model of CCGs. We turn to the problem of designing CCGs. For i E [n], let e; (v:: 0) be a cost function with parameters 0 E θ We assume (3 0) be strictly increasing in y; for any O and differentiable with respect to 0 for any y E C. Let fyy 0) Eie(m) Jo ci(u; 0) be parameterized potential function, which is strictly convex in y for any O O. A leader who designs CCGs aims to optimize 0 values so that an objective function, F θ x C - R, is minimized at an equilibrium of CCGs. Typically, which represents the total cost incurred by all players. Since an equilibrium is characterized as a minimizer of potential function f, the leader's problem can be written as follows:
a social-cost function defined as F(O. y) Eig(n) ( 0 O)yi.
minimize Gg
F(e.y) y)
subject to y argmin f(u; 0). uEC
Since minimizer y(0)= = approximate derivatives of F(O, y()) with respect to for applying gradient- based methods to (1).
y is unique, we can regard F(O. y ()) function of A. We study how to
Example I: traffic management. We are given network with an origin-destination (OD) pair. Let [ni] be the edge set and let S C 2(m] be the set of all OD paths. Each edge in the network has cost. function (v:; f). where 9 controls the width of the roads (edges). natural example of the cost functions is c(U:; 0) 0./0, for 0, > 0 (see, e.g., [46]), which satisfies the above assumptions, i.e., strictly increasing in y4 and differentiable in 0,. Once is fixed, players selfishly choose OD paths and consequently reach equilibrium. The leader wants to find 0 that minimizes social cost F at equilibrium, which can be formulated as a Stackelberg model of form (1), Note that although the Stackelberg model of standard selfish routing is well studied [46]. there are various variants (e.g.. routing with budget constraints [28, 42]) for which existing methods do not work efficiently.
Example 2: communication network design. We consider situation where multi-site meetings are held on a communication network (see, e.g., [24, 42]). Given an undirected network with edge set [nx] and some vertices called terminals, groups of people at terminals hold multi-site meetings, including people at all the terminals. Since each group wants to minimize the communication delays caused by congestion, each selfishly chooses way to connect all the terminals, namely, Steiner tree covering all the terminals. If we let c, (y θ) indicate the delay of the i-th edge, a group choosing Steiner tree S E S incurs cost cs (3: 0). As with the above traffic- management example, the problem of optimizing A to minimize the total delay at equilibrium can be written as (1).
1.2 Related work
Problems of form (1) arise in many fields, e.g., Stackelberg games [55], mathematical programming with equilibrium constraints [36], and bilevel programming [10, 13], which have been gaining attention in machine learning [17, 15]. Optimization problems with bilevel structures are NP-hard in most cases [22] (tractable cases include, e.g., when follower's problems are unconstrained and strongly convex [19]. which does not hold in our case). Thus, how to apply gradient-based methods occupies central interest [15, 20J. In our Stackelberg model of CCGs, in addition to the bilevel structure, the follower's 's problem is defined on combinatorial strategy sets S, further complicating it. Therefore, unlike the above studies, we focus on how to address such difficult problems by leveraging computational tools, including ZDDs [39] and automatic differentiation [34, 21].
Stackelberg models often arise in traffic management. Although many existing studies [46, 35, 6, 9] analyze theoretical aspects utilizing instance-specine structures (e.g.. compact representations of flow polyhedra), applications to other types of realistic CCGs remain unexplored. By contrast, as with the previous method [42], our method is built on versatile 7DD representations of strategy sets, and the derivatives with respect to CCG parameters can be automatically computed with backpropagation. Thus, compared to the methods studied in traffic management, ours can be easily applied to and works efficiently with a broad class of realistic CCGs with complicated combinatorial strategies.
Our method is inspired by the emerging line of work on differentiable optimization [4, 60, 2, 51]. For differentiating outputs with respect to the parameters of optimization problems, two major approaches have been studied [20]: implicit and iterative differentiation. The first approach applies the implicit (KKT) condition (akin
function theorem to equation systems derived from the Karush-Kuhn-Te to the single-level reformulation approach to bilevel programming). In our case, this approach is too expensive since the combinatorial nature of CCGs generally makes the KKT equation system exponentially large [16]. Our method is categorized into the second approach, which computes
3

---

numerical approximation of an optimum with iterations of differentiable steps. This idea has yielded success in many fields [14, 37, 45. 7, 17]. Concerning combinatorial optimization, although differentiable methods for linear objectives are well studied [38, 60, 47, 8). no differentiable method has been developed for convex minimization on polytopes of, e.g., Steiner trees or Hamiltonian paths; this is what we need for dealing with the potential function minimization of CCGs. To this end, we use a Frank -tolee algorithm and ZDD representations of combinatorial objects.
2 Differentiable iterative equilibrium computation
We consider applying gradient-based methods (c.g.. projected gradient descent) to problem (1). To this end, we need to compute the following gradient with respect to 0 E O C IR* in each iteration:
FF v()) = VoF v(0) + Vy(o) V (fF(0,y(0), v()),,
where (oF(() and V ((0) denote the gradients with respect the first and second arguments, respectively, and Vy(0) is the & Jacobian matrix.' ! The computation of Vy(0) is the most challenging part and requires differentiating y(0) argmin f(u: 0) with respect to A. We employ the iterative differentiation approach for efficiently approximating (y)
2.1 Technical overview
For computing equilibrium y0), Nakamura et al. [42] solved potential function minimization with a variant of the Frank-Wolfe algorithm [33], whose iterations can be performed efficiently by using compact ZDD representations of combinatorial strategies. To the best of our knowledge, no other equilibrium computation methods can deal with various CCGs that have complicated combinatorial strategies, e.g., Steiner trees. Hence we build on [42] and extend their method to Stackelberg models.
First, we review the standard Frank-Wolfe algorithm. Starting from Do E C. it alternately computes 8, = argmin sec ( V f(v;; 0), 8) and æ; = (1 - - + 7r, where " is conventionally set to E42 As shown in [18, 27], ær has an objective error of ((1/T). Thus, we can obtain numerical approximation (r) = ZT of equilibrium (0) such that f(r (0); 0) (v(()) 0) I O(1/T).
2
For obtaining gradient V (f)) however, the above Frank-Wolfe algorithm does not work (neither does its faster variant used in [42]). This is because 8, = arginin .ec (V (ax;; 0), 8) is piecewise constant in 0, which makes yyr (0) zero almost everywhere and undefined at some 0.
To resolve this issue, we develop a differentiable Trole algorithm by using softmin. We denote the softmin operation by (s)(c) (detailed below). Since softmin can be seen as differentiable proxy for argmin, one may simply replace 8, = argmin (V 0), s) with 8, = (s V O)). where 7/ > 0 is a scaling factor. Actually, the modified algorithm yields an O(1/T) convergence by setting 7/- = (t) (see 127, Theorem 1]). This modification, however, often degrades the empirical convergence of the leveraging softmin for acceleration while keeping the iterations differentiable. Based on an accelerated Fronk-Wolfe algorithm [59], we compute yr as in Algorithm and obtain Vyr (0) by applying backpropagation. Furthermore, in Section 3, we explain how to efficiently compute (ss(c) by using a ZDD-based technique [52]; importantly, its computation procedure also accepts the backpropagation.
algorithm, demonstrated in Section 4. We, therefore, consider
While our work is built on the existing methods [59, 52, 42], none of them are intended to develop differentiable methods. A conceptual novelty of our work is its careful combination of those methods for developing a differentiable and accelerated optimization method, with which we can compute (f). This enables the application of gradient- based methods to the Stackelberg models of CCGs.
2.2 Details of Algorithm
We compute (0) with Algorithm 1. Note that 8t, Ct, and ær depend on O, which not explicitly indicated for simplicity. The most crucial part is Step 5, where use softmin rather than argmin to
Although the derivatives of y may not be unique, we abuse the notation and write Vy(0) for simplicity. As we will see shortly, we numerically approximate y() with yr (0) whose derivative, Vyr(O). exists uniquely. Therefore, when discussing our iterative differentiation method, ignore the abuse of notation.

---

Algorithm Differentiable Frank-Wolfe-based equilibrium computation
1: Co 0, 40 (ss(Co) and = 1 = o,...,
2:
for 1,...,
3: 8r 8t-1 1 + (a--1 +
4: C = = 17a f [(41)
Vfy: 0); (v 0) is differentiable in
[(++1)
5: Compute 2, = (c( with Algorithm
> Differentiable softmin computation
return yr( = T(7+1) Ei=1 ay
make the output differentiable in Specifically, given any c R", we compute (s(()) as follows:
cxp (-c
(s(c))
Σ 1s SES
S' exp (-c 1s))
Intuitively, each entry in e represents the cost of each i E [n], and e 1y represents the cost of S E S. We consider a probability distribution over S defined by softmin with respect to costs {c _ (s]1s) 1ssess and then marginalize it. The resulting vector is convex combination of {1s) sess and thus always included C. In the context of graphical modeling, this operation is called marginal inference [58]. Here, lss is defined by summation over S, and explicitly computing it is prohibitively expensive. Section 3 details how to efficiently compute ps by leveraging the ZDD representations of
2.3 Convergence guarantee
Algorithm I is designed to induce Nesterov's acceleration [43, 59] and achieves O(1TT²) con- vergence, which faster than the O(1/T) convergence of the original Frank-Wolfe algorithm.
Theorem 1. Fix O E @ and assume f(: 0) to be L-smooth on Red, i.e., ((2) = f( Ses 2s ssls; 0) (Vz E IBd) satisfies (x2') < 4(2)+ (VD(=), 2) - for all z, z' IRd.2 If let
r) E lOL, 4T.) for some C > 4, Algorithm returns (0) such that
CLInd
T
We present the proof Appendix B. essence, softmin can be seen as dual mirror descent step with the Kullback-Leible divergence, and combining it with primal gradient descent step yields the acceleration [3]. Although the acceleration technique itself is well studied, has not been explored in the context of differentiable optimization. To the best of our knowledge, simultaneously making iterative optimization methods both differentiable and faster is novel idea. This observation can be beneficial for developing other fast differentiable iterative algorithms. Experiments in Section 4.1 demonstrate that the acceleration indeed enhances the convergence speed in practice.
Note that the faster convergence enables us to more efficiently compute both (r) and (0). The latter is because Algorithm with smaller T generates a smaller computation graph, which determines the computation complexity of the backpropagation for obtaining (f). Therefore, Algorithm is suitable as an efficient differentiable pipeline between O and (r)).
2.4 Implementation consideration: how to choose 1) and
While Theorem suggests setting 7) to 3r, or less, this choice is often too conservative in practice. Thus, we should search for 7) values that bring high empirical performances. When using Algorithm as subroutine of gradient-based methods, it is repeatedly called to solve similar equilibrium computation instances. Therefore, a simple and effective way for locating good values is to apply Algorithm with various values to example instances, empirical performance to improve with line search of 7,, which we leave for future work.
will do in Section 4.1. We expect the
Smoothness parameter L defined on d can be, in general, exponentially large in n, albeit constant in T. How to alleviate the dependence remains open problem.
5

---

Root
Algorithm Computation of us with ZDD Zs = (V,A)
2
BT and B1 =0
2: for E V {T, } (bottom-up):
3
3: B, B + exp(-a,) Bę
4: P, and P. = 0 (v E V (r))
4
5
5: x (O......))
6:
for V ( [T, (top-down))
Figure I: Example of ZDD Zs (right), where and S is family of all simple s-t paths (left). ZDD has two terminal nodes (T and I) and non-terminal nodes labeled by E [n]. Solid (dashed) ares represent 1-arcs (0-ares).
7:
p" Bey /B, and p 1 pm
8:
P + prP, and Pa += p'P.
9: 21, - p'Pv
10: return x = (TI,...,TT
To check whether the Frank-Wolfe algorithm has converged or not, we usually use the Frank-Wolfe gap [27], an upper-bound on an objective error. To obtain high-quality solutions, we terminate the algorithm when the gap becomes sufficiently small. In our case, however, our purpose is to obtain gradient information Vyr(0), and yr (0) with a small 7 sometimes suffices to serve the purpose. By using small T,, we can reduce the computation complexity. Experiments in Section 4.2 show that the performance of a projected gradient method that uses Vyr(0) is not so sensitive to T' values.
3 Efficient softmin computation with decision diagrams
This section describes how to efficiently compute ps(c) by leveraging ZDD representations of S. The main idea is to apply a technique called weight pushing [40] (or path kernel [56]) to ZDDs. A similar idea was used for obtaining efficient combinatorial bandit algorithms [52], but this research does it to develop differentiable algorithms. Our of weight pushing comes from another important observation: it consists of simple arithmetic operations that accept reverse-mode automatic differentiation with respect to c, shown in Algorithm 2. In other words, Algorithm does not use. e.g.. or argmin. Therefore, ZDD-based weight pushing can be incorporated into the pipeline from yr(0) without breaking the differentiability.
3.1 Zero-suppressed binary decision diagrams
Given set family S C 2|n], we explain how to represent it with ZDD Zs = AV, DAG-shaped data structure (see, e.g., Figure 1). The node set, V, has two terminal nodes and 1 (they represent true and false, respectively) and non-terminal nodes. There is single root, E V {1, T}. Each v E V [L.T] has label L, E [n] and two outgoing arcs, 1- and O-ares, which indicate whether I, is chosen not, respectively. Let c., c/ E V denote two nodes pointed by 0- and 1-arcs, respectively, outgoing from For any v V \ (T, {), let R, C 2 be the set of all directed paths from T. We define R = UVeVYT.L) Ry, For any R E R, let X(R) = { [m] (v, c)) R i.e., labels of tails of 1-ares belonging to R. ZDD Zs represents S set of paths: S = {X(R) R R. There is a one-to-one correspondence between S E S and R E R,, i.e., 5 == XR)..
Figure presents an example of ZDD Zs. where S is the family of simple s-l. paths. For example, S (2 E S is represented in Zs by the red path, R R, with labels {1, 3, 5, T]. The labels of the tails of the 1-arcs form X (R) (2, 5}. which equals S.
We define the size of Zs (V, by IZsl [V]. Note that A S 2 Zs always holds. In general, the ZDD sizes and the complexity of constructing ZDDs can be exponential in n. Fortunately, many existing studies provide efficient methods for constructing compact ZDDs. One such method is the frontier-based search [30], which is based on Knuth's Simpath algorithm [32]. Their method family of network substructures such as Hamiltonian paths, Steiner trees, matchings, and cliques. Furthermore, the family algebra [39, 32) of ZDDs enables us to deal with various logical constraints. Using those methods, we can flexibly construct ZDDs for
particularly effective when
various complicated combinatorial structures, c.g., Steiner trees whose size is at most certain value.

---

Moreover, we can sometimes theoretically bound the ZDD sizes and the construction complexity. For example, if S consists of the aforementioned substructures on network G = (V, E) with a constant pathwidth, the ZDD sizes and the construction complexity are polynomial in E| [30, 26).
3.2 Details of Algorithm and computation complexity
Algorithm 2 computes x = (s((c) for any c (cI,...,Cr) Cn) E R". First, it computes (By in bottom-up topological order of Zs. Note that B, = -sE (R()) RER.) exp(- -ii-s 6:) holds. Then it computes hev. Each Pv indicates the probability that top-down random walk starting from root node reaches v V, where we choose O-are (I-are) with probability pd (p'). From B the construction of [Bvv the random walk never reaches 1, and its trajectory R E R, recovers Therefore, by summing the probabilities of reaching and choosing a 1-arc outgoing from for each i E [n] as in Step 9, we obtain æ = (c) In practice, we recommend implementing Algorithm 2 with the log-sum-exp technique and double-precision computations for numerical stability.
and
X (R) E S with a probability proportional to exp(- Eie X(R) 4) exp(-c"
Algorithm 2 runs in O(Izs)) time, and thus Algorithm I takes O(n [[mn+CG Cp + IZ+))) time, where Cp is the cost of computing f. From the cheap gradient principle [21], the complexity of computing FO. yr (0)) with backpropagation is almost the same as that of computing F(0, yr (0)). That is, smaller ZDDs make the computation of both yr (0) and yor (0) faster. Therefore, our method significantly benefits from the empirical compactness of ZDDs Note that we can construct ZDD Zs in preprocessing step; once we obtain Zs. we can reuse it every time (.)(.) is called.
Experiments
Section 4.1 confirms the benefit of acceleration to empirical convergence speed. Section 4.2 demon- strates the usefulness of our method via experiments on communication network design instances. Section 4.3 presents experiments with small instances to whether our method can empirically find globally optimal 0. Due to space limitations, we present full experimental results in Appendix C.
All the experiments were performed using a single thread on a 64-bit macOS machine with 2.5 GHz Intel Core i7 CPUs and 16 GB RAM. We used C++11 language, and the programs were compiled by Apple clang 12.0.0 with -03 -DNDEBUG option. We used Adept 2.0.5 [23] as an automatic differentiation package and Graphillion 1.4 [25] for constructing ZDDs, where we used a beam- search-based path-width optimization method [26] to specify the traversal order of edges. The source code available at https: / htt///gtttuuuu thub. com/ wwatttssaaddffffeeee comput- zdd.
Problem setting. We address Stackelberg models for optimizing network parameters 0 E R where [n] represents an edge set. We focus on two situations where combinatorial strategies S C 2 are Hamiltonian cycles and Steiner trees. The former is a variant of the selfish-routing setting, and the latter arises when designing communication networks as in Section 1.1. Note that in both settings, common operations on C, e.g. projection and linear optimization,
harh We use two
types of cost functions: fractional cost Ca (;;;; 9) = d1(1 + C' x (0, + 1)) and exponential cost es (ys; 0) d1(1 + C x yi exp(-0,)), where d, (0, 1] is the length of the i-th edge (normalized so that max;e[[] d2 = holds) and C > O controls how heavily the growth in y; (congestion) affects cost G. We set C = 10. Note that edge with a larger 0, is more tolerant to congestion. The leader aims to minimize social cost F(O, (0)) = Σie(n) (0); 0) 0)y; (0). In realistic situations, the leader cannot let all edges have sufficient capacity due to budget constraints. To model this situation, we impose constraint on by defining e { R e 1 = n), where is the all-one vector.
Datasets. Table 1 summarizes the information about datasets and ZDDs used in the experiments. For the Hamiltoniancyclle setting (HAMILTON), we used att48 (ATT) and dantzig42 (DANTZIG) datasets in TSPLIB [48]. Following [11, 44], we obtained networks in Figure 4 using Delaunay triangulation [54]. For the Steiner-tree setting (STHINER), we used Uninett 2011 (UNINETT) and TW Telecom (Tw) networks of Internet Topology Zoo [31]. We selected terminal vertices as shown in Figure 4. We can see in Table that ZDDs are much smaller than the strategy sets. As mentioned in Section 3.2, we can construct ZDDs in a preprocessing step, and the construction times were so short as to be negligible compared with the times taken for minimizing the social cost (see Section 4.2). Therefore, we do not take the construction times into account in what follows.
7

---

Table 1: Sizes of networks G EV, strategy sets and ZDDs Zş. ZDDs for DANTZIG, ATT, UNINETT, and Tw were constructed in 172, 258, 4, and 6 ms, respectively.
STRATEGY
DATASET
VV
[E]
S
[ss
DANTZIG
42
115
15164782028 (> 1.5 10
23479
HAMILTON
ATT
48
130
1041278451879 (2 1.0 x 1
35388
UNINETT
69
96
5892888554825344229114888 (2 8.8 x 10
3284
STEINER
TW
76
115
(2 7.1 100h)
5583
21 A
22A.1-2 25
25
204.B
+SA. 1.8
ww 300
201
1045
300
180
20
(a) ATT, fractional cost
(b) ATT, fractional cost
(c) ATT, exponential cost (d) ATT, exponential cost
110
PX (2.))
PM
4W Wi-d1
Trae (ta)
(e) Tw, fractional cost
(I) Tw, fractional cost
(g) Tw, exponential cost (h) Tw, exponential cost
Figure 2: Convergence results of equilibrium computation methods, where w/ A, w/o A, and FW represent Algorithm naive differentiable Frank- Wolfe without acceleration, and standard non- differentiable Wolfe, respectively. We present the results on the other settings in Appendix C.
4.1 Empirical convergence of equilibrium computation
We studied the empirical convergence of Algorithm with acceleration (w/ A), where we let 17 0.05, 0.1, 0.2, and 0.5. We applied to the minimization problems of form mingee fly 0), where f is potential function defined by cost function cv 0) (fractional exponential). We let 0 1.
For comparison, we used two kinds of baselines. One a differentiable Frank- without acceleration (w/o A), which just replaces argmin with softmin explained in Section 2.1.
algorithm
To guarantee the convergence of the modified algorithm, we let 7 = 7o x t (7o = 0.1, 1.0, and 10.0). The other is the standard oon-differentiable Frank- Wolfe algorithm (FW) implemented as in [27].
Figure 2 shows how quickly the Frank Wolfe gap [27], which is an upper bound of the objective error, decreased as the number of iterations and the computation time increased. w/ A and w/o A tend to be faster and slower than FW, respectively. That is, Algorithm (w/ A) becomes both differentiable and faster than the original FW, while the naive modified one (w/o A) becomes differentiable but slower. As in the Tw results, however, w/ with a too large 7) (1) = 0.5) sometimes failed to be accelerated; this is reasonable since Theorem requires yj to be moderate value. Thus, if we can discussed in Section 2.4, can search for by examining the empirical convergence for various 77 values, did above.
locate appropriate 7, Algorithm achieves faster convergence in practice.

---

Oui sodle Fim
Tonkoc Pork
(a) ATT, fractional cost (b) ATT, exponential cost (c) Tw, fractional cost
(d) TW, exponential cost
Figure 3: Plots of social costs achieved on network design instances. Error bands baseline methods
show standard deviations over 20 trials. We present results other settings in Appendix C.
(a) DANTZIG, (0)
(b) DANTZIG,
(c) ATT, yr (r
(d) ATT.
(c) UNINETT, yr (0)
(f) UNINETT, O
TW, yr (0)
(h) Tw, e
Figure 4: Network illustrations: five square vertices in UNINETT and TW indicate terminals. Blue (a. g) and red (b, d, f, h) edges represent (f) and 0 values, respectively, computed by our method with = 0.1 and = 300 for fractional-cost instances.
4.2 Stackelberg models for designing communication networks
We consider minimizing social cost F(0, ( To this end, roughly speaking, we should assign large 0, values edges with large y/s values. We applied the projected gradient method with step size of 5.0 to problem (1). We approximated (F(0, (()) by applying automatic differentiation to F(O. (r)). where yr was computed by Algorithm I with T 100. 200, and 300.
To the best our knowledge, no existing methods can efficiently deal with the problems considered here due the complicated structures of S. Therefore, as baseline method, we used the following iterative heuristic. Given current y (0), we replace O with + (()(() 0- (()1),, where å > 0 and (00) = Eie(n) (O). That is, we increase/decrease 0g if edge is used more/less than average. then project 9 onto and compute y@) with Algorithm (I 300). F(O, y()) value does not decrease after the above update, restart from random point in e.
Figure compares our method (1) 0.1) and the baseline on ATT and Tw instances, where both started from 0 = 1 and continued to update for two minutes. Our method found better 0 values than the baseline. The results only imply the empirical tendency, and our method not guaranteed to find globally optimal 0. Nevertheless, experiments in Section 4.3 show that it tends to find global optimum at least for small instances. Figure shows the (r( and values obtained by our method with 7 0.1 and T 300 for tractional-cost instance. We confirmed that large 0, values were successfully assigned to edges with large yi values. Those results demonstrate that our method useful for addressing Stackelberg models of CCGs with complicated combinatorial strategy sets S.

---

4.3 Experiments on empirical convergence to global optimum
We performed additional experiments on small instances to see whether the projected gradient method used in Section 4.2 can empirically find 0 that is close to being optimal. We used small selfish-routing instances, where a graph is given by the left one in Figure I and the edges are numbered from 1 to in that order. We let strategy set S be the set of all simple s-t paths. The cost functions and feasible region ④ were set as with those in the above sections. Our goal is to minimize social cost F(O, (()).
As in Section 4.2, we computed y(0) using Algorithm 1 with r) 0.1 and T= = 300, and performed the projected gradient descent to minimize F(O, y ( where gradient V F yy))) was computed with backpropagation. On the other hand, to obtain (approximations of) globally optimal 9, performed an exhaustive search over the feasible region, where the step size was set to 0.05. Regarding computation times, the projected gradient method converged in less than 30 iterations, which took less than 20 ms, while the exhaustive search took about 1000 seconds.
Results on fractional costs. A global optimum found by the exhaustive search was 0 (0, 2.5, 0, 0, 2.5), whose social cost F(O, (()) was 6.444. Our method started from 1, whose social cost was 7.000, and returned f (1.25, 1.25, 0, 1.25, 1.25) with social cost 6.444. Although the solution is different from that of the exhaustive search, both attain the identical social cost. Thus, the solution returned by the projected gradient method is also globally optimal.
Results on exponential costs. A global optimum found by the exhaustive search was 0 = (0, 2.5, 0, 0, 2.5) with social cost 3.517. Our method started from O 1 with social cost 5.678 and reached = (0, 2.5, 0, 2.5) with social cost 3.517. Along the way, the projected gradient method was about to be trapped in 0 (1.25, 1.25, 0, 1.25, 1.25) with social cost 4.865, which seems to be a saddle point. However, it successfully got out of there and reached the global optimum.
5 Conclusion and discussion
We proposed a differentiable pipeline that connects CCG parameters to their equilibria, enabling us to apply gradient- based methods to the Stackelberg models of CCGs. Our Algorithm 1 leverages softmin to make the Frank-Woll algorithm both differentiable and faster. ZDD-base softmin computation (Algorithm 2) enables us efficiently deal with complicated CCGs. It also naturally works with automatic differentiation, offering an easy way to compute desired derivatives. Experiments confirmed the accelerated empirical convergence and practicality of our method.
An important future direction is further studying theoretical aspects. From our experimental results, Vyr (0) is expected to converge (O),), although its theoretical analysis is very difficult. Recently, some relevant results have been obtained for simple cases where iterative optimization methods are written by a contraction map defined on an unconstrained domain [1, 20]. In our CCG cases, however, we need to study iterative algorithms that numerically solve the constrained potential minimization, which requires a more profound understanding of iterative differentiation approaches. Another interesting future work is to make linearly convergent Frank- Wolfe variants [33] differentiable.
Finally, we discuss limitations and possible negative impacts. Our work does not cover cases where minimizer y()) of potential functions not unique. Since the complexity of our method mainly depends on the ZDD sizes, does not work if ZDDs are prohibitively large, which can happen when strategy sets consist of the substructures of dense networks. Nevertheless, many real-world networks are sparse, and thus our ZDD-based method is often effective, as demonstrated in experiments. At meta-level, optimizing social infrastructures in terms of a single objective function (e.g., the social cost) may lead to an extreme choice that is detrimental some individuals. We hope our method can provide a basis for designing social infrastructures that are beneficial for all.
Acknowledgements
The authors thank the anonymous reviewers for their valuable feedback, corrections, and suggestions. This work was partially supported by JST ERATO Grant Number JPMJER 1903 and JSPS KAKENHI Grant Number JP20H05963.
10

---

References
[1] Ablin, G. Peyré, and T. Moreau. Super-efficiency of automatic differentiation for functions defined minimum. In Proceedings of the 37th International Conference Machine Learning, volume 119, pages 92-41. PMLR, 2020.
[2] A. Agrawal, B. Amos, S. Barratt, S. Boyd, S. Diamond, and J. Z. Kolter. Differentiable convex optimization layers. In Advances in Neural Information Processing Systems, volume 32, pages 9562-9574. Curran Associates, Inc., 2019.
[3] 7. Allen-Zhu and I.. Orecchia. Linear coupling: An ultimate unification of gradient and mirror descent. Proceedings of the 8th Innovations Theoretical Computer Science Conference, volume 67, pages 3:1-3:22. Schloss Srestuull-Libbniz-Zettte fuer Informatik, 2017.
[4] B. Amos and Z. Kolter. OptNet: Differentiable optimization layer in neural networks. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pages 136-145. PMLR, 2017.
[5] H. Bar-Gera. Origin- baged algorithm for the traffic assignment problem. Transp. Sci., 36(4):
398-417,20 2002.
[6] H. Bar-Gera, F. Hellman, and M. Patriksson. Computational precision of traffic equilibria sensitivities in automatic network design and road pricing. Procedia Soc. Behav. Sci., 80:41-60, 2013.
[7] D. Belanger, B. Yang, and A. McCallum. End-to-end learning for structured prediction energy networks. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pages 429-439. PMLR, 2017.
[8] Q. Berthet, M. Blondel, Teboul, M. Cuturi, J.-P. Vert, and F. Bach. Learning with differen- tiable perturbed optimizers. In Advances in Neural Information Processing Systems, volume 33, pages 9508-9519, Curran Associates, Inc., 2020.
[9] U. Bhaskar, K. Ligett, L. J. Schulman, and C. Swamy. Achieving target equilibria in network routing games without knowing the latency functions. Games Econom. Behav., 11:5333-699 2019.
[10] J. Bracken and J. T. McGill. Mathematical programs with optimization problems in the constraints. Oper: Res., 21(1)337-44, 1973.
[11] W. Cook and P. Seymour. Tour merging via branch-decoomosition. INFORMS Comput., 15 (3):233-248, 2003.
[12] J. R. Correa and N. E. Stier-Moses. Wardrop equilibria. In Wiley Encyclopedia of Operations Research and Management Science. Wiley Online Library, 2011.
[13] S. Dempe, V. Kalashnikov, G. A. Pérez- Valez,Valdé,, and N. Kalashnykova. Bilevel Programming Problems. Springer, 1st edition, 2015.
[14] Domke, Generic methods for optimization-based modeling. In Proceedings of the 15th International Conference Artificial Intelligence and Statistics, volume 22, pages 318-326. PMLR, 2012.
[15] T. Fiez, B. Chasnov, and L.. Ratliff. Implicit learning dynamics in Stackelberg games: Equi- libria characterization, convergence analysis, and empirical study. In Proceedings of the 37th International Conference on Machine Learning, volume 119, pages 3133-3144, PMLR, 2020.
[16] S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, and R. de Wolf. Exponential lower bounds for polytopes in combinatorial optimization. J. ACM, 62(2):1-23, 2015.
[17] L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil. Bilevel programming for hyperparameter optimization and meta-learning In Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 1568-1577. PMLR, 2018.
[18] M. Frank and P. Wolfe. An algorithm for quadratic programming. Naval Res. Logis. Quart., 3 (1-2):95-110, 1956. [19] S. Ghadimi and M. Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:180..02246. 2018.

---

[20] R. Grazzi, L. Franceschi, M. Pontil, and S. Salzo. On the iteration complexity of hypergradient computation. In Proceedings of the 37th International Conference on Machine Learning. volume 119, pages 7748-3758, PMLR, 2020.
[21] A. Griewank and A. Walther. Evaluating Derivatives. SIAM, 2nd edition, 2008
[22] Hansen, B. Jaumard, and Savard. New branch- -nd---ndddood rules for linear bilevel program-
ming. SIAM J. Sci. Statist. Comput., 13(5):1 19411114111 1992.
[23] R. J. Hogan. Adept 2.0: a combined automatic differentiation and array library for C++, 2017.
[24] M. Imase and M. Waxman. Dynamic Steiner tree problem. SIAM Discrete. Math., 4(3):
369-384, 1991.
[25] T. Inoue, H. Iwashita, J. Kawahara, and S. Minato. Graphillion: software library for very large sets of labeled graphs. Int. J. Software Tool. Tech. Tran., 18(1):57-66) 2016.
[26] Y. Inoue and S. Minato. Acceleration of ZDD construction for subgraph enumeration via path- width optimization. Technical report, TCS-TR-A-16-88. Hokkaido University, 2016.
[27] M. Jaggi. Revisiting Frank-Wolfe: Projection-free sparse convex optimization. In Proceedings of the 30th International Conference on Machine Learning, volume 28, pages 427-435 PMLR, 2013.
[28) O. Jahn, R. H. Möhring, A. S. Schulz, and N. E. Stier-Moses. System-optimal routing of traffic flows with user constraints in networks with congestion. Oper. Res., 53(4):600- 616, 2005.
[29] E. Jang. S. Gu, and B. Poole. Categorical reparameterization with Gumbel-Softmax. In Proceedings of the 5th International Conference on Learning Representations, 2017.
[30] Kawahara, T. Inoue, H. Iwashita, and S. Minato. Frontier-based search for enumerating all constrained subgraphs with compressed representation. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E100.A(9)11733-1784 2017.
[31] S. Knight, H. X. Nguyen, N. Falkner, R. Bowden, and M. Roughan. The Internet Topology Zoo. IEEE J. Sel. Areas Commum., 1765 2011. http://wwdt http:///ww.topolooyy. dataset. html.
org/
[32] D. E. Knuth. The Art of Computer Programming: Combinatorial Algorithms,, Part 1, volume 4A. Addison- Addison-Wesley Professional, 1tt edition, 2011.
[33] S. Lacoste-Julien and M. Jaggi. On the global linear convergence of Frank-Wolfe optimization variants. In Advances in Neural Information Processing Systems, volume 28, pages 496-504. Curran Associates, Inc., 2015.
[34] Y. LeCun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubhard, and L. D. Jackel. Backpropagation applied to handwritten zip code recognition. Neural Comput., 144:5541-551, 1989.
[35] C. Li, H. Yang, D. Zhu, and Q. Meng. A global optimization method for continuous network design problems. Transport. Res. B-Meth., 46(9):11444 115-1158, 1158, 2012.
[36] Z.-Q. Luo, J.-S. Pang, and D. Ralph. Mathematical Programs with Equilibrium Constraints. Cambridge University Press, 1996.
[37] D. Maclaurin, D. Duvenaud, and R. Adams. Gradient-based hyperparameter optimization through reversible learning. In Proceedings of the 32nd International Conference on Machine Learning, volume 37, pages 2113-2122. PMLR, 2015.
[38] A. Mensch and M. Blondel. Differentiable dynamic programming for structured prediction and attention. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 3462-3471, PMLR, 2018.
[39] S. Minato. Zero-suppressed BDDs for set manipulation in combinatorial problems. In Pro- ceedings of the 30th International Design Automation Conference, pages 272-277. IEEE, 1993.
[40] M. Mohri. Weighted Automata Algorithms, pages 213-254. Springer, 2009.
[41] D. Monderer and I., S. Shapley. Potential games. Games Écon. Behav. 14(1):124-144 1996.
[42] K. Nakamura, S. Sakaue, and N. Yasuda. Practical Frank-Wolfe method with decision diagrams for computing Wardrop equilibrium of combinatorial congestion games. In Processings of the
34th AAAI Conference Artificial Intelligence, volume 34, pages 2200-2209, 2020.
12

---

[43] Y. Nesterov. A method of solving a convex programming problem with convergence rate O(1/k²). Dokl. Akad. Nauk SSSR, 269(3):543-544 1983.
[44] M. Nishino, N. Yasuda, S. Minato, and M. Nagata. Compiling graph substructures into sentential decision diagrams. In Proceedings of the s1 AAAI Conference on Artificial Intelligence, pages
1213-1221, 2017.
[45] P. Ochs, R. Ranftl, T. Brox, and T. Pock. Techniques for gradient-basede bilevel optimization with non-smooth lower level problems. J. Math. Imaging Vis., 56(2):155-194, 2016.
[46] M. Patriksson and R. Rockafellar. mathematical model and descent algorithm for bilevel traffic management. Transport. Sci., 36(3):271-291, 2002.
[47] M. V. Pogančié, A. Paulus, V. Musil, G. Martius, and M. Rolinek. Differentiation of black- box combinatorial solvers. In Proceedings of the 8th International Conference on Learning Representations, 2020.
[48] G. Reinelt. TSPLIB a traveling salesman problem library. INFORMS Journal on Computing, 3(4):376-34, 1991. attp://sn cttp:tt/cc...../////////ooo... ift.p.iifi...i...... www.umiieiiii. hheidelberg de stfftwtre/////eo Swwaare/TSPPIB9///
[49] R. W. Rosenthal. A class of games possessing pure-strategy nash equilibria. Int. J. Game Theory, 2(1))65-67, 1973.
[50]
Roughgarden. Selfish Routing and the Price of Anarchy. The MIT Press, 2005.
[51] S. Sakaue. Differentiable greedy algorithm for monotone submodular maximization: Guarantees, gradient estimators, and applications. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, volume 130, pages 38336. PMLR, 2021.
[52] S. Sakaue, M. Ishihata, and S. Minato. Efficient bandit combinatorial optimization algorithm with rero-suppressed binary decision diagrams. Processings of the 2 International Conference Artificial Intelligence and Statistics, volume 84, pages 585-594. PMLR, 2018.
[53] W. H. Sandholm. Potential games with continuous player sets. J. Econ. Theory, 97(1):81-108, 2001.
[54] J. R. Shewchuk. Triangle: Engineering 2D quality mesh generator and delaunay triangulator. In Applied Computational Geometry Towards Geometric Enngineerigg pages 203-222, Springer, 1996. https: //www. cmu. edu/"quake/
eqquakettriangl. /trinnggeen..eeeeeee httl..
[55] H. Stackelberg. The Theory of the Market Economy. Oxford University Press, 1952.
[56] E. Takimoto and M. K. Warmuth. Path kernels and multiplicative updates. J. Mach. Learn. Res., 4(Occ):773-818, 2003.
[57] Thai. On learning Game-Theoretical models with Application Urban Mobility. PhD thesis, UC Berkeley, 2017. ProQuest ID: Thai_berkeley _022800109908 ark:/1 Nkks/330000m55566mbg Retrieved from https://esccholarshhpp
bew_eeeey_022e____170 Merritt ID:
wtrg/uccitem///ue
[58] M. J. Wainwright and M. Jordan. Graphical models, exponential families, and variational inference. Found. Trends Mach. Learn., 1(1-2):1-305, 2008
[59] J.-K. Wang and Abemnetyy. Acceleration through optimistic no-regret dynamics. In Advances in Neural Information Processing Systems, volume 31, pages 3824-3834 Curran Associates, Inc., 2018
[60] B. Wilder, B. Dilkina, and M. Tambe. Melding the data-decisions pipeline: Decision-focused learning for combinatorial optimization. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, volume 33, pages 1658-1665, 2019.
13


Reviews:
[{"review_id": "MjO6pdbCwHT", "reviewer": "Reviewer_WtUV", "summary": "This paper studies the problem of designing parameters of combinatorial congestion games, where selfish non-atomic agents choose an optimal route/network to optimize their own objectives. The combinatorial congestion games are a special type of potential games. The equilibrium of a congestion game with given parameters can be solved by optimizing the potential function. The problem of optimizing the game parameters is therefore a bilevel optimization problem with an equilibrium (potential function optimization problem) involved in the inner problem. Benefited from the recent development of differentiable optimization, the authors propose to solve the bilevel optimization problem by backpropagating the gradient from the argmax of the inner problem to the outer objective to run gradient descent. This end-to-end gradient descent approach can avoid solving the bilevel optimization problem with complex constraints by directly running end-to-end gradient descent.\n\nThe challenge involved in this end-to-end differentiable optimization approach is how to efficiently compute the gradient of a complex optimization problem (equilibrium computation/potential function optimization) with high-dimensional constraints. The authors leverage the Frank-Wolfe algorithm to solve the optimization problem and to get the corresponding gradient of the optimal solution. The use of the Frank-Wolfe algorithm decomposes the optimization problem into an iterative algorithm composed of multiple minimization problems, where each of them is relaxed to a softmin in order to make them differentiable. To solve the softmin problem with complex constraints, they use zero-suppressed binary decision diagrams (ZDD) to compactly represent the decision variables, which can speed up the optimization step while keeping the differentiability. The authors also utilize Nesterov's acceleration to improve the convergence of the Frank-Wolfe algorithm to $O(1/T^2)$, with the differentiability maintained.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The contribution of the paper falls mostly into the claim of making Nesterov’s acceleration differentiable. From the perspective of differentiable optimization, due to the complex constraints in this problem, the authors use the iterative Frank-Wolfe algorithm to optimize the potential function. Thus the optimization operators involved in the algorithm are simply argmin/argmax only. To my knowledge, there is no need to use KKT conditions and they also explained in the paper that they can’t efficiently express the complex KKT conditions as well. Thus the technique used in the problem is more about relaxing argmin to softmin in the Frank-Wolfe algorithm and Nesterov’s acceleration, and less about generalizing differentiable optimization. Overall, I still consider making Nesterov’s acceleration algorithm differentiable a nice contribution in this paper. \n\nI am familiar with differentiable optimization but less familiar with the recent literature on Nesterov’s acceleration. I agree that the main contribution is more on Nesterov's acceleration part. Making Nesterov’s acceleration differentiable is new to me from the perspective of differentiable optimization, but it is relatively a smaller modification compared to previous works in differentiable optimization using Frank-Wolfe algorithms, e.g., Wilder et al. [59] used KKT conditions as opposed to unrolling the entire Frank-Wolfe algorithm to achieve differentiability. I would reserve my judgment on Nesterov’s part to other reviewers, and I would appreciate it if the authors could elaborate more on some similar literature of relaxing argmin/argmax in Nesterov’s acceleration.\n\nPost-response: I am satisfied with the explanation and the additional elaboration of Nesterov’s acceleration that the authors gave. I agree that KTT conditions can sometimes be unnecessarily high-dimensional and complicated. It makes sense to me to sometimes consider unrolling and relaxing argmin/argmax instead of differentiating through the KKT conditions.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately address negative societal impact and limitations. The main limitations are the structure of the potential games and objectives. The same approach does not work when the games are not potential games. The theoretical guarantee of Frank-Wolfe style algorithms also fails when the objectives are not convex. Lastly, the algorithm largely relies on the use of zero-suppressed binary decision diagrams due to the complex constraints. The first two limitations are problem-specific and thus less a concern to me. The last limitation is discussed in the paper that ZDD can be precomputed to reduce its expensive computation cost.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "JOQliCOBnTH", "reviewer": "Reviewer_3ev8", "summary": "This paper focus on the Stackelberg model of combinatorial congestion games (CCGs), which is important for the case involved the leader and multiple self-interested followers. The main contribution of this paper is proposing a fully differentiable framework which can take the advantage of automatic differentiation.\n\nMy main concern is the contribution of this paper. There are two key techiniques in the proposed algorithms, softmin and Zero-suppressed binary decision diagrams (ZDD), where softmin is a widely used technique to make argmax operation to be differetiable and the ZDD technique is proposed in the 2020 AAAI paper, Practical Frank–Wolfe Method with Decision Diagramsfor Computing Wardrop Equilibrium of Combinatorial Congestion Games. I would like to ask authors to clearly state the difference of the techniques in this paper and the one in the 2020 AAAI paper.\n\nMinor issues and typos:\n\n\"practical utility\" in line 60, \"utility\" -> usage or application?\n\"Our method introduces benefits by improving the designs of social infrastructures\" is strange.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality \nA recent paper [42] proposed ZDDs method to tackle the combinatorial nature of CCGs. This paper moves one step forward to consider the Stackelberg models. \n\nQuality\nThe submission is technically sound. \n\nClarity \nClearly written.\n\n\n\nSignificance\nThe studied problem is not new, and the proposed method are mainly based on [42]. However, the Stackelberg model is very important, and the proposed technical novelties are very effective, thus I think the paper can be accepted. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "FrpE1Uce1o-", "reviewer": "Reviewer_Xufg", "summary": "The problem of computing equilibria in CGs is consider an easy task whenever the strategy space has a compact representation, since it turns out that the users minimize a convex function. When having to decide on some parameters of the CG in order to optimize the performance at equilibrium we get a bi-level optimization problem, where in the upper level the designer sets the parameters and in the lower level the users optimize their function reaching an equilibrium. Solving this bi-level problem is regarded to be far more difficult. This work deals with the latter problem and combines optimization techniques to give an algorithm that performs well in practice.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem of computing equilibria in CGs is consider an easy task whenever the strategy space has a compact representation, since it turns out that the users minimize a convex function. When having to decide on some parameters of the CG in order to optimize the performance at equilibrium we get a bi-level optimization problem, where in the upper level the designer sets the parameters and in the lower level the users optimize their function reaching an equilibrium. Solving this bi-level problem is regarded to be far more difficult. This work deals with the latter problem and combines optimization techniques to give an algorithm that performs well in practice.\n\nThe goal of the network designer is to minimize a function F that depends on the choice of the strategies of the players (let it be described by vector y) and a parameter vector \\theta. The choice of \\theta is on the designer and users reach an equilibrium based on that choice, minimizing a different function f so that y=argmin f.  For the case of fixed \\theta we get a single level program computing an equilibrium of the CG. A recent work (Nakamura et al. 20) used a data structure (zero-suppressed binary decision diagrams (ZDDs)) to get a compact strategy space representation for interesting cases and applied a Frank-Wolfe style algorithm that performs well whenever the representation using ZDDs is indeed compact. Here, for the bi-level program, this technique does not work as is because of non differentiability wrt \\theta. To get differentiability, the authors use softmin instead of argmin in the computation of y, while keeping the ZDDs representation for the strategy space, and provide an algorithm that seemingly performs well in practice.\n\nPros. The idea of using softmin (and making it work) in order to make the equilibrium differentiable wrt \\theta is interesting\n\nCons. Limited theoretical guarantees (although, in general this is difficult for bi-level programs)\n\nIf we fix \\theta, how does Algorithm 1 compare to the algorithm of Nakamura et al.?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "948bR7J-H_O", "reviewer": "Reviewer_2skQ", "summary": "The authors of this paper aim to find a combinatorial congestion game that optimizes a given objective over some parameterized class of games, assuming that the players in the game attain a Wardrop equilibrium. The problem is formulated using a framework of Stackelberg bi-level optimization models, where the designer (leader) chooses the game's parameters, and the followers then play the induced game. The authors propose to apply gradient-based methods to approximate the solution. To this end, it remains critical to be able to compute the followers' equilibrium and estimate its gradient, i.e., the changes in the equilibrium when the parameters of the game shift. For this purpose, the authors introduce a differentiable variant of the Frank–Wolfe algorithm. Instead of the strict minimization included in the original version, the authors suggest using softmin. Computing the softmin may be computationally demanding because it sums over all possible strategies, which is (in general) a set exponential in the problem size. More efficient computation can be achieved using the so-called zero-suppressed binary decision diagrams (ZDDs), a data structure enabling calculation of the softmin in time linear in its size. Because the size of the ZDDs is often many orders of magnitude smaller than the cardinality of the set of strategies, ZDDs offer a significant speedup in practice. In the last part of the manuscript, the authors present empirical results achieved with their algorithm and its variants on two classes of games per each strategy representation (Hamiltonian cycles and Steiner trees). The results show that the algorithm can converge to Wardrop equilibria faster than baselines, and the gradient descent running on top of it consequently designs better congestion games than the heuristic baselines.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written, all concepts are rigorously explained, and the notation is clear. I appreciate the examples described in the introduction that well illustrate the motivation of this paper. Also, the authors explain well how their work fits into the existing literature on the topic. As far as I can tell, the results are sound, the analyses and the proof of Theorem 1 seem correct to me.\n\nThe contributions of this paper may not be as strong since the approach is relatively similar to the method introduced in [42], i.e., a Frank–Wolfe-type algorithm accelerated using the ZDDs. Despite some similarities, this work makes the cut in my eyes because of the introduction of the Stackelberg setting, which required adapting the Frank–Wolfe algorithm for computing the gradients.\n\nWhile Theorem 1 establishes the convergence guarantee of solutions returned by the Frank–Wolfe-type algorithm to the Wardrop equilibrium, the work does not offer any results on the optimality of the final parameters computed by the gradient descent. If I interpret it correctly, there is no guarantee of how close to the global optimum the computed parameters are, given that the criterion F is non-convex in general. Did the authors try to perform some experiments on very small settings when the globally optimal Stackelberg parameters can be found using, e.g., linearization into MILPs, to see how well the gradient descent can approximate the global solution in practice?\n\nOne minor note: the legends of all graphs in Figure 2 obstruct the view of the plots. Since the legend is shared across all the graphs, it might be better to put one legend underneath them all. Similarly also in Figure 3.\n\n### After rebuttal\n\nI would like to thank the authors for a very detailed response to my questions and the amount of effort they put into coming with examples and running the additional experiments. I especially appreciate the example illustrating the difficulty of global optimization in this bilevel setting. My impression of this work remains unchanged, I believe it is a good research that deserves publication. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I find the limitations the authors mention in Section 5 honest and sufficient. Some discussion of the optimality of the gradient descent might be included for completeness. ", "review_text": "", "extra_scores": {"ethical_concerns": "I do not have any ethical concerns. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "25"}, "extra_text": {}}]

Author rebuttal:

Meta-review: I and the Reviewers have positive opinions on the paper and no major concern has been raised during the reviewing and discussion phases. Furthermore, the Reviewers found the rebuttals very useful, illustrating and clarifying better several points. In particular, I encourage the authors to add the example provided in the rebuttal to Reviewer 2skQ in the camera ready to their paper (the authors could add the example in the supplementary material if no space is available in the main body of the paper).
Decision: Accept (Poster)