We consider a network of cooperating agents in which every agent has to make a decision from a finite set. The agents aim to maximize a global function f that can be decomposed as a sum of local cost functions, each one indicating interaction between two agents. The network is endowed with a probabilistic structure in which local cost functions are sampled from a distribution.

Our aim is to be able to characterize the efficiency of a decentralized solution generated on the basis of local information. More precisely, we suppose that each agent knows the structure of the network and the cost functions within a distance at most r, and takes a decision with this knowledge at hand, without coordination (i.e. without knowing the decisions of other agents). Under this constraint, how suboptimal is a decentralized solution of radius r, and can it be computed efficiently?

We look at these questions in light of density evolution and the correlation decay phenomenon and, by introducing a cavity-type recursion, find sufficient conditions for correlation decay relating the local costs distribution and the degree of the graph considered.