Nash Equilibrium Seeking in Subnetwork Zero-Sum Games with Switching Communication Graphs.
Youcheng Lou, Yiguang Hong, Lihua Xie, Guodong Shi, Karl Henrik Johansson · arXiv (Cornell University) · 2013
In this paper, we investigate a distributed Nash equilibrium seeking problem for a time-varying multi-agent network consisting of two subnetworks. We propose a subgradient-based distributed algorithm to seek a Nash equilibrium of a zero-sum game, where the two subnetworks share the same sum objective function. We show that the proposed distributed algorithm with homogenous stepsize can achieve a Nash equilibrium under uniformly jointly strongly connected (UJSC) weight-balanced digraphs. Then for weight-unbalanced graphs, we show, by considering a special case, that generally a Nash equilibrium cannot be achieved with homogenous stepsize unless certain conditions on the objective functions hold. Next we show that for any UJSC digraphs, there always exist stepsizes under which a Nash equilibrium can be achieved. Finally, for two general weight-unbalanced cases, we show that by adaptively updating the stepsize along with the arc weights in the proposed algorithm, a convergence to the Nash equilibrium can still be guaranteed.