Pith. sign in

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 →

arxiv 1908.02458 v1 pith:E2BFMKUP submitted 2019-08-07 eess.SY cs.SY

classification eess.SYcs.SY MSC 91A1091A4391A6568W15
keywords leader-followergamenetworkaggregativegeneralizedNashequilibriumprojectedsubgradientmethodstochasticcommunicationactivenessalmostsureconvergencemeansquare
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies a non-cooperative game with one leader and many followers. Each follower's cost depends on its own strategy, a weighted aggregate of its neighbors' strategies, and the leader's strategy; the leader's cost depends on its strategy and a weighted aggregate of all followers' strategies. The authors propose a fully distributed projected subgradient algorithm in which each follower updates only when randomly active and uses only information delivered over randomly established links, while the leader wakes up, updates, and broadcasts at time instants separated by at most $\bar{K}$ iterations. The central claim is that, under strong convexity and Lipschitz assumptions and a uniform bound on the ratio of step sizes, Algorithm 1 converges to the unique generalized Nash equilibrium in both almost sure and mean square senses. A sympathetic reading would summarize the contribution as: stochastic communication and sleeping agents degrade the convergence rate but not the convergence itself, provided each agent's cost curvature is large enough relative to the coupling.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

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)
  1. [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.
  2. [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.
  3. [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.
  4. [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)
  1. [Theorem 1 statement] “almost surly” should be “almost surely”.
  2. [Section IV, proof around Eq. (21)] The proof refers to “Assumption 6” when the intended reference is Assumption 1.
  3. [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.
  4. [Appendix B] “e.i.” should be “i.e.”.

Circularity Check

0 steps flagged · score 0.0 of 10

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 0 free parameters · 7 assumptions · 0 invented entities

The central claim rests on seven technical assumptions. Most are standard domain assumptions for strongly convex games and stochastic approximation, but Assumption 5 is ad hoc and the application of Perron-Frobenius is mathematically incorrect. No free parameters are fitted and no new entities are introduced.

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).
    Provides the quadratic lower bounds (6) and (7) used in inequalities (16)-(24), and guarantees existence of a GNE via Rosen [24].
  • domain assumption Communication and activeness probabilities are bounded below: p_nm ≥ γ and q_n ≥ δ for all n, m (Assumption 2).
    Used in Lemma 3 to show the information staleness term decays, and in (27) to replace E{e} with δ so that T_4 remains positive.
  • domain assumption Leader wake-up intervals are bounded by K̄ (Assumption 3).
    Ensures the leader's information is not arbitrarily stale and gives C_0 > κ K̄ L̄ as a sufficient condition.
  • standard math Step sizes are nonincreasing, with divergent sum and square-summable (Assumption 4).
    Standard Robbins-Siegmund condition; also used in Lemma 2 and Lemma 3 to bound the accumulated perturbations.
  • 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).
    Unusual coupling condition; necessary in (23) to express all follower and leader step sizes relative to ᾱᵏ, and to make the mixed terms in (27) negative.
  • standard math Robbins-Siegmund nonnegative almost supermartingale convergence lemma (cited as Lemma 1, Thm 1 of [25]).
    The backbone of the a.s. convergence proof; requires the drift term βᵏ summable and the positive part ηᵏ summable.
  • standard math Perron-Frobenius theorem bounds the largest eigenvalue of nonnegative matrices by the maximum row sum (cited as [27]).
    The paper uses it to conclude ||V|| ≤ max(2L, L_0), but the theorem only controls spectral radius; the quadratic form bound vᵀVv ≤ L̄ ||v||² does not follow for the non-symmetric matrix V.

how reviews work

0 comments
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

Figures reproduced from arXiv: 1908.02458 by the authors.

Figure 1
Figure 1. The information scheme of leader-follower network game [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. The price of leader along the algorithm iterations. [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. The average power of followers along the algorithm iterations. [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

  1. [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

  2. [2]

    Distributed nash equilibrium seeking in networked graphical games,

    “Distributed nash equilibrium seeking in networked graphical games,” Automatica, vol. 87, pp. 17 – 24, 2018

  3. [3]

    Network Games,

    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

  4. [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

  5. [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

  6. [6]

    Cheat-proof distributed power control in full-duplex small cell networks: A repeated game with imperfect public monitoring,

    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

  7. [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

  8. [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

Show all 29 references
  1. [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

  2. [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

  3. [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

  4. [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

  5. [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

  6. [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

  7. [15]

    H. A. Simon, The Sciences of the Artificial , 3rd ed. Cambridge, MA: MIT Press, 1996

  8. [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

  9. [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

  10. [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

  11. [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

  12. [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

  13. [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

  14. [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

  15. [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

  16. [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

  17. [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

  18. [26]

    J.-S. P. Francisco Facchinei, Finite Dimensional Variational Inequalities and Complementarity Problems, 1st ed. Springer, 2003, vol. volume 1

  19. [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

  20. [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

  21. [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

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.