Electrical and Electronic Engineering - Research Publications

Permanent URI for this collection

http://hdl.handle.net/11343/362

Filters

2016 - 2019 2
Reset filters

Settings
Statistics
Citations
Author: Alpcan, Tansu × Author: Nair, Girish × Type: Journal Article × Start date: 2010 × End date: 2019 ×

Search Results

Now showing 1 - 2 of 2
  • Item
    Thumbnail Image
    An Information Analysis of Iterative Algorithms for Network Utility Maximization and Strategic Games
    Alpcan, T ; Nekouei, E ; Nair, GN ; Evans, RJ (IEEE, 2019)
    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.
  • Item
    Thumbnail Image
    Performance Analysis of Gradient-Based Nash Seeking Algorithms Under Quantization
    Nekouei, E ; Nair, GN ; Alpcan, T (IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC, 2016-12-01)
    This paper investigates the impact of quantized inter-agent communications on the asymptotic and transient behavior of gradient-based Nash-seeking algorithms in non-cooperative games. Using the information-theoretic notion of entropy power, we establish a universal lower bound on the asymptotic rate of exponential mean-square convergence to the Nash equilibrium (NE). This bound depends on the inter-agent data rate and the local behavior of the agents' utility functions, and is independent of the quantizer structure. Next, we study transient performance and derive an upper bound on the average time required to settle inside a specified ball around the NE, under uniform quantization. Furthermore, we establish an upper bound on the probability that agents' actions lie outside this ball, and show that this bound decays double-exponentially with time. Finally, we propose an adaptive quantization scheme that allows the gradient algorithm to converge to the NE despite quantized inter-agent communications.