Year: 2021

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.

text: 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.

heading: 1 INTRODUCTION
text: Game theory has been playing a fundamental role in understanding how competition and rationality arise among decision makers, termed players (Von Neumann & Morgenstern (2007); Bicchieri (2004)). Players place individual decisions, for which the payoffs characterize their gains. The payoff of any player not only depends on her own decision, but also the decisions of all other players, 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 a result, at Nash equilibriums all players tend to stay at their current decisions, i.e., rationality takes place. The power of Nash equilibriums in explaining behavioral decisions, and the possibility of designing payoffs in shaping player decisions, have enabled game theory to be applied in a variety of disciplines solving problems ranging from route planning in transportation (Bianco et al. (2016)) and channel allocations in wireless communications (Niyato & Hossain (2008)) to online E-commerce (Sen & King (2003)) and security of machine learning (Barreno et al. (2010)).
The crucial insight in game-theoretical decision mechanisms, lies in the fact that players act according to their own payoff functions and other players’ decisions, holding no knowledge about other players’ payoffs. Since the payoffs might encode players’ preferences, economic status, and interpersonal relations, etc., it is of interest to investigate when and how payoffs of players can be learned from observations of player actions.

heading: 1.1 LINEAR QUADRATIC GAMES
text: A game can be associated with a graph, where the players are represented by nodes, and the interdependency among the players in payoffs defines links. In a network game with n players and linear-quadratic payoffs, each node (player) i ∈ V := {1, 2, . . . , n} selects her action xi ∈ R to
maximize payoff Ji described by
Ji = αixi − 1
2 x2i + n∑ j=1 gijxixj . (1)
In (1), the first two terms characterize the benefit of player i by setting her own action xi, where the parameter αi > 0 is called the marginal benefit, capturing the level of selfishness of player i. The last term of this payoff function reflects the peer effect suffered by player i from the actions of other players: if gij > 0, players i and j are strategic complements (friends or acquaintances); if gij < 0, players i and j are strategic substitutes (opponent or adversary); if gij = 0, there is no influence on player i from player j.
Let G ∈ Rn×n be the matrix formed by the gij , i.e., the ij-entry of G is gij . The interaction graph G = (V,E) underlying the game (1) is then defined as the induced graph of G, where a directed link (j, i) ∈ E if and only if gij 6= 0.

heading: 1.2 FICTITIOUS PLAYS AND ACTION-COMPROMIZED PLAYERS
text: For players participating in a game, Nash equilibriums can not be known or played immediately when the game starts since the payoff functions are held in private. Instead, in real-world the behaviors of players are better described in a sequential decision process (Littman (1994)). Let time be indexed at k = 0, 1, 2, . . . , T , and let player i hold decision xi(k) for time k. Then, it is reasonable to assume that any rational player at any given t will decide her next action as the decision that maximizes her payoff given other players’ current decisions. This is known as fictitious plays or best responses (Fudenberg et al. (1998)). As a result, in repeated plays for the linear-quadratic game, the dynamics of xi(k) obey
xi(k + 1) = arg max xi Ji(xi,x−i(k)) = αi + n∑ j=1 gijxj(k), i = 1, . . . , n. (BR)
In practice, players might be influenced or manipulated by an adversary in their actions. We term such players as action-compromised players, indexed in the set M ⊆ V. Then V \ M contains benign players who just follows (BR). For i ∈ M, we model the influence of the adversary as a perturbation ui(k) over the best response. The fictitious plays of the players in the presence of the action-compromised players become
xi(k + 1) = arg max xi Ji(xi,x−i(k)) + IM(i)ui(k)
= αi + n∑ j=1 gijxj(k) + IM(i)ui(k), i = 1, . . . , n. (p-BR)
where IM(i) is the indicator function: IM(i) = 1 if i ∈ M; IM(i) = 0 otherwise.

heading: 1.3 PROBLEM DEFINITION
text: For the adversary, it is easier and affordable to observe actions only from a number of action-leaked players. We let O ⊆ 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 to risks of being fully identified/learned by the adversary. To be precise, the adversary holds information
I : { ui(k), i ∈ M, k = 0, . . . , T }⋃{ xj(k), j ∈ O, k = 0, . . . , T } with the ui(k) and xi(k) being produced by (p-BR). The problems of interest from the perspective of the adversary lie in
• Learnability: Whether it is possible to uniquely determine G from I, perhaps with the help of strategically designed ui(k), i ∈ M, k = 0, . . . , T .
• Learning: How to build effective learning frameworks for estimating G from I, perhaps with prior structural information such as stability and sparsity.

