Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the minmax problem where the second player's (follower) action set depends on the action of the first player. Naturally, Stackelberg equilibrium is the concept to study here. The authors use a sub-gradient formulation of the known envelope theorem to solve the problem and experiment on Fisher market set-up.

main_review: In my reading of the paper, the work felt incremental because of
1) The algorithm as such is exactly (for Alg 1) or mostly (for Alg 2) in the style of Jin et al. (or actually, papers before that also) with the difference being that the sub-gradient is used. Hence, the convergence proof also mostly follows standard sub-gradient convergence proofs.
2) Fisher market and the Eisenberg Gale convex form has already been shown to admit first order methods on the direct EG form in Gao and Kroer. So, not sure why the same problem needs to be solved in a different way and is there any advantage of this first order form over that? The authors leave this future work but this comparison should be done for this work.
3) More details on experiments (how the utility defining parameters were chosen instead of just higher and lower values as in Fig.1 ) needs to be in the main paper

Writing:
Easy to read, short simple examples given to assist the readers in understanding the problem with and without dependent sets. 
The introduction is just too long, suggest breaking it up into more sections.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors study sequential (aka Stackelberg) games, where the actions of the follower are subjects to constraints depending on the leader's action.
They derive a formula for the subgradient of leader's utility (under optimal action of the follower) and use it to derive subgradient descent algorithms with convergence guarantees.
main_review: The authors study minimization problems of the form $\min \limits_{x} V(x) = \min \limits_{x} \max \limits_{y: g(x, y) \geq 0} f(x,y)$
for f convex-concave and g component-wise concave.
The convex function $V(x)$ is convex but in general only subdifferentiable.
If $V$ is differentiable in $x$, recent results by Milgrom and Segal allow to express its gradient in terms of the optimal solution $y, \lambda$ of the inner loop, where $\lambda
$ is a lagrange multiplier associated to the constraint.
The authors extend this results to a characterization of the subgradient of $V(x)$ in arbitrary points, and derive rates for the resulting first order methods, accounting also fo
r the solution of the inner loop.
They furthermore test their algorithms on a series of Fisher markets.

This appears to be solid work, although I am not sure about the relevance of the author's results to the rest of the NeurIPS community.
The authors do not provide any explanation to this effect, with the exception of line 376, which is fairly vague (in which GAN model do dependent strategy sets arise?).
Venues more focused on economics or convex optimization might also be better positioned to appreciate the theoretical contribution of the Subdifferential Envelope Theorem.

I am therefore somewhat on the fence about this paper, maybe slightly leaning towards rejection but open to being convinced otherwise in the rebuttal.

Comments to authors: As illustrated in the paper, convex games with dependent strategy sets do not satisfy a minimax theorem in general. 
However, they can also be interpreted as simultaneous (non-\{sequential/stackelberg\}) non-zero-sum games (with rewards attaining $-\infty$).
I might be helpful to change the title and possibly introduction to clarify that the paper deals with sequential games.
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies min-max optimization problems with dependent strategy sets, and introduces a first-order method that solves a large class of convex-concave min-max games with dependent strategy sets. In doing so, the authors provide a suitable envelope theorem which generalizes known results to the case of dependent strategies. That result is used to build two algorithms: max-oracle gradient-descent (which returns an approximation of the inner player's value function), and nested gradient-descent/ascent (which computes both players' strategies explicitly). The algorithms are shown to converge in polynomial time, and  they are experimentally evaluated through the computation of competitive equilibria in Fisher markets with varying utility structures. 
main_review: The paper is well written and mostly clear. The general problem of minmax games with dependent strategy sets is well motivated by applications such as computing equilibria in Fisher markets. The set of techniques presented may be a good starting point for future works on other related problems. 

I'd be interested in hearing more about how the method proposed by the authors compares (in the Fisher markets setting) to other recent works such as Gao and Kroer [23]. 


limitations_and_societal_impact: See main review
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work introduces two first order (subgradient) methods (1 requiring an oracle) to solve convex-concave min-max problems with convex dependent feasible sets. The convergence of both algorithms is analyzed, and their performance is demonstrated on computing Stackleberg equilibria of a family of Fisher market models.


Contributions:
1) A subgradient algorithm assuming access to an oracle plus a nested subgradient algorithm (paired with explicit Fisher market counterparts) for computing Stackleberg equilibria in min-max problems with feasible sets
2) Convergence guarantees for the proposed algorithms
3) Adaptation of the general algorithms to the Fisher market domain
4) Empirical analysis of the proposed algorithms on problems from either side of the boundary designated by the algorithmic assumptions
main_review: Originality:
To my knowledge, these are the first subgradient algorithms for convex-concave min-max problems with convex dependent feasible sets.

Quality:
The paper is of high quality.

Clarity:
The paper is written very clearly. I only had one question around Theorem 3.3 below.

Significance:
The computation of equilibria in min-max games is generally important and connections to Fisher markets in economist are made. It’s possible additional connections to robust optimization could increase the paper’s significance.


Overall, I think the paper is well written and comprehensive. I think the paper could benefit from a few changes
1) A discussion of uniqueness of the solutions to the min-max problems.
2) Baselines and experiments
3) Potentially add robust optimization to related work


- [1] “Theory and Applications of Robust Optimization” Bertsimas et al. 2011
- [2] “Online first-order framework for robust convex optimization” Ho-Nguyen and Kılınç-Karzan. 2016


