Electrical and Electronic Engineering - Research Publications
Permanent URI for this collection
Search Results
1 - 4 of 4
-
ItemAn Information Analysis of Iterative Algorithms for Network Utility Maximization and Strategic Games(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.
-
ItemImpact of quantized inter-agent communications on game-theoretic and distributed optimization algorithms(Springer, 2018-01-01)Quantized inter-agent communications in game-theoretic and distributed optimization algorithms generate uncertainty that affects the asymptotic and transient behavior of such algorithms. This chapter uses the information-theoretic notion of differential entropy power to establish universal bounds on the maximum exponential convergence rates of primal-dual and gradient-based Nash seeking algorithms under quantized communications. These bounds depend on the inter-agent data rate and the local behavior of the agents’ objective functions, and are independent of the quantizer structure. The presented results provide trade-offs between the speed of exponential convergence, the agents’ objective functions, the communication bit rates, and the number of agents and constraints. For the proposed Nash seeking algorithm, the transient performance is studied and an upper bound on the average time required to settle inside a specified ball around the Nash equilibrium is derived under uniform quantization. Furthermore, an upper bound on the probability that the agents’ actions lie outside this ball is established. This bound decays double exponentially with time.
-
ItemLower Bounds on the Best-Case Complexity of Solving a Class of Non-cooperative Games(Elsevier, 2016)This paper studies the complexity of solving the class G of all N-player non-cooperative games with continuous action spaces that admit at least one Nash equilibrium (NE). We consider a distributed Nash seeking setting where agents communicate with a set of system nodes (SNs), over noisy communication channels, to obtain the required information for updating their actions. The complexity of solving games in the class G is defined as the minimum number of iterations required to find a NE of any game in G with ε accuracy. Using information-theoretic inequalities, we derive a lower bound on the complexity of solving the game class G that depends on the Kolmogorov 2ε-capacity of the constraint set and the total capacity of the communication channels. We also derive a lower bound on the complexity of solving games in G which depends on the volume and surface area of the constraint set.
-
ItemSample Complexity of Solving Non-Cooperative Games(Institute of Electrical and Electronics Engineers, 2020-02-01)This paper studies the complexity of solving two classes of non-cooperative games in a distributed manner, in which the players communicate with a set of system nodes over noisy communication channels. The complexity of solving each game class is defined as the minimum number of iterations required to find a Nash equilibrium (NE) of any game in that class with ∈ accuracy. First, we consider the class G of all N-player non-cooperative games with a continuous action space that admit at least one NE. Using information-theoretic inequalities, a lower bound on the complexity of solving G is derived which depends on the Kolmogorov 2∈-capacity of the constraint set and the total capacity of the communication channels. Our results indicate that the game class G can be solved at most exponentially fast. We next consider the class of all N-player non-cooperative games with at least one NE such that the players' utility functions satisfy a certain (differential) constraint. We derive lower bounds on the complexity of solving this game class under both Gaussian and non-Gaussian noise models. Finally, we derive upper and lower bounds on the sample complexity of a class of quadratic games. It is shown that the complexity of solving this game class scales according to Θ (1/∈ 2 ) where € is the accuracy parameter.