Learning and Steering Game Dynamics Towards Desirable Outcomes

We are grateful to the reviewer for their insightful feedback. We address the reviewer's concerns below.

1. Some key concepts in the text lack clear definitions or explanations, which may confuse readers; further clarification is recommended. For example, the concept of "side-information constraints"(First shown at Page 2 Lines 56) is central to the paper, yet it lacks a clear definition and explanation. It’s not evident what constitutes side information and how it contributes to enhancing the accuracy of the learned controlled dynamics. The term "Strategic Nature" (Page 5, Line 230) is mentioned to justify the validity of the second side-information constraint. However, what actually plays a crucial role in supporting this constraint is the concept of Positive Correlation (PC). It's unclear why the authors introduced the notion of "Strategic Nature" in this context.

We will address your concern by providing a clearer definition of "side information" in the relevant sections of the revised manuscript. Side information refers to additional knowledge about the learning dynamics of agents or assumptions regarding their behavior beyond the trajectory data. Specifically, in our setting, it is any knowledge that can be expressed as polynomial non-negativity or equality constraints over a semi-algebraic set.

"Positive correlation" refers to the positive correlation between the directions of motion and a quantity known in the literature as the pseudogradient of the players' payoff. This relationship expresses the rationality of the players, as it encodes that players prefer directions that do not decrease their expected payoff. This is clearly an information about the strategic nature of the players.

2. Lack of theoretical justification. The paper does not provide evidence that a polynomial regressor is sufficient to accurately capture system dynamics, especially given the limited number of samples (K=5). The two side-information constraints are proposed to aid in learning an accurate model of the controlled system dynamics with limited data. However, there is no theoretical justification provided on how these constraints contribute to this goal. This is particularly concerning given that the second step involves MPC, which requires a high-fidelity model. Additionally, the use of SOS optimization introduces further uncertainty in achieving a precise model.

The SIAR solution is a regressor, and therefore its quality depends on the quality and number of samples. The benefit of SIAR is that it incorporates side-information, and thus reducing the size of the problem's feasible set. To the best of our knowledge, there are no theoretical results that quantify the improvements such a reduction provides to the regressor. A relevant question is whether, a polynomial regressor, as returned by SIAR, can be inherently "bad". In that regard, the results of [R1] can readily be extended in the presence of control, and therefore the existence of a "good" polynomial regressor (a feasible solution) that satisfies the given side-information constraints with SOS certificates is guaranteed to exist for some level of the SOS hierarchy. We will add the proof in the appendix of the revised manuscript.

[R1] Sakos, Iosif, Antonios Varvitsiotis, and Georgios Piliouras. "Data-Scarce Identification of Game Dynamics via Sum-of-Squares Optimization" arXiv preprint arXiv:2307.06640 (2023).

We are grateful to the reviewer for their insightful feedback. We address the reviewer's concerns below.

1. Can the authors clarify on the technical novelties of this paper? For example, one contribution of this paper is its superiority in data-scarce settings. However using PINN enhances performance in this setting is straightforward to me. Is there some technical difficulty I am missing here?

We are not sure what the reviewer means by saying that ``using PINN enhances performance in this setting is straightforward'', though. Could the reviewer please clarify this point?

Our contributions lie in demonstrating that SIARc can perform well in scenarios where PINNs and SINDYc do not do well. In particular, our examples show settings where PINN is not able to converge to the target equilibrium, while SIARc consistently achieves this. Additionally, we conducted further experiments, detailed in the Appendix A, where SIARc outperforms PINN across multiple metrics, further highlighting its robustness in extreme data-scarce settings.

2. For the central planner, steering is not free. Larger $\omega$ is clearly more costly in real-world application. Should we compare the algorithms under the fixed budget?

For clarity, in this work we assume that the budget is fixed per time. The accumulated budget is not constrained. This is by design in order to include games that target Nash equilibrium is unstable, e.g., any non-zero-sum game with a unique interior Nash equilibrium. As a well-known example, we refer the reviewer to [R3]. We are going to add such an example to further motivate this idea.

3. This paper places no constraint on how we choose $\omega$ in the first phase. On the one hand, we cannot intervene a real-world game arbitrarily at our wishes, so this seems to be a strong constraint. On the other hand, if we allow online learning, i.e. adaptively picking so that the data is more informative, the sample complexity should be even lower. Is online learning a more natural setting?

In our framework, incentives are conceptualized as control inputs designed by the MPC that affect the payoff matrix. As the payoff matrix, by definition, encodes all the information about the player's incentives, altering the payoffs is the natural method for influencing agent behavior. Which payoffs can be affected is a setting-specific question: for example, in our RPS game we only allow the controller to add incentives to certain outcomes, and these restrictions hold for all phases of our framework (training, verification, and control).

In all phases of our framework, we also impose lower and upper bounds on the control input $\omega$, effectively enforcing a fixed budget per time step. Additionally, for the training phase, we scale the control input and explain the rationale behind this decision (see Section 5.1, line 355). Specifically, $\omega$ is sampled from a normal distribution with a mean of zero, constrained within the predefined upper and lower limits. This ensures that the aggregated control cost remains low during the system identification phase.

Randomization of the control inputs in the training phase is an easy way to get different control inputs for learning how the dynamics depends on the control, and we show empirically that it suffices for learning in our examples. We do not think the method of choosing control inputs in this phase matters much but agree with the reviewer that there might be more natural ways of selecting control inputs rather than randomly generating them, and that could be the subject of future work.

We do not see how an online learning method would work better though. Could the reviewer clarify the intuition behind this?

[R3] Robert Kleinberg, Katrina Ligett, Georgios Piliouras and Éva Tardos, "Beyond the Nash Equilibrium Barrier," In 2010 Innovations in Computer Science (ICS), pp. 125-140, 2010.

We are grateful to the reviewer for their insightful feedback. We address the reviewer's concerns below.

1. The submission doesn't do a very good job communicating how the reader ought to be interpreting these incentives.

In our framework, incentives are conceptualized as control inputs designed by MPC that affect the payoff matrix. As the payoff matrix, by definition, encodes all the information about the player's incentives, altering the payoffs is the natural method for influencing agent behavior. These incentives can be thought of, for example, as monetary rewards given that certain outcomes occur.

Which payoffs can be affected is a setting-specific question and we experimented this idea in our RPS game where we only allow the controller to add incentives to certain outcomes.

We will make the necessary modifications to ensure these clarifications are appropriately reflected in the relevant sections of the paper.

2. The submissions touts the "diverse range of games" on which it performs experiments. In fact, it performs experiments on 2 2x2 matrix games and 1 3x3 matrix game. I would hesitate to call this diverse.

Our intention was to showcase that our method is capable of handling a variety of game types, each with distinct challenges and undesired behaviors. For example, in zero-sum games like Matching Pennies, our method successfully addresses and manages cyclic behaviors, while in Rock-Paper-Scissors, it handles chaotic dynamics effectively. In coordination games, such as Stag Hunt, our approach overcomes the issue of converging to a suboptimal equilibrium, successfully steering the system toward a socially optimal outcome.

Moreover, we conducted additional simulations to demonstrate the performance of the proposed SIAR-MPC method under varying payoff matrices. Specifically, for the Stag Hunt Game, we generated 50 random payoff matrices while ensuring that the game maintained its cooperative nature with a socially optimal equilibrium. We evaluated the performance of SIAR-MPC across 50 systems and compared it with other methods based on our performance metrics, as detailed in Appendix A of the manuscript.

The results given in the above table clearly demonstrates that SIAR-MPC consistently achieves lower error values and control cost compared to the other methods.

3. The submission notes the "larger dimensionality" of rock-paper-scissors. This strikes me as somewhat concerning. If the dimensionality of rock-paper-scissors is already noteworthy in the context of the method, is there much hope of applying it to more interesting settings?

