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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

2 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Article number8281515
Pages (from-to)151-162
Journal / PublicationIEEE Transactions on Control of Network Systems
Volume6
Issue number1
Online published5 Feb 2018
Publication statusPublished - Mar 2019
Externally publishedYes

Abstract

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.

Research Area(s)

  • Game theory, information entropy, optimization methods

Citation Format(s)