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

Abstract We consider a class of $N$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>N</mml:mi> </mml:math> -player nonsmooth aggregative games over networks in stochastic regimes. In such a game, the $i$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>i</mml:mi> </mml:math> th player minimizes a composite cost function comprising (i) a smooth expectation-valued function $f_{i}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>f</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:math> that depends its own strategy and an aggregate function of rival strategies, (ii) a convex hierarchical term $d_{i}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>d</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:math> that depends on its strategy, and (iii) a nonsmooth convex function $r_{i}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>r</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:math> 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_{i}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>r</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:math> 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 $\epsilon $ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ϵ</mml:mi> </mml:math> -Nash equilibrium requires $\mathcal{O}(1/\epsilon ^{2+\delta })$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:msup> <mml:mi>ϵ</mml:mi> <mml:mrow> <mml:mn>2</mml:mn> <mml:mo>+</mml:mo> <mml:mi>δ</mml:mi> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:math> oracle evaluations where $\delta &gt; 0$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>δ</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:math> . 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.