Beating Price of Anarchy and Gradient Descent without Regret in Potential Games

We are delighted to hear that you found our paper to be well-written, and that you appreciated our efforts to provide intuition for our results!

• Question 1: Why focus on metrics which measure performance with respect to random initialization instead of other methods of initialization, e.g. initializing to the uniform distribution over actions as is canonical in the literature on learning in games?

• Response:

  • Firstly, as we show, starting from the uniform distribution, the dynamics are guaranteed to converge to the risk-dominant equilibrium which, unless it coincides with the payoff dominant equilibrium, can be detrimental to social welfare. Thus, the convention to start at the uniform distribution is, in fact, a restriction rather than a desirable norm.
  • Secondly, we believe that our quantification of uncertainty is more appropriate for our purpose. Specifically, if we assume that all the agents always start from a uniform distribution that seems to convey a belief from the perspective of the experimenter that the related individuals do not have any inherent biases for choosing one action versus another. But in practice there could be a lot of conscious or unconscious biases at play; for instance, due to how the order with which the actions are presented to the participants, or the names given to the actions, etc. Thus, we believe that it is more appropriate to encode a type of epistemic uncertainty that means that we are not being certain about what the relevant probability distribution is (see also the Wikipedia discussion here). Critically, this was also the choice in the original paper by Panageas and Piliouras that we are building upon.
  • Finally, perhaps it is also useful to point out why our results are robust to the choice of the initial measure which does not have to be exactly the uniform measure, i.e., the Lebesgue measure. Specifically, we could easily allow for the measure of each set to be within some fixed multiplicative constant, $\gamma$, of its true Lebesgue measure, in which case, the probability of converging to the good/bad equilibrium could only be amplified/reduced by at most $\gamma$. Combining this with the analysis for the uniform case, one could then derive such APoA bounds, but now they would be parametric on $\gamma$.

• Question 2: Do you have any insights on how your results would carry over to the discrete-time setting?

• Response: The details of the analysis would depend on the exact choice of discretization, e.g., whether you discretize replicator as Multiplicative Weight Updates (i.e. the Euler method in the dual space), or via a discretization in the primal space, or e.g., via discrete replicator dynamics also known as linear MWU). Generally there could be shuttle differences in the behavior of a given orbit given the exact choice of discretization (see [1]). Such subtleties aside, a good rule of thumb is that by choosing small enough step-size the regions of attraction of the discretized systems can effectively become indistinguishable from the continuous-time one. Pushing such approaches towards understanding larger steps sizes, which could destabilize some discretizations into chaos (again see [1]) is an interesting direction but beyond the scope of this work.

  1. Palaiopanos, Gerasimos, Ioannis Panageas, and Georgios Piliouras. "Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos." Advances in Neural Information Processing Systems 30 (2017).

Thank you for the interesting questions!

We are very happy to hear that you found the conceptual questions addressed by our work interesting and suggestive of intriguing future directions!

Suggestion: While this work does give good discussion on how the current paper extends the original results of Panageas and Piliouras, it may be worth providing a short discussion on the technical differences that allow these extensions. This would also help convince the reader of the novelty of these results... A bit more discussion about the technical differences with prior work (i.e. that of Panageas and Piliouras [PP]).

Response: We will be happy to expand a bit further on our technical differences between our paper and the precursor one by Panageas and Piliouras 2016 ([PP16]). What [PP16] show is that the APoA is effectively well-posed for all linear congestion games using a rather elaborate but hard to generalize argument. This argument critically relies on the exact definition of replicator dynamics as well as on the linearity of costs. Instead, our approach follows a different proof technique that allows us to generalize along both the game and the learning dynamics dimensions. We can break down our technical differences in three parts.

• Well-posedness of APoA: Our first technical contribution is that our analysis allows for APoA to be effectively well-defined and applied to all generic potential games for all q-replicator dynamics (Section 3). The related techniques have no analogue in the original paper and leverage recent advances in the theory of potential games (Swenson 2020). This is the convergence result of Theorem 3.1. Such approaches that target generic (versus all games) within some class of games are commonly used in game dynamics (see e.g. Theorem 3.3 in [1]) or the quasi-strict genericity assumption in [2-5].

  1. Bailey, James P., and Georgios Piliouras. "Multiplicative weights update in zero-sum games." Proceedings of the 2018 ACM Conference on Economics and Computation. 2018.

  2. Vlatakis-Gkaragkounis, Emmanouil-Vasileios, et al. "No-regret learning and mixed nash equilibria: They do not mix." Advances in Neural Information Processing Systems 33 (2020): 1380-1391.

  3. Johanne Cohen et al Learning with bandit feedback in potential games. In NIPS’17: Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017.

  4. Laraki, Rida, et al. Mathematical foundations of game theory. New York, NY, USA: Springer, 2019.

  5. Fudenberg, Drew, and Jean Tirole. Game theory. MIT press, 1991.

• Average APoA analysis: Regarding the dynamics dimension, our second technical contribution is that we generalize the analysis from replicator to a broad class of related dynamics. Our approach extends the invariant function technique, see Lemma 4.7, which enables the proof of Theorem 4.6. Despite the thematic similarity between this part and the related part in the [PP] paper, there is also a lot of new technical content on the exact nature of the separatrix and how it affects the dynamics. For instance, one such result is captured in Lemma B.3 (supplementary) which concerns the curvature of the separatrix. Such results inform our intuition on the reasons why our main results hold (for instance Theorem 4.6) and we believe that they can enable a lot of interesting follow-up work. We also believe that our proof technique is flexible enough to be applied on different classes of learning dynamics. Other similar papers that generalize findings from replicator like dynamics to other related dynamics are: from [1] to [2] and from [3] to [4].

  1. Piliouras, Georgios, and Jeff S. Shamma. "Optimization despite chaos: Convex relaxations to complex limit sets via Poincaré recurrence." Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2014

  2. Mertikopoulos, Panayotis, et al. "Cycles in adversarial regularized learning." Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms. Society for Industrial and Applied Mathematics, 2018.

  3. Palaiopanos, Gerasimos, et al. "Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos." Advances in Neural Information Processing Systems 30 (2017).

  4. Bielawski, Jakub, et al. "Follow-the-regularized-leader routes to chaos in routing games." International Conference on Machine Learning. PMLR, 2021.

• Experiments: Finally, our paper has an extensive experimental section (along with accompanying code) that as the Reviewer acknowledges raises some very intriguing directions for future work. No such section or software package was made available in [PP].

We hope that the above clarify the technical differences between the two papers. Thank you again for your support and helpful suggestions!