On Local Equilibrium in Non-Concave Games

Q: At a high level, I’m concerned about the motivation. The authors introduce a new solution concept and design algorithms, but don’t really stop to motivate their solution concept. The way I understand, in practice GAN training with OGD has limited success because it gets stuck in cycles. Now you’re basically telling me that the path of this training satisfies some new solution concept. What should I learn from that? By analogy, in Game Theory correlated equilibrium has a natural interpretation with a correlating device, and is known to satisfy some good properties (“Price of Anarchy”). What can I do with the fact that the trajectory of my GAN training algorithm is an approximate “local correlated equilibrium”?

A: Thank you for the comment on the motivation of our proposed solution concepts. We appreciate the opportunity to further elucidate our goals. Our primary objective is to introduce a new solution concept for non-concave games that satisfies the following three requirements: game theoretic meaningfulness, universality, and computational tractability. Our notion of local correlated equilibrium is meaningful as it generalizes the notion of correlated equilibrium and coarse correlated equilibrium to non-concave games. Additionally, as we argue in the paper, this solution concept always exists, hence its universality. Finally, for the two instantiations, we show that these solution concepts are computationally tractable.

As highlighted by the reviewer, correlated equilibrium is a useful concept when there is a signaling device that could be used to correlate different agents’ actions. However, in the context of non-concave games, finding a correlated equilibrium is computationally intractable. We believe our solution concept serves as a useful alternative in these non-concave games where a signaling device is available, which includes many multi-agent systems such as market dynamics (see the respones to Review oLqg (Q1) for an example), cooperative strategies among self-driving cars, and interactions within social networks.

Finally, it’s important to note that the training GANs is a min-max optimization problem where the goal is to identify the minimax strategy for the min-player (controlling the generator network). Our focus on finding a local correlated equilibrium is very different from the pursuit of a minimax strategy, and as such, doesn’t inherently guarantee high performance of the generator.

Q: The paper is motivated by a hardness result from [DSZ21] for the stronger notion of local Nash equilibrium. But the hardness result in [DSZ21] holds only in a non-standard setting where the feasible domain is not a product. In contrast, your work seems to rely on having a product domain.

A: Thanks for pointing this out! The result from [DSZ21] shows that local Nash equilibrium is intractable even in two-player zero-sum games with coupled domain. Thus whether local Nash equilibrium in two-player zero-sum games can be efficiently computed with product domain is still open. However, we study the more general multi-player non-concave games that include two-player general-sum games as a special case. Note that in a two-player general-sum bimatrix game, since the loss function is linear in each player’s strategy, it is not hard to see that every local Nash equilibrium is also a Nash equilibrium, and, therefore, is PPAD-hard to compute [DGP09, CDT09]. The intractability of local Nash equilibrium in general-sum games motivates our new local solution concepts that is universal for multiplayer non-concave smooth games.

[DSZ21] Daskalakis, Constantinos, Stratis Skoulakis, and Manolis Zampetakis. "The complexity of constrained min-max optimization." STOC, 2021

[DGP09] Daskalakis, Constantinos, Paul W. Goldberg, and Christos H. Papadimitriou. "The complexity of computing a Nash equilibrium." SICOMP, 2009

[CDT09] Chen, Xi, Xiaotie Deng, and Shang-Hua Teng. "Settling the complexity of computing two-player Nash equilibria." JACM, 2009

Q: I think your solution concept should be called “local coarse correlated equilibrium”: You consider a single deviation rule and want to apply it to all x’s in the distribution. This also explains why you can find it by minimizing external regret.

A: We would like to clarify that both coarse correlated equilibrium (CCE) and correlated equilibrium (CE) consider a single strategy modification (deviation rule) that is applied to all strategies. The core difference between CCE and CE is that CCE allows only constant strategy modification that maps any strategy to a fixed strategy, while CE allows all possible linear transformations over the strategy space (i.e., the simplex). In the context of normal-form games, both CCE and CE are special cases of $\Phi$-equilibria: a CCE is a $\Phi_{ext}$-equilibrium where $\Phi_{ext}$ contains only constant strategy modifications; a CE is a $\Phi_{swap}$-equilibrium where $\Phi_{swap}$ contains all linear transformations $\phi: \Delta \rightarrow \Delta$.

