Lemma 2 — average tracking identity
ProvedAggGameNet.GossipConst.lemma_2consensusgossipp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
For a gossip run with , let be the mean of the agents' estimates. Then at every tick and on every trajectory,
This identity identifies the common estimate mean with the true average decision. Formalization Note The column-stochastic hypothesis printed in Lemma 2 is automatic for the gossip matrices (26).
Preamble
import Mathlib import Definitions.Def_AggGameNet_GossipConst_Gossip
Formal statement
namespace AggGameNet.GossipConst
theorem lemma_2 {N n : ℕ} (hN : 0 < N) {Ω : Type*}
(K : Fin N → Set (AggGameNet.Sync.E n)) (F : Fin N → AggGameNet.Sync.E n → AggGameNet.Sync.E n → AggGameNet.Sync.E n)
(I J : ℕ → Ω → Fin N) (alpha : Fin N → ℝ)
(x v : ℕ → Ω → Fin N → AggGameNet.Sync.E n)
(hrun : IsGossipRun K F I J alpha x v) :
∀ k ω, AggGameNet.Gossip.yavg v k ω = (1 / (N : ℝ)) • ∑ i, x k ω i := by sorry
end AggGameNet.GossipConst
Source
Koshal, Nedić, Shanbhag, Distributed Algorithms for Aggregative Games on Graphs, arXiv:1605.00267v2, Lemma 2, p. 10, applied to (26)–(29)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.