Network Learning in Quadratic Games from Fictitious Plays
Authors: KEMI DING
Yijun Chen
Lei Wang
Xiaoqiang Ren
Guodong Shi
Venue: ICLR 2022 Submitted (2022)
Keywords: network learning
game theory

Abstract: We study the ability of an adversary learning the underlying interaction network from repeated fictitious plays in linear-quadratic games. The adversary may strategically perturb the decisions for a set of action-compromised players, and observe the sequential decisions from a set of action-leaked players. Then the question lies in whether such an adversary can fully re-construct, or effectively estimate the underlying interaction structure among the players. First of all, by drawing connections between this network learning problem in games and classical system identification theory, we establish a series of results characterizing the learnability of the interaction graph from the adversary's point of view. Next, in view of the inherent stability and sparsity constraints for the network interaction structure, we propose a stable and sparse system identification framework for learning the interaction graph from full player action observations. We also propose a stable and sparse subspace identification  framework for learning the interaction graph from partially observed player actions. Finally, the effectiveness of the proposed learning frameworks is demonstrated in numerical examples. 


Under review as a conference paper at ICLR 2022
NETWORK LEARNING IN QUADRATIC GAMES FROM FICTITIOUS PLAYS
Anonymous authors Paper under double-blind review
ABSTRACT
We study the ability of an adversary learning the underlying interaction network from repeated fictitious plays in linear-quadratic games. The adversary may strate- gically perturb the decisions for a set of action-compromised players, and observe the sequential decisions from set of action-leaked players. Then the question lies in whether such an adversary can fully re-construct, or effectively estimate the underlying interaction structure among the players. First of all, by drawing connections between this network learning problem in games and classical system identification theory, we establish series of results characterizing the learnabil- ity of the interaction graph from the adversary's point of view. Next, in view of the inherent stability and sparsity constraints for the network interaction structure, we propose stable and sparse system identification framework for learning the interaction graph from full player action observations. We also propose stable and sparse subspace identification framework for learning the interaction graph from partially observed player actions. Finally, the effectiveness of the proposed learning frameworks demonstrated in numerical examples.
INTRODUCTION
Game theory has been playing a fundamental role in understanding how competition and rational- ity arise among decision makers, termed players (Von Neumann & Morgenstern) (2007); Bicchieri (2004)). Players place individual decisions, for which the payoff's characterize their gains. The payoff of any player not only depends on her own decision, but also the decisions of all other play- ers, leading to intrinsic competitions. The Nash equilibrium defines decision profiles at which any player observing her payoff and other players decisions, understands that any unilateral change of the decision could only upset her own payoff. As result, at Nash equilibriums all players tend to stay at their current decisions, i.c., rationality takes place. The power of Nash equilibriums in plaining behavioral decisions, and the possibility of designing payoffs shaping player decisions, have enabled game theory to be applied in variety of disciplines solving problems ranging from route planning in transportation (Bianco et al. (2016)) and channel allocations in wireless commu- nications (Niyato & Hossain (2008)) to online E-commerce (Sen & King (2003)) and security of machine learning (Barreno et (2010))
The crucial insight in game-theoretical decision mechanisms, lies in the fact that players act accord- ing to their own payoff' functions and other players' decisions, holding no knowledge about other players' payoffs. Since the payoff's might encode players' preferences, economic status, and inter- personal relations, etc., it is of interest to investigate when and how payoffs of players can be learned from observations of player actions.
1.1 LINEAR QUADRATIC GAMES
A game be associated with graph, where the players are represented by nodes, and the in- terdependency among the players in payoffs defines links. a network game with n players and linear-quadratic payoffs, each node (player) V == 21,2,...p ,n) selects her action x; E R to

---

Under review as a conference paper at ICLR 2022
maximize payoff Jj described by
Jj = 0;
2x1 + Ii,X,X,
(I)
In (T), the first two terms characterize the benefit of player by setting her own action x,, where the parameter o; > 0 is called the marginal benefit, capturing the level of selfishness of player i. The last of this payoff function reflects the peer effect suffered by player from the actions of other players: if goj 0, players and j are strategic complements (friends or acquaintances); if Dig < O, players and j are strategic substitutes (opponent or adversary); if gij = O, there no influence on player i from player j.
Let G [Rax" be the matrix formed by the 9ijs i.c., the ij-entry of is gij. The interaction graph G (V, E*) underlying the game (I) is then defined the induced graph of G, where directed link (j. i) E E and only 9sj + 0.
1.2 FICTITIOUS PLAYS AND ACTION-COS COMONN--MPROMIEED PLAYERS
For players participating in game, Nash equilibriums not be known played immediately when the game starts since the payoff functions are held in private. Instead, in real-world the behav- iors of players are better described in a sequential decision process (Littman (1994)). Let time be indexed at k 0, assume that any rational player at any given will decide her next action as the decision that max-
T. and let player hold decision x; (k) for time k. Then, it is reasonable
imizes her payoff given other players' current decisions. This is known as fictitious plays or best responses (Fudenherg al. (1998)). As a result, in repeated plays for the linear-quadratic game, the dynamics of [k) obey
x, (k + +) arg [x, a + Σ Jo i i 1.....,,
(BR)
In practice, players might be influenced or manipulated by an adversary in their actions. We term such players as restio-compromised players, indexed in the set M C V. Then V \ M contains benign players who just follows (BR). For M. we model the influence of the adversary perturbation u,(k) over the best response. The fictitious plays of the players in the presence of the action-compromised players become
x; (A: + = arg max X + (i)u,)
(p-BR)
=a +
91 (k) + (k)), i = 1....,
where (i) is the indicator function: M i i M; (i) = otherwise.
1.3 PROBLEM DEFINITION
For the adversary, it is easier and affordable to observe actions only from a number of action-leaked players. We let O C V denote the group of players having their actions being observed. In this paper, we are interested in whether and how the underlying graph G (or equivalently, its adjacency matrix G) is exposed risks of being fully identificd/eammed by the adversary. To be precise, the adversary holds information
I: (k), E M, k: o,...,T .T) (K) O, = O....,
with the (k) and x; (k)) being produced by (p-BR. The problems of interest from the perspective of the adversary lie in
Learnability: Whether is possible to uniquely determine from I, perhaps with the help of strategically designed u, (A:), E M, A: = O...., T.
Learning: How to build effective learning frameworks for estimating G from I, perhaps with prior structural information such stability and sparsity.
2

---

Under review as a conference paper at ICLR 2022
1.4 CONTRIBUTIONS AND RELATED WORK
Contributions. The connection between the network learning problem in quadratic games and clas- sical system identification theory is uncovered. The key insight the observation that the unknown marginal payofí' do not play any role in the dynamics driving the difference between two consecu- tive player actions. As result, we manage to establish a series of results characterizing the learn- ability of the interaction graph by the adversary: with full player action observations, the learnability shown to be equivalent to certain observability conditions; with partial action observations, the learnability is shown to be determined by the unique solvability of an equation for Markov parame- ters. Next, noting the inherent stability and sparsity properties for the network interaction structure, propose stable and sparse system identification framework for learning the interaction graph from full player action observations, and a stable and sparse subspace identification framework for learning the interaction graph from partially observed player actions. Numerical examples validate the effectiveness of the proposed learning frameworks.
Related Work. Our paper is closely related to the recent studies on learning network games, such as Honorio & Ortiz (2015); Ghoshal & Honorio H Leng et al. (2020); Garg & Jaakkola (2016) Ghoshal & Honorio (2018), where the behavioral actions are collected to recover the game graph. Particularly, Leng et al. (2020) studies a learning problem of linear quadratic games on net- works, over which a number of independent games are played with all Nash equilibrium actions observed for learning the graph. We note that the learning frameworks in these works focus on static games where observations for learning are steady or Nash equilibrium actions, which differ- ent from our considered setting of dynamic games where transient actions are observed during the decision-making process.
The considered learning problem is also related to the network inference problem in the fields of machine learning and signal processing. To handle such problem, several approaches have been proposed, differing in the applied models such probabilistic graphical models (Friedman et al. eoyysicall-mmoivateed motivated models (Gomez- Rodrigue et al. (20IT)) and signal processing mod-
(2008), physically-me els (Dong et al. ()
Technically, this work is built upon the results of linear system identification (Van Overschee & De Moor 20022) Ljung (1998). in which measured input/output data explored to build mathe- matical models of linear (network) systems, and even identify the system matrices or network struc- ture under some structure and/or excitation conditions e.g.. Bazanella al.. (2019); Yu et al.) (2019);
Shen et al. (2017). Recent ad advances of system identification include its applications to machine learning (Chiuso & Pillonetto (2019)), reinforcement learning (Ross Bagnell (2012) and deep learning (De la Rosa & Yu (2016)). In view of this, this paper can be regarded as a generalization of system identification approaches network learning of games.
2 NETWORK LEARNABILITY FROM FICTITIOUS PLAYS
In this section, we investigate the learnability condition under which the network structure G can be uniquely determined by the adversary. The adversary may have access the system dynamics (p- BR for a single trajectory where the network game is played only once, or for multiple trajectories where the network game is independently played for a number of times.
2.1 LEARNABILITY BY SINGLE TRAJECTORY
For notational simplicity, we denote the aggregated action profile of all players and the overall in- jected perturbations at time & by x(k) := [x1 (k),.... [k, (k)] E R" and u(k) ju, (k), M] E RRT respectively. We also denote the cardinalities of the sets M and as m and I, respec- tively. Within these sets, the indexes of action--omppomiied and action-leaked players sorted in ascending order with M == (pr....,Pml and O == {qI....,
Introduce two matrices B E R= and C E R to represent the sets of M and O. Specifically, the (i, ji-th entry of matrix B satisfies that
[1, Pjj B
(2)
0, otherwise.
3

---

Under review as a conference paper at ICLR 2022
The (j. 1)h entry of matrix C satisfies that
1, i Oyi
CJ.
0, otherwise.
From classical control theory (Wonham (9855 ) the pair (G, B) is said to be controllable the matrix (where the subscript n denotes the number of block columns)
C2 = B
GB
G Th GB
has rank n; the pair (G, C) said to be observable if the nl x n matrix (where the subscript n denotes the number of block rows)
C
CG
On ==
LCG
has rank
2.1.1 FULL PLAYER ACTION OBSERVATIONS
We present the following result showing that if the adversary has access all players' actions but has no ability to add action perturbations, namely V and M = 0, the learnability of the network structure G can be precisely characterized by special form of observability.
Theorem Assume O V and M 0. Let the adversary has access single trajectory of from (p-BR). Then G can be uniquely determined by the adversary for sufficiently large T if and only if (G, x(1) x(0)) is controllable.
In fact, can further prove that (G,x(1) x()) is observable if and only if the characteristic polynomial of G coincides with the minimal polynomial of G, and x(1) x(0) has nontrivial projections
all generalized eigenvector of G (see more details in Proposition of Appendix B). The next result characterizes the ability to learn G by feedback perturbations, namely u(k) Kx(k) for K E R m
Theorem Assume O= V and M + 0. Let the adversary has access one single trajectory of I from (p-BR). Suppose u(k) is generated by u(k) = Kx(k). Then there exists K such that G can be uniquely determined if the following conditions hold:
(i) 0 # x(1) x0) E Im(B):
(ii) (G.B) is controllable.
2.1.2 PARTIAL PLAYER ACTION OBSERVATIONS
When O is only a subset of V, the learnability of G by the adversary becomes much more chal- lenging question.
Block Hankel Matrices. For a time series, the block Hankel matrices provide way of representing the time evolution compact forms, given by an operator H that maps the time series into block matrices Van Overschee & De Moor (202) (see Appendix A). Let w(k) denote the collection of observed actions (A), Of generated from (p-BR) at time The block Hankel matrices of the sequences W Worr, Unj can be defined, respectively, leading to W, ps W from H(Worr-)),
WF. WT from ((W11z), U,, b U from H(Uofr-1). and Up.. U from HUU1)))
Convolution Matrix. The lower-triangular convolution matrix for the triplet (G, B, C) defined as
0 CB
0
Tn =
CG 2
CB
4

---

Under review as a conference paper at ICLR 2022
The reversed extended controllability matrix for matrix pair (G, is defined as
Cn G G '
GB
B
Markov Parameter Equations. For any k. x(A: can be represented as a linear combination of the past
observations {x,(s), O,...,k i, O} and the past perturbations {u)(s), O...., 1,j E M) with > O. Consequently, the elements in the first column in matrix Tn (termed Markov parameters) must satisfy the following equation (see Appendix D):
A O, O,,"',,,WW + +O, C. G AU, + T,AU,
(4)
where , = w - W,, AWp == W - Wp and AU,, AUp are defined similarly. We are now ready to present the following result.
Theorem Lel the adversary has access one single trajectory of I from (p-BR). Suppose (G, C) is observable and T z 2n. Then G can be uniquely determined by the adversary if and only if the Markov parameter equation admits a unique solution with respect to G.
2.2 LEARNABILITY BY INFINITE TRAJECTORIES
The transfer function of the perturbed best-response ( BR is defined as Fa(z) C
Here C, and (2 captures the relation between u and V/.xx.. the frequency (2) domain. Inspired by the recent breakthrough on network system identification (van Waarde et al. (2021)), we present the following result. asserts that either full observation of players' actions or full injected perturbations is necessary for the learnability of G when the adversary has infinitely trajectories.
Let the adversary have access to infinitely many trajectories I from (p-BR) subject to different initial player actions and perturbation sequences. Then the network structure G is uniquely learnable by the adversary if and only if
Theorem
=c(z)==Fah for - G;
G
or equivalently, if and only if at least one of the following conditions holds:
(i) rank C = n and (G, B) is controllable;
(ii) rank B and (G, C) is observable.
3 NETWORK LEARNING WITH FULL ACTION OBSERVATIONS
In this section, develop framework for learning the network structure G from the information generated by (p-BR) with full action observations (i.e., O = V).
3.1 THE FRAMEWORK: STABLE AND SPARSE SYSTEM IDENTIFICATION
We define yk) (k 1) x; (R) and v.(k) ui(k 1) (k)).. Then (-BR) can be rewritten as
y(k 1)= =y + Bv(k).
In practice, it is expected that the best response dynamics (BR) should converge to Nash equilib- rium (Jackson 2010)). This is guaranteed by the condition (Ballester et al. (2006)) that p(G) 1, where p G) is the spectral radius. Moreover, in practice, G is typically a sparse matrix.
Let be the set stable matrices = i.e.. S == {A R=x" p(A) 1}. When observations of the x(k) (and thus, yk)) are subject to the influence of noises,
y T (k) y(k)) e

---

Under review as a conference paper at ICLR 2022
will be the actually observed actions, where e₁ R k ....., are stationary random noises with zero mean and co-variance Sn. So the adversary has access to
Z (1m (2)
y (T)]:
(5)
Y (0) (1)
y (T 1)];
V [v(0) v(1) v(T 1)].
We propose the following Stable Sparse System Identification (SSSI) for learning the network struc- ture G from full player action observations:
SSSI:
Gessi arg inf
- -YY- - BV +||G|||
GES
3.2
INFORMATION
ALGORITHM
As S is open and nonconvex set, solving recently developed algorithm for stable system identification in JJogennee al. (202I), where an Cnormatioon-teoreee projection onto S was used soften the computational complexity by solving Riccati equations. This leads to the following algorithm.
numerically challenging. We propose adopt the
Algorithm 1: Informatioo-theorrtie Projection SSSI Algorithm
Input: Z, V,
Output: Network graph structure G Solve the regularized least square solution
G
arg min 2 -Y BV [3 G|
(9)
Random generate 8 2 0;
Solve the algebraic Riccati equation (DARE) with the unique solution Ps:
P=I- GT PPP (268.))²)) 'PG
"
(10)
Compute Lg (Ps (268.))1)-
Return Gsssi G + Lg.
NETWORK LEARNING WITH PARTIAL ACTIONS
In this section, we develop framework for learning the network structure G from the information generated by (p-BR) with partial action observations, i.e., the of players that the adversary can observer actions O is only subset of the overall player set V.
4.1 REFINED MARKOV PARAMETER EQUATION
Recall that w(k) is the vector representing the collection of the observed actions {x, e OH generated from (p-BR) at time k. Defining z(k) w(k + 1) w(k), Z, Zp V, V, as the
block Hankel matrices that can be constructed from the sequences {z(k), = 0, O,..., T 1} and
(v(k), O...., T 1}. the Markov parameter equation (4 can be equivalently reformulated as follows:
Z, O, On G.. G"OO V
V +TV,
(11)
= 2. V V, + T.V.
This refined Markov parameter equation directly connects the network structure with the data accessible by the adversary.
4.2 NETWORK LEARNING BY STABLE AND SPARSE SUBSPACE IDENTIFICATION
Again, when the observations of the players' actions w(k) (and thus, z(k)) are masked by noises in practice, (k) z(k) + e₁ will be the actually observed action differences. The adversary has

---

Under review as a conference paper at ICLR 2022
access to
mm 2
-(
H((oor-1)-
We are ready to propose the following Stable and Sparse Subspace Identification (SSSubl) learning framework.
Algorithm 2: Network Learning by Stable and Sparse Subspace Identification
Input: Z Zy, Vp. Vs, C,B
Output: Network graph structure G
From II carry out classical subspace identification [Ref], and produce T, as an optimal
estimate for Tn:
Take M; as the (1 (++2 2, 1) block entries for Th for = O,.... 2, and then solve
Gsssubl arg min
CG'B - G|G
Return Gsssubi.
When solving GSssubl. again we can first solve
G = arg min GeREXN
JCG 2 M + G|G
(12)
and then the information-theoreii projection in Jongeneel al. (2021) to project G onto S.
NUMERICAL VALIDATIONS
In this section, we provide numerical examples to validate the two proposed learning frameworks. For reproduction of the reported results, all source codes have been provided in the supplementary material.
5.1 FULL ACTION OBSERVATIONS: STABLE AND SPARSE SYSTEM IDENTIFICATION
In this section, we examine the performance of Algorithm 1 on three types of synthetic networks generated using the Erdös-Rényi (ER), the Watts-Strogatz (WS) and the Barabási-Albert (BA)
models. The networks under evaluation have n = 100 nodes.
Network setup. In the ER graph, each link takes place with probability Per 0.1 independently with all the other links; in the WS graph, each node's average degree and the random rewiring process is set to be kiss = 5 and pas 0.2, respectively; in the BA graph, a new node each time step is created to connect to Maa 2 existing nodes via preferential attachment. After the realization of each graph, nonzero random number selected between -5 and as the weight for each link. Each entry of the adjacency matrix G is then divided by its largest absolute value of its cigenvalues to ensure the stability G.
Data synthesis. A set M representing action-compromised players is selected and matrix B created according to (2). We then generate x(0). u(k). = 0, 0....,Z ,T, and a by considering x(0), u(k), a (0,0 I), and simulate the dynamics (p-BR) obtain x(k), k 1, 1..... T. The ob- servation noises follow normal distribution e₁ ~ * (0. I) where & represents the noise intensity level. Upon Eq. 5 -
finally obtain three matrices Z, Y.V. V.
Experiment. We apply Algorithm to the respective settings and compare the outcomes against the ground truth by relative error
Ggsss Grrutulle
Err
(13)
|Grrubblll ||
We also implement two other baseline approaches: the stable least square (SLS) and stable L2- regularized least square (SL2LS), which are described in Appendix F. For SSSI and SL2LS,

---

Under review as a conference paper at ICLR 2022
provide the results using the parameters and / that yield the greatest average performance across 50 randomly generated graph instances.
Results. First and foremost, performance. We fix noise level to be Ş = 0.1, use different values of {15, 20, 25, 30, 35, 40 and follow the aforementioned data generation process. The learning performance of the three methods versus trajectory length on the ER, WS, BA networks illustrated in Fig. | We next examine the robustness of the three methods in the face of various levels of noise during the observations. Let the trajectory length be T = 40 and the noise intensity level take values in Ç {0.05, 0.1, 0.15, 0.2, 0.25, 0.3}. The learning performance of the three methods versus noise intensities on the ER, WS, BA networks is shown in Fig. 2 Clearly in terms of reconstructing the weights for the groundtruth links, the SSSI outperforms the other two baseline methods significantly. Moreover, the BA networks appear to be more difficult to learn under SSSI in all cases, compared to the ER graphs and WS graphs.
to discover how the the trajectory length affects the learning
Erdos-Renyi
Watts Strogatz
Barabasi-Albert
1.0
1.0
1.0
Relative error
0.8
Relative error
0.8
0.4
0.4
3551
5551
5551
SLS
15
20
25
30
40
20
30
35
40
15
20
25
30
35
40
T
(a) Erdos Renyi
(b) Watts Strogatz
(c) Barabasi Albert
Figure 1: The relative errors from SSSI, SLS, SL2LS versus trajectory length over the ER, WS and BA networks.
Erdos-Renyi
Watts Statts-Strogazz
Barabasi-Alberr
1.0
1.0
1.0
0.8
Relative error
0.8
Rolative error
0.8
0.8
0.4
0.4
S561
SLS
0.05
0.1
0.15
0.2
0.25
0.3
0.05
0.1
0.15
0.2
0.25
0.3
0.05
0.1
0.15
0.2
0.25 0.3
noise level
noise level
noise level
(a) Erdos Renyi
(b) Watts Strogatz
(c) Barabasi Albert
Figure 2: The relative errors from SSSI, SLS, SL2LS versus noise intensity level over the ER, WS and BA networks.
5.2 NETWORK LEARNING WITH PARTIAL ACTIONS: SUBSPACE IDENTIFICATION
In this section, we evaluate the performance Algorithm 2 on the ER, WS and BA networks. In particular, since the Step subspace identification has been established approach (Van Overschee & De Moor (2012). ) we focus our attention on the effectiveness of Step 2. The networks used for experiments are of the size of 10 nodes.
Network setup. We follow the network setup process in Section 5.] to obtain the adjacency matrix G. where Per 0.2, kwss 2, Pvs 0.2 and 1ib
8

---

Under review as a conference paper at ICLR 2022
Data synthesis. Two sets O, M representing the action-leaked and action- corionn-ompommieed players selected, from which C, B are obtained based on (3) and We compute M7. ....., , 2, directly from the ground truth of G, C.
Experiments. The metric for learning performance evaluation continues to be the relative error described in (33 The benchmark is set to be stable subspace identification (SSubl) described in Appendix F.2 which obtained by removing the the L regularization from (SSSubl). We report the results using 7 that leads the best average performance across 20 randomly created graph instances.
Results. The relative emrors from SSSubl and SSubl over the ER, WS and BA networks de- picted in Fig. 3 We see that SSSubl indeed provides better accuracy than SSubl in inferring the network structure in all network types. Again, the BA networks are apparently more difficult to learn compared to ER and WS networks.
SSSubl
Relative error
0.6
0.0
W5
BA
Network type
Figure The relative errors from SSSubl and SSubl over the ER, WS and BA networks.
CONCLUSIONS
We have studied the problem of learning the interaction network structure from dynamic played ac- tions of the players from the perspective of an adversary, who may strategically perturb the decisions for a set of action-compromised players, and observe the sequential decisions from a set of action- leaked players. Results characterizing the learnability of the interaction graph by the adversary were established, where key insights came from classical system identification theories. Two learning frameworks were proposed for fully and partially player actions, respectively, for which numerical examples validate their usefulness. This work opened the doors for learning the underlying interac- tion graph from fictitious plays in network games. Future work may include extensions of this line of research to network games with general payoff functions, and applications of the work to the real world.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Coralio Ballester, Antoni Calvó-Armengol, and Yves Zenou. Who's who in networks. wanted: The key player. Econometrica, 74(5):1403-1417, 2006.
Marco Barreno, Blaine Nelson, Anthony Joseph, and J Doug Tygar. The security of machine learning. Machine Learning, 81(2):211-148, 2010.
Alexandre Bazanella, Michel Gevers, and Julien M Hendrickx. Network identification with partial excitation and measurement. In 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 5500-5506. IEEE, 2019.
Lucio Bianco, Massimiliano Caramia, Stefano Giordani, and Veronica Piccialli. A game-theoretic approach for regulating hazmat transportation. Transportation Science, 50(2):424-438, 2016.
Cristina Bicchieri. Rationality and game theory. The Oxford handbook of rationality, pp. 182-205, 2004.
Alessandro Chiuso and Gianluigi Pillonetto. System identification: A machine learning perspective.
Annual Review of Control, Robotics, and Autonomous Systems, 2:281-304, 2019.
Erick De la Rosa and Wen Yu. Randomized algorithmss for nonlinear system identification with deep learning modification. Information Sciences, 197-122, 2016.
Xiaowen Dong, Dorina Thanou, Michael Rabbat, and Pascal Frossard. Learning graphs from data:
A signal representation perspective. IEEE Signal Processing Magazine, 36(3):44-63, 2019.
Jerome Friedman, Trevor Hastie, and Robert Tibshirani. Sparse inverse covariance estimation with the graphical lasso. Biostatistics, 933):4324441 2008
Drew Fudenberg, Fudenberg Drew, David K Levine, and David K Levine. The theory of learning in games, volume 2. MIT press, 1998.
Vikas Garg and Tommi Jaakkola. Learning structured potential games. Advances in Neural Information Processing Systems, 29: 1951-5215 2016.
Vikas K Garg and Tommi Jaakkola. Local aggregative games. In Proceedings of the 31st Interna- fional Conference on Neural Information Processing Systems, pp. 5347-5357, 2017.
Asish Ghoshal and Jean Honorio. Learning graphical games from behavioral data: Sufficient and necessary conditions. In Artificial Intelligence and Statistics, pp. 1532-1540. PMLR, 2017.
Asish Ghoshal and Jean Honorio. Learning sparse polymatrix games in polynomial time and sample complexity. In International Conference Artificial Intelligence and Statistics, pp. 1494-
PMLR, 2018.
Manuel Gomez Rodriguez, David Balduzzi, and Bernhard Schölkopf. Uncovering the temporal dynamics of diffusion networks. In Proceedings the 28th International Conference Interna- tional Conference on Machine Learning, pp. 561-568, 2011.
MS Grewal and Keith Glover. Identifiability of linear and nonlinear dynamical systems. IEEE Transactions on automatic control, 21(6))833-837, 1976.
Jean Honorio and Luis E Ortiz. Learning the structure and parameters of prgeepppulation graphical games from behavioral data. J. Mach. Learn. Res., 16(1):1157-1110, 2015.
Matthew O Jackson. Social and economic networks. Princeton university press, 2010.
Wouter Jongeneel, Tobias Sutter, and Daniel Kuhn. Efficient learning of linear dynamical system with stability guarantees. arXiv preprint arXiv:2102.0366 2021.
Yan Leng, Xiaowen Dong, Junfeng Wu, and Alex Pentland. Learning quadratic games networks. In International Conference on Machine Learning, pp. 5820-5830. PMLR, 2020.
Michael L Littman. Markov games as a framework for multi-agent reinforcement learning. In
Machine learning proceedings 1994, pp. 157-163. Elsevier, 1994.
10

---

Under review as a conference paper at ICLR 2022
Lennart Ljung.
System identification. In Signal analysis and prediction, pp- 163-173, Springer,
1998.
Cyrus Colton MacDuffee. The theory of matrices, volume 5. Springer Science & Business Media, 2012.
Dusit Niyato and Ekram Hossain. Competitive pricing for spectrum sharing in cognitive radio net- works: Dynamic game, inefficiency of nash equilibrium, and collusion. IEEE journal on selected areas communications, 26(1) ): 1912:220000000 202, 2008.
Stéphane Ross and Andrew Bagnell. Agnostic system identification for model-based reinforcement learning. In Proceedings of the 29th International Coference International Conference Machine Learning, pp. 1905-1912, 2012.
Ravi Sen and Ruth C King. Revisit the debate on intermediation, disintermediation and reinterme- diation due to e-commerce. Electronic Markets, 13(2):153-162, 2003.
Yanning Shen, Brian Baingana, and Georgios Giannakis. Kernel-baeed structural equation models for topology identification of directed networks. IEEE Transactions on Signal Processing, 65(10): 2503-2516, 2017.
Peter Van Overschee and BL De Moor. Subspace identification for linear systems: The- ory camplemmnntaioon-ppliiceei
Springer Science & Business Media, 2012.
Henk J van Waarde, Pietro Tesi, and M Kanat Camlibel. Topology identification of heterogeneous networks: Identifiability and reconstruction. Automatica, 123: 12::109331, 2021.
John Von Neumann and Oskar Morgenstern. Theory of games and economic behavior. Princeton university press, 2007.
W.M. Wonham. Linear Multivariable Control: A Geometric Approach, volume 10. Springer-Veite Verlag New York, 1985.
Chengpu Yu, Lennart Ljung, Adrian Wills, and Michel Verhaegen. Constrained subspace method for the identification of structured state-space models (cosmos). IEEE Transactions on Automatic Control, 65(10))4201-422 2019.

---

Under review as a conference paper at ICLR 2022
A BLOCK HANKEL MATRICES
For time sequence s(k) E R" k == =, O..... T. collection of samples from time & to time + / is denoted as Sui++ == [s(k) s(k+1) 1)
s(k + 1)] Take = + 2n. A block Hankel
matrix of the sequence S is defined as
s(O)
s(1)
s(2)
s(h-1) 1) s(h)
s(1)
s(2)
s(3)
: s(n + h - 2) s(n + 1)
s(n 1)
s(n)
s(n 1)
H H(SOTT-1
s(n)
s + +1
2
s(n +1
s(n ( 2)
s(n +3)
s(n + h)
: -TT-1) 1)
s(2n - 1)
s(2n)
s(n 1)
Sp
S
The block Hankel matrix of Sujr is defined as
St p
H(S r) =
S
B PROOF OF THEOREM
Regarding the action dynamics described in (p-BR), we define the action difference and the pertur- bation difference (kk) := (k + 1) (k) and v.(k) u 1) u,(k) respectively, in order to eliminate the effect of marginal benefit o; in learning graph structure G.
Adding the observation ports to the action dynamics (p-BR), we arrive the compact form of an input-output linear invariant system:
y(k + 1) = Gy(k) + Bv(k), z(k) Cy(k),
(14)
(k)], the input signal v(k) E RT, B E Raxm and C E ii The nonzero entries of matrices B and correspond to the set of action-compromised and action-leaked players. respectively. Hence, the adversary has a trajectory of the input/output T).
which the state y(k) :=
signal of this system (14 I == {v(+), (k),,
When O = V and M
0, (4) is degenerated as
(k+1) = y(k + Gy(k).
Then, the single trajectory satisfies
= GY,
where =
E RaxX and = (2), yT -1)] E gaxT.
This equation can be decoupled as several linear equations: G [2T]; Vi with [+] repre- senting the i-th column. Then, G is uniquely constructable from the trajectory 7 if and only if each
of these linear equations has unique solution, i.c.. rank(Y) rank([] [2 11]) n, vi.
Note that Y = (y()), (()....., - 1)] = [y()), Gy(O). GT of which the vectors span G-cyclic subspace of g" denoted by H (0(); G). This subspace is an invariant subspace for G, in the sense that (y(); G) C H0)(0); G). which validates rank(Y)) = rank([Y 1.)). Moreover, the condition rank(Y) holds if and only if (G, y()) is controllable.
Proposition 1 The following statements are equivalent:
1. (G,Y(0) is controllable;
12

---

Under review as a conference paper at ICLR 2022
2. The characteristic polynomial of G coincides with the minimal polynomial of G, and y(0) has nontrivial projections on to all generalized eigenvector of G.
Proof: We first prove "1 = 2". Suppose that (i), the minimal polynomial of G, termed m(t), is not equal to its characteristic polynomial, termed k(t); or (ii). (0) has zero projections one generalized eigenvector of G.
For the pair (()), we form the sequence of vectors
(0). Gy(O), G²y
and they reside in a G-invariant subspace P with dimension p. where p the degree of the minimal polynomial for vector y() with the linear operator G, termed (t). Moreover, Sy (t) divides m(t). Interested readers are suggested to (MacDuffee 2012 Section VII-4) for the definition of annihilating polynomial and its property.
If (i) holds, i.c., m(t) * x(t), then the degree of m(() is less than n as m(t) divides x(t), and further the degree of (tt) satisfies p < n. Then (a))( Gy), = p < n and (G. y()) is uncontrollable. Obviously, if (ii) holds, the dimension of the G-invariant subspace IP satisfies and further (G. (()) is uncontrollable.
We next prove "2 = 1". Denote the set of distinct eigenvalues of G as (G) with cardinality g- Given an eigenvalue Åę its geometric multiplicity, termed μ4, is equal to since m(() = x()), and its algebraic multiplicity is equal to its multiplicity in the minimal polynomial mll) is denoted by r.
with Di= T3 T7==1 n.
Let ex.ú denote the generalized eigenvectors of rank j (1 S S r;) corresponding to G and its eigenvalue \; E (G). From statement 2, we have that
g
y(0)=
Σ 1=1
E,
axur CASyr 10N.r--1A,mm-1 +... +0,,1
with nonzero a' i vector, have
1,...,9I5 = , According to the definition of generalized eigen-
E. Σ j=1
Σ axy (G Xx1) Dextr
with nonzero matrix D. Note that and G commute, and hence the minimal polynomial of vector E, termed SE, (t), is equal to the minimal polynomial of vector ex..o. termed Sexu.r (t) = (t- T
Since the minimal polynomials for vectors E; and E, with j & i coprime, according to (MacDuffee 2012 Section VII-4, Lemma in Page 181), the minimal polynomials for vectors (0) equal the product of ÇE. (t), i = 1,....g. Hence, the degree of Cy(o) is p >i= T; n, which implies the controllability of the pair (G,y
C PROOF OF THEOREM 2
When O V and M + 0. is degenerated as
z(k: + 1 y(k + 11 Gy(k)+ Bv(k).
Setting v/+) = Ky (k), there holds
ykk + 1) BK)y(k))
According to Theorem G can be uniquely determined by the adversary from one single trajectory I if and only if (G + BK, y0)) is controllable.
Then, the proof of Theorem can be complemented by the following lemma (Wonham 1985 Lemma 2.2), and the proof is omitted here.
Lemma Let + y(0) E Im(B). If (G, is controllable, there exists K such that (G + BK, (0)) is controllable.
13

---

Under review as a conference paper at ICLR 2022
D PROOF OF THEOREM
Consider the input sequence Vorr-1 and output one Zorr-1 of (14, and construct the correspond- ing block Hankel matrices, introduced in Section 2.1.2, termed Vp V.. Zp Zy. Then, we reformulate the state-space model in (14) as follows:
= O, No TwV,
(15)
where the observability matrix On and the convolution matrix Tn are defined in Section 2.1.2, spectively. Throughout the article, it is stipulated that the dimension parameter T+1 > 3n such that the Hankel matrices z and y have more columns than rows. Note that in (15) the term Y n//7-n unknown to the adversary. Hence, we hope to construct wIT-> from the past input-output data streams, and utilize it to establish equation of G totally based the input-output data streams.
First, consider the past output sequences constructed as follows
Zp = On YoJT 1 2n + Tn V
similar to 15
When the observability matrix On has full column rank, the state sequence Y >Ir-nn can be repre- sented as
Y T-n Y 0 2n C. V = + Cnn G"O Vp.
where Cn the reversed controllability matrix.
Replacing Y n in 15 by the above representation, we obtain that
Z = O, GO + On CC. GO V + TaV,
(16)
By now, the adversary construct (16) from the single trajectory I. Then, the sufficiency and necessity Theorem can be casily derived from [16).
E DEFINITION OF INDISTINGUISHABLITY AND PROOF OF THEOREM
By introducing the action and perturbation difference, we obtain the state-space form (4 of the perturbed game play (--R).. Let Zv.y. and ( denote the trajectories of z(k), k 0, 1,... of two different systems of the form (14). where the subscripts emphasize the dependence on the perturbation difference v(-). the initial states yo, Vo, and the topology matrix G, G, respectively. We introduce the following definition.
The topology matrices and G are indistinguishable if there exist initial conditions Yo. Vo R such that
Definition
Zv.oo.()) Zv.so.(()
for all injected perturbation difference v.
Clearly, the indistinguishabiiiy defined above points to infinite trajectories of I as it is concerned with all possible initial player actions and perturbation sequences. Obviously, the topology of the linear-quadratic network game said to be learnable if G and G are distinguishable for all real G G.
To prove Theorem 4, we give the following two statements
Lemma A pair of parameter values (G, G) indistinguuishable if and only if the Markov param- eters satisfying:
CG B = C. 0,,,,
(17)
'The proofs of I Lemma 2 and Lemmas 3-4 are inspired by and adopted from the proofs for system identifia- bility in Grewal Glover (976)) and van Waarde al. (02T)) respectively.
14

---

Under review as a conference paper at ICLR 2022
Proof: We first prove the sufficiency. If 17 holds, then the output trajectories of two systems 14 associated with (G, G) satisfy that when yo Yo-
R-1
yo. = z(kk CG +
Σ
CG' Z c..
t=0
for all vkk E R" and for k 2 0. According to Definition indistinguishable.
the topology matrices G and G are
The necessity proved as follows, Assume (G, G) are indistinguishable, then there exist initial conditions yo, Yo s.t.
k-1 CG --) cG + Σ CG'
1-
holds for all input functions v and for all k 2 0. It implies that
CG yo cG* wk 2 0,
(18)
and
Σ CCG'B-C''BlyC - =)
(19)
Hence, if yo and Yo are set zero vectors, then (18) holds for all k, which implies the existence of Yo and yn. Since v(.) E Th has a nonempty interior, (99 means that
CG'B CÂ'B, A/ 0,
Hence, the indistinguishabiliy implies that at different values of the parameter G, the Markov pa- rameters of the system CG B are identical.
Lemma 3 If the topology G is learnable, then (G, B) is controllable and (G, C) is observable.
Proof: Suppose (G, B) is uncontrollable. Let E Rn be a nonzero vector in the uncontrollable subspace of (G, B), i.e.,
U JG 0, vk 0, 1,...
Given topology matrix G, we can construct G G + vo satisfying that
G = G + oo j + vu T BB = [G + ov ]
GB JGB
[G ov T [ + vo JGB
[G + vo T
GBB.
Hence, we have CG'B C,'B, YI 0,1,... but G * G. It implies the topology is not learaalle according to Lemma 2
The proof for necessity of observability of (G, C) is analogous to the above and is omitted here.
Lemma 4 If the topology G is learnable, then rank(B)
rank (C)
Proof: Suppose that rank(B) < and rank(C) < Then there exist nonzero vectors E TR such that Cv and B define matrix A = 1 + vu. Its inverse - exists according to Sherman-Morrison formula with A11=1
Without loss of generality, we assume u T * -1. Next, we
7+
construct G == G which satisfies CG'B C B for all / = 0, I,... Then, according to Lemma 2 the topology G is not learnable.
Given topology matrix G,
Proof of Theorem 4: The transfer function (z(2) can be expanded as follows:
+00
Fo(2) = - GB Cs- -1
(a
G
k=0
15

---

Under review as a conference paper at ICLR 2022
Hence, (17) in Lemma 2 can be equivalently stated Fa(z) FQ(z), which concludes the learn- ability of in terms of the transfer function.
Next, prove the learmability condition in terms of matrices G, B and C.
Sufficiency: Suppose rank = 7t and (G, B) controllable. is sufficient to prove that for a pair of parameter values (G, G) F& (z) = F (2) holds and only if G = G.
Consider two topology matrix G, G with difference A = G G. Suppose Fa(2) = (z) As C has full column rank, we have
(=l - Pa())) A G)B
(k+1)
AG*B =0
-
k=
As -k++1 is nonzero, it is derived from the above that
AG O, vk. 0,1,...
(20)
Since (G, is controllable, (20) holds and only if A is zero matrix, which shows G G. The proof for case (i.e., full row rand of matrix B and observability of (G, CJ) is analogous the above and is omitted here.
Necessity: These can be obtained directly from Lemmas 3 and 4
F BASELINE APPROACHES
F.1 BASELINES IN SECTION 5.
The method of stable least square (SLS) is defined by the optimization problem
inf GEs ? || GY--VV
(21)
The method of stable Lg-regularized least square (SL2LS) solves
}
inf GES
l - GY BV G|G
(22)
Solving Eq. 21 and (2 numerically challenging. We propose to solve G = arg ming -
GY - BV F and GSLAL = arg ming 11 - GY 2 -BVI + + and project them to their
nearest stable ones by applying Eq. (10).
F.2 BASELINE SECTION 5.2
The method of stable subspace identification (SSubl) is posed by solving the following problem
inf GES
(CG'B-Mi18..
(23)
We first compute Gssubl argming Er= | Mf and then follow Eq. 10 project
to its nearest stable matrix.
16


Reviews:
[{"review_id": "wWDG6G9AMdR", "reviewer": "Reviewer_2igb", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: The model is quite interesting and I think the model has a lot of potential. The methods used are non-trivial and the results are quite surprising and general.\n\n \n\nWeaknesses: The paper is not very accessible.\nHow can all components of G be uniquely determined? That is, how can one distinguish between G_1  with g_{1,2}=5 and all other entries are say 1 or 10000 and G_2 which is the same but g_{1,2}=4.999?\n\nWhy was the name controllable chosen?\nWhat do you mean by the indexes are sorted (besides the obvious)?\nThe authors spend no time giving intuition behind the theorems and since the proofs are not part of the paper, I cannot vouch for the correctness.  \nWhat does a \"trajectory\" mean in your setting?\nNotation (G, vector) \nNotation Im(B) unclear ", "summary_of_the_paper": "The authors study a game theory problem in linear quadratic games (family of payoffs) with the following assumptions\n1) players are assumed to use the best-response strategy \n2) an adversary can observe a subset of the nodes' actions\n3) an adversary can modify the wards for a subset of the players\n4) one part of the payoff function that is governed by a matrix G and models the non-marginal payoffs i.e., the part of the payoff that is a function of the actions taken by the other agents.\n\n\nThe authors study under what circumstances G can be learned. \nOne result is that that under some mild assumptions when the adversary can observe all players agents, then G can be learned.  \nThe authors show for more settings necessary and sufficient conditions for learning G. The authors also perform some simulations on random graphs.", "summary_of_the_review": "Seems like a very nice paper, but not accessible enough for me to understand all the details.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "n5eukSDBC-", "reviewer": "Reviewer_YLLb", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I do not believe the paper is a good fit for ICLR for the following reasons:\n\n1. The authors' model is highly stylized and I was unable to see any connection to the type of applications and/or theoretical questions that are relevant to ICLR. [For instance, the role of the \"overseeing adversary\" is never explained, nor the player dynamics, nor the specific game model] Even though the paper cites some papers that have appeared in ML venues and seem to be relevant, there is no denying that the core of the paper lies in control theory (or, possibly, econometrics). In particular, the authors do not attempt to provide _any_ intuition or motivation for many of the notions that they employ (for instance, the notion of \"controllability\"), so the paper would be inaccessible to the wider ICLR community.\n\n1. In addition to the above, the paper suffers from imprecise writing, to the extent that the main theorems are impossible to parse. For example, Theorems 1 and 2 state that \"$G$ can be uniquely determined by the adversary for sufficiently large $T$\" if and only if a certain condition holds. But what does \"uniquely determined\" mean in this context? What algorithm is the adversary following? One of the algorithms described in Sections 3 and 4? If so, the corresponding theorems should be stated as guarantees for the algorithms in question (and the paper completely rewritten accordingly); if not, what is the notion of \"learnability\" that the authors refer to, and what is the role of $T$? Likewise, what does \"access to infinitely many trajectories\" mean? The adversary is assumed to be able to maintain a variable with infinite memory?\n\n1. The authors make no attempt to explain whether the conditions provided in Theorems 1-4 are light or stringent, and they likewise provide no intuition as to what they mean for the underlying game. The notion of controllability is classical in control theory, but this does not shed any insight on what this actually means for the system at hand, and the authors make no effort to explain any of this. [Incidentally, this further reinforces my belief that this paper is more appropriate for a control venue like CDC, and not ICLR.]\n\nI do not think that the above can be fixed with a revision in a few days, hence my \"strong reject\" score. The authors should not interpret this as a critique on the worth of their results, but as an indication of (a) the suitability of this paper to the ICLR community at large; and (b) the level of rewriting that would be required to make the paper accessible to said community in the first place.\n### Specific remarks\n\nI am providing below a list of detailed remarks that could help the authors in an eventual resubmission /revision of the paper (irrespective of venue):\n\n1. The use of the term \"fictitious play\" is erroneous. Fictitious play means best-responding to the empirical frequency of the opponents' play, not to their last action (see the original papers by Brown and Robinson in the 50's). The (unperturbed) process considered by the authors is the best response dynamics considered by, e.g., Monderer and Shapley (1996), not fictitious play.\n\n1. The plural of \"equilibrium\" is \"equilibria\", not \"equilibriums\".\n\n1. The authors never define $g_ii$. Is it allowed to take any value? Is it assumed that the sum in (1) is only taken over $j\\neq i$ (which would give $g_{ii} = -1/2$)?\n\n1. The authors state in the beginning of Section 3 that the best response dynamics are expected to converge to Nash equilibrium, and that this is the case if $\\rho(G) < 1$ (Ballester et al., 2006). The authors subsequently seem to suggest that this occurs \"in practice\" because $G$ is sparse but I do not see what this has to do with the spectral radius of $G$: the matrix $g_{1,n} = g_{n,1} = 1$ and $g_{ij}=0$ otherwise is as sparse as it can get, but its spectral radius is $1$.\n\n1. What does \"random generate $\\delta$\" mean in Algorithm 1? And if the algorithm is stochastic, how does it connect to the (presumably) deterministic Theorems 1-4?\n\n1. Line 1 in Algorithm 2 is also problematic: what does \"carry out classical subspace identification\" mean, and how is this implemented?\n\n", "summary_of_the_paper": "In this paper, the authors consider quadratic network games with payoff functions of the form\n$$\nJ_i(x_i;x_{-i}) = \\alpha_i x_i - x_i^2/2 + \\sum\\nolimits_{j=1}^{n} x_i x_j\n$$\nwhere $\\alpha_i>0$ denotes the marginal benefit of the $i$-th player from playing $x_i \\in \\mathbb{R}$, and $g_{ij}$ is a matrix of interactions that determines whether players $i$ and $j$ are adversaries ($g_{ij}<0$), friends ($g_{ij}>0$), or non-interacting ($g_{ij}=0$).\n\nThe authors assume that players follow a \"perturbed\" best-response model of the form\n$$\nx_i(t+1) = \\arg\\max\\nolimits_{x_i\\in\\mathbb{R}} J_i(x_i;x_{-i}(t)) + u_i(t+1)\n$$\nwhere $u_i$ is a perturbation that affects only a subset $M$ of \"manipulable\" players (possibly empty).\n\nThe authors are interested in conditions under which the underlying interaction matrix $G=(g_{ij})_{i,j=1,\\dots,n}$ can be learned from the outcome of the players' learning process. In this regard, they provid the following results:\n\n1. If all player actions are observable, $G$ is learnable from a single trajectory of play if and only a certain matrix involving $x(1) - x(0)$ is controllable (Theorems 1 and 2; the condition in Theorem 2 involves a non-empty set of manipulable players and is less stringent).\n\n1. If only a subset of players are observable, $G$ is learnable from a single trajectory of play if and only if a certain Markov equation admits a unique solution (Theorem 3).\n\n1. Finally, if the learner has access to infinitely many trajectories, $G$ is learnable if and only if two pairs of matrices are controllable / observable.\n\nTwo algorithms for identifying $G$ are described in Sections 3 and 4 with full partial action observations respectively (though it was not clear to me what the exact relation is with respect to Theorems 1-4). Finally, in Section 5, the authors provide a series of numerical validation results over different random network structures (Erdős-Rényi, Barabasi-Albert,etc.).\n\n\n", "summary_of_the_review": "I do not believe the paper is a good fit for ICLR for the following reasons:\n\n1. The authors' model is highly stylized and there is no connection to the type of applications and/or theoretical questions that are relevant to ICLR.\n\n1. The paper suffers from imprecise writing, to the extent that the main theorems are impossible to parse.\n\n1. The authors make no attempt to explain their results and the connections of the required conditions to the underlying game.\n\nThis paper could be a good fit to a control theory conference like CDC, but not ICLR.\n\n---------------\nPost-rebuttal\n---------------\nI have read the answers of the authors.  Unfortunately, I am not convinced and I will retain my original score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Z3y1jy8_GPN", "reviewer": "Reviewer_Zoba", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- Strengths:\n  - Learning the structure of games of this type has attracted some attention recently and using fundamental concepts from control theory (observability and controllability of a linear system) is an interesting view of this problem. \n -  The fact that the adversary may have a partial observation of the actions of the agents can be quite relevant in practice and does not seem to have been explored in previous work. \n\n- Weaknesses: The paper has some technical issues; more specifically :\n   - The title of the paper is misleading, as the paper examines the case where all players play the best response (Fictitious play usually denotes a strategy where each player plays the best response to the \"average\" strategy observed from her opponents). \n  -  The setting is very specific, as only best response dynamics are treated (in principle, agents may use other learning algorithms). In addition, the authors mention that \"In practice, it is expected that the best response dynamics (BR) should converge to a Nash equilibrium\", however this is generally not the case (even if the NE of a game is unique) - the authors should provide a reference or prove that in this particular game BR converges to a NE. \n   -  The ability of the adversary to affect / perturb the agents' actions seems arbitrary and needs to be motivated. In addition, the effect of this ability is never really explored in the paper (can it, for example, offset partial observability?).\n   -  Similarly, the fact that $G$ is usually sparse is nowhere motivated.   \n   -  Theorem 2 seems to hold only for the case where the adversary can also purturb the actions of all agents (in addition to having full observability). \n   -  Theorem 4 seems just a direct application of van der Waarde et al. (2021)\n\n- Other comments: \n   - The authors mention that they consider a \"setting of dynamic game\" (\"Related work\" paragraph, Section 1.4), however this is not true; the game under consideration is a repeated game, where agents follow best response dynamics. \n   -  It is unclear what is the connection of Sections 3 and 4 to Section 2: the theorems proved in the latter section do not seem to be used in any way.   \n   -  In Section 4.2 it is mentioned that the observation of the actions of the players is \"masked by noise\" - however, noisy observations are not mentioned before.  ", "summary_of_the_paper": "The paper addresses the problem of an adversary learning the structure (i.e. coupling matrix $G$ among agents in the payoff) of a repeated game with quadratic payoffs where the agents are playing under best response dynamics and the adversary can potentially observe the actions of only a subset $O$ of players and also affect the action of another subset $M$ of players. The authors give conditions for which $G$ can be recovered, depending on the sets $O$ and $M$, when a single trajectory or multiple trajectories of the game are available. In addition, they give algorithms for the cases where all and part of the actions are observable and $G$ is a sparse matrix. ", "summary_of_the_review": "Application of concepts of control theory in learning the structure of a game with linear-quadratic payoff may be interesting, especially in the case of partially observable actions, however the setting of this paper seems specific without being very well motivated, there are some technical errors and not well supported arguments and the paper reads somewhat incoherent. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors consider linear quadratic network games (also known as graphical games) and they discuss a number of conditions and procedures to learn the underlying graph of the game from observations of best-response trajectories (or possibly infinite sets thereof) in the game.

The reviewers' initial assessment was overall negative, with two reviewers recommending rejection and one giving a borderline positive recommendation. The authors' rebuttal did not address the concerns of the reviewers recommending rejection, and the authors did not provide a revised paper for the reviewers to see how the authors would implement the suggested changes, so the overall negative assessment remained.

After my own reading of the paper, I concur with the majority view that the paper has several weaknesses that do not make it a good fit for ICLR (especially regarding the lack of precision in the theorems and the statement of the relevant assumptions), so I am recommending rejection.
Decision: Reject