The solution concept we propose, $(\epsilon, \Phi(\delta))$-local correlated equilibrium, is determined by the set of strategy modifications $\Phi(\delta)$. In general, $\Phi(\delta)$ could include all possible (local) strategy modifications, not only constant strategy modifications. The two specific instantiations considered in the paper, $\Phi_{int}(\delta)$ and $\Phi_{proj}(\delta)$, also allow non-constant strategy modifications. That is why we choose to call it local correlated equilibrium instead of local coarse correlated equilibrium. Additionally, we have showed in the paper that $Reg_{proj}(\delta)$ is incomparable with the external regret and minimizing external regret does not always lead to a $\Phi_{proj}(\delta)$-local correlated equilibrium (Example 1 and 2 in section 5).

Q: There are two definitions (2 and 4) called “local correlated equilibrium”

A: Thanks for pointing out! We have changed Definition 4 to "Two Instantiations of Local Correlated Equilibrium".

Thank you for your very detailed review and insightful questions! We address your questions below

Q1: One has to be fair and recognize the novelty of the paper and the absence of pre-existing criteria for its assessment; nevertheless, it would be rational to ask for some justification of the proposed equilibrium notion other than computational complexity arguments. In a sense, what are real-world examples where the proposed notions of equilibria are already established as desirable states of a game?

A: We appreciate your recognition of the novelty of our work and your interest in the practical relevance of our proposed equilibrium notion. We will use the dynamics of pricing in a competitive market as an example to illustrate the applicability of our $\Phi_{proj}(\delta)$-local correlated equilibrium concept in a real-world scenario.

The market has multiple agents selling identical goods. Each agent sets a price $p^i_t$ for their goods at day $t >=1$. The reward everyday depends on the agent’s price: a high price decreases the demand of the goods but increases revenue per unit; while a low price could increase demand but decreases revenue per unit. In a complex market environment, the utility function in terms of $p_t^i$ could be non-concave so that even computing the optimal price given the knowledge of the utility functions is intractable. If each player adjusts their price using the online gradient descent algorithm, then our results show that their pricing strategy converges to a $\Phi_{proj}(\delta)$-local correlated equilibrium. In such equilibrium, each player would not regret to be more conservative (i.e., posting a slightly lower price $p_t- \delta$ everyday) or to be more aggressive (i.e., posting a slightly higher price $p_t + \delta$ everyday). This scenario demonstrates the equilibrium's relevance: in a market where agents have bounded rationality and make decisions based on localized price adjustments, our proposed equilibrium notion provides a stability guarantee. More generally, the proposed solution concepts may have practical implications, especially in multi-agent systems where agents encounter complex, non-concave utility functions and operate under the constraints of bounded rationality.

Q2: What kinds of $\Phi(\delta)$ families would the authors consider as important for future study and of game-theoretic importance?

A: This is a great question! One family of $\Phi(\delta)$ that is important is a generalization of $\Phi_{int}(\delta)$. Recall that $\Phi_{int}(\delta)$ contains strategy modifications that interpolates between current strategy $x$ and a fixed strategy $x^*$. One can consider a strategy modification that interpolates between current strategy $x$ and a modified strategy $\phi(x)$ for $\phi \in \Phi’$ where $\Phi'$ is a set of (possibly not local) strategy modifications. $\Phi_{int}(\delta)$ then becomes a special case where $\phi(x) = x^*$ is a constant strategy modification. By a similar proof to that in section 4, it is easy to show that regret minimization under the new set reduces to $\Phi’$-regret minimization. We think obtaining a more fine-grained understanding of the complexity of $\Phi’$-regret minimization for more general classes of strategy modifications $\Phi’$ is an interesting future direction. For instance, is it possible to define a meaningful complexity measure of a set $\Phi’$ that characterizes the computational / oracle complexity of $\Phi’$-regret minimization.

