We focus on a class of nonconvex cooperative optimization problems that involve multiple participants. We study the duality framework and provide geometric and analytic character- izations of the duality gap. The dual problem is related to a market setting in which each participant pursuits self interests at a given price of common goods. The duality gap is a form of price of anarchy. We prove that the nonconvex problem becomes increasingly convex as the problem scales up in dimension. In other words, the price of anarchy vanishes to zero as the number of participants grows. We prove the existence of a solution to the dual problem that is an approximate global optimum and achieves the minimal price of anarchy. We develop a coor- dination procedure to identify it from the set of all individual’s best responses. Furthermore, we propose a globally convergent duality-based algorithm that relies on individual best responses to achieve the approximate social optimum. Convergence and rate of convergence analysis as well as numerical results are provided.
Citation
ORFE, Princeton Univeristy. July, 2015