Control of Stochastic Evolutionary Games on Networks∗

We investigate the control of stochastic evolutionary games on networks, in which each edge represents a two-player repeating game between neighboring agents. The games occur simultaneously at each time step, after which the agents can update their strategies based on local payoff and strategy information, while a subset of agents can be assigned strategies and thus serve as control inputs. We seek here the smallest set of control agents that will guarantee convergence of the network to a desired strategy state. After deriving an exact solution that is too computationally complex to be practical on large networks, we present a hierarchical approximation algorithm, which we show computes the optimal results for special cases of complete and ring networks, while simulations show that it yields near-optimal results on trees and arbitrary networks in a wide-range of cases, performing best on coordination games.