Learning and Steering Game Dynamics Towards Desirable Outcomes

## Abstract

Abstract The dynamic behavior of agents in games, which captures how their strategies evolve over time based on past interactions, can lead to a spectrum of undesirable behaviors, ranging from non-convergence to Nash equilibria to the emergence of limit cycles and chaos. To mitigate the effects of selfish behavior,
central planners can use dynamic payments to guide strategic multi-agent systems toward stability and socially optimal outcomes.
However, the effectiveness of such interventions critically relies on accurately predicting agents’ responses to incentives and dynamically adjusting payments so that the system is guided towards the desired outcomes. These challenges are further amplified in real-time applications where the dynamics are unknown and only scarce data is available. To tackle this challenge, in this work we introduce the SIAR-MPC method, combining the recently introduced Side Information Assisted Regression (SIAR) method for system identification with Model Predictive Control (MPC). SIAR utilizes side-information constraints inherent to game theoretic applications to model agent responses to payments from scarce data, while MPC uses this model to facilitate dynamic payment adjustments.
Our experiments demonstrate the efficiency of SIAR-MPC in guiding the system towards socially optimal equilibria, stabilizing chaotic behaviors, and avoiding specified regions of the state space.
Comparative analyses in data-scarce settings show SIAR-MPC’s superior performance over pairing MPC with Physics Informed Neural Networks (PINNs), a powerful system identification method that finds models satisfying specific constraints.

## I Introduction

Game theory is a mathematical framework for studying strategic interactions among self-interested decision-making agents, also interchangeably referred to as players.
Static equilibrium theory predicts that agents, when fully informed about the payoffs of all participants in the system, will adopt strategies that collectively form a Nash equilibrium. However, this perspective is increasingly recognized as limited in real-world applicability, given that computing Nash equilibria is intractable and there may exist numerous such equilibria.

The modern approach to understanding the outcome of a strategic interaction adopts a dynamic viewpoint [], where players engage in repeated play, allowing their strategies to evolve in response to past outcomes.
Studying the dynamic behavior of agents in games offers profound insights into strategic multi-agent system behaviors, demonstrating that individual self-interest can destabilize the system and lead to socially suboptimal outcomes.
Specifically, agent learning dynamics can display a wide range of undesirable behaviors, including failure to converge to Nash equilibria, convergence to suboptimal equilibria, limit cycles, Poincaré recurrence, and chaotic behavior [, ].
Moreover, recent impossibility results reveal a fundamental limitation of game dynamics: there exist games for which all game dynamics fail to converge to Nash equilibria from all starting points [].

Aiming to counteract undesirable system behaviors and circumvent limitations imposed by impossibility theorems, in this work we assume the perspective of a central planner, who tries to control the system by issuing rewards/penalties to agents as incentives. Our primary objective is to determine:

Can we influence players, whose behavior is not a priori known, toward a desirable outcome?

To address this challenge we introduce a new computational framework called \acs*SIAR-\acs*MPC for controlling strategic multi-agent systems that integrates cutting-edge approaches for real-time system identification and control (see Fig. 1 for an example illustrating the impact of control). In the system identification step, we predict agents’ reactions to incentives, a task made particularly demanding for time-critical applications (e.g., rerouting traffic post-accident) where rapid adjustments are necessary with few observational data.
In the subsequent control step, once the system has been accurately modeled, we develop dynamic reward/penalty strategies aimed at achieving targeted outcomes with minimal control effort.

Figure: Figure 1: Replicator dynamics trajectories in the matching pennies game, with and without control. Starting from three initial conditions, (left) without control the system cycles around the equilibrium; (right) with control, trajectories are guided towards the specified equilibrium (indicated by $\star$.)

To address the system identification step, we extend the recently introduced the \acSIAR method [], originally developed to identify agents’ learning dynamics from a short burst of a system trajectory.
To adapt it to our needs, we broaden the scope of \acSIAR to incorporate the influence of control parameters.
To compensate for the absence of data, \acSIAR searches for polynomial regressors that approximate the controlled dynamics, satisfying side-information constraints native to game theoretical applications.

Following the modeling of agent responses to payments with \acSIAR, we use \acMPC to develop a dynamic payment scheme that steers the system towards desired outcomes. \acMPC is a control technique that leverages a mathematical model of the system to predict future behavior and calculate optimal control inputs that minimize an appropriate objective function []. A key advantage of MPC is its ability to handle constraints, such as limits on monetary incentives for agents (control constraints) and restrictions on the states that agents can reach (state constraints) in our case. However, the success of MPC depends on the existence of an accurate system model, which is not readily available in time-critical applications. Therefore, system identification becomes crucial to uncover the underlying dynamics of the system and enable the successful application of MPC.

Several recent papers have studied how incentive-based control could steer players to a desired equilibrium: [] gives a survey of control in population/network games under specific dynamics such as replicator and imitation dynamics and an incentive-based control model of payments offered to each player based only on their own actions; [] studied this problem in normal-form and extensive-form games under the assumption that the players use no-regret dynamics, and with a more general incentive model in which the payment function to each player is a non-negative function that is linear in her strategy and continuous in the other players’ strategies; [, , ] studied incentive-based control in specific models of population games and evolutionary dynamics, solved for optimal control where possible, and proved convergence and day-to-day results for them. All these works assumed either specific games or dynamical properties, and ours is, to our knowledge, the first to combine system identification with incentive-based control, giving a general framework for control under unknown, general, and possibly noisy dynamic models.