heading: 1.4 CONTRIBUTIONS AND RELATED WORK
text: Contributions. The connection between the network learning problem in quadratic games and classical system identification theory is uncovered. The key insight is the observation that the unknown marginal payoffs do not play any role in the dynamics driving the difference between two consecutive player actions. As a result, we manage to establish a series of results characterizing the learnability of the interaction graph by the adversary: with full player action observations, the learnability is 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 parameters. Next, noting the inherent stability and sparsity properties for the network interaction structure, we propose a 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 (2017); Leng et al. (2020); Garg & Jaakkola (2016; 2017); 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 networks, 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 is different 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 as probabilistic graphical models (Friedman et al. (2008)), physically-motivated models (Gomez-Rodriguez et al. (2011)) and signal processing models (Dong et al. (2019)).
Technically, this work is built upon the results of linear system identification (Van Overschee & De Moor (2012); Ljung (1998)), in which measured input/output data are explored to build mathematical models of linear (network) systems, and even identify the system matrices or network structure under some structure and/or excitation conditions e.g., Bazanella et al. (2019); Yu et al. (2019); Shen et al. (2017). Recent 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 to network learning of games.

heading: 2 NETWORK LEARNABILITY FROM FICTITIOUS PLAYS
text: 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 to the system dynamics (pBR) 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.

