Click here to flash read.
Information compression techniques are majorly employed to address the
concern of reducing 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 compression operators, 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.
No creative common's license