To demonstrate the efficacy of our \acs*SIAR-\acs*MPC framework, we apply it to a diverse range of game types, from zero-sum games like Matching Pennies and Rock-Paper-Scissors to coordination games such as Stag Hunt.
Our results demonstrate that \acs*SIAR-\acs*MPC can successfully steer strategic systems towards socially optimal configurations, stabilize chaotic learning dynamics, and navigate away from specific regions in state space, all while relying on minimal data.

Finally, we benchmark \acs*SIAR-\acs*MPC against
\acPINN coupled with \acMPC. \acsPINN is a system identification method that trains a neural network with additional error terms in the objective function to guarantee adherence to physical laws and boundary conditions, similar to \acSIAR’s implementation of side-information constraints [, , ].

## II Preliminaries

In this work, we model a multi-agent system as a time-evolving normal-form game of $n$ players.
Each player $i$ is equipped with a finite set of strategies $\mathcal{A}_{i}$ of size $m_{i}$, and a time-varying reward function $u_{i}:\mathcal{A}\times\Omega\to\mathbb{R}$, where $\mathcal{A}\equiv\prod_{i=1}^{n}\mathcal{A}_{i}$ is the game’s strategy space, of the form

$$ $u_{i}(a,\omega(t))\\ =u_{i}(a,0)+\omega_{i,a}(t),\ \text{for $t\in\mathbb{R}_{+}$, $a\in\mathcal{A} $}.$ (1) $$

The value $\omega_{i,a}(t)$ denotes the control signal from the policy maker towards player $i$ regarding the strategy profile $a\coloneqq(a_{1},\dots,a_{n})$ at time $t$, where $a_{i}\in\mathcal{A}_{i}$.
We refer to the ensemble $\omega_{i}(t)\coloneqq\big{(}\omega_{i,a}(t)\big{)}_{a\in\mathcal{A}}$ as the control signal of $i$ at time $t$, and to $\omega(t)\coloneqq\big{(}\omega_{i}(t),\dots,\omega_{n}(t)\big{)}$ as the system’s control signal at $t$.
Typically, we restrict the control signals $\omega_{i}(t)$ in some semialgebraic sets $\Omega_{i}$.
We are going to refer to the product $\Omega\equiv\prod_{i=1}^{n}\Omega_{i}$ as the game’s control space. The value $u_{i}(a)\coloneqq u_{i}(a,0)$ describes the reward of player $i$ at strategy profile $a$ in the absence of any control by the policy maker. The utilities
$u_{i}(\cdot)$, $i=1,\dots,n$, will be considered common knowledge throughout this work.

In addition to the above, each player $i$ is allowed access to a set of mixed strategies $\mathcal{X}_{i}\equiv\operatorname{\Delta}(\mathcal{A}_{i})$, which is the $(m_{i}-~{}1)$-simplex that corresponds to the set of distributions over the pure strategies $\mathcal{A}_{i}$ of $i$.
The players’ reward function naturally extends to the space of mixed strategy profiles $\mathcal{X}\equiv\prod_{i=1}^{n}\mathcal{X}_{i}$ with $u_{i}\big{(}x,\omega\big{)}=\mathbb{E}[u_{i}(a,\omega)]$ for all $x\in\mathcal{X}$ and $\omega\in\Omega$, where the expectation is taken with respect to the distributions $x_{1},\dots,x_{n}$ over the player’s pure strategies.

Finally, we assume that the evolution of the above game is dictated by some controlled learning dynamics of the form

$$ $\displaystyle\dot{x}(t)$ $\displaystyle=f(x(t),\omega(t)),$ for $t\in\mathbb{R}_{+}$ (2) $\displaystyle x(0)$ $\displaystyle\in\mathcal{X},$ $$

where the update policies $f_{i}:\mathcal{X}\times\Omega_{i}\to\mathbb{R}^{m_{i}}$, $i=1,\dots,n$ and the ensemble thereof, given by $f(x,\omega)\coloneqq\big{(}f_{1}(x,\omega_{1}),\dots,f_{n}(x,\omega_{n})\big{)}$, are considered unknown, and are going to be discovered in the identification step of the framework described below.
Notice that the above assumption also implies that, at each time $t$, the control signal $\omega_{i}(t)$ of player $i$ is observed by that player, while the strategy profile $x(t)$ is observed by all the players.

Throughout this work, given some strategy profile $x$, we adopt the common game-theoretic shorthand $(x_{i},x_{-i})$ to distinguish between the strategy of player $i$ and ones of the rest of the players in $x$.
Furthermore, if $x_{i}$ corresponds to a pure strategy $a_{i}$ of $i$, we write $(a_{i},x_{-i})$ to point to that fact.

## III The SIAR-MPC Framework

In this section, we describe the \acs*SIAR-\acs*MPC framework for the real-time identification and control of strategic multi-agent systems.
As outlined in the introduction, \acs*SIAR-\acs*MPC involves two steps.
First, the system identification step aims to approximate the controlled dynamics in (2) using only a limited number of samples.
Second, after modeling agents’ reactions to payoffs, the control step employs \acMPC to steer the system towards a desirable outcome by optimizing specific objectives.
The subsequent subsections elaborate on these two steps.

#### The System Identification Step

To model the controlled dynamics in (2) we extend the \acSIAR framework introduced in [], which was in turn motivated by recent results in data-scarce system identification [].
\AcSIAR relies on polynomial regression to approximate agents’ learning dynamics of the form $\dot{x}(t)=f\big{(}x(t)\big{)}$ based on a small number of potentially noisy observations $x(t_{k}),\dot{x}(t_{k})$ (typically, $K=5$ samples) taken along a short burst of a single system trajectory.
To ensure the accuracy of the derived system model, \acSIAR searches for polynomial regressors that satisfy side-information constraints native to game-theoretic applications, which serve as a regularization mechanism.

To extend the \acSIAR method for our control-oriented scenario, we also need to identify the effects of the control signal $\omega(t)$.
We refer to the resulting method as \acSIAR with control (\acs*SIARc).
\acs*SIARc aims to model the controlled dynamics in (2) for each agent $i$ through a polynomial vector field $p_{i}(x,\omega)$.
To do so, during the data collection phase, we assemble a dataset $x(t_{k}),\omega(t_{k}),\dot{x}(t_{k})$, where $x(t_{k})$ represents a (possibly noisy) snapshot of the system state, $\omega(t_{k})$ is a randomly (typically, normally distributed) generated input reflecting various possible payments given to players (cf. (1)), and $\dot{x}(t_{k})$ is the velocity at time $t_{k}$, which is obtained either through direct measurement (if possible) or estimated from the state variables.
The process of training the \acs*SIARc model essentially involves solving an optimization problem to find a polynomial vector field that minimizes the mean square error relative to this dataset.
However, straightforward regression often yields suboptimal models due to the limited available samples.
To overcome this challenge, we search over regressors that satisfy additional side-information constraints, encapsulating essential game-theoretic application features and refining the search for applicable models.
Formally, a generic \acs*SIARc is given by

$$ $\displaystyle\underset{p_{1},\dots,p_{n}}{\text{min}}$ $\displaystyle\sum_{k=1}^{K}\sum_{i=1}^{n}\big{\|}p_{i}\big{(}x(t_{k}),\omega(t _{k})\big{)}-\dot{x}_{i}(t_{k})\big{\|}^{2}$ (3) s.t. $p_{i}$ are polynomial vector fields in $x$ and $\omega$ $\displaystyle\text{$p_{i}$ satisfy side-information constraints}.$ $$

In this work, we utilize two specific types of side-information constraints (though a broader array is available []).
The first side-information constraint we use ensures that the state space $\mathcal{X}$ of the system, i.e., the product of the simplices $\mathcal{X}_{i}\equiv\operatorname{\Delta}(\mathcal{A}_{i})$, $i=1,\dots,n$, is robust forward invariant (\acsRFI) with respect to the controlled dynamics in (2).
This means that for any initialization $x(0)\in\mathcal{X}$, we have that $x(t)\in\mathcal{X}$ for all subsequent times $t>0$, and any control signal $\omega(t)\in\Omega$.
To search over regressors that are \acRFI, we rely on a specific characterization of the property that dictates a set remains robustly forward invariant under system (2) only if $f(x,\omega)$ lies in the tangent cone of $\mathcal{X}$ at $x$ for every control $\omega\in\Omega$.
Using the characterization of the tangent cone at each simplex $\mathcal{X}_{i}$ [], enforcing \acRFI is reduced to verifying that, for all $x\in\mathcal{X}$ and $\omega\in\Omega$:

$$ $\displaystyle\sum_{a_{i}\in\mathcal{A}_{i}}p_{ia_{i}}(x,\omega)$ $\displaystyle=0,$ ( \acs *RFI) $\displaystyle p_{ia_{i}}(x,\omega)$ $\displaystyle\geq 0,$ $\displaystyle\text{whenever $x_{ia_{i}}=0$}.$ $$

The second type of side-information constraint we use is based on a fundamental assumption about agent behavior that arises from their strategic nature.
The agents as strategic entities are expected to behave rationally, preferring actions that enhance their immediate benefits, a property known as positive correlation (\acsPC) [].
Specifically, agents are inclined to choose actions that are likely to increase their expected utility, assuming other agents’ behaviors remain unchanged, i.e., for all $x\in\mathcal{X}$ and $\omega\in\Omega$

$$ $\langle\nabla_{x_{i}}u_{i}(x,\omega),\,p_{i}(x,\omega)\rangle>0,\;\text{ whenever $p(x,\omega)\neq 0$}.$ (PC) $$

To enforce these side-information constraints computationally in our polynomial regression problem, we utilize sum-of-squares (\acsSOS) optimization [, , , , , ].
Both \acRFI and \acPC are represented as polynomial inequality or nonnegative constraints over the semialgebraic sets $\mathcal{X}$ and $\Omega$ (in \acPC’s case, we need to relax the inequality []).
Using the \acSOS approach, instead of searching over polynomials $p(x)$ that are nonnegative over a semialgebraic set $\mathcal{S}\equiv\big{\{}x\nonscript\ \big{|}\nonscript\ \mathopen{}g_{j}(x)
\geq 0,h_{\ell}(x)=~{}0,\,j\in[m],\,\ell\in[r]\big{\}}$, we search over polynomials $p(x)$ that can be expressed as $p(x)=\sigma_{0}(x)+\sum_{j=1}^{m}\sigma_{j}(x)g_{j}(x)+\sum_{\ell=1}^{r}q_{
\ell}(x)h_{\ell}(x)$, where $q_{\ell}$ are polynomials, and $\sigma_{j}$ are sum-of-squares polynomials.
Such polynomials $p$ are guaranteed to be nonnegative over $\mathcal{S}$, a condition that is also necessary under mild assumptions on the set $\mathcal{S}$ [, Theorem 3.20].
Furthermore, for any given degree $d$, we can look for \acSOS certificates of degree $d$ through semidefinite programming, creating a hierarchy of semidefinite problems.

#### The Control Step

After estimating the controlled dynamics which describes how players’ strategies ($x$) respond to the incentives ($\omega$), our subsequent objective is to steer the system towards desired outcomes.
To achieve this, we employ \acMPC, which formulates an optimization problem to identify the optimal sequence of control actions over a set horizon, subject to constraints on control inputs and system states.
In our setting, control constraints could be limits on the monetary incentives for agents, and state constraints describe which states are reachable for agents.
The essence of \AcMPC lies in its ability to leverage a mathematical model of the system to predict future system behavior over a prediction horizon $T$. Each prediction is based on the current state measurement $x(t)$ and a future control signal sequences $\omega_{t}\coloneqq\{\omega_{0|t},\dots,\omega_{N-1|t}\}\subset\Omega$, which is calculated by solving a constrained optimization problem.
Here, $N$ is the number of control steps within the control horizon $T\coloneqq N\cdot\Delta t$ that determines the time period over which the control sequence is optimized.
Typically, the objective function of the \acMPC is given by

$$ $J(\omega_{t})=\sum_{n=0}^{N}\|x_{n|t}-x^{*}\|^{2}+\alpha\sum_{n=0}^{N-1}\| \omega_{n|t}\|^{2},$ (4) $$

where $x_{n|t}$, $n=1,\dots,N$ correspond to values of the forecasted trajectory, and $x^{*}$ is a desirable target system state.
The first term of $J(\omega_{t})$ penalizes deviations of the predicted states $x_{n|t}$ from the target value $x^{*}$, while the latter term accounts for the control effort at weight $\alpha$.
In addition to the above, large control signal variations can also be penalized by adding the term $\sum_{n=1}^{N}\|\omega_{n|t}-\omega_{n-1|t}\|^{2}$ at some desired weight.
The optimal control sequence is obtained by solving the constrained optimization problem

$$ $\displaystyle\underset{\omega_{t}}{\text{min}}$ $\displaystyle J(\omega_{t})$ (5) s.t. $\displaystyle\omega_{n|t}\in\Omega,\,\ 0\leq n\leq N$ $\displaystyle x_{n+1|t}=x_{n|t}+\Delta t\cdot p(x_{n|t},\omega_{n|t}),\,\ 1 \leq n\leq N$ $\displaystyle x_{0|t}=x(t).$ $$

The first control signal $\omega_{0|t}$ is then applied to the system and the optimization is repeated at time $t+\Delta t$ once the new state measurement $x(t+\Delta t)$ is obtained.

It is important to note that \acMPC has two key features: First, by optimizing control actions across a finite horizon, it can predict and maintain the system within predefined operational limits to avoid critical conditions. Second, applying only one control action at a time, allows the system to adapt to rapid changes in the environment.

## IV Numerical Examples

In this section, we demonstrate the applicability and the performance improvements provided by the \acs*SIAR-\acs*MPC framework in comparison to coupling \acMPC with solutions from unconstrained regression (Reg-\acs*MPC)—similar to sparse identification of nonlinear dynamics with control (SINDYc) [] in the monomial basis—and \acsPINN (\acs*PINN-\acs*MPC) in various normal-form games of independent interest.

PINN is a powerful deep learning approach designed to inherently accommodate side-information constraints, including symmetries, conservation laws, and boundary conditions [].
The idea is straightforward: a \acPINN is a neural network that models the update policies, $f$, of the system dynamics $\dot{x}(t)=f\big{(}x(t),\omega(t)\big{)}$.
The side-information constraints are integrated into the \acPINN during its training as terms in the loss function that penalize violations of the desired constraints.
In our setting, we aim to enforce \acRFI and \acPC as such constraints.
Due to the insufficient number of training samples—in most cases, $5$ samples—we are restricted to a simple neural network architecture comprised of two hidden layers of size $5$.
This limitation in the neural network’s expressivity is counterbalanced by the simplicity of the ground-truth update policies $f$ (which, in most cases, are polynomial).
As activation functions we use the $\tanh$ function.
Finally, the side-information constraints are imposed by $2,500$ collocation points.

We begin our demonstration with a well-known coordination game; the stag hunt game.
As coordination games correspond to non-cooperative setups where equilibration to a well-defined—socially optimal—state is desirable, a stag hunt game is a natural candidate to compare the performance of the different control methods in guiding the agents toward the game’s optimal state.
Our results show that, in the absence of “sufficient” training data, the \acs*SIAR-\acs*MPC framework outperforms \acs*PINN-\acs*MPC, which fails to steer the ground-truth replicator dynamics.
More importantly, even if sufficient data are available in order to train the above data-driven models, our results indicate that the steering cost of the \acMPC based on those models far exceeds the one of the \acs*SIAR-\acs*MPC solution.
Moreover, moving away from the ideal landscape of coordination games, and into the more challenging regime of two-player zero-sum games, we demonstrate the performance of the \acs*SIAR-\acs*MPC framework in the twofold goal of steering, possibly non-polynomial, learning dynamics of non-vanishing regret toward a Nash equilibrium of the game; and steering a provably chaotic multi-agent system.
We conclude this section with an example of \acs*SIAR-\acs*MPC steering that incorporates area avoidance as added constraints to the \acMPC subproblems, a well-known advantage of \acMPC throughout the literature [].

Figure: Figure 2: Performance comparison of the Reg-\acs*MPC (left), \acs*PINN-\acs*MPC (center), and \acs*SIAR-\acs*MPC (right) solutions in steering the replicator dynamics for the stag hunt game. A dataset of $4$ samples is used to train the system identification methods. Only the \acs*SIAR-\acs*MPC solution succeeds in steering the system to the superior Nash equilibrium in $x^{*}_{1,1}=x^{*}_{2,1}=1$.

Figure: Figure 3: Comparison of the aggregated control cost of the \acs*PINN-\acs*MPC and \acs*SIAR-\acs*MPC solution in steering the replicator dynamics for the stag hunt game based on $6$ samples. The \acs*SIAR-\acs*MPC solution has the lower aggregated control cost.

### IV-A Stag Hunt Game

The stag hunt game is a two-player two-action coordination game that models a strategic interaction in which both players benefit by coordinating their actions toward a specific superior outcome (the hunt of a stag).
However, if that outcome is not possible, each player prefers to take advantage of the lack of coordination and come out on top of their opponent by choosing the alternative (hunt a rabbit by themselves) rather than coordinating to an inferior outcome (hunt a rabbit together).
In this example, in the absence of control the players default to a stag hunt game given by the players’ reward functions $u(\cdot)\coloneqq u(\cdot,0)$

$$ $u_{1}(a)=u_{2}(a)=\mathbf{A}_{a_{1},a_{2}},\;\text{where}\;\mathbf{A}=\begin{ pmatrix}4&1\\ 3&3\end{pmatrix}.$ (6) $$

For expositional purposes, we restrict the game’s evolution to a subset of symmetric two-player two-action games given by the control signals $\omega_{1,a_{1},a_{2}}(t)=\omega_{2,a_{2},a_{1}}(t)\in[0,2]$ for all $t$.
Furthermore, for tractability purposes, we fix $\omega_{1,2,2}(t)\coloneqq 0$.
We assume that the agents’ behavior is dictated by the replicator dynamics given, for player $i$ and action $a_{i}$ of $i$, by the polynomial update policies

$$ $f_{i,a_{i}}(x,\omega)=x_{i,a_{i}}(u_{i}(a_{i},x_{-i},\omega)-u_{i}(x,\omega))$ (7) $$

for all $x\in\mathcal{X}$ and $\omega\in\Omega$.

We are going to search for $f$ using the \acSIAR framework.
Specifically, for each $i$ and $a_{i}$, we are going to search for polynomial $p_{i,a_{i}}:\mathcal{X}\times\Omega\to\mathbb{R}$ such that $p_{i,a_{i}}\big{(}x(t),\omega(t)\big{)}\approx f_{i,a_{i}}\big{(}x(t),\omega(t
)\big{)}$ for all $t\in\mathbb{R}_{+}$.
As side-information constraints, we are going to impose the \acRFI and \acPC properties as given in the previous sections.
Then, by substituting (6) to (PC) we have the following \acSIAR problem

$$ $\displaystyle\underset{p}{\text{min}}$ $\displaystyle\sum_{k=1}^{K}\big{\|}p\big{(}x(t_{k}),\omega(t_{k})\big{)}-\dot{ x}(t_{k})\big{\|}^{2}$ (8) s.t. $\displaystyle p_{i,1}(x,\omega)+p_{i,2}(x,\omega)=0,\,\forall i$ $\displaystyle p_{i,1}\big{(}(0,1),x_{-i},\omega\big{)}\geq 0,\,\forall i$ $\displaystyle p_{i,2}\big{(}(1,0),x_{-i},\omega\big{)}\geq 0,\,\forall i$ $\displaystyle v_{i,1}(x,\omega)p_{i,1}(x,\omega)+v_{i,2}(x,\omega)p_{i,2}\geq 0 ,\,\forall i,$ $$

where $x\in\mathcal{X}$, $\omega\in\Omega$, and $v_{i,a_{i}}:\mathcal{X}\times\Omega\to\mathbb{R}$ are given by

$$ $\displaystyle v_{1,1}(x,\omega)$ $\displaystyle=(4+\omega_{1,1})x_{2,1}+(1+\omega_{1,2})x_{2,2}$ (9a) $\displaystyle v_{1,2}(x,\omega)$ $\displaystyle=(3+\omega_{2,1})x_{2,1}+3x_{2,2}$ (9b) $\displaystyle v_{2,1}(x,\omega)$ $\displaystyle=(4+\omega_{1,1})x_{1,1}+(1+\omega_{1,2})x_{1,2}$ (9c) $\displaystyle v_{2,2}(x,\omega)$ $\displaystyle=(3+\omega_{2,1})x_{1,1}+3x_{1,2}.$ (9d) $$

Since the update policies $f_{i,a_{i}}$ in (7) correspond to the replicator dynamics, the solution to the above optimization problem can be recovered by a $7$-degree \acSOS relaxation [].
Fig. 2 (right) shows the performance of the \acs*SIAR-\acs*MPC using this solution as a model for the \acMPC method.
In the top panel of the figure, we have the trajectory
$x(t)$ initialized at $x_{0}=(0.4,0.3)$ corresponding to the control signal $\omega(t)$ depicted in the bottom panel.
The plot is divided into three sections, corresponding to the system identification phase, an evaluation period, and a control phase.
In the first section, we set the control signals to normally distributed noise with mean zero (bounded in $\Omega$) and a sample of $K=4$ datapoints from the resulting trajectory.
In doing so, we achieve two things.
On the one hand, the noise supplies variety between the data samples, which improves the efficiency of the system identification methods.
On the other hand, we make sure to maintain a low aggregated control cost during the system identification phase.
At the end of this phase, we solve the optimization problem in (8) and acquire a model of the system’s update policies.
In the second section of the plot, we compare the ground-truth dynamics with the model’s predicted trajectory (in dashed red lines); here, the control signal is chosen randomly.
Finally, in the steering phase, we steer the ground truth using the output of the \acMPC as the control signal: the objective is to steer the system to the superior Nash equilibrium of the stag hunt game at $x^{*}_{1,1}=x^{*}_{2,1}=1$, which is achieved by the \acs*SIAR-\acs*MPC framework at $t\approx 8$.
In comparison, the Reg-\acs*MPC and \acs*PINN-\acs*MPC solutions (Fig. 2 (left) and Fig. 2 (center), respectively) fail to complete the steering objective.
However, as the latter are data-driven techniques, for fairness we also repeat the comparison based on a larger training dataset of $K=6$ samples.
Although this dataset is sufficiently large to permit the training of all the system identification methods, the \acs*SIAR-\acs*MPC solution still carries the least aggregated control cost, as we depict in Fig. 3.

Figure: Figure 4: Performance comparison of the \acs*PINN-\acs*MPC, and \acs*SIAR-\acs*MPC solutions in steering the log-barrier dynamics for the matching pennies game (left) and the replicator dynamics for a $0.25$-RPS game (right).

### IV-B Zero-Sum Games & Chaos

The stag hunt game arguably provides an ideal landscape for the steering of game dynamics to a Nash equilibrium.
This is because of the existence of a socially optimal Nash equilibrium (the hunt of a stag) that has a positive-measure basin of attraction.
The class of zero-sum games, on the other hand, does not possess such merit, since in a zero-sum game, by definition, the player rewards sum up to zero independently of the strategies chosen by the players.
To make matters worse, well-known game dynamics, e.g., the replicator dynamics, are known to exhibit undesirable behavior in zero-sum games such as Poincaré recurrence [], or even chaos [].
Even if we amuse ourselves by instead pondering the more relaxed notion of time-average convergence, positive results in that area revolve around the notion of no-regret dynamics [], and the steering of learning dynamics of non-vanishing regret is, to the best of our knowledge, unexplored.
In that regard, in the next couple of examples we demonstrate the performance of \acs*SIAR-\acs*MPC in steering the log-barrier dynamics—well-known learning dynamics of non-vanishing regret—in the matching pennies game and in the steering of chaotic replicator dynamics in an $\epsilon$-perturbed rock-paper-scissors game.
In both cases, we demonstrate the \acs*SIAR-\acs*MPC framework is able to steer the system toward the desired Nash equilibrium of the game.

#### Matching Pennies Game

The matching pennies game is a two-player, two-action zero-sum game where one player benefits by the existence of coordination among the two, while the other player benefits by the lack thereof.
Formally, a matching pennies game is encoded in the uncontrolled players’ reward functions in (1) by

$$ $u_{1}(a)=-u_{2}(a)=\mathbf{A}_{a_{1},a_{2}},\;\text{where}\;\mathbf{A}=\begin{ pmatrix}[r]1&-1\\ -1&1\end{pmatrix}.$ (10) $$

For similar reasons as in the previous example, we are going to restrict the game’s evolution to a subset of two-player two-action zero-sum games given by $\omega_{1,a}(t)=\omega_{2,a}(t)\in[-1,1]$ for all $t$, and set $\omega_{1,2,2}(t)\coloneqq 0$.
The log-barrier dynamics of the above time-varying game are, for player $i$ and action $a_{i}$ of $i$, given by the rational update policies

$$ $f_{i,a_{i}}\big{(}x,\omega\big{)}=x_{i,a_{i}}^{2}\bigg{(}u_{i,a_{i}}-\frac{x_{ i,1}^{2}u_{i,1}+x_{i,2}^{2}u_{i,2}}{x_{i,1}^{2}+x_{i,2}^{2}}\bigg{)}$ (11) $$

for all $t\in\mathbb{R}_{+}$ and $x\in\mathcal{X}$, where the shorthand $u_{i,x_{j}}\coloneqq u_{i}(x_{j},x_{-i},\omega)$ is used for compactness.
Observe that, as is the case for the updated policies of the replicator dynamics in (7), $f_{i}$ depends on $\omega(t)$ through $u_{i}$.
In Fig. 4 (left), we show that \acs*SIAR-\acs*MPC solution is able to steer a trajectory $x(t)$ of the above system initialized at $x(0)=(0.2,0.6)$ to the unique mixed Nash equilibrium $x^{*}_{1,1}=x^{*}_{2,1}=1/2$ of the matching pennies game with only $K=6$ training samples.

#### ϵ italic-ϵ \epsilon italic_ϵ -RPS Game

In our last example, we use the \acs*SIAR-\acs*MPC method to steer the replicator dynamics in an $\epsilon$-perturbed rock-paper-scissors game ($\epsilon$-RPS), a two-player, three-action zero-sum game where the replicator dynamics exhibit chaotic behavior [, ].
In a nutshell, this means that any two initializations of the system—even the ones that are infinitesimally close to each other—may lead to completely different trajectories.
In other words, the accurate estimation of the agents’ update policies is futile due to the finite precision of any numerical method.
A $\epsilon$-RPS game may be encoded in the players’ reward functions by replacing the payoff matrix in (10) with

$$ $\mathbf{A}=\begin{pmatrix}[r]\epsilon&-1&1\\ 1&\epsilon&-1\\ -1&1&\epsilon\end{pmatrix}.$ (12) $$

Due to the larger dimensionality of this game, compared to ones in the previous examples, we are going to consider time-evolving games in the subset of two-player three-action zero-sum games given by $\omega_{1,a}(t)=\omega_{2,a}(t)\in[-1,1]$ for all $t$, and only four non-zero signals, namely, $\omega_{1,1,2}(t)$, $\omega_{1,1,3}(t)$, $\omega_{1,2,1}(t)$, and $\omega_{1,3,1}(t)$.
In Fig. 4 (right), we show the successful steering to the chaotic replicator dynamics for the $0.25$-RPS game, given as in (7), toward the unique mixed Nash equilibrium of the game $x^{*}_{1}=x^{*}_{2}=(1/3,1/3,1/3)$ based on a dataset of $K=11$ samples.

Figure: Figure 5: Vector field of the steering direction of the \acs*SIAR-\acs*MPC when the additional state avoidance constraint is (right), and is not (left) imposed. The restricted area is shaded in blue. The green line corresponds to a controlled trajectory of the replicator dynamics for the matching pennies game.

#### State Avoidance Constraints

We conclude this section by revisiting the example of a matching pennies game to illustrate a key feature of \acMPC: its ability to incorporate state constraints.
In our case, the purpose of these state constraints is to keep the system trajectory away from specific, undesirable areas of the state space.
Consider a scenario where the policymaker aims to steer the system toward the mixed Nash equilibrium at $x^{*}_{1,1}=x^{*}_{2,1}=1/2$, while simultaneously ensuring that the system trajectory avoids a ball of radius $0.4$ centered at $\big{(}(0,1),(1,0)\big{)}$.
This constraint can be incorporated into the \acMPC problem and as illustrated in Fig. 5, \acs*SIAR-\acs*MPC can steer the system to the desired equilibrium while also avoiding the restricted area of the state space (shaded in blue).

## V Conclusions

In this work, we introduced \acs*SIAR-\acs*MPC, a new computational framework that integrates \acSIAR for system identification with \acMPC for dynamic payment adjustments, to steer strategic agents toward desired outcomes in real-time settings with limited data availability.
We demonstrated that \acs*SIAR-\acs*MPC effectively stabilizes chaotic behaviors, steers systems toward optimal equilibria, and navigates away from undesirable regions of the state space.
Our comparative analysis revealed that \acs*SIAR-\acs*MPC outperforms alternative methods, such as \acs*PINN-\acs*MPC, in data-scarce settings.

Future research can explore several potential directions.
Firstly, we aim to extend our framework to games that are not in normal form, expanding its applicability to a wider range of strategic interactions.
Secondly, we plan to investigate the scalability of our approach by exploring the uncoupling assumption, which could potentially enable the application of our method to larger systems with many agents.
Finally, we intend to investigate the integration of additional side information that is sum-of-squares representable, which could further enhance the performance of the system identification and control process.

## Peer Reviews

confidence: 2
contribution: 2
initial_rating: 3
presentation: 2
questions: See above
soundness: 2
strengths: The problem is well motivated and the paper is overall easy to follow.
summary: This work studies how to steer game dynamics towards desirable outcomes. To do so, the authors introduce a framework that combines side information assisted regression and model predictive control. The framework first tries to perform a system identification step to approximate the control dynamics and subsequently utilizes MPC to steer the system. The authors also give several empirical studies on games, demonstrating the effectiveness of the proposed framework.
weaknesses: The originality and significance of the contributions seem limited. The framework primarily extends existing techniques, coupled with well-studied MPC approaches. It is not clear how the contributions could be translated into broader insights for the community. Also, is it possible to provide some theoretical justification?

---

confidence: 2
contribution: 2
initial_rating: 6
presentation: 3
questions: - what if there is error in the dynamics modelling step, what will happen in the MPC phase? Can MPC accomodate the error?
soundness: 3
strengths: - Most of this paper is well-structured and well-written.
summary: This paper propose Side Information Assisted Regression with Model Predictive Control (SIAR-MPC), a framework to learn the dynamics of game and steer game dynamics towards desirable outcomes when data is scarce. This framework has two components, which includes system identification part and MPC part. In system identification step, the algorithm approximated the controlled dynamics using only a limited number of samples. Second, in MPC step, based on the learned dynamics, MPC is applied to steer the system towards a desirable outcome. This framework is evaluated in data-scarce settings and show this framework have superior performance compared to other baselines.
weaknesses: - The font in the plots could be larger, it is relatively hard to read. The introduction of RFI could be more detailed in section 4.1.
- 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 avalibility of the data varies.

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: How should the reader be interpreting these incentives in the context of the games studied?

How scalable are these approaches to larger settings? Are there fundamental barriers to scaling here or is there hope of overcoming dimensionality-related limitations?
soundness: 3
strengths: The problem of identifying and steering game dynamics is both difficult and seems to be understudied, though I am not a domain expert. The approach described in the submission seems sensible and technically interesting.

---

Overall, I am not sure how useful the submission is, but I found its object of study and ideas interesting. I consider the latter to be enough to merit acceptance. On the other hand, I am not an expert in this domain, so both my perception of the submission's strengths and weaknesses should be treated with a non-zero amount of skepticism. I left my confidence low so as to leave room for reviewer's who may feel more confident in their expertise on the subject matter.
summary: The submission investigates the problem of steering game unknown game dynamics. The submission's approach involves first identifying these dynamics by extending SIAR to control settings. Then, it uses MPC to adjust steer these dynamics. The submission gives examples of its approach for stag hunt, matching pennies and epsilon-rock-paper-scissors.
weaknesses: 1. The submission doesn't do a very good job communicating how the reader ought to be interpreting these incentives.
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.
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?
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.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 4
questions: 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?
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?
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 $\omega$ so that the data is more informative, the sample complexity should be even lower. Is online learning a more natural setting?
soundness: 3
strengths: 1. The paper is clearly written and easy to follow.
2. This framework is very general. Only reasonable constraints are placed to enhance the sample efficiency of the learning.
summary: This paper investigates the problem of steering agent behaviors in normal-form games.There is a central planner being able to influence the game's utility function. The agents change their policy according to the current state of the game. The paper proposes the SIRC-MPC framework. In this framework the planner first learn the agent's behavior by fitting the dynamics with polynomial regressors. To facilitate the learning, RFI and PC are incorporated as regularizations. Then it steers the behavior via a MPC. Finally it conducts experiments to illustrate the effectiveness of this framework.
weaknesses: 1. The technical novelties of this paper is a bit unclear to me. See questions below.
2. The motivation of this paper is a bit unclear to me. See questions below.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: 1.	Why did the authors choose these two specific side-information constraints among all possible options as listed in the reference?

2.	In every experiment, there is only one initial reward matrix. Can the proposed method achieve similar performance with different reward values?

3.	How critical is MPC in this approach? How does the prediction horizon impact performance? It would be helpful if the authors could provide additional experiments to explore this.
soundness: 2
strengths: 1.	The paper presents an interesting setting with a clear motivation, making it easy to follow and understand. The approach of first identifying system dynamics and then planning to control the system is particularly intriguing.

2.	The use of polynomial regression with side-information constraints (RFI and PC) and the application of sum-of-squares (SOS) optimization shows a solid foundation in mathematical. The framework also leverages MPC effectively to solve constrained optimization problems dynamically.
summary: This paper proposes a new framework, SIAR-MPC, to address undesirable behaviors in game dynamics. The framework consists of two steps: first, it identifies controlled system dynamics using a polynomial regressor, incorporating side information as additional constraints to improve the accuracy of the learned dynamics. Second, Model Predictive Control (MPC) is adapted to predict the desired control actions.
weaknesses: 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.

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.

3.	Experimental issues: In the first paragraph of Experiments (Page 6, lines 294), the neural network consisting of two hidden layers of size 5 is trained with only 5 samples, which arose the problem of underfitting. The maximum number of samples used in the training phase is 11, for such a scare data, the comparison between any neural network-based method with the proposed method is unfair. Additionally, the baselines (PINNs from 2019 and SINDYc from 2018) are relatively outdated. More recent methods, such as Phycrnet, are mentioned in the related work. Besides, in data-scarce settings, traditional linear programming methods like pseudospectral method, optimal control(based on the Pontryagin maximum principle) should be considered.