Random Reshuffling-Based Distributed Nash Equilibrium Seeking

This paper studies random reshuffling (RR)-based distributed Nash equilibrium seeking for noncooperative games.

The game is motivated as a sample-average approximation of an underlying expected-value stochastic game, while the algorithmic focus is placed on the resulting finite-sum equilibrium problem.

Unlike existing distributed stochastic Nash equilibrium methods that mainly rely on with-replacement sampling, the proposed approach incorporates without-replacement component updates into equilibrium computation over networks.

We first consider a full-information benchmark, for which an intermediate reference trajectory and a shuffling variance are introduced to characterize the epoch-wise dynamics induced by RR.

The method is then extended to the more practical partial-decision-information setting, where each player updates its action using local estimates of the joint action profile.

For the full-information case, a descent-type bound is established for the RR iterates.

For the distributed partial-decision-information case, it is shown that, under constant parameters, the proposed algorithm converges linearly to a neighborhood of the Nash equilibrium, while under diminishing parameters, it converges exactly to the Nash equilibrium almost surely and in mean square.

Numerical experiments on an EV charging game and a nonquadratic edge resource admission game demonstrate that RR consistently outperforms the conventional with-replacement SGD baseline in both steady-state accuracy and long-horizon performance.