REVIEW 4 major objections 4 minor 29 references
Leader-Follower Network Aggregative Game with Stochastic Agents' Communication and Activeness
T0 review · 4 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read A distributed projected subgradient algorithm converges almost surely and in mean square to the unique generalized Nash equilibrium of a leader-follower network aggregative game, despite stochastic communication, stochastic activeness…
desk verdict A novel leader-follower NAG model with an unsound convergence proof—two reversed inequalities and an invalid mean-square step. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is Algorithm 1: the projected subgradient recursions $x_n^{k+1} = \Pi_{X_n}(x_n^k - e_n^k \alpha_n^k d_n(x_n^k, \tilde{\sigma}_n^k, y^k))$ for followers and $y^{k+1} = \Pi_Y(y^k - \alpha_0^k d_0(y^k, \sigma_0^k))$ for the leader at wake-up instants. The random binary variables $e_n^k$ (activeness) and $l_{n,m}^k$ (message delivery) realize the stochastic communication model. The argument's load-bearing step is the almost-supermartingale inequality (27), which decomposes the expected squared error accumulated over one leader sleep period into two summable perturbation terms and two non-positive quadratic terms; the non-positivity is certified by combining the lower bounds $\gamma$ and $\delta$ from Assumption 2, the step-size ratio bound $\kappa$ from Assumption 5, and the spectral-radius bound for the nonnegative coupling matrix $V^{k'}$.
What would settle it
Run Algorithm 1 on a small network (two followers and one leader) with quadratic strongly convex costs satisfying the theorem's thresholds, gossip communication, and a leader that wakes every $\bar{K}$ iterations, and check whether the squared distance to the computed GNE goes to zero; a persistent nonzero error or convergence to a different point would falsify the claim.
Extended reading notes
Core claim
Theorem 1 states that if the strong-convexity constants from Assumption 1 satisfy $C_n > \frac{\kappa}{\delta}\bar{L}$ for every follower and $C_0 > \kappa\bar{K}\bar{L}$ for the leader, with $\bar{L} = \max(2L, L_0)$, then Algorithm 1 converges almost surely to the unique GNE point. Proposition 1 adds mean-square convergence, and Proposition 2 establishes that the equilibrium is unique under the same conditions. In the paper's own terms, the randomness in who communicates and who updates is handled as a perturbation that is summable with respect to the step sizes, so the expected squared distance to equilibrium is driven to zero by the two negative terms $T_3^j$ and $T_4^j$ in inequality (27).
Load-bearing premise
The proof requires that at every iteration the ratio of the largest to the smallest step size across all followers and the leader is bounded by one fixed constant; if some agents' step sizes shrink at very different rates, the negative terms that drive convergence can no longer be shown non-positive.
Editorial extensions
If this is right
- A network of selfish cost-minimizing agents can reach the unique equilibrium with a simple gradient-following rule, without solving best-response problems at each step.
- Gossip-style communication, in which at most one neighboring pair exchanges information per iteration, is a special case of the model and inherits the convergence guarantee.
- The leader can sleep for arbitrarily long but bounded stretches; followers continue updating with the last broadcast value and the system still converges.
- The mean-square convergence result means that independent runs of the algorithm will concentrate around the equilibrium, not merely converge on a set of probability one.
- The explicit thresholds $C_n > \kappa\bar{L}/\delta$ and $C_0 > \kappa\bar{K}\bar{L}$ give quantitative guidance for when unreliable communication is tolerable.
Reading between the lines
- A natural extension the authors do not pursue is relaxing Assumption 5, the uniform step-size ratio; if some agents' step sizes decay much faster than others', the cross-term bound in (23) can fail, and the conjecture is that convergence may be lost.
- The proof only uses lower bounds $\gamma$ and $\delta$ on communication and activeness probabilities, so the same guarantee should hold for any scheduling mechanism—energy-aware sleeping, deterministic duty cycles, or randomized gossip—that respects those bounds.
- In the small-cell power-control application, the threshold condition translates into a quantitative rule: a macrocell base station that updates less often needs a stronger penalty curvature or a smaller maximum sleep gap; the paper's simulation uses one operating point but does not map out this trade-off.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper considers a leader-follower network aggregative game in which each follower's cost depends on the leader's strategy and the aggregated strategies of its neighbors, while the leader's cost depends on the aggregate of all followers' strategies. Communication among followers and the activeness of each follower are stochastic and may be dependent; the leader wakes up and updates only at an infinite set of iterations with bounded gaps. The authors propose a distributed projected subgradient algorithm and claim that it converges almost surely to the unique generalized Nash equilibrium under strong convexity, Lipschitz subgradients, and an assumption bounding the ratio of the largest to the smallest step size. They also claim mean-square convergence and include simulations for a small-cell power allocation example.
Significance. The model is well motivated and, if the convergence results were correct, the paper would be a useful contribution: it extends network aggregative games to a leader-follower setting with stochastic communication and activeness, and it offers a distributed subgradient scheme with a clean algorithmic statement. The simulation example is appropriate for the application domain. However, the central convergence proof contains two sign errors in the treatment of the step sizes, and the mean-square claim rests on an invalid subsequence argument. As written, the main theorem is not established, so the paper does not yet provide the claimed justification for the algorithm.
major comments (4)
- [Section IV, Theorem 1 proof, Eq. (23)] The replacement of the follower step size by the maximum step size is invalid. Since α_n^k ≤ α^k, the inequality -α_n^k C_n ||∇x_n^k||^2 ≤ -α^k C_n ||∇x_n^k||^2 has the wrong sign; the left-hand side is actually larger. Assumption 5 gives α_n^k ≥ α^k/κ, so the correct negative coefficient is at most -(α^k/κ) C_n, not -α^k C_n. Consequently the positivity of T_4 in Eq. (27) does not follow from the stated supermartingale inequality.
- [Section IV, Theorem 1 proof, Eq. (26)] The bound for the leader term reverses the monotonicity of the step sizes. For each k' in K'_j, ||∇y^{k_L_j}||^2 is constant, but since the step sizes are non-increasing, α^{k'} ≥ α^{k_L_j}; hence ∑_{k'∈K'_j} α^{k'} ||∇y^{k_L_j}||^2 is at least α^{k_L_j}(k_L_j-k_L_{j-1})||∇y^{k_L_j}||^2, not at most. This makes the displayed coefficient (C0 - κ(k_L_j-k_L_{j-1}) \bar L) in T_3 unjustified, and the supermartingale inequality obtained by combining (20) and (27) is not established.
- [Section IV, Proposition 1] The proof claims that ∑ α^k E||∇x^k||^2 < ∞ together with ∑ α^k = ∞ forces E||∇x^k||^2 → 0. This implication is false in general; for example, one can take α_k = 1/k and E||∇x^k||^2 = 1 on a sufficiently sparse subsequence. No L1 or uniform-integrability argument is supplied from the almost-sure convergence, so the mean-square convergence claim is unsupported.
- [Section IV, Eq. (26) and Proposition 2] The matrices V^{k'} are not symmetric, and the Perron-Frobenius theorem controls the spectral radius from row sums, not the quadratic form v^T V v. Since v^T V v = v^T ((V+V^T)/2) v, the bound \bar L ||v||^2 would require an eigenvalue estimate on the symmetric part of V, not on V itself. The current justification for v^{k'⊤} V^{k'} v^{k'} ≤ \bar L ||v^{k'}||^2 is therefore incomplete and is also used in the uniqueness argument.
minor comments (4)
- [Theorem 1 statement] “almost surly” should be “almost surely”.
- [Section IV, proof around Eq. (21)] The proof refers to “Assumption 6” when the intended reference is Assumption 1.
- [Section IV, after Eq. (27)] The sentence “Also, based on Lemma 3 we have ∑ T_j^1 < ∞” appears to refer to T_j^2; Lemma 3 bounds the communication-error terms, not the already-bounded square-step-size sum T_j^1.
- [Appendix B] “e.i.” should be “i.e.”.
Circularity Check
No significant circularity: the proof is a standard stochastic-approximation argument built on external lemmas; the authors' prior work appears only as background.
full rationale
The paper's central claim is convergence of Algorithm 1 to the GNE of a leader-follower network aggregative game. The derivation is self-contained in the relevant sense: Theorem 1 is proved by constructing a Lyapunov function and applying the Robbins-Siegmund supermartingale lemma (Lemma 1, cited to [25]), with norm bounds obtained from Perron-Frobenius theory and projection nonexpansiveness, and uniqueness imported from Rosen's external theorem. No parameter is fitted to data and no prediction is made from fitted quantities; the constants C_n, C_0, L, L_0, κ, and δ are assumptions of the model, and the conditions in Theorem 1 are sufficient inequalities used in the drift bound rather than definitions of the desired conclusion. The only self-citations are [18] and [20] in the introduction, where they serve as background on leader-follower games and applications, and neither is load-bearing in the proof. I therefore find no circular step and assign score 0.
Assumptions & free parameters
assumptions (7)
- domain assumption Follower and leader subgradients satisfy strong monotonicity with constants C_n, C_0 and Lipschitz conditions with constants L, L_0 (Assumption 1).
- domain assumption Communication and activeness probabilities are bounded below: p_nm ≥ γ and q_n ≥ δ for all n, m (Assumption 2).
- domain assumption Leader wake-up intervals are bounded by K̄ (Assumption 3).
- standard math Step sizes are nonincreasing, with divergent sum and square-summable (Assumption 4).
- ad hoc to paper There exists κ such that the ratio of max to min step sizes across all players is bounded by κ at every iteration (Assumption 5).
- standard math Robbins-Siegmund nonnegative almost supermartingale convergence lemma (cited as Lemma 1, Thm 1 of [25]).
- standard math Perron-Frobenius theorem bounds the largest eigenvalue of nonnegative matrices by the maximum row sum (cited as [27]).
Cite this review
Pith. "Pith review of Leader-Follower Network Aggregative Game with Stochastic Agents' Communication and Activeness." pith.science (2026). https://pith.science/paper/E2BFMKUP
@misc{pith2026190802458,
author = {Pith},
title = {Pith review of: Leader-Follower Network Aggregative Game with Stochastic Agents' Communication and Activeness},
year = {2026},
howpublished = {\url{https://pith.science/paper/E2BFMKUP}},
note = {Machine review of arXiv:1908.02458}
}
read the original abstract
This technical note presents a leader-follower scheme for network aggregative games. The followers and leader are selfish cost minimizing agents. The cost function of each follower is affected by strategy of leader and aggregated strategies of its neighbors through a communication graph. The leader infinitely often wakes up and receives the aggregated strategy of the followers, updates its decision value and broadcasts it to all the followers. Then, the followers apply the updated strategy of the leader into their cost functions. The establishment of information exchange between each neighboring pair of followers, and the activeness of each follower to update its decision at each iteration are both considered to be drawn from two arbitrary distributions. Moreover, a distributed algorithm based on subgradient method is proposed for updating the strategies of leader and followers. The convergence of the proposed algorithm to the unique generalized Nash equilibrium point of the game is proven in both almost sure and mean square senses.
Figures
Reference graph
Works this paper leans on
-
[1]
Distributed optimization over directed graphs with row stochasticity and constraint regularity,
V . S. Mai and E. H. Abed, “Distributed optimization over directed graphs with row stochasticity and constraint regularity,” Automatica, vol. 102, pp. 94 – 104, 2019
work page 2019
-
[2]
Distributed nash equilibrium seeking in networked graphical games,
“Distributed nash equilibrium seeking in networked graphical games,” Automatica, vol. 87, pp. 17 – 24, 2018
work page 2018
-
[3]
A. Galeotti, S. Goyal, M. O. Jackson, F. Vega-Redondo, and L. Yariv, “Network Games,” The Review of Economic Studies , vol. 77, no. 1, pp. 218–244, 01 2010
work page 2010
-
[4]
Design and stability of load- side primary frequency control in power systems,
C. Zhao, U. Topcu, N. Li, and S. Low, “Design and stability of load- side primary frequency control in power systems,” IEEE Transactions on Automatic Control , vol. 59, no. 5, pp. 1177–1189, May 2014
work page 2014
-
[5]
Opinion dynamics are proximal dynamics in multi- agent network games,
S. Grammatico, “Opinion dynamics are proximal dynamics in multi- agent network games,” in 2017 IEEE 56th Annual Conference on Decision and Control (CDC) , Dec 2017, pp. 3835–3840. 8
work page 2017
-
[6]
P. Semasinghe, E. Hossain, and S. Maghsudi, “Cheat-proof distributed power control in full-duplex small cell networks: A repeated game with imperfect public monitoring,” IEEE Transactions on Communications , vol. 66, no. 4, pp. 1787–1802, April 2018
work page 2018
-
[7]
On the private provision of public goods on networks,
N. Allouch, “On the private provision of public goods on networks,” Journal of Economic Theory , vol. 157, pp. 527 – 552, 2015
work page 2015
-
[8]
Multiple activities in networks,
Y .-J. Chen, Y . Zenou, and J. Zhou, “Multiple activities in networks,” American Economic Journal: Microeconomics , vol. 10, no. 3, pp. 34– 85, August 2018
work page 2018
Show all 29 references
-
[9]
Distributed nash equilibrium seeking for aggregative games with coupled constraints,
S. Liang, P. Yi, and Y . Hong, “Distributed nash equilibrium seeking for aggregative games with coupled constraints,” Automatica, vol. 85, pp. 179 – 185, 2017. [Online]. Available: http://www.sciencedirect.com/ science/article/pii/S0005109817304132
2017
-
[10]
Distributed algorithms for aggregative games on graphs,
J. Koshal, A. NediÄ ˘G, and U. V . Shanbhag, “Distributed algorithms for aggregative games on graphs,” Operations Research, vol. 64, no. 3, pp. 680–704, 2016
2016
-
[11]
Nash and wardrop equilibria in aggregative games with coupling constraints,
D. Paccagnan, B. Gentile, F. Parise, M. Kamgarpour, and J. Lygeros, “Nash and wardrop equilibria in aggregative games with coupling constraints,” IEEE Transactions on Automatic Control , pp. 1–1, 2018
2018
-
[12]
Network ag- gregative games: Distributed convergence to nash equilibria,
F. Parise, B. Gentile, S. Grammatico, and J. Lygeros, “Network ag- gregative games: Distributed convergence to nash equilibria,” in 2015 54th IEEE Conference on Decision and Control (CDC) , Dec 2015, pp. 2295–2300
2015
-
[13]
Proximal dynamics in multiagent network games,
S. Grammatico, “Proximal dynamics in multiagent network games,” IEEE Transactions on Control of Network Systems , vol. 5, no. 4, pp. 1707–1716, Dec 2018
2018
-
[14]
A variational inequality framework for network games: Existence, uniqueness, convergence and sensitivity analysis,
F. Parise and A. Ozdaglar, “A variational inequality framework for network games: Existence, uniqueness, convergence and sensitivity analysis,” Games and Economic Behavior , 2019
2019
-
[15]
H. A. Simon, The Sciences of the Artificial , 3rd ed. Cambridge, MA: MIT Press, 1996
1996
-
[16]
Synchronization of coupled oscillators is a game,
H. Yin, P. G. Mehta, S. P. Meyn, and U. V . Shanbhag, “Synchronization of coupled oscillators is a game,” in Proceedings of the 2010 American Control Conference, June 2010, pp. 1783–1790
2010
-
[17]
Mean field lqg control in leader-follower stochastic multi-agent systems: Likelihood ratio based adaptation,
M. Nourian, P. E. Caines, R. P. Malhame, and M. Huang, “Mean field lqg control in leader-follower stochastic multi-agent systems: Likelihood ratio based adaptation,” IEEE Transactions on Automatic Control, vol. 57, no. 11, pp. 2801–2816, Nov 2012
2012
-
[18]
Discrete-time robust hierarchical linear- quadratic dynamic games,
H. Kebriaei and L. Iannelli, “Discrete-time robust hierarchical linear- quadratic dynamic games,” IEEE Transactions on Automatic Control , vol. 63, no. 3, pp. 902–909, March 2018
2018
-
[19]
Hierarchical mean field games for multiagent systems with tracking-type costs: Distributed ε-stackelberg equilibria,
B. Wang and J. Zhang, “Hierarchical mean field games for multiagent systems with tracking-type costs: Distributed ε-stackelberg equilibria,” IEEE Transactions on Automatic Control, vol. 59, no. 8, pp. 2241–2247, Aug 2014
2014
-
[20]
Pricing and rate optimization of cloud radio access network using robust hierarchical dynamic game,
M. Saffar, H. Kebriaei, and D. Niyato, “Pricing and rate optimization of cloud radio access network using robust hierarchical dynamic game,” IEEE Transactions on Wireless Communications , vol. 16, no. 11, pp. 7404–7418, Nov 2017
2017
-
[21]
Stackelberg game-theoretic model for optimizing advertising, pricing and inventory policies in vendor managed inventory (vmi) production supply chains,
Y . Yu, G. Q. Huang, and L. Liang, “Stackelberg game-theoretic model for optimizing advertising, pricing and inventory policies in vendor managed inventory (vmi) production supply chains,” Computers & Industrial Engineering, vol. 57, no. 1, pp. 368 – 382, 2009
2009
-
[22]
Managing price uncertainty in prosumer-centric energy trading: A prospect-theoretic stackelberg game approach,
G. El Rahi, S. R. Etesami, W. Saad, N. B. Mandayam, and H. V . Poor, “Managing price uncertainty in prosumer-centric energy trading: A prospect-theoretic stackelberg game approach,” IEEE Transactions on Smart Grid, vol. 10, no. 1, pp. 702–713, Jan 2019
2019
-
[23]
Randomized gossip algorithms,
S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, “Randomized gossip algorithms,” IEEE Transactions on Information Theory , vol. 52, no. 6, pp. 2508–2530, June 2006
2006
-
[24]
Existence and uniqueness of equilibrium points for concave n-person games,
J. B. Rosen, “Existence and uniqueness of equilibrium points for concave n-person games,” Econometrica, vol. 33, no. 3, pp. 520–534, 1965
1965
-
[25]
A convergence theorem for non negative almost supermartingales and some applications,
H. Robbins and D. Siegmund, “A convergence theorem for non negative almost supermartingales and some applications,” pp. 233 – 257, 1971
1971
-
[26]
J.-S. P. Francisco Facchinei, Finite Dimensional Variational Inequalities and Complementarity Problems, 1st ed. Springer, 2003, vol. volume 1
2003
-
[27]
A note on the proof of the perron- frobenius theorem,
T. C. Y . Cheng and M. Elgindi, “A note on the proof of the perron- frobenius theorem,”Applied Mathematics, vol. 3, no. 11, pp. 1697–1701, 2012
2012
-
[28]
Distributed generalized nash equilibria computation of monotone games via double-layer preconditioned proximal-point algorithms,
P. Yi and L. Pavel, “Distributed generalized nash equilibria computation of monotone games via double-layer preconditioned proximal-point algorithms,” IEEE Transactions on Control of Network Systems , vol. 6, no. 1, pp. 299–311, March 2019
2019
-
[29]
Tikhonov regularization for a general nonlinear constrained optimization problem,
N. Buong, “Tikhonov regularization for a general nonlinear constrained optimization problem,” Computational Mathematics and Mathematical Physics, vol. 47, no. 10, pp. 1583–1588, Oct 2007. [Online]. Available: https://doi.org/10.1134/S0965542507100016
2007 doi
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.