Vanishing price of decentralization in large coordinative nonconvex optimization

We focus on nonconvex multi-agent optimization where a large number of participants collaboratively optimize some social cost function and their individual preferences. We focus on the semidecentralized multi-agent best response setting where a central planner attempts to coordinate the agents and each participant pursues self-interest. By studying the duality framework, we provide geometric and analytic characterizations of the duality gap and the price of decentralization. We prove that the nonconvex problem becomes increasingly convex as the problem scales up in dimension. Upon appropriate coordination, the price of decentralization asymptotically vanishes to zero as the number of participants grows. We develop a duality-based coordination procedure for the central planner to adapt the price vector and select a particular best response for each participant. The coordination algorithm is able to induce individual best responses to dynamically converge to an approximate global optimum, regardless of the initial solution. A convergence rate and complexity analysis as well as numerical results are provided. In the case without any coordination, we provide counterexamples showing that the price of decentralization can be disastrously high.