An Efficient Distributed Nash Equilibrium Seeking with Compressed and Event-triggered Communication

Xiaomeng Chen, Wei Huo, Yuchi Wu, Subhrakanti Dey, Ling Shi

Distributed Nash equilibrium (NE) seeking problems for networked games have been widely investigated in recent years. Despite the increasing attention, communication expenditure is becoming a major bottleneck for scaling up distributed approaches within limited communication bandwidth between agents. To reduce communication cost, an efficient distributed NE seeking (ETC-DNES) algorithm is proposed to obtain an NE for games over directed graphs, where the communication efficiency is improved by event-triggered exchanges of compressed information among neighbors. ETC-DNES saves communication costs in both transmitted bits and rounds of communication. Furthermore, our method only requires the row-stochastic property of the adjacency graph, unlike previous approaches that hinged on double-stochastic communication matrices. We provide convergence guarantees for ETC-DNES on games with restricted strongly monotone mappings, testifying that such a communication method is efficient without sacrificing the accuracy of the algorithm. The algorithm and analysis are extended to a compressed algorithm with stochastic event-triggered mechanism (SETC-DNES). In SETC-DNES, we introduce a random variable in the triggering condition to further enhance algorithm efficiency. We demonstrate that SETC-DNES guarantees linear convergence to the optimal NE while achieving even greater reductions in communication costs compared to ETC-DNES. Finally, numerical simulations illustrate the effectiveness of the proposed algorithms.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment