Optimal Seeding in Large-Scale Super-Modular Network Games

We study optimal seeding problems for binary super-modular network games. The system planner’s objective is to design a minimal cost seeding guaranteeing that at least a predefined fraction of the players adopt a certain action in every Nash equilibrium. Since the problem is known to be NP-hard and its exact solution would require full knowledge of the network structure, we focus on approximate solutions for large-scale networks with given statistics. In particular, we build on a local mean-field approximation of the linear threshold dynamics that is known to hold true on large-scale locally tree-like random networks. We first reduce the optimal intervention design problem to a linear program with an infinite set of constraints. We then show how to approximate the solution of the latter by standard linear programs with finitely many constraints. Our solutions are then numerically validated.

I. Introduction

Designing interventions by a central planner in order to modify the outcomes of a network game and steer them towards a socially desirable objective is a fundamental problem in many multi-agent systems. Applications in socio-technical systems are countless, ranging from pricing and toll design in transportation and energy networks to viral marketing in social networks. The optimal intervention design problem for network games is known to be challenging since an intervention on a single individual or on a group of them has direct and indirect effects on all the others. Such spill-over effects depend both on the geometry of the network and on the type of influence mechanisms that individuals’ actions have on their neighbors’ utilities (e.g., strategic complements vs strategic substitutes) [1], [2], [3]. Especially over the past two decades, a large body of literature has in particular highlighted the role of network centrality measures in order to determine the network nodes that the intervention should target in order to optimize its effect [4], [5], [6].