1) Uniqueness:
One part of Theorem 3.3 appears suspect. It is claimed that Algorithm 1 converges asymptotically to $(x^*, y^*)$ which is a $(0, \delta)$-Stackleberg equilibrium, but is $(x^*, y^*)$ a unique equilibrium? I would assume there are many such $(0, \delta)$-equilibria. Can you please address this and add a discussion around uniqueness of solutions for these minmax problems with dependent feasible sets? Maybe you meant to say that Algorithm 1 converges to one of the many $(0, \delta)$-equilibria, not a specific one.


2) Baselines and Experiments:
- After reading the related work section, I was expecting an empirical comparison to the interior point methods of Ye [33] and first-order methods of Gao & Kroer [23]. Is there a reason you did not compare to them? The paper would benefit from having baselines to compare against.
- Didn’t you need to set a value for $\epsilon$ or $\delta$ for the inner loop? Ah, I see you opted for number of iterations $T_X$ instead. I’d be interested to know the ratio of $T_X / T_p$ used in the experiment. Also, I would like to see a sweep over this parameter, which could provide further insight into understanding at which point GDA might fail (low values of the ratio move Alg 4 closer to alternating ascent descent which is closer to GDA).


3) Robust Optimization:
At first glance, the min-max problem with dependent feasible sets seems related to robust optimization. Briefly, see https://en.wikipedia.org/wiki/Robust_optimization, https://en.wikipedia.org/wiki/Wald%27s_maximin_model or [1] and [2] for first-order online approaches.


Minor:
- Are the $g_i$ required to be concave so that the intersection with $Y$ forms a convex set? Is this the most general setting?
- A figure illustrating how taking a step changes the feasible set and hence presents problems for GDA could be enlightening and convince the reader of the difficulty of the problem
- line 60: After a double-take, I understand what you’re saying but saying $V(x)$ is $y$’s problem is confusing as $y$ doesn't appear as an argument. It’s probably better to write out "player $y$'s problem is $\max_{y \in Y}:g(x,y) \ge 0 f(x,y) = V(x)$" again.
- line 98: does $\epsilon$-approximation refer to error in the strategy space or value function space or both? It appears value function space (Def 2.1). It would help the reader if you mentioned this around line 98.
- Table 2, strongly concave case — I didn’t check the proof, but shouldn’t $\log(\epsilon)$ be $\log(\frac{1}{\epsilon})$? Seems like a typo.
- Figure 1 - maybe refer to the algorithms with a description as well since they are not included in the main body, e.g., Algorithm 3 (oracle, in blue) and Algorithm 4 (nested, in orange). Also, why not plot on a log scale?
limitations_and_societal_impact: The authors mention the connection of their work to fairness and adequately address any possible negative impact.
review_title: null

Meta-review: This paper studies a class of min-max games where each player's actions are subject to coupled constraints, i.e., the actions avaible to one player depend on the action chosen by the other, and vice versa. The authors examine two sequential algorithms for solving the game - one based on best responses and another based on a nested version of gradient descent - and they derive a series of polynomial complexity guarantees for the algorithms under study.

The reviewers appreciated the contributions of the paper and were initially positive. However, during the discussion phase, it became clear that the paper is ignoring an extensive literature on generalized Nash equilibrium problems. This literature dates back at least to Debreu's seminal 1952 paper and it treats essentially the same problem as the authors: in particular, there is a series of asymptotic convergence results (for different classes of games) that should be discussed by the authors. More precisely, even though the literature on learning in generalized Nash equilibrium problems does not provide rates of convergence, the results provided therein prove the convergence of the actual sequence of play (something which does not seem possible with the authors' approach and techniques).

Another - more minor - concern had to do with the relevance of such models for the ML/AI community, but this was partially addressed by the authors.

Overall, the paper definitely has merits: to the best of the committee's knowledge, this is the first polynomial complexity result of its kind in the class of games with coupled constraints (which is perhaps not surprising since the literature on generalized Nash equilibrium problems otherwise focuses on the convergence of the actual sequence of play, not the "best" or "time-averaged" iterate). However, the lack of proper positioning is a major issue that has to be fixed for the camera-ready version; specifically, the committee has the following expectations:
1. The authors should provide adequate pointers to the literature on generalized Nash equilibrium problems, especially on early work by Facchinei and co-authors, as well as more recent contributions by Grammatico and co-authors - e.g., the recent preprint by Fabiani et al., "Local Stackelberg equilibrium seeking in generalized aggregative games" should be discussed in detail. [Certain references were already provided during the discussion phase, and the authors would be expected to expand on those]
2. The authors should present in detail the notion of generalized Nash equilibria in the paper (during the discussion phase, there seemed to be some confusion on this point by the authors, but it was eventually cleared up). In particular, the committe expects the authors to provide an in-depth comparison to the model of Fabiani et al. - not in regard to the _class of games_ considered, but as to the _notion of equilibrium_ under study. Put simply, now that the authors are aware of the literature on the problem, the committee would expect an in-depth and balanced treatment.
3. The algorithms studied by the authors should be incorporated in the main text - otherwise, the statements of the authors' theorems are impossible to parse.

Modulo the above, I am happy to recommend acceptance.
Decision: Accept (Poster)