Games on large random interaction structures: Information and complexity aspects

Games on large structures of interacting agents are considered. The participants of the game do not have a full knowledge of the interaction structure or the characteristics of the other players. Instead of that, an ensemble of possible interaction structures as well as a probability measure on that ensemble are assumed to be a common knowledge among the players. Furthermore, we assume that the agents have also local information. Specifically, they know the characteristics of some players, important for them. A new notion of equilibrium, describing approximate Nash equilibrium with high probability, is introduced. A concept of complexity of a game is also defined, as the minimum amount of information needed, in order to play almost optimally. Some special cases are then analyzed. Particularly, games on random graphs are considered and are shown to be simple, under high connectivity assumptions. Games on rings, under quadratic and non quadratic cost functions, are finally studied. Bounds on the complexity of the ring games are derived.