Q3: What is the connection of $\Phi(\delta)$-regret minimization and bounded rationality? Putting the computational theoretic aspects aside, we in a sense assume agents to be as rational as their first-order derivative dictates. Would assuming bounded rationality for the agents lead to tractable notions of equilibria as well?

A: This is a great question! We believe $\Phi(\delta)$-regret minimization is a model of bounded rationality. In this context, we refer to bounded rationality as the idea that agents have limitations in their decision-making processes, particularly in terms of the information they consider and the computational resources they have.

In $\Phi(\delta)$-regret minimization, the set $\Phi(\delta)$ only contains local deviations that are bounded by $\delta$. Thus agents are not fully rational as they ignore global deviations that might be more beneficial. Moreover, as you pointed out, assuming agents to be as rational as their first-order derivative dictates is a choice of bounded rationality. Furthermore, the cardinality and complexity of the set of $\Phi(\delta)$ reflect a degree of an agent’s rationality: A more rational agent, within the bounds of their capabilities, might consider a larger and more complex set of potential deviations compared to a less rational agent. Our results demonstrate that two sets of $\Phi(\delta)$ lead to tractable notions of local correlated equilibrium. This suggests that by assuming bounded rationality, agents can achieve stable outcomes even in complex non-concave environments.

Exploring other models of bounded rationality, different equilibrium concepts, and learning dynamics that converge to these equilibria are very interesting future directions.

Q4: What would qualitatively change if we assumed access to second-order information?

A: We remark that by assuming access to second-order information, [DGSZ23] developed a second-order algorithm that converges to local Nash equilibrium although without concrete convergence rates. This result improves over first-order methods which usually get stuck in limit cycles and shows the power of second-order methods. If we assume access to second-order information, it is possible that we can develop algorithms with faster convergence to local correlated equilibrium than first-order algorithms. This is a very interesting future direction.

[DGSZ23] Daskalakis, C., Golowich, N., Skoulakis, S., & Zampetakis, E. STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games. COLT, 2023

Q: I'm confused about your response to this reviewer's Q1 about the (lack) of motivation for the new solution concept that you introduce, which you also cited in your response to my review: You propose to motivate your solution concept in that if the no-regret dynamics converge to it, then each player would have low regret. But if all you're trying to achieve is low regret, why talk about equilibria at all? I.e. why not just analyze the performance of no-regret algorithms in non-concave games?

A: There seems to be some misunderstanding regarding the example's purpose. It was intended to illustrate the kind of guarantee our solution concept offers. To rephrase: If a correlating device (mediator) suggests prices to each player according to an $(\epsilon, \Phi_{proj}(\delta))$-local correlated equilibrium, then no player would have more than $\epsilon$-incentive to deviate slightly from the recommended price, either by increasing or decreasing it. This example serves to motivate the $(\epsilon, \Phi_{proj}(\delta))$-local correlated equilibrium by showing its ability to provide stability guarantees under a certain form of bounded rationality assumption.

An additional feature of our solution concept is that it is computationally tractable. Indeed, they can be computed if all players employ simple no-regret learning algorithms. Guaranteed convergence by decentralized learning dynamics is an appealing feature of our solution concept, and this property holds for (coarse) correlated equilibrium in concave games and for Nash equilibrium in two-player zero-sum bimatrix games.

Thank you for your very positive review and constructive comments! We will incorporate your suggestions in the next version of the paper. We address the questions below.

Q1: Aren’t part 1) of assumption 1 redundant given part 3? And part 2) redundant given part 1 and compactness of strategy sets?

A: Thank you for your thoughtful observations regarding the structure of Assumption 1.

Regarding your first point, we agree that Part 1 of Assumption 1 is implied by Part 3. Part 1 should be the definition of differentiable games while smooth games are differentiable games with additional smoothness assumptions. For clarity, we have removed Part 1 and added the definition of differentiable games in the paragraph above.

