Computational tractability and social welfare (aka. efficiency) of equilibria are two fundamental but in general orthogonal considerations in algorithmic game theory. Nevertheless, we show that when (approximate) full efficiency can be guaranteed via a smoothness argument \`a la Roughgarden, Nash equilibria are approachable under a family of no-regret learning algorithms, thereby enabling fast and decentralized computation. We leverage this connection to obtain new convergence results in large games -- wherein the number of players $n \gg 1$ -- under the well-documented property of full efficiency via smoothness in the limit. Surprisingly, our framework unifies equilibrium computation in disparate classes of problems including games with vanishing strategic sensitivity and two-player zero-sum games, illuminating en route an immediate but overlooked equivalence between smoothness and a well-studied condition in the optimization literature known as the Minty property. Finally, we establish that a family of no-regret dynamics attains a welfare bound that improves over the smoothness framework while at the same time guaranteeing convergence to the set of coarse correlated equilibria. We show this by employing the clairvoyant mirror descent algortihm recently introduced by Piliouras et al.
Paper
Similar papers
Peer review
Summary
This paper considers a specific type of smooth game first introduced in [Roughgarden 2015]. The main result of this paper is that when the game has robust PoA lower bounded by 1-$\epsilon$ (defined by the concept of smoothness of the game) and all the players apply optimistic gradient descent algorithm (OGD), the best iterate over the learning process will achieve $(\sqrt{\epsilon}/\sqrt{\delta n}, \delta)$ weak Nash-equilibrium, meaning that there are $\delta$ fraction of the players having low NE gap. The authors also show that under certain condition of the game, CGD, a variant of OGD, performs better social welfare guarantees.
Strengths
- The paper considers a certain type of game with good rPoA guarantee and shows that classic OGD algorithm performs good results with provable guarantees. - The general idea of the proof is intuitive and clear to me. The analysis also looks correct to me in general.
Weaknesses
- One issue is the motivation of the study and the novelty of the proposed analysis. Specifically, it is less clear why the class of game with $rPoA\geq 1-\epsilon$ is an interesting class of games. It seems to me that this is more about a technical assumption that makes the proof work. More concretely, with respect to the first result showing the convergence to Nash, the analysis follows the recent line of works about last-iterate convergence and constant individual regret bound in general-sum games using OGD/OFTRL, which show that lower bounded sum-of-regret leads to stability of the dynamic, which furthre leads to low NE gap guarantees. The rPoA condition basically guarantees that the sum-of-regret is lower bounded according to the smoothness condition of the game. - Another related issue is the trackability of rPoA. As mentioned mentioned by the authors, while rPoA can be calculated within polynomial time if the game is explicitly represented, meaning that the game representation already takes exponential space with respect to the number of players, which may not be the case when the utility function for each player is define by certain concrete functions. Therefore, deciding whether rPoA is lower bounded or not is also computationally intractable when the number of players is large. - The description of Observation 3.3 does not look very clear. Specifically, the equivalence should define a certain choice of $(\lambda, \mu)$ in the definition of smooth game and I do not find a proof for this observation. - The notations used in this paper are not very clear. - In section 3, many notations are with superscript $n$, which would be better if they are replaced by $*^{(n)}$ in order to distinguish with the exponent notation. Specifically, in line 194, $rPoA\geq 1-\epsilon^n$ is very misleading. - In line 302, should $rPoA_G^{\epsilon}$ be replaced by $PoA_G^{\epsilon}$, since $rPoA$ is not defined with respect to NE. - In line 324, the guarantee should be $rPoA_G\cdot OPT$. Specifically, in line below line 926, the RHS should also include $OPT$.
Questions
- Can the authors explain more on the class of game with $rPoA\geq 1-\epsilon$? Is there a certain class of previously studied games or real applications that satisfy this condition? - The obtained results for good NE gap strategy is with respect to the best-iterate. I wonder whether the results may also extend to the average-iterate case, which may lead to less computational complexity to derive the output strategy?
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
2 fair
Contribution
2 fair
Limitations
See weakness and questions for details.
Summary
This paper studies the convergence properties of no-regret dynamics in $(\lambda,\mu)$-smooth games. More precisely the authors show that for any $(\lambda,\mu)$-smooth game at which the bound of $\frac{\lambda}{1+\mu}$ converges to $1$ as the number of agents grows, the resulting Online Gradient Descent dynamics converges in polynomial time to an $(\epsilon,\delta)$-weak Nash Equilibrium. In an $(\epsilon,\delta)$-weak NE, $(1-\delta)$-fraction of the agents cannot increase their payoff by more that $\epsilon$ by deviating to another mixed strategy. The latter implies that if $\frac{\lambda}{1-\mu} = 1$ then the resulting OGD dynamics converges to an $\epsilon$-MNE in $O(1/\epsilon^2)$ steps. The latter reveals an interesting phase transition on the computational complexity of equilibrium computation of general multi-player games with PoA = 1 and the smaller class of $(\lambda,\mu)$-smooth games with $\frac{\lambda}{1-\mu} = 1$ (this naturally implies PoA = 1). Motivated by the work of Roughgarden et al. establishing that no-regret dynamics in $(\lambda,\mu)$-smooth games guarantees $\frac{\lambda}{1-\mu}$ fraction of the optimal payoff, the authors show that the latter result can be improved for a specific class of $(\lambda,\mu)$-smooth satisfying an additional condition (Condition 4). More precisely, the authors show that if all agents adopt Clairvoyant Gradient Descent then the time-average joint probability distribution converges to a CCE while there exists an iteration at which the respective mixed strategy profile attains strictly more than $\frac{\lambda}{1+\mu}$ fraction of the optimal payoff.
Strengths
I believe that the convergence results to an $(\epsilon,\delta)$-weak NE in $(\lambda,\mu)$-smooth games is a solid contribution. I also find surprising the phase transition on the computational complexity of equilibrium computation of games with PoA = 1 (that are PPAD hard) and the respective complexity of $(\lambda,\mu)$-smooth games with $\frac{\lambda}{1+\mu} = 1$. Also I find the second presented result, improving upon the $\frac{\lambda}{1+\mu}$ fraction of the optimal social welfare, interesting. I overall believe that this is a good paper aligned with the interest of the online learning/game theory audience of NeuRIPS.
Weaknesses
In my opinion the only weakness of the paper concerns the comparison of the second result with the respective previous result of Roughgarden et al. As far as I understand, Roughgarden et al. show that the time-average payoff attained by any no-regret dynamics (in an $(\lambda,\mu)$-smooth game) is at least $\frac{\lambda}{1+ \mu}$ fraction of the optimal social welfare. However Theorem~4.2 guarantees social welfare strictly more than $\frac{\lambda}{1+ \mu}$ fraction the optimal one only at a specific iteration. That being said I still consider the result interesting. However in case I am not missing something, an additionally discussion is needed so as to fairly compare the two results.
Questions
Your second results refers to the $best-iterate$ while the result of Roughgarden et al. refets to the time-average payoff. Could you elaborate more on how the two results compare?
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.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
N/A
Summary
This paper discusses the convergence and welfare of learning algorithms in smooth games. The authors show that when approximate full efficiency can be guaranteed via a smoothness argument, Nash equilibria are approachable under a family of no-regret learning algorithms, thereby guaranteeing fast and decentralized computation. They also leverage this connection to obtain new convergence results in large games, as well as extensions to Bayesian mechanisms. The paper unifies recent works in two-player zero-sum games, illuminating an equivalence between smoothness and a well-studied condition in the optimization literature known as the Minty property. Finally, the authors establish that a family of no-regret learning dynamics outperforms the welfare predicted by the smoothness framework under a generic condition, while at the same time guaranteeing convergence to the set of coarse correlated equilibria.
Strengths
The strength of this paper lies in its contribution to the understanding of the convergence and welfare of learning algorithms in smooth games. The authors provide new insights into the relationship between efficiency and the behavior of a family of no-regret learning algorithms, and they also unify recent works in two-player zero-sum games.
Weaknesses
The paper does have quite a few notations, but it's understandable. I've got a few questions, which might also point out some areas in the paper that could be improved. I've put these questions and potential weaknesses together in the question section for easy reference. But, I think this is an overall well-written paper.
Questions
1. Is there any counterexample that if rPOG does not converge to 1, then the decentralized algorithm (OGD) provided in this paper does not converge to Nash Equilibrium? or If Condition 4.1 does not hold, then still thm 4.2.1 hold? 2. What is the indication of Condition 4.1? Are there some examples that condition 4.1 holds?
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.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
The authors adequately addressed the limitation and potential negative societal impact on their work.
Summary
This work studies the connections between the efficiency of Nash equilibria, as measured for example by social welfare, and tractability of computing these equilibria through efficient no regret learning algorithms. The authors provide the key insight that the smoothness framework introduced by Roughgarden, that is typically used to analyze price of anarchy, can be also leveraged to analyze the efficient convergence of optimistic gradient descent (OGD) to Nash equilibria. They use this insight to prove that if as the number of players increases, the robust price of anarchy goes to 1 without increasing the games Lipschitz constant too quickly, then OGD converges to weak Nash equilibria. This finding unifies previous findings on zero sum games and is connected to existing work on the Minty property. Even beyond OGD, the authors study the connections between convergence to CCE and social welfare for clairvoyant GD (CGD). They show for the first time that convergence to CCE and outperforming restricted price of anarchy can be combined through an efficient algorithm.
Strengths
Overall I believe that the paper makes a very strong and original contribution. To the best of my knowledge, connections between efficiency of equilibria and tractability have not received a lot of attention. This is evidenced by the fact that relatively simple observations like 3.3 are commonly overlooked. In addition to the novelty of this works topic, the technical results are very extensive and non trivial.
Weaknesses
The paragraph from 179 to 190 could benefit from expansion. In the common setting where we analyze a fixed game, one can always normalize the utilities to get a Lipschitz constant of 1. I have a sense that such a normalization would affect the value of $\epsilon$ in the general case thus we cannot always get $\gamma$ to be small for free. I am not sure though. Adding more intuition would help.
Questions
See above for a question/suggestion.
Rating
8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
4 excellent
Limitations
No limitations applicable.
Summary
This work studies the connection between efficiency and computation tractability of equilibrium in smooth games. Its major finding is that optimistic mirror descent reaches a weak Nash equilibrium for large games satisfying the property that asymptotically smoothness can guarantee efficiency of equilibria. This result establishes the connection between smoothness arguments and the approachability of no-regret learning algorithms to Nash equilibria.
Strengths
This work draws new insights on an interesting angle connecting two fundamental subjects in algorithmic game theory. Robust price of anarchy characterizes the fraction of optimal social welfare that smoothness argument can guarantee for every Nash equilibria. It turns out from this paper that robust PoA $\to 1$ also ensures the convergence of no-regret dynamics, which is non-trivial. The results also recover existing theories of the covergence of OMD in two-player zero-sum games.
Weaknesses
The rates (e.g. $n^{-\alpha/3}$) are dependent on the number of players instead of the number of iterations, which is different from what we commonly see/expect. I am not sure how useful the rates are, for example, in large games, still a $n^{2/3}$ number of players may yield bad responses.
Questions
What are some natural examples where the conditions in Thm 3.1 are satisfied and non-trivial rates are obtained? Is there direct generalization to mean-field games?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
The authors adequately addressed the limitations.
Thank you for your response. I have read the other reviews and I am confident for my positive evaluation of the paper.
Thank you. After reading the rebuttal and other reviews I decide to keep my positive evaluation.
Some questions
Dear authors, Thank you for your timely responses. I have now gone through your original submission, the reviewers' input, and your rebuttals. As we are now in the author-committee discussion phase, I would like to jumpstart an exchange on the following points: - Regarding the point raised by Reviewer Q8mF that "$n^{2/3}$ players could be playing bad responses". I read your response regarding Corollary A.3 (which is only in the supplement if I'm not mistaken), but this is contingent on a strong condition for the game's rPoA. Could you comment when this condition is verified in practice? Do you have an example? - Regarding the guarantee of Theorems A.2 and A.18 (the precise version of Theorems 3.1 and 4.2 in the main), and related to a point raised by Reviewer Qpnv. As far as I understand, the guarantee is that if OGD/CGD is run for $T$ iterations (with $T$ specified in the supplement), there is some time $t^\ast$ such that $x(t^\ast)$ is a weak approximate equilibrium. In order to stop the algorithm at $t^\ast$ and harvest the solution, you ostensibly assume that the full structure of the game is known, correct? If not, what is your stopping criterion for the algorithm? - Related to the above: it is not clear if you are taking a centralized, offline viewpoint (whereby OGD/CGD is run by a central optimization device) or a distributed, online viewpoint (whereby OGD/CGD is run by the players, each with local gradient/payoff information). If it is the former, could you comment on the memory/storage requirements as $n\to\infty$? If it is the latter, could you comment on the communication requirements in order to harvest the algorithm's "best iterate" at $t^\ast$? [In other words: how would the players know that they are at a weak approximate equilibrium in order to stop the algorithm?] - Is there any difference between CGD and the classical proximal point algorithm of Rockafellar ("*Monotone operators and the proximal point algorithm*", SIOPT, 1976)? Regards, The AC
Thank you for the Questions
We are grateful to the AC for the engagement. - A simple class of examples revolves around games with bounded influence. In particular, as noted by Kearns and Mansour [51], there are certain games (such as voting games under the plurality rule) in which the maximum influence of a player on its utility is bounded by $1/n$; Corollary 3.4 then implies that only a constant number of players (independent on $n$) could have a large best response gap. Beyond such games, the main result of [37] shows that rPoA converges to $1$ with a rate of $1/\sqrt{n}$ in a certain regime, but this rate can be improved depending on the parameterization of the underlying combinatorial auction (Theorem 18 of [37] exactly quantifies this), in which case Corollary A.3 directly kicks in. - We do not require that the full structure of the game is known. First, we point out that the guarantee of Theorem A.2 readily extends (with high probability) by taking a random joint strategy, not necessarily the best one (Eq. (9) in the proof of Theorem A.2 suffices to see this). Further, if we want a deterministic guarantee each player can compute locally its best response gap (which can be trivially done with gradient feedback in our setting without any further information), and then terminate the algorithm when the desired accuracy has been reached (without any other information about the game). Regarding Theorem 4.2 (and Theorem A.18), it is direct to see from our proof that Item 2 can be made to hold for a $1-\delta$ fraction of the iterates, not just a single one, where the improvement over rPoA now is an additive factor of $\delta \cdot \epsilon_0^2 C(\mathcal{G})$. We will make sure to highlight those refinements in the revised version. - We are taking a decentralized online viewpoint wherein each player updates its strategy using the gradient of its own utility, although we believe that our results are also interesting from a purely centralized perspective. In particular, from a decentralized standpoint, as we discussed above if we are satisfied with a probabilistic guarantee then taking a random joint strategy in the trajectory suffices without inducing any communication overhead. Alternatively, we would need a minimal amount of communication to make sure to extract the best joint strategy. From a centralized perspective, the running time and the memory of the underlying algorithm of course scale with the number of players $n$, but the dependence is polynomial in $n$, which is the best we can hope for. - The CGD algorithm can be indeed seen as an approximate version of the classical proximal point algorithm, as discussed in detail in the references [35, 77, 17]. More precisely, CGD revolves around a contraction mapping in order to approximate the proximal point algorithm. As shown by Piliouras et al. [77], CGD only requires gradient feedback of the utilities, and can be implemented as an uncoupled no-regret learning algorithm.
Thanks for your input, but the core of my questions remains: > As noted by Kearns and Mansour [51], there are certain games (such as voting games under the plurality rule) in which the maximum influence of a player on its utility is bounded by $1/n$. In this case (i.e., for the type of games considered by Kearns and Mansour), since $L^n$ grows as $\sqrt{n}$ in general, we would have $\gamma^n = \sqrt{n}$, i.e., $\alpha = 1/2$, so as many as $O(n^{5/6})$ players might be playing a "bad response" (I'm getting the $5/6$ exponent as $1-\alpha/3$ from L178, but the description in the paragraph preceding Corollary 3.4 left me in doubt). Am I missing something here? > The main result of [37] shows that rPoA converges to $1$ with a rate of $1/\sqrt{n}$ in a certain regime, but this rate can be improved depending on the parameterization of the underlying combinatorial auction (Theorem 18 of [37] exactly quantifies this), in which case Corollary A.3 directly kicks in. Just to be clear, since $L^n$ may grow as $\sqrt{n}$, if the rPoA has a $1/\sqrt{n}$ rate of convergence, Corollary A.3 cannot be directly invoked, right? In the combinatorial auction setup of [37], Corollary A.3 can only be invoked under the specific parameter schedule of Theorem 18, is this correct? > First, we point out that the guarantee of Theorem A.2 readily extends (with high probability) by taking a random joint strategy. How would random stopping be applied to a multi-player context? If you have $n$ players, each drawing a stopping time from $1,\dots,T$, the probability that they pick the same $t^\ast$ (which is what's needed for the random stopping trick to work in your case) is exponentially small in $n$. This is related to my question regarding the centralized / decentralized viewpoint: are agents taking the decisions themselves or is there a central coordinator? > If we want a deterministic guarantee each player can compute locally its best response gap (which can be trivially done with gradient feedback in our setting without any further information). If I'm not mistaken, Eq. (32) provides a guarantee for the sum of the players' best response gaps, and there is no guarantee that all players will reach, at the same time, a state where their individual best response gap is small, right? If so, how would a player know when to stop? I don't see a way of leveraging the PoA bound without summing over all players' regrets / gaps - am I wrong in this? In fact, if I'm not further mistaken, when the algorithm stops, there will still be a fraction of players that are not playing approximate best responses, so their stopping criterion would not have been activated. In this case, how would the players know "who is who" (i.e., who stops and who doesn't)? I could potentially see how this could be circumvented if players knew the game (and/or they were able to observe each other's mixed strategies, an assumption which is stronger than requiring access to a deterministic gradient oracle), but not in the current setting. Am I missing something? > Alternatively, we would need a minimal amount of communication to make sure to extract the best joint strategy. What does "minimal" mean here, exactly? If each player needs to communicate with every other player, we are talking about $O(n^2)$ bits exchanged, right? And, if players are allowed to exchange information about their mixed strategies, aren't we talking about an information model which is more exacting than requiring access to a deterministic gradient oracle? > The CGD algorithm can be indeed seen as an approximate version of the classical proximal point algorithm. Understood. I misread $w^t$ in (21) as $x^t$, thanks for clarifying. In retrospect, it would have been much clearer if this had been included in the main, as the textual description can lead to misunderstandings. That being said, I still have a question: how would players run the fixed-point iteration (21) in a decentralized way? If each player has their own stopping criterion - say $\epsilon/n$ - then one player might stop updating prematurely, so it is not clear if the standard fixed-point analysis applies (at least not without knowledge of the game or knowledge of each other's strategies). Could you comment on that as well? Best, The AC
Thank you for the follow-up questions. *“In this case (i.e., for the type of games considered by Kearns and Mansour), since $L^n$ grows as $\sqrt{n}$ in general...”* $L^n$ does not have to grow as $\sqrt{n}$ in such games. In particular, suppose that each player $i$ selects $x_i \in [0, 1]$, so that $u_i^j(x_1, \dots, x_n) = u_i^j( \frac{\sum_{i'=1, i' \neq i }^n x_{i'} }{n})$ where $u_i^j : \mathbb{R} \to \mathbb{R}$ is a $1$-Lipschitz utility function corresponding to action $j = 0, 1$. Let us denote by $S = \frac{1}{n} \sum_{i=1}^n x_{i}$. For two joint strategy profiles $x, x’$, we have $\sum_{i=1}^n \sum_{j =0}^1 | u_i^j(S) - u_i^j(S') |^2 \leq 2 \sum_{i=1}^n | S - S' |^2 \leq 2 \sum_{i=1}^n | x_i - x_i’ |^2$. So, $L^n$ is independent on $n$, which in turn implies that only a constant number of agents can have a large best response gap (this follows by taking $\delta = \Theta(1/n)$ in Eq. (2)), as we claimed. This same of course applies beyond taking the average as the summarization function. We apologize for not explaining this argument in more detail in our earlier response. Corollary A.3 cannot be directly invoked, right? In the combinatorial auction setup of [37], Corollary A.3 can only be invoked under the specific parameter schedule of Theorem 18, is this correct? Yes, this is correct. *“How would random stopping be applied to a multi-player context? If you have $n$ players, each drawing a stopping time from $1, \dots, T$, the probability that they pick the same $t^\star$ (which is what's needed for the random stopping trick to work in your case) is exponentially small in $n$.”* For this we are assuming that players have access to a common source of randomness. Alternatively, if there is no access to a common source of randomness, a central coordinator can choose a random index $t^\star$, and transmit $\log (\lceil 1/T \rceil )$ bits to each player. *“In fact, if I'm not further mistaken, when the algorithm stops, there will still be a fraction of players that are not playing approximate best responses, so their stopping criterion would not have been activated. In this case, how would the players know "who is who" (i.e., who stops and who doesn't)?”* Let us fix some parameters $\epsilon, \delta$, with the goal of terminating at an $(\epsilon, \delta)$-weak Nash equilibrium. At each iteration every player determines with its own local information whether its own best response gap is at most $\epsilon$, and transmits that information—a single bit of information—to a central coordinator. The coordinator then sums those bits, and if their fraction is above $1-\delta$ the coordinator signals to the players that they can terminate. No further information about the game is needed to implement this. *“I could potentially see how this could be circumvented if players knew the game (and/or they were able to observe each other's mixed strategies, an assumption which is stronger than requiring access to a deterministic gradient oracle), but not in the current setting. Am I missing something?”* As we explained above we do not need any knowledge of the game beyond a deterministic gradient oracle. *“What does "minimal" mean here, exactly? If each player needs to communicate with every other player, we are talking about $O(n^2)$ bits exchanged, right? And, if players are allowed to exchange information about their mixed strategies, aren't we talking about an information model which is more exacting than requiring access to a deterministic gradient oracle?”* Players do not have to exchange information about their mixed strategies, and they only need to observe gradient feedback. In particular, as we explained above, players only have to send a single bit in every iteration to a central coordinator, which amounts to $n$ bits of communication, not $O(n^2)$. We used the word “minimal” in our previous response because $1$ bits of information is negligible compared to the bit complexity of the gradient. *"That being said, I still have a question: how would players run the fixed-point iteration (21) in a decentralized way? If each player has their own stopping criterion - say $\epsilon/n$ - then one player might stop updating prematurely, so it is not clear if the standard fixed-point analysis applies (at least not without knowledge of the game or knowledge of each other's strategies). Could you comment on that as well?"* The stopping criterion could be that all players apply the contraction for a fixed number of iterations, which is the same for each player. As long as there is an agreed bound on that number of iterations one can use the standard fixed-point analysis.
Thanks for the clarification regarding the Lipschitz constant in voting games. For the rest, in all your replies, a central coordinator is required to take an active part in the decision-making - e.g., to process the players' best response gaps and then send a signal to terminate the process (my comments concerned the case where no such entity is assumed). From a game-theoretic perspective, this hybrid model raises itself several questions (for example, truthfulness in reporting: players may have an incentive to misreport their gap or if, by so doing, they believe they can keep the game going and steer it to a better outcome), but I do not want to belabor the point. Thank you for your replies. Regards, The AC
Truthfulness is an interesting consideration. While the proposed distributed protocol is indeed by no means truthful, lack of truthfulness is a general issue encountered under regularized learning algorithms. Although there have been some recent papers on exploitability of learning dynamics, most of the work does not address exploitability. So, while we are not addressing exploitability, neither is the bulk of this literature. We can include a discussion on this point if the AC considers it important for our setting. We thank the AC again for their time.
We thank again the reviewer for their time and the helpful feedback. Given that the discussion period soon comes at an end, we wanted to see if our response adequately addressed the concerns, and if the reviewer has any further questions for us.
Thanks for the clarification
Thank you for the clarification!
Decision
Accept (poster)