Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Corollary 1, pp. 12–13 — one node partition on which every equilibrium of a non-expansive network solves the linear system (27)

Proved
SaturatedNet.Uniqueness.corollary_1

by mikedeng1 · Oct 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-systemnetwork-equilibriumnon-expansivep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1saturation

Let (P,w)(P, w)(P,w) be a non-expansive network and c∈Rnc \in \mathbb R^nc∈Rn any exogenous flow. Then there is a partition V=V+∪V0∪V−\mathcal V = \mathcal V_+ \cup \mathcal V_0 \cup \mathcal V_-V=V+​∪V0​∪V−​ of the nodes into three pairwise disjoint sets such that, writing z=(z(+),z(0),z(−))z = (z^{(+)}, z^{(0)}, z^{(-)})z=(z(+),z(0),z(−)) for the corresponding split of a vector and P(αβ)P^{(\alpha\beta)}P(αβ) for the block of PPP with rows in Vα\mathcal V_\alphaVα​ and columns in Vβ\mathcal V_\betaVβ​:

  1. every network equilibrium xxx satisfies
x(−)=0,x(0)=P(00)⊤x(0)+P(+0)⊤x(+)+c(0),x(+)=w(+);x^{(-)} = 0,\qquad x^{(0)} = P^{(00)\top}x^{(0)} + P^{(+0)\top}x^{(+)} + c^{(0)},\qquad x^{(+)} = w^{(+)};x(−)=0,x(0)=P(00)⊤x(0)+P(+0)⊤x(+)+c(0),x(+)=w(+);
  1. any two network equilibria x,yx, yx,y satisfy x(−)=y(−)x^{(-)} = y^{(-)}x(−)=y(−) and x(+)=y(+)x^{(+)} = y^{(+)}x(+)=y(+).

The partition is the same for all equilibria; uniqueness can therefore be decided on the exposed block, where equilibria solve a linear system. It is the reduction used in Propositions 4 and 5.

Formalization Note. The middle equation is written coordinatewise: for i∈V0i \in \mathcal V_0i∈V0​, xi=∑k∈V0Pkixk+∑k∈V+Pkixk+cix_i = \sum_{k \in \mathcal V_0} P_{ki}x_k + \sum_{k \in \mathcal V_+} P_{ki}x_k + c_ixi​=∑k∈V0​​Pki​xk​+∑k∈V+​​Pki​xk​+ci​. The partition is a single triple of sets chosen before the equilibria, not a function of xxx.

Preamble
import Mathlib
import Definitions.Def_SaturatedNet_Uniqueness_Model
open Matrix
Formal statement
namespace SaturatedNet.Uniqueness

theorem corollary_1 {n : Type*} [Fintype n] [DecidableEq n]
    (P : Matrix n n ℝ) (hP : ∀ i j, 0 ≤ P i j) (w : n → ℝ) (hw : 0 ≤ w) (c : n → ℝ) (hne : IsNonExpansive P) :
    ∃ Vp V0 Vm : Finset n,
      Disjoint Vp V0 ∧ Disjoint Vp Vm ∧ Disjoint V0 Vm ∧ Vp ∪ V0 ∪ Vm = Finset.univ ∧
      (∀ x ∈ equilibria P w c,
        (∀ i ∈ Vm, x i = 0) ∧
        (∀ i ∈ V0, x i = ∑ k ∈ V0, P k i * x k + ∑ k ∈ Vp, P k i * x k + c i) ∧
        (∀ i ∈ Vp, x i = w i)) ∧
      (∀ x ∈ equilibria P w c, ∀ y ∈ equilibria P w c,
        (∀ i ∈ Vm, x i = y i) ∧ (∀ i ∈ Vp, x i = y i)) := by sorry

end SaturatedNet.Uniqueness
Source
Massai, Como & Fagnani, Equilibria and Systemic Risk in Saturated Networks, arXiv:1912.04815v2, pp. 12–13, Corollary 1, (26)–(28)
Human review
  • Endorsed by Shuze Chen · Oct 22, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 22, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me