Concerning Part 2, your insight is correct that it could be inferred from the combination of the former Part 1 and the compactness of strategy sets. Nevertheless, we have chosen to retain this part for explicitness, particularly to specify the Lipschitz constant $G$. This explicit specification is useful for some of our subsequent analyses and results. We have rephrased it in the revised version of the paper to clarify its role.

These changes, along with the revised introduction of differentiable and smooth games, are highlighted in the updated version of our paper.

Q2: The local Nash definition that is studied in the paper considers only pure strategies, however, local correlated equilibrium is studied in correlated mixed strategies (logically). This begs the questions, can mixed local Nash equilibria be efficiently computed or is that out of reach as well? It seems like that would be out of reach since the randomization would reduce the problem to a multilinear game (albeit infinite dimensional) for which computation of Nash is PPAD. I think a description of this point is important to understand the jump from pure strategies to mixed strategies

A: Thank you for your insightful question on the complexity of mixed local Nash equilibria, which indeed warrants further discussion in our paper.

To address your question: Computing mixed local Nash equilibria is PPAD-hard for general-sum normal-form games, which are concave games. Since the agents have multi-linear utility functions, every local mixed Nash equilibrium is also a Nash equilibrium. Computing a Nash equilibrium in general-sum normal-form games is known to be PPAD-hard [DGP09, CDT09], so computing a mixed local Nash equilibrium is also PPAD-hard. [DSZ21] indeed considers pure local Nash equilibria, but they show that this is PPAD-hard even in two-player zero-sum games with non-concave utility functions.

We will expand upon these points in the revised version of our paper, providing a clearer bridge between the concepts of pure and mixed strategies and their respective computational implications.

Q3: Does Lemma 1 assume Lipschitz smoothness/continuity on the convex regrets or no?

A: Thanks for this question. Lemma 1 holds when there exists an online learning algorithm that has $\Phi$-regret against convex loss functions. In the context of lemma 1, we do not need other assumptions. $G$-Lipschitzness is required to achieve sublinear regret for specific algorithms like GD / OG, . But Lemma 1 still holds if there exists a no-$\Phi$-regret algorithm that does not require such assumptions.

Q4: How does part 2 of Lemma 1 relate to Hazan et al’s [2] results and in general how do the authors’ result relate to your results on projected \phi regret?

A: Firstly, it's important to clarify that Part 2 of Lemma 1 and the results by Hazan et al. [HSZ17] study very different notions of regret (See examples below for an illustration), leading to distinct local equilibrium concepts. As such, they are not directly comparable. Moreover, we've included a detailed discussion in the related works section of Appendix A. The discussion is as follows.

The work most closely related to ours is [HSZ17]. The authors propose a notion of $w$-smoothed local regret against non-convex losses, and they also define a local equilibrium concept for non-concave games. They use the idea of smoothing to average the loss functions in the previous $w$ iterations and design algorithms with optimal $w$-smoothed local regret. The concept of regret they introduce suggests a local equilibrium concept. However, their local equilibrium concept is very non-standard in that its local stability is not with respect to a distribution over strategy profiles sampled by this equilibrium concept. Moreover, the path to attaining this local equilibrium through decentralized learning dynamics remains unclear. The algorithms provided in [HSZ17] require that every agent $i$ experiences (over several rounds) the average utility function of the previous $w$ iterates, denoted as $F^t_{i,w}:=\frac{1}{w} \sum_{\ell=0}^{w-1} u_i^{t-\ell}(\cdot,x_{-i}^{t-\ell})$. Implementing this imposes a significant coordination burden on the agents. In contrast, we focus on a natural concept of local correlated equilibrium, which is incomparable to that of [HSZ17], and we also show that efficient convergence to this concept is achieved via decentralized gradient-based learning dynamics.''

