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

We consider a class of N N -player nonsmooth aggregative games over networks in stochastic regimes. In such a game, the i i th player minimizes a composite cost function comprising (i) a smooth expectation-valued function fᵢ f i that depends its own strategy and an aggregate function of rival strategies, (ii) a convex hierarchical term dᵢ d i that depends on its strategy, and (iii) a nonsmooth convex function rᵢ r i 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 rᵢ r i 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+δ) O ( 1 / ϵ 2 + δ ) oracle evaluations where δ > 0 δ > 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.