We agree that rock-paper-scissors should not be called a game with "larger dimensionality", and does not showcase our method's scalability. The point of restricting the controllers to be nonzero only on a subset of the outcomes was to demonstrate steerability even with incomplete controls.

4. I think the first paragraph of section 5.2 could be clearer. In the first part of the paragraph, the submission explains that replicator dynamics and learning algorithms with non-vanishing regret possess undesirable behavior. Thereafter, it states "In that regard, ... we demonstrate the performance SIAR-MPC in steering [learning dynamics of non-vanishing regret]." If I am reading between the lines correctly, the submission is meaning to communicate something positive---that it successfully steers learning dynamics with undesirable properties. But the writing doesn't effectively get that point across, in part because there is no previously mentioned "regard" that makes the sentence read correctly.

You are reading our intended meaning correctly, and we will make the paragraph clearer in the camera-ready version of the manuscript.

5. How should the reader be interpreting these incentives in the context of the games studied?

The incentives in our work should be interpreted as mechanisms like monetary rewards or penalties that are assigned to players with the purpose of influencing their behavior within the game. For example, incentives might take the form of bonuses to encourage cooperative behavior or fines to discourage actions that result in socially suboptimal outcomes. Please see the answer to the Comment 1 above as well.

We thank the reviewer for their feedback. Please see our responses below.

1. The font in the plots could be larger, it is relatively hard to read.

We will enlarge the font in the revised manuscript.

2. The introduction of RFI could be more detailed in section 4.1.

We will provide more details for the RFI in the camera-ready version of the manuscript.

3. The effectiveness of the algorithm in data-scarce setting could be emphasized more in the experiments, it is interesting to see how the performance is affected when the availability of the data varies.

It is true that this is an interesting question. In our work, we demonstrate that our method is viable for learning and controlling the system in a data-scarce setting even when other methods fail. Exploring results under varying data conditions could be an interesting future work.

4. What if there is error in the dynamics modelling step, what will happen in the MPC phase? Can MPC accommodate the error?

Even though MPC is based on a model of the dynamics that we learn during the system-identification step, it does not allow error in the model to propagate unchecked over time as it continually takes in state measurements at each timestep and optimizes for the next few control steps over a relatively small (moving) prediction horizon.

As the predicted trajectory within this small prediction horizon and the optimal control inputs computed by MPC depend on the model, how close the learned model is to the true dynamics does affect the MPC phase, but in a bounded way.

We thank the reviewer for their feedback.

While we acknowledge that this work builds on prior research that focuses on system identification for game dynamics, our contributions go beyond this foundation. Previous work primarily focuses on identifying system dynamics without addressing the unique challenges of game dynamics, which often hinder desirable outcomes (as defined in our paper). Our work tackles a fundamentally different problem: steering such dynamics toward desirable outcomes, particularly in data-scarce settings where the underlying dynamics are unknown. While the control method we use is well-established, our novelty lies in its adaptation to incentive-driven game dynamics, offering a fresh perspective and actionable insights for such scenarios.

For the question regarding the theoretical justification:

The SIAR solution is a regressor, and therefore its quality depends on the quality and number of samples. The benefit of SIAR is that it incorporates side-information, and thus reducing the size of the problem's feasible set. To the best of our knowledge, there are no theoretical results that quantify the improvements such a reduction provides to the regressor. A relevant question is whether, a polynomial regressor, as returned by SIAR, can be inherently "bad". In that regard, the results of [R1] can readily be extended in the presence of control, and therefore the existence of a "good" polynomial regressor (a feasible solution) that satisfies the given side-information constraints with SOS certificates is guaranteed to exist for some level of the SOS hierarchy. We will add the proof in the appendix of the revised manuscript.

[R1] Sakos, Iosif, Antonios Varvitsiotis, and Georgios Piliouras. "Data-Scarce Identification of Game Dynamics via Sum-of-Squares Optimization" arXiv preprint arXiv:2307.06640 (2023).