The following two examples shows that the $w$-smoothed local regret and $\Phi_{proj}(\delta)$ (we will refer to it as $\delta$-projected regret) are incomparable. A sequence of actions may suffer linear $w$-smoothed local regret but constant $\delta$-projected regret (Example 1), and vise versa (Example 2).
Example 1:

1. Loss sequence: $f^t(x) = |x|$ for every $t \in [T]$ over $X = [-1,1]$.
2. Action sequence: $x^t = 1/2$ for odd $t$; $x^t = -1/2$ for even $t$
3. Regret: For any $\eta < 1/2$ and $w \ge 1$, the $w$-local regret is at least $\Omega(T / w)$; For $\delta > 0$, the $\delta$-projected regret of $\{x^t\}$ is at most $\delta$.

Example 2:

1. Loss sequence: $f^t(x) = -x^2$ for every $t \in [T]$ over $X = [-1,1]$.
2. Action sequence: $x^t = 0$ for all $t \in [T]$
3. Regret: For any $\eta > 0$ and $w \ge 1$, the $w$-local regret is $0$; For any $\delta < 1$, the $\delta$-projected regret of $\{x^t\}$ is at least $\delta^2 T.$

Q5: Naive regret bound in section 3.1 seems meaninglessly loose. That is, having an additive Lipschitz continuity constant G suggests that the algorithm might make no progress at all?

A: The regret bound of naive $\Phi$ regret minimization is $O(\delta G\sqrt{T \log|\Phi^\gamma|} + \gamma G T)$. By setting $\gamma = 1/T$ we can get a regret bound that is sublinear in $T$. However, as we mentioned in the paper, this approach leads to a regret bound that depends on $\log|\Phi^\gamma|$ while the per-iteration complexity depends on $|\Phi^\gamma|$, which is prohibitively high.

Q6: Reg_proj does not have a learning rate in the step it takes. This seems to affect the notion that projected and external regret can in general be unrelated?

A: Reg_proj (we will refer to it as projected regret) is parameterized by $\delta$, which is the largest $\ell_2$ norm of a possible deviation. As we demonstrated in the paper (example 1 and 2), projected regret is indeed incomparable with external regret in the sense that (1) a sequence of actions could have linear external regret but 0 projected regret; (2) a sequence of actions could have linear projected regret but 0 external regret. Despite the difference, we show that the online gradient descent algorithm achieves sublinear regret bounds for both notions of regret.

[HSZ17] Hazan, Elad, Karan Singh, and Cyril Zhang. "Efficient regret minimization in non-convex games." ICML, 2017

[DSZ21] Daskalakis, Constantinos, Stratis Skoulakis, and Manolis Zampetakis. "The complexity of constrained min-max optimization." STOC, 2021

[DGP09] Daskalakis, Constantinos, Paul W. Goldberg, and Christos H. Papadimitriou. "The complexity of computing a Nash equilibrium." SICOMP, 2009

[CDT09] Chen, Xi, Xiaotie Deng, and Shang-Hua Teng. "Settling the complexity of computing two-player Nash equilibria." JACM, 2009

Comment: I found that the paper writing is not sufficiently neat in some parts. While all the concepts and results are introduced and adequately explained, there are some issues with terminology and notation, which is not coherent across different sections. For example, in Section 3 the paper talks about differential games, but these have never been introduced in the previous sections (only the definition of smooth game is provided). My score reflects the weakness above. I strongly encourage the authors to carefully proofread the paper in order to improve it, and I am willing to increase my score if they do so.

A: Thank you for your feedback. We acknowledge the issues you've pointed out regarding our writing, particularly in the use of terminology and notation across different sections. We have conducted a thorough review of the paper for clarity and consistency. Specifically, we revised the introduction of differentiable games and smooth games in Section 2, ensuring a more coherent flow into Section 3. The updated version of the paper, with these changes highlighted, has been uploaded for your review.

We appreciate your willingness to reconsider your score upon improvements. We are committed to continuing our proofreading efforts to ensure consistency. If you find any further issues or have additional suggestions in the revised version, please do not hesitate to inform us. Your feedback is invaluable in helping us refine our work.

