Targeting in networks under costly agreements

We consider agents organized in an undirected network of local complementarities. A principal with a fixed budget offers costly bilateral contracts in order to increase the sum of agents' effort. We study contracts rewarding effort exceeding the effort made in the absence of the principal. First, targeting a subgroup of the whole society becomes optimal under substantial contracting costs, which significantly increases the computational complexity of the principal's problem. In particular, under sufficiently low intensity of complementarities, a correspondence is established between optimal targeting and an NP-hard problem. Second, for any intensities of complementarities, the optimal unit returns offered to all targeted agents are positive for all contracting costs and in general heterogeneous, even though networks are undirected. Yet, heterogeneity never leads to negative returns, which implies that, with these linear payment schemes, coordination is never an issue for the principal.