Linear Convergent Distributed Nash Equilibrium Seeking with Compression

Information compression techniques are majorly employed to reduce communication cost over peer-to-peer links. In this paper, we investigate distributed Nash equilibrium (NE) seeking problems in a class of non-cooperative games over directed graphs with information compression. To improve communicati...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on automatic control 2024-11, p.1-8
Main Authors: Chen, Xiaomeng, Wu, Yuchi, Yi, Xinlei, Huang, Minyi, Shi, Ling
Format: Article
Language:English
Subjects:
Bandwidth
Compressors
Convergence
Directed graphs
distributed networks
Finite element analysis
Games
information compression
Linear matrix inequalities
Nash equilibrium
Nash equilibrium seeking
noncooperative games
Quantization (signal)
Vectors
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Information compression techniques are majorly employed to reduce communication cost over peer-to-peer links. In this paper, we investigate distributed Nash equilibrium (NE) seeking problems in a class of non-cooperative games over directed graphs with information compression. To improve communication efficiency, a compressed distributed NE seeking (C-DNES) algorithm is proposed to obtain a NE for games, where the differences between decision vectors and their estimates are compressed. The proposed algorithm is compatible with a general class of compressors, including both unbiased and biased compressors. Moreover, our approach only requires the adjacency matrix of the directed graph to be row-stochastic, in contrast to past works that relied on balancedness or specific global network parameters. It is shown that C-DNES not only inherits the advantages of conventional distributed NE algorithms, achieving linear convergence rate for games with restricted strongly monotone mappings, but also saves communication costs in terms of transmitted bits. Finally, numerical simulations illustrate the advantages of C-DNES in saving communication cost by an order of magnitude under different compressors.
ISSN:0018-9286
1558-2523
DOI:10.1109/TAC.2024.3505812