Thank you for your comment! We address your questions below.

Q1: "First, I would like to understand how to read Theorem 1 ... – is this correct?"

A: This is correct. Our results on convergence to local correlated equilibrium (Theorem 1, 2 and 5) rely on Lemma 1 and hold in the local regime where $\delta < \sqrt{2\epsilon / L}$ with $L$ being the smoothness constant. We have included this condition in the statement of Theorem 1, 2 and 5 in the revised paper. We remark that we also provide hardness results for both the computational and oracle complexity of local correlated equilibria in the global regime where $\delta = D_{\mathcal{X}}$ (Appendix D).

Q2: "Specifically, consider the single-player maximization game with $\mathcal{X} = [-1,1]$ and $u(x) = x^2/2$ ... Am I missing something?"

A: In this paper, our goal is to introduce a solution concept that is universal, meaning it exists in all games, and is also efficiently computable. In your example, $x=0$ is indeed a local correlated equilibrium based on our definition. But it turns out that including stationary points seems to be the only way to guarantee universality and computational tractability, which we detail in the following paragraph.

Allowing stationary points is necessary: The only solution concept previously known to guarantee existence and finite representation — essential for efficient computation — is the local Nash equilibrium. However, it has been demonstrated to be computationally intractable in the local regime in [DSZ21]. Therefore, we propose a solution concept that relaxes the local Nash equilibrium and is aditionally efficiently computable. To ensure existence, the set of local Nash equilibria must include stationary points. This can be illustrated with a basic zero-sum (min-max) game, characterized by the utility function $u(x,y) = (x - y)^2$, where $x, y \in [-1, 1]$. In this game, a simple analysis reveals that no global Nash equilibrium exists. Likewise, there isn't a solution where the min-player chooses a local minimum and the max-player a local maximum. However, any point $(x, y)$ with $x = y$ is a local Nash equilibrium, as at these points each player encounters a zero gradient, indicating no incentive to deviate when considering only local gradient information. Our concept of local correlated equilibrium, being a more generalized version of local Nash equilibrium (encompassing it as a special case), naturally includes stationary points. The inclusion of stationary points is an unavoidable compromise; excluding them would lead to the loss of either universality or finite representation in the solution concept.

[DSZ21] Daskalakis, Constantinos, Stratis Skoulakis, and Manolis Zampetakis. "The complexity of constrained min-max optimization." STOC, 2021

It goes without saying that no equilibrium concept is perfect. Even for well-established ones, like Nash equilibrium, there is a vast literature giving example settings where we don’t like its predictions, proposing refinements or other solution concepts to fix these problems, and this keeps going. In our setting of non-concave games, by no means do we want to suggest that our proposed solution concept solves the problem of identifying the right equilibrium target. We think that this is an extremely hard problem, but one that is important already and will be even more important in the future. Unfortunately, prior to our work, there had just not been a proposed solution concept that exists and is tractable and that is (even very weakly) stable under individual player deviations. We are happy with the progress that is made in our paper and it is an invitation to the community to think about this important problem. Game-theoretic settings are extremely hard, and there cannot be progress if small steps are quashed.

Just to give some historical context here, when Nash went to one of the most prominent mathematicians of his time (von Neumann) to present his theorem, von Neumann dismissed it as trivial. Anecdotally, it is believed that von Neumann said something like “you know this is just a fixed point.” von Neumann is right. Nash equilibrium is a very weak solution for many reasons, much weaker than the much sharper minimax equilibrium that von Neumann had worked on. However, Nash’s theorem has been much more impactful than von Neumann’s because, despite its weaknesses, Nash equilibrium is guaranteed to exist beyond two-player zero-sum games. We similarly invite you not to dismiss our contribution. This is truly the best solution concept we can guarantee exists, is tractable and satisfies some weak unilateral deviation property. It is really an invitation to think along this plane (of existence, tractability, meaningfulness) for better solution concepts.