Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proves pointwise convergence of q-replicator dynamics to NE and corresponding bounds on average price of anarchy, generalizing previous works.
strength_and_weaknesses: Strengths:

The results are solid. The motivation and proof ideas are well explained. 

Weaknesses:

I'm not familiar with this specific topic studied in this paper, however I found it's a follow-up of (and resembles) the EC paper "Average Case Performance of Replicator Dynamics in Potential Games via Computing Regions of Attraction" (PP16) which this paper doesn't seem to give enough credit to. The studies of convergence of RD to NE, region of attraction and average price of anarchy already appeared in PP16, yet this paper doesn't have enough discussion on PP16 at all. PP16 were only mentioned and cited a few places in this paper just like other much less relevant papers, which might cause misleading judgement on the novelty of the results.

The significance of results seems questionable. Theorem 3.2 is a generalization of PP16 to QRD whose proof idea seems similar. The applications Theorems 4.4/4.6 are limited to the 2X2 case.

Some terms are not defined rigorously. For example, $x_k^*$ is a point in simplex in Definition 2.1, what do you mean by a best response is contained in a point?
clarity,_quality,_novelty_and_reproducibility: This paper is well-written in general. However I believe there should be more discussion on comparison with PP16.
summary_of_the_review: I tend to reject due to lack of comparison with PP16 and seemingly incremental results.

After discussion with other reviewers, I'm satisfied with added discussion with PP16 and will raise the score accordingly.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper motivates the study of the relative sizes of regions of attraction of different equilibria, then tackles the case of symmetric, 2x2 coordination games. For this class of games, some partial/preliminary results are given.
strength_and_weaknesses: I found the paper to be well written and easy to read. It is certainly convincing in terms of motivation, the problem is interesting and challenging.

My main concern is that the paper asks interesting questions, but makes little progress in terms of answering them. The paper sets out to compare the average performance of q-replicator dynamics for the class of symmetric 2x2 coordination games. Even in this 2-dimensional case, the results presented in the paper are very partial and feel preliminary in nature:
- Theorem 4.4 compares average performance between q=0 and q=1, when $\alpha \geq 0.5$. Nothing is said about other values of $q$.
- An invariant function is given in Lemma 4.5, which gives empirical evidence (through plots) that the regions of attraction are monotonic in q, but no formal proof is given. This left me with the impression that there is no treatment of the general case that was promised in the introduction (i.e. general q) except a conjecture at this point.
- It is also unclear if/how this geometric approach would generalize to other game classes, especially in higher dimensions. It would be great if the authors could argue why this approach can generalize and can be useful beyond the two dimensional case.

clarity,_quality,_novelty_and_reproducibility: The paper is clearly written.
The problem is of interest to the community.

Additional comments:
- Theorem 4.4, as stated, does not say anything about the case $\alpha < 0.5$, but the preceding paragraph seems to suggest that when $\alpha \geq 0.5$, RD is better than GD. Can you clarify which is correct, the theorem or the paragraph?
- Please avoid overloading notation. $\alpha$ is used both in equation (4) and later to denote an equilibrium of the game.
- On page 8, the factorization of $\Psi_q(x, y)$ should be explained better.
- I find the abstract to be an inaccurate account of what is actually done in the paper. It should be mentioned at least that the main results concern 2x2 symmetric coordination games.
- The formatting of citations should be improved. In its current form, it hurts readability.
- Top of page 9: "monotonicity of the stable manifolds": did you mean of the regions of attraction?
summary_of_the_review: The problem is relevant and the empirical/visual approach is promising. This can make a fine contribution if the formal results are expanded to have more formal proofs or a more complete treatment of the 2x2 symmetric games case.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this paper, the authors consider the problem of finding dynamics that not only converge to Nash Equilibria but also converge to "good" equilibria according to some objective function, e.g., the social-welfare. The main results are the following:
  1. The social welfare of the 0-replicator dynamics is higher than the social welfare of the 1-replicator dynamics.
  2. For the special case of symmetric two player game with two strategies (2-by-2 games) the price-of-anarchy, i.e., the ratio of the optimal social welfate divided with the social welfare of the equilibrium given by the dynamics, is bounded by 2.
strength_and_weaknesses: Strengths
======================
  - The problem that the authors consider is very important and difficult and even the results for the special case of 2-by-2 games are very important.

  - The paper is well-written and the algorithms, techniques, and results are well-explained.

Weaknesses - Comments
========================

  1. 2-by-2 games is a rather restricted case, it would be nice if the authors can explain why their techniques cannot be extended to more general games. Do we have lower bounds for more general games.

Post-Rebuttal
========================
I thank the authors for the response! After discussion with other reviewers, I agree in the following weaknesses of the paper:
a. The contribution of the paper should be expressed more clearly. In particular, it should be clear from the abstract that this is not the first work that explores the average case performance of no-regret algorithms in games. Also, I believe the authors should highlight more, even in the abstract, that the class of games that they consider captures games for which the worst-case PoA is unbounded.
b. The number of people that would be interested in this result is smaller compared to other conferences, e.g., EC, which are a better fit for this paper.
I still recommend acceptance but I would reduce my score to 7 instead of 8 if there was such an option.
clarity,_quality,_novelty_and_reproducibility: Very well written paper.
summary_of_the_review:   Based on my comments above I recommend acceptance.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper considers the problem of quantifying the quality of equilibria a class of dynamics converge to in games. Their contributions are 
1. They first show that for a general class of games Q replicator dynamics (which cover GD and some other natural dynamics) converge point wise to Nash Equilibria.
2. They further focus on the quality of the equilibria by studying theoretically and experimentally average metrics (such as average price of anarchy) of the equilibria the dynamics converge to. This latter result is primarily established theoretically for 2x2 symmetric games.

Overall the reviewers had a divided opinion about the paper. While the reviewers unanimously agreed on the technical contribution and the main result which the reviewers agreed is a hard problem to solve and found the solution valuable. On the other hand the reviewers had concerns that the results were somewhat limited due to them being for the specific 2x2 case and the main theorem in that setting also particularly was focussed on specific values. Reviewers also suggested that the initial writing almost seemingly made the reader believe that the question itself was being introduced by the paper. 

Overall there is one clear contribution by the paper, it was not fully clear to the reviewers what the contribution to the ICLR community at large might be. The paper is truly borderline taking everything into consideration according to the reviewers and due to the slightly limited scope of the eventual results of the paper, I am making my recommendation. I would like to re-stress that the reviewers appreciated the results' technicality.
justification_for_why_not_higher_score: As I have detailed in my review, the slightly limited scope of the paper's result were the reason for the score.
Decision: Reject