An Information Analysis of Iterative Algorithms for Network Utility Maximization and Strategic Games

A variety of resource allocation problems on networked systems, for example, those in cyber-physical systems or Internet-of-things applications, require distributed solution methods. Modern distributed algorithms usually require bandwidth-limited digital communication between the system and its users, who are often modeled as independent decision makers with individual preferences. This paper presents a quantitative information flow and knowledge gain analysis of decentralized iterative algorithms with bounded trajectories in the context of convex network utility maximization problems and strategic games with a unique Nash equilibrium solution. First, a novel generic framework is introduced to quantify knowledge gain in network resource allocation problems using entropy by taking into account priors in the solution space. Second, a general result is presented on the interplay between quantization of information and distributed algorithm performance both for linear and sublinear convergence. Third, information flow in distributed algorithms is studied and a lower bound is derived on the total amount of information exchanged for convergence under uniform quantization. The well-known primal-dual decomposition algorithm is used as an example to illustrate the results. Finally, convergence guarantees for distributed algorithms with estimation are investigated. This paper establishes specific links between information concepts and iterative algorithms in addition to building a foundation for integrating learning schemes into distributed optimization.