  We consider a setting where individuals interact in a network, each choosing
actions which optimize utility as a function of neighbors' actions. A central
authority aiming to maximize social welfare at equilibrium can intervene by
paying some cost to shift individual incentives, and the optimal intervention
can be computed using the spectral decomposition of the graph, yet this is
infeasible in practice if the adjacency matrix is unknown. In this paper, we
study the question of designing intervention strategies for graphs where the
adjacency matrix is unknown and is drawn from some distribution. For several
commonly studied random graph models, we show that there is a single
intervention, proportional to the first eigenvector of the expected adjacency
matrix, which is near-optimal for almost all generated graphs when the budget
is sufficiently large. We also provide several efficient sampling-based
approaches for approximately recovering the first eigenvector when we do not
know the distribution. On the whole, our analysis compares three categories of
interventions: those which use no data about the network, those which use some
data (such as distributional knowledge or queries to the graph), and those
which are fully optimal. We evaluate these intervention strategies on synthetic
and real-world network data, and our results suggest that analysis of random
graph models can be useful for determining when certain heuristics may perform
well in practice.
