  Network games provide a natural machinery to compactly represent strategic
interactions among agents whose payoffs exhibit sparsity in their dependence on
the actions of others. Besides encoding interaction sparsity, however, real
networks often exhibit a multi-scale structure, in which agents can be grouped
into communities, those communities further grouped, and so on, and where
interactions among such groups may also exhibit sparsity. We present a general
model of multi-scale network games that encodes such multi-level structure. We
then develop several algorithmic approaches that leverage this multi-scale
structure, and derive sufficient conditions for convergence of these to a Nash
equilibrium. Our numerical experiments demonstrate that the proposed approaches
enable orders of magnitude improvements in scalability when computing Nash
equilibria in such games. For example, we can solve previously intractable
instances involving up to 1 million agents in under 15 minutes.
