Collective optimization problems with optimal decentralized selfish strategies

In this paper, we consider cooperative multi-agent systems minimizing a social cost. Cooperation is induced by the cost that penalizes the divergence of each agent from the average collective behavior. In principle, the optimal solution is centralized and requires a complete communication graph. We study this problem for two important system input-output norms, the l₁ induced norm and the per-agent H₂ norm squared, as function of the number of agents, n, and various cost structures. For the case of identical agents, and the simplest cost setting, we show that the optimal social solution is always the optimal decentralized selfish solution. For more general cost functions, we show that the optimal solution is always decentralized in the l₁ induced norm case. In the case of the per-agent H₂ norm squared cost, we show that the optimal decentralized selfish solution is socially optimal in the limit of large n. All of these also hold for several classes of problems with nonidentical agents. In simple terms, these results, identify important problem classes where decentralized/selfish behaviors are socially optimal, and for which inter-agent communication is or becomes unnecessary for large n.