Performance Analysis of Gradient-Based Nash Seeking Algorithms Under Quantization

摘要

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.