Dynamic Games among Agents with Partial Information of the Structure of the Interactions Graph: Decision Making and Complexity Issues

We consider dynamic games on large networks, motivated by structural and decision making issues pertaining in the area of Systems of Systems. The players participating in the game do not know the network structure and the characteristics of the dynamics and costs of the players involved. Instead, they know some local characteristics of the topology, as well as a statistical description of the network. An approximate equilibrium concept is introduced and a complexity notion that describes the minimum amount of structural and feedback information needed for the players in order to behave approximately in Nash equilibrium, is defined. An example of a Linear Quadratic game on a ring is finally studied and an asymptotic upper bound for the complexity of the game is derived.