A Distributed Iterative Tikhonov Method for Networked Monotone Stochastic and Hierarchical Aggregative Games

We consider a class of N-player nonsmooth aggregative games over networks in stochastic regimes. In such a game, the ith player minimizes a composite cost function comprising (i) a smooth expectation-valued function fi that depends its own strategy and an aggregate function of rival strategies, (ii) a convex hierarchical term di that depends on its strategy, and (iii) a nonsmooth convex function ri of its strategy with an efficient prox-evaluation. Although the true aggregate is unknown, players may estimate it by interacting with their neighbors. We design a fully distributed iterative proximal stochastic gradient method overlaid by a Tikhonov regularization, where each player may independently choose its steplengths and regularization parameters while meeting some coordination requirements. Under a monotonicity assumption on the concatenated gradient mapping, we prove that the generated sequence converges almost surely to the least-norm Nash equilibrium. When each ri is an indicator function of a compact convex set, we establish the convergence rate for the expected gap function at the time-averaged sequence. We further derive high probability bounds for the gap function via both Markov’s inequality as well as a more refined argument that leverages Azuma’s inequality. Furthermore, we consider the extension to the private hierarchical regime, where each player is a leader with respect to a collection of private followers competing in a strongly monotone game, parametrized by leader decisions. By integrating a convolution-smoothing technique with our regularization framework, we present amongst the first fully distributed schemes for such hierarchical games. Using a Fitzpatrick gap function, we extend our rate guarantees to this setting. Notably, both sets of fully distributed schemes display near-optimal sample-complexities, i.e. computation of an ϵ-Nash equilibrium requires O(1/ϵ2+δ) oracle evaluations where δ>0. This suggests that the hierarchical structure has little impact from the standpoint of performance degradation. Finally, numerical experiments on a networked Nash-Cournot problem and its hierarchical generalization demonstrate the beneficial impact of regularization.