Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In large scale incentive design processes, the classical approach is one of estimating behavior, adjusting incentives, evaluating the outcome, repeated until a fixed point is reached. At each step, you may need to wait long enough for behavior to stabilize into an equilibrium or to see enough data for the econometric task at hand.

This work considers an alternative approach in which the behavior gradient is used to estimate how the behavior will change, and hence allowing the algorithm to adjust incentives faster to the way that agents are responding to the incentives, effectively adjusting both in continuous time to lead to equilibrium (e.g., more of an optimal control based approach).

The approach is implemented on a few problems: second-best tolling, and pollution taxes, both showing empirical convergence in line with the theoretical convergence results. 

strengths_and_weaknesses: The work seems to be a substantial original contribution in showing that simultaneous design and react can be used to quickly converge to optimal policies, across a broad range of problems.

The exposition does a good job of clearly illustrating the robustness of the techniques.

The simultaneous design & move approach is advocated for as an improvement over waiting for convergence to equilibrium at each step. While this claim makes intuitive sense that it would be an improvement, it would strengthen the argument to show an explicit theoretical or empirical gain in convergence relative to the bilevel approaches.
questions: Can you discuss the improvement in theoretical convergence or empirical performance relative to the best known prior approaches? 
limitations: Yes, the authors have adequately addressed limitations.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors study how to compute the Stackelberg equilibrium in a Stackelberg (bilevel) game where the first mover is a social designer and the second movers are agents that simultaneously best respond to the designed incentives. Different from existing methods that require solving the agents' level equilibrium repeatedly for each update on the designer's strategy, the authors propose a simultaneous design-and-play algorithm that updates strategies on both levels in each update step. The authors show convergence of the new algorithm mainly under conditions that guarantee the uniqueness of the equilibrium and discussed the multiple equilibria case briefly. 
strengths_and_weaknesses: Strengths:
1. Clear problem statement
2. Clear presentation of the algorithms and the theoretical guarantees of the new algorithms

Weaknesses:
1. The performance bounds on the related works or baselines are not clearly given, making it hard to know the efficiency improvement of the new algorithms. Personally, I would like to see a table showing what are the common assumptions used in this paper and other related works, and whether each of them guarantees convergence and at what convergence rate, adding other comparison metrics like the order of floating-point operations steps would be even better
2. It would be better to have a table in the appendix showing the notations used in the paper
questions: 1. So a natural thought on this new approach is flattening the bilevel game into a single-level game and treating the designer as another agent in the network that is connected to all other agents. If we use this flattened view to solve the variational inequalities directly, can it still work under your assumptions, and what are the main differences between your approach and this "brute force" flattened approach?
2. Same as discussed in the weaknesses, is it possible to add quantitative comparisons between your algorithms and other bi-level optimization and MPEC works?
limitations: As discussed in the weaknesses, the paper seems to be a bit short of information in its quantitative comparisons to the related works.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper claims to introduce algorithms for incentive design in convex games. In particular, the incentive designer is faced with selecting a parameter $\theta$ such that the resulting game has an equilibrium $x_*(\theta)$ that is desirable for the designer. The authors state some preliminary results about such games, and then give an algorithm that attempts to find an optimal parameter $\theta$, prove properties of their algorithms, and give some experimental evidence of their effectiveness in practice (appendix).
strengths_and_weaknesses: The problem and analysis presented in the paper are interesting. However, I have some concerns, mostly pertaining to setting this paper within the field of computational game theory.

Perhaps most notably, I do not think the authors have done a sufficient job relating this paper to prior work in computational game theory. For example, the techniques of this paper are based on online learning--Algorithms 1 & 2 are, modulo some careful tuning of step sizes, essentially "every player run online mirror descent", which is a very well-known idea in computational game theory. However, the authors do not discuss this connection at all. Further, the "bilevel optimization problem" is essentially a Stackelberg game with a single leader and multiple followers, and I believe there should be a concrete connection drawn to that literature. For example, if $n=1$, then it is known that equilibria are easy to find even in general normal-form games, by a standard linear programming algorithm. 

I would also like to see a much more in-depth discussion of the Assumptions 5.1-5.3 as they pertain to useful classes of games. For example:
1. The monotonicity/strong stability condition (e.g., Assumption 5.1, Section 6 Case II) seems *very* strong. I understand that this is the only thing preventing the paper from breaking long-standing assumptions in complexity theory (e.g., implying a polynomial-time algorithm for Nash in normal-form games), but I feel that the authors should take more time to discuss intuition for what these assumptions mean in practice. For example: what, if anything, does this paper say about normal-form ("nonatomic", in this paper's language) games?
1. The convexity of $f_*(\theta)$ is perhaps too strong an assumption. The authors admit this, but that does not make it less bothersome. 
1. Can the bounded variance in Assumption 5.3 be replaced with an $x^i$-dependent variance, as is usual in the online learning literature (see, e.g., the analysis of Exp3)?

questions: A few minor points about the exposition (atomic and nonatomic games):

1. Why separate "atomic games" from "nonatomic games"? It seems to me that a nonatomic game is simply an atomic game over simplices with multilinear utility functions. 
2. Also, why define one in terms of utility and one in terms of cost? To me this only introduces extra needless confusion.
3. Isn't "nonatomic game" just a normal-form game here? Why bother introducing "continuum of players", and why not use the usual language of normal-form games?

Miscellaneous things:

1. Throughout the paper, "quantum" should probably be "quantal", as in "quantal response equilibrium". I've never heard of that referred to as "quantum equilibrium".
1. Line 145: since the utility is being maximized, $u^i$ should be concave, not convex
limitations: The authors have adequately addressed limitations, modulo concerns I have already stated above.
review_title: null

Meta-review: metareview: Executive summary:

This paper considers the incentive design problem (making sure players in a non-cooperative game play a certain equilibrium by setting incentives appropriately) in both atomic and non-atomic games. It deviates from the classic computational learning approach which is looping over two steps: (1) setting incentives and (2) waiting for the system to converge to equilibrium. This work proposes a "simultaneous design and play" approach in which the behavior gradient is used to estimate how the behavior will change, and hence allowing the algorithm to adjust incentives faster to the way that agents are responding to the incentives, effectively adjusting both in continuous time to lead to equilibrium. 

On the theoretical side, the paper establishes that this "single loop" approach provably converges in two important cases (Theorem 5.7 and Theorem 5.8). On the empirical side, the paper applies the proposed approach to two problems (second-best tolling, and pollution taxes).

Discussion and recommendation:

We had a very lively discussion around this paper. All reviewers agreed that the paper pursues a natural and original idea, but all reviewers had important objections and/or suggestions.

Our conclusion after the rebuttals was that all these can be addressed through proper rewriting.

We in particular felt that it is crucial to corroborate the intuitive claim that the simultaneous approach is more efficient with numerical results. So please include a numerical comparison of your proposed approach to state-of-the-art algorithms using the two step approach as e.g. promised in the reply to reviewer 1gpF.

Weak accept.
confidence: Certain
Decision: Accept