Performance Analysis of Gradient-Based Nash Seeking Algorithms under Quantization

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

7 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Article number7400978
Pages (from-to)3771-3783
Journal / PublicationIEEE Transactions on Automatic Control
Volume61
Issue number12
Online published8 Feb 2016
Publication statusPublished - Dec 2016
Externally publishedYes

Abstract

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.

Research Area(s)

  • Data rate, differential entropy, noncooperative games, quantization

Citation Format(s)