heading: 2.1 LEARNABILITY BY SINGLE TRAJECTORY
text: For notational simplicity, we denote the aggregated action profile of all players and the overall injected perturbations at time k by x(k) := [x1(k), . . . ,xn(k)]> ∈ Rn and u(k) := [ui(k), i ∈ M]> ∈ Rm, respectively. We also denote the cardinalities of the sets M and O as m and l, respectively. Within these sets, the indexes of action-compromised and action-leaked players are sorted in ascending order with M := {p1, . . . , pm} and O := {q1, . . . , ql}. Introduce two matrices B ∈ Rn×m and C ∈ Rl×n to represent the sets of M and O. Specifically, the (i, j)-th entry of matrix B satisfies that
Bi,j =
{ 1, i = pj ;
0, otherwise. (2)
The (j, i)-th entry of matrix C satisfies that
Cj,i =
{ 1, i = qj ;
0, otherwise. (3)
From classical control theory (Wonham (1985)), the pair (G,B) is said to be controllable if the n× nm matrix (where the subscript n denotes the number of block columns)
Cn := [ B GB . . . Gn−1B ] has rank n; the pair (G,C) is said to be observable if the nl × n matrix (where the subscript n denotes the number of block rows)
On :=  C CG
... CGn−1  has rank n.

heading: 2.1.1 FULL PLAYER ACTION OBSERVATIONS
text: We present the following result showing that if the adversary has access to all players’ actions but has no ability to add action perturbations, namely O = V and M = ∅, the learnability of the network structure G can be precisely characterized by a special form of observability.
Theorem 1 Assume O = V and M = ∅. Let the adversary has access to one single trajectory of I 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, we can further prove that (G,x(1) − x(0)) 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 on to all generalized eigenvector of G (see more details in Proposition 1 of Appendix B). The next result characterizes the ability to learn G by feedback perturbations, namely u(k) = Kx(k) for K ∈ Rm×n.
Theorem 2 Assume O = V and M 6= ∅. Let the adversary has access to 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 6= x(1)− x(0) ∈ Im(B);
(ii) (G,B) is controllable.

heading: 2.1.2 PARTIAL PLAYER ACTION OBSERVATIONS
text: When O is only a subset of V, the learnability of G by the adversary becomes a much more challenging question.
Block Hankel Matrices. For a time series, the block Hankel matrices provide a way of representing the time evolution in compact forms, given by an operator H that maps the time series into block matrices Van Overschee & De Moor (2012) (see Appendix A). Let w(k) denote the collection of the observed actions {xi(k), i ∈ O} generated from (p-BR) at time k. The block Hankel matrices of the sequences W0|T , U0|T can be defined, respectively, leading to Wp,Wf from H(W0|T−1), W+p ,W + f fromH(W1|T ), Up,Uf fromH(U0|T−1), and U+p ,U + f fromH(U1|T ).
Convolution Matrix. The lower-triangular convolution matrix for the triplet (G,B,C) is defined as
Tn :=  0 0 · · · 0 CB 0 · · · 0 ... . . . . . . ...
CGn−2B · · · CB 0
 .
The reversed extended controllability matrix for a matrix pair (G,B) is defined as
Ĉn := [ Gn−1B . . . GB B ] .
Markov Parameter Equations. For any k, x(k) can be represented as a linear combination of the past observations {xi(s), s = 0, . . . , k − 1, i ∈ O} and the past perturbations {uj(s), s = 0, . . . , k − 1, j ∈ M} with s > 0. Consequently, the elements in the first column in matrix Tn (termed Markov parameters) must satisfy the following equation (see Appendix D):
∆Wf = OnGnO†n∆Wp +On [ Ĉn −GnO†nTn ] ∆Up + Tn∆Uf , (4)
where ∆Wf := W+f −Wf , ∆Wp := W+p −Wp and ∆Uf , ∆Up are defined similarly.
We are now ready to present the following result.
Theorem 3 Let the adversary has access to one single trajectory of I from (p-BR). Suppose (G,C) is observable and T ≥ 2n. Then G can be uniquely determined by the adversary if and only if the Markov parameter equation (4) admits a unique solution with respect to G.

heading: 2.2 LEARNABILITY BY INFINITE TRAJECTORIES
text: The transfer function of the perturbed best-response (p-BR) is defined as FG(z) := C(zI−G)−1B. Here z ∈ C, and FG(z) captures the relation between u and yu,x0,G in the frequency (z) domain. Inspired by the recent breakthrough on network system identification (van Waarde et al. (2021)), we present the following result. It 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.
Theorem 4 Let the adversary have access to infinitely many trajectories of 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
FG(z) = FG̃(z) for G̃ ∈ R n×n =⇒ G = G̃;
or equivalently, if and only if at least one of the following conditions holds:
(i) rankC = n and (G,B) is controllable;
(ii) rankB = n and (G,C) is observable.

heading: 3 NETWORK LEARNING WITH FULL ACTION OBSERVATIONS
text: In this section, we develop a framework for learning the network structure G from the information I generated by (p-BR) with full action observations (i.e., O = V).

heading: 3.1 THE FRAMEWORK: STABLE AND SPARSE SYSTEM IDENTIFICATION
text: We define yi(k) := xi(k + 1) − xi(k) and vi(k) := ui(k + 1) − ui(k). Then (p-BR) can be rewritten as
y(k + 1) = Gy(k) + Bv(k).
In practice, it is expected that the best response dynamics (BR) should converge to a Nash equilibrium (Jackson (2010)). This is guaranteed by the condition (Ballester et al. (2006)) that ρ(G) < 1, where ρ(G) is the spectral radius. Moreover, in practice, G is typically a sparse matrix.
Let S be the set of stable matrices in Rn×n, i.e., S := {A ∈ Rn×n : ρ(A) < 1}. When observations of the x(k) (and thus, y(k)) are subject to the influence of noises,
ym(k) = y(k) + ek
will be the actually observed actions, where ek ∈ Rd, k = 0, . . . , T are stationary random noises with zero mean and co-variance Sn. So the adversary has access to
Z = [ym(1) ym(2) · · · ym(T )] ; (5) Y = [ym(0) ym(1) · · · ym(T − 1)] ; (6) V = [v(0) v(1) · · · v(T − 1)] . (7)
We propose the following Stable Sparse System Identification (SSSI) for learning the network structure G from full player action observations:
SSSI : GSSSI = arg inf G∈S
1 2 ||Z −GY −BV ||2F + θ||G||1. (8)

heading: 3.2 AN INFORMATION-THEORETIC ALGORITHM
text: As S is an open and nonconvex set, solving (8) is numerically challenging. We propose to adopt the recently developed algorithm for stable system identification in Jongeneel et al. (2021), where an information-theoretic projection onto S was used to soften the computational complexity by solving Riccati equations. This leads to the following algorithm.
Algorithm 1: Information-theoretic Projection SSSI Algorithm Input: Z, Y, V,B Output: Network graph structure G
1 Solve the regularized least square solution
Ĝ = arg min G
1 2 ||Z −GY −BV ||2F + θ||G||1; (9)
2 Random generate δ ≥ 0; 3 Solve the algebraic Riccati equation (DARE) with the unique solution Pδ:
P = I + Ĝ>PĜ− Ĝ>P(P + (2δSn)−1)−1PĜT ; (10)
4 Compute Lδ = −(Pδ + (2δSn)−1)−1PδĜ; 5 Return GSSSI = Ĝ + Lδ .

heading: 4 NETWORK LEARNING WITH PARTIAL ACTIONS
text: In this section, we develop a framework for learning the network structure G from the information I generated by (p-BR) with partial action observations, i.e., the set of players that the adversary can observer actions O is only a subset of the overall player set V.

heading: 4.1 REFINED MARKOV PARAMETER EQUATION
text: Recall that w(k) is the vector representing the collection of the observed actions {xi(k), i ∈ O} generated from (p-BR) at time k. Defining z(k) = w(k + 1) − w(k), Zf ,Zp,Vf ,Vp as the block Hankel matrices that can be constructed from the sequences {z(k), k = 0, . . . , T − 1} and {v(k), k = 0, . . . , T − 1}, the Markov parameter equation (4) can be equivalently reformulated as follows:
Zf = OnGnO†nZp +On [ Ĉn −GnO†nTn ] Vp + TnVf (11)
: = ΦnZp + ΨnVp + TnVf . This refined Markov parameter equation directly connects the network structure G with the data accessible by the adversary.

heading: 4.2 NETWORK LEARNING BY STABLE AND SPARSE SUBSPACE IDENTIFICATION
text: Again, when the observations of the players’ actions w(k) (and thus, z(k)) are masked by noises in practice, zm(k) = z(k) + ek will be the actually observed action differences. The adversary has
access to [ Zmp Zmf ] = H ( Zm0|T−1 ) , [ Vp Vf ] = H ( V0|T−1 ) .
We are now ready to propose the following Stable and Sparse Subspace Identification (SSSubI) learning framework.
Algorithm 2: Network Learning by Stable and Sparse Subspace Identification Input: Zmp ,Zmf ,Vp,Vf ,C,B Output: Network graph structure G
1 From (11) carry out classical subspace identification [Ref], and produce T ?n as an optimal estimate for Tn; 2 Take M?l as the (l + 2, 1)-th block entries for T ?n for l = 0, . . . , n− 2, and then solve
GSSSubI = arg min G∈S n−2∑ l=1 ||CGlB−M?l ||2F + γ||G||1;
3 Return GSSSubI.
When solving GSSSubI, again we can first solve
Ḡ = arg min G∈Rn×n n−2∑ l=1 ||CGlB−M?l ||2F + γ||G||1 , (12)
and then use the information-theoretic projection in Jongeneel et al. (2021) to project Ḡ onto S.

heading: 5 NUMERICAL VALIDATIONS
text: 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.

heading: 5.1 FULL ACTION OBSERVATIONS: STABLE AND SPARSE SYSTEM IDENTIFICATION
text: In this section, we examine the performance of Algorithm 1 on three types of synthetic networks generated using the Erdős–Rényi (ER), the Watts–Strogatz (WS) and the Barabá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 is kws = 5 and pws = 0.2, respectively; in the BA graph, a new node at each time step is created to connect to mba = 2 existing nodes via preferential attachment. After the realization of each graph, a nonzero random number is selected between −5 and 5 as the weight for each link. Each entry of the adjacency matrix G is then divided by its largest absolute value of its eigenvalues to ensure the stability G.
Data synthesis. A set M representing action-compromised players is selected and a matrix B is created according to (2). We then generate x(0), u(k), k = 0, · · · , T, and α by considering x(0),u(k),α ∼ N (0, I), and simulate the dynamics (p-BR) to obtain x(k), k = 1, . . . , T . The observation noises follow a normal distribution ek ∼ ξ ∗N (0, I) where ξ represents the noise intensity level. Upon Eq. (5)-(7), we finally obtain three matrices Z, Y, V .
Experiment. We apply Algorithm 1 to the respective settings and compare the outcomes against the ground truth by relative error
Err := ||GSSSI −GTruth||F ||GTruth||F . (13)
We also implement two other baseline approaches: the stable least square (SLS) and stable L2regularized least square (SL2LS), which are described in Appendix F.1. For SSSI and SL2LS, we
provide the results using the parameters θ and β that yield the greatest average performance across 50 randomly generated graph instances.
Results. First and foremost, we are to discover how the the trajectory length affects the learning performance. We fix noise level to be ξ = 0.1, use 6 different values of T = {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 is illustrated in Fig. 1. 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.

heading: 5.2 NETWORK LEARNING WITH PARTIAL ACTIONS: SUBSPACE IDENTIFICATION
text: In this section, we evaluate the performance of Algorithm 2 on the ER, WS and BA networks. In particular, since the Step 1 subspace identification has been an 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.1 to obtain the adjacency matrix G, where per = 0.2, kws = 2, pws = 0.2 and mba = 1.
Data synthesis. Two sets O,M representing the action-leaked and action-compromised players are selected, from which C,B are obtained based on (3) and (2). We compute M?l , l = 0, . . . , n − 2, directly from the ground truth of G,C,B.
Experiments. The metric for learning performance evaluation continues to be the relative error described in (13). The benchmark is set to be stable subspace identification (SSubI) described in Appendix F.2, which is obtained by removing the the L1 regularization from (SSSubI). We report the results using γ that leads to the best average performance across 20 randomly created graph instances.
Results. The relative errors from SSSubI and SSubI over the ER, WS and BA networks are depicted in Fig. 3. We see that SSSubI indeed provides better accuracy than SSubI 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.

heading: 6 CONCLUSIONS
text: We have studied the problem of learning the interaction network structure from dynamic played actions 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 actionleaked 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 interaction 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.

heading: A BLOCK HANKEL MATRICES
text: For a time sequence s(k) ∈ Rn, k = 0, . . . , T , a collection of samples from time k to time k + l is denoted as Sk|k+l := [s(k) s(k + 1) · · · s(k + l)] . Take h = T + 1 − 2n. A block Hankel matrix of the sequence S0|T−1 is defined as
H ( S0|T−1 ) := 
s(0) s(1) s(2) · · · s(h− 1) s(1) s(2) s(3) · · · s(h)
... ...
... . . . ... s(n− 1) s(n) s(n+ 1) · · · s(n+ h− 2) s(n) s(n+ 1) s(n+ 2) · · · s(n+ h− 1) s(n+ 1) s(n+ 2) s(n+ 3) · · · s(n+ h) ... ... ... . . . ...
s(2n− 1) s(2n) s(2n+ 1) · · · s(T − 1)  := [ Sp Sf
] The block Hankel matrix of S1|T is defined as
H ( S1|T ) := [ S+p S+f ] .

heading: B PROOF OF THEOREM 1
text: Regarding the action dynamics described in (p-BR), we define the action difference and the perturbation difference as yi(k) := xi(k + 1) − xi(k) and vi(k) := ui(k + 1) − ui(k) respectively, in order to eliminate the effect of marginal benefit αi in learning graph structure G.
Adding the observation ports to the action dynamics (p-BR), we arrive at the compact form of an input-output linear invariant system:
y(k + 1) = Gy(k) + Bv(k), (14) z(k) = Cy(k),
in which the state y(k) := [y1(k), . . . ,yn(k)]>, the input signal v(k) ∈ Rm, B ∈ Rn×m and C ∈ Rl×n. The nonzero entries of matrices B and C correspond to the set of action-compromised and action-leaked players, respectively. Hence, the adversary has a trajectory of the input/output signal of this system (14): I := {v(k), z(k), 0 ≤ k ≤ T}. When O = V and M = ∅, (14) is degenerated as
z(k + 1) = y(k + 1) = Gy(k).
Then, the single trajectory satisfies Z = GY,
where Z = [y(1),y(2), . . . ,y(T )] ∈ Rn×T and Y = [y(0),x(2), . . . ,y(T − 1)] ∈ Rn×T . This equation can be decoupled as several linear equations: Y >[G>]i = [Z>]i,∀i with [·]i representing the i-th column. Then, G is uniquely constructable from the trajectory T if and only if each of these linear equations has a unique solution, i.e., rank(Y ) = rank([Y >, [Z>]i]) = n, ∀i. Note that Y = [y(0),y(1), . . . ,y(T − 1)] = [y(0),Gy(0), . . . ,GT−1y(0)], of which the vectors span a G-cyclic subspace of Rn, denoted byH(y(0);G). This subspace is an invariant subspace for G, in the sense that GH(y(0);G) ⊆ H(y(0);G), which validates rank(Y ) = rank([Y >, [Z>]i]). Moreover, the condition rank(Y ) = n holds if and only if (G,y(0)) is controllable.
Proposition 1 The following statements are equivalent:
1. (G,y(0)) is controllable;
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 κ(t); or (ii). y(0) has zero projections on to one generalized eigenvector of G.
For the pair (G,y(0)), we form the sequence of vectors
y(0),Gy(0),G2y(0), . . .
and they reside in a G-invariant subspace P with dimension p, where p is the degree of the minimal polynomial for vector y(0) with the linear operator G, termed ζy(0)(t). Moreover, ζy(0)(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.e., m(t) 6= κ(t), then the degree of m(t) is less than n as m(t) divides κ(t), and further the degree of ζ(t) satisfies p < n. Then rank([y(0),Gy(0), . . .]) = p < n and (G,y(0)) is uncontrollable. Obviously, if (ii) holds, the dimension of the G-invariant subspace P satisfies p < n and further (G,y(0)) is uncontrollable.
We next prove “2 =⇒ 1”. Denote the set of distinct eigenvalues of G as σ(G) with cardinality g. Given an eigenvalue λi, its geometric multiplicity, termed µi, is equal to 1 since m(t) = κ(t), and its algebraic multiplicity is equal to its multiplicity in the minimal polynomial m(t) is denoted by ri with ∑g i=1 ri = n.
Let eλi,j denote the generalized eigenvectors of rank j (1 ≤ j ≤ ri) corresponding to G and its eigenvalue λi ∈ σ(G). From statement 2, we have that
y(0) = g∑ i=1 Ei := g∑ i=1 αλi,rieλi,ri + αλi,ri−1eλi,ri−1 + · · ·+ αλi,1eλi,1
with nonzero αλi,j , i = 1, . . . , g, j = 1, . . . , ri. According to the definition of generalized eigenvector, we have
Ei := ri∑ j=1 αλi,jeλi,j = [ ri∑ j=1 αλi,j(G− λiI)ri−j ]eλi,ri := Deλi,ri
with nonzero matrix D. Note that D and G commute, and hence the minimal polynomial of vector Ei, termed ζEi(t), is equal to the minimal polynomial of vector eλi,ri , termed ζeλi,ri (t) = (t−λi) ri .
Since the minimal polynomials for vectors Ei and Ej with j 6= i coprime, according to (MacDuffee, 2012, Section VII-4, Lemma in Page 181), the minimal polynomials for vectors y(0) is equal to the product of ζEi(t), i = 1, . . . , g. Hence, the degree of ζy(0) is p = ∑g i=1 ri = n, which implies the controllability of the pair (G,y(0)).

heading: C PROOF OF THEOREM 2
text: When O = V and M 6= ∅, (14) is degenerated as z(k + 1) = y(k + 1) = Gy(k) + Bv(k).
Setting v(k) = Ky(k), there holds
y(k + 1) = (G + BK)y(k).
According to Theorem 1, G can be uniquely determined by the adversary from one single trajectory I if and only if (G + BK,y(0)) is controllable. Then, the proof of Theorem 2 can be complemented by the following lemma (Wonham, 1985, Lemma 2.2), and the proof is omitted here.
Lemma 1 Let 0 6= y(0) ∈ Im(B). If (G,B) is controllable, there exists K such that (G + BK,y(0)) is controllable.

heading: D PROOF OF THEOREM 3
text: Consider the input sequence V0|T−1 and output one Z0|T−1 of (14), and construct the corresponding block Hankel matrices, as introduced in Section 2.1.2, termed Vp,Vs,Zp,Zf . Then, we can reformulate the state-space model in (14) as follows:
Zf = OnYn|T−n + TnVf , (15) where the observability matrix On and the convolution matrix Tn are defined in Section 2.1.2, respectively. Throughout the article, it is stipulated that the dimension parameter T+1 3n such that the Hankel matrices Zf and Vf have more columns than rows. Note that in (15) the term Yn|T−n is unknown to the adversary. Hence, we hope to construct Yn|T−n from the past input-output data streams, and utilize it to establish an equation of G totally based on the input-output data streams.
First, consider the past output sequences constructed as follows
Zp = OnY0|T−2n + TnVp, similar to (15).
When the observability matrix On has full column rank, the state sequence Yn|T−n can be represented as
Yn|T−n = G nY0|T−2n + ĈnVp = GnO†nZp + [ Ĉn −GnO†nTn ] Vp,
where Ĉn is the reversed controllability matrix. Replacing Yn|T−n in (15) by the above representation, we obtain that
Zf = OnGnO†nZp +On [ Ĉn −GnO†nTn ] Vp + TnVf (16)
By now, the adversary can construct (16) from the single trajectory I. Then, the sufficiency and necessity of Theorem 3 can be easily derived from (16).

heading: E DEFINITION OF INDISTINGUISHABLITY AND PROOF OF THEOREM 4
text: By introducing the action and perturbation difference, we obtain the state-space form (14) of the perturbed game play (p-BR). Let Zv,y0,G(·) and Zv,ỹ0,G̃(·) 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 y0, ỹ0, and the topology matrix G, G̃, respectively. We introduce the following definition.
Definition 1 The topology matrices G and G̃ are indistinguishable if there exist initial conditions y0, ỹ0 ∈ Rn such that
Zv,y0,G(·) = Zv,ỹ0,G̃(·)
for all injected perturbation difference v.
Clearly, the indistinguishability 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 is said to be learnable if G and G̃ are distinguishable for all real G 6= G̃. To prove Theorem 4, we give the following two statements1:
Lemma 2 A pair of parameter values (G, G̃) is indistinguishable if and only if the Markov parameters satisfying:
CGlB = CG̃lB, l = 0, 1, 2, · · · . (17) 1The proofs of Lemma 2 and Lemmas 3-4 are inspired by and adopted from the proofs for system identifia-
bility in Grewal & Glover (1976) and van Waarde et al. (2021), respectively.
Proof: We first prove the sufficiency. If (17) holds, then the output trajectories of two systems (14) associated with (G, G̃) satisfy that when y0 = ỹ0,
Zv,y0,G(k) := z(k) = CGky0 + k−1∑ t=0 CGtBv(k − 1− t) = Zv,ỹ0,G̃(k),
for all v(k) ∈ Rm and for k ≥ 0. According to Definition 1, the topology matrices G and G̃ are indistinguishable.
The necessity is proved as follows. Assume (G, G̃) are indistinguishable, then there exist initial conditions y0, ỹ0 s.t.
CGky0 + k−1∑ t=0 CGtBv(k − 1− t) = CG̃kỹ0 + k−1∑ t=0 CG̃tBv(k − 1− t)
holds for all input functions v and for all k ≥ 0. It implies that
CGky0 = CG̃ kỹ0,∀k ≥ 0, (18)
and k−1∑ t=0 [CGtB−CG̃tB]v(k − 1− t) ≡ 0. (19)
Hence, if y0 and ỹ0 are set as zero vectors, then (18) holds for all k, which implies the existence of y0 and ỹ0. Since v(·) ∈ Rm has a nonempty interior, (19) means that
CGlB = CG̃lB, ∀l = 0, 1, . . . . Hence, the indistinguishability implies that at different values of the parameter G, the Markov parameters of the system CGkB 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 v ∈ Rn be a nonzero vector in the uncontrollable subspace of (G,B), i.e., v>GlB = 0, ∀k = 0, 1, . . . Given a topology matrix G, we can construct G̃ = G + vv>, satisfying that
G̃lB = [G + vv>]l−1[G + vv>]B = [G + vv>]l−1GB
= [G + vv>]l−2[G + vv>]GB = [G + vv>]l−2G2B
= .... = GlB.
Hence, we have CGlB = CG̃lB, ∀l = 0, 1, . . . but G 6= G̃. It implies the topology G is not learnable 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) = n or rank(C) = n.
Proof: Suppose that rank(B) < n and rank(C) < n. Then there exist nonzero vectors v, u ∈ Rn such that Cv = 0 and u>B = 0. Without loss of generality, we assume u>v 6= −1. Next, we define a matrix A := I + vu>. Its inverse A−1 exists according to Sherman-Morrison formula with A−1 = I − vu >
I+u>v .
Given a topology matrix G, we can construct G̃ := A−1GA, which satisfies CGlB = CG̃lB for all l = 0, 1, . . . Then, according to Lemma 2 the topology G is not learnable.
Proof of Theorem 4: The transfer function FG(z) can be expanded as follows:
FG(z) = C(zI −G)−1B = Cz−1 +∞∑ k=0 (z−1G)kB.
Hence, (17) in Lemma 2 can be equivalently stated as FG(z) = FG̃(z), which concludes the learnability of G in terms of the transfer function.
Next, we prove the learnability condition in terms of matrices G,B and C.
Sufficiency: Suppose rankC = n and (G,B) is controllable. It is sufficient to prove that for a pair of parameter values (G, G̃) FG(z) = FG̃(z) holds if and only if G = G̃.
Consider two topology matrix G, G̃ with difference ∆ := G − G̃. Suppose FG(z) = FG̃(z). As C has full column rank, we have
(zI − G̃)C†[FG(z)− FG̃(z)] = ∆(zI −G)B = ∞∑ k=0 z−(k+1)∆GkB ≡ 0.
As z−(k+1) is nonzero, it is derived from the above that
∆GkB ≡ 0, ∀k = 0, 1, . . . (20)
Since (G,B) is controllable, (20) holds if and only if ∆ is zero matrix, which shows G = G̃.
The proof for case 2 (i.e., full row rand of matrix B and observability of (G,C)) is analogous to the above and is omitted here.
Necessity: These can be obtained directly from Lemmas 3 and 4.

heading: F BASELINE APPROACHES
text: F.1 BASELINES IN SECTION 5.1
The method of stable least square (SLS) is defined by the optimization problem
inf G∈S
1 2 ||Z −GY −BV ||2F . (21)
The method of stable L2-regularized least square (SL2LS) solves
inf G∈S
1 2 ||Z −GY −BV ||2F + β||G||2F . (22)
Solving Eq. (21) and (22) is numerically challenging. We propose to solve ĜSLS = arg minG 12 ||Z− GY −BV ||2F and ĜSL2LS = arg minG 12 ||Z −GY −BV || 2 F + β||G||2F and project them to their nearest stable ones by applying Eq. (10).
F.2 BASELINE IN SECTION 5.2
The method of stable subspace identification (SSubI) is posed by solving the following problem
inf G∈S n−2∑ l=1 ||CGlB−M?l ||2F . (23)
We first compute ĜSSubI = arg minG ∑n−2 l=1 ||CGlB−M?l ||2F and then follow Eq. (10) to project it to its nearest stable matrix.

Review summaries:
In this paper, the authors consider quadratic network games with payoff functions of the form $$ J_i(x_i;x_{-i}) = \alpha_i x_i - x_i^2/2 + \sum\nolimits_{j=1}^{n} x_i x_j $$ where $\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$).  The authors assume that players follow a "perturbed" best-response model of the form $$ x_i(t+1) = \arg\max\nolimits_{x_i\in\mathbb{R}} J_i(x_i;x_{-i}(t)) + u_i(t+1) $$ where $u_i$ is a perturbation that affects only a subset $M$ of "manipulable" players (possibly empty).  The 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:  1. 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).  1. 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).  1. Finally, if the learner has access to infinitely many trajectories, $G$ is learnable if and only if two pairs of matrices are controllable / observable.  Two 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.).   

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. 

The authors study a game theory problem in linear quadratic games (family of payoffs) with the following assumptions 1) players are assumed to use the best-response strategy  2) an adversary can observe a subset of the nodes' actions 3) an adversary can modify the wards for a subset of the players 4) 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.   The authors study under what circumstances G can be learned.  One result is that that under some mild assumptions when the adversary can observe all players agents, then G can be learned.   The authors show for more settings necessary and sufficient conditions for learning G. The authors also perform some simulations on random graphs.