Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

The 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.

Pros. The idea of using softmin (and making it work) in order to make the equilibrium differentiable wrt \theta is interesting

Cons. Limited theoretical guarantees (although, in general this is difficult for bi-level programs)

If we fix \theta, how does Algorithm 1 compare to the algorithm of Nakamura et al.?
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

My 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.

Minor issues and typos:

"practical utility" in line 60, "utility" -> usage or application?
"Our method introduces benefits by improving the designs of social infrastructures" is strange.
main_review: Originality 
A recent paper [42] proposed ZDDs method to tackle the combinatorial nature of CCGs. This paper moves one step forward to consider the Stackelberg models. 

Quality
The submission is technically sound. 

Clarity 
Clearly written.



Significance
The 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. 

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

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.

The 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.

While 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?

One 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.

### After rebuttal

I 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. 

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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

The 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.
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. 

I 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.

Post-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.
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.
review_title: null

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)