Theorem 1: a network is rationalizable as pairwise stable with -anonymous preferences iff it satisfies -WARPS
ProvedProcNetStab.theorem_1graph-theorynetwork-formationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1pairwise-stabilityrevealed-preference
Let be a set of agents, each with a type given by , let be the observed network on , and let . Then is rationalizable as pairwise stable with preferences that satisfy -anonymity if and only if satisfies -WARPS:
Here -WARPS says that for all agents there is no non-link with and , where is rooted, type-preserving isomorphism of -neighborhoods in networks adjacent to .
This is the paper's main result: it characterizes the testable content of pairwise stability under the assumption that agents with the same local network position have the same incentives to form links, and it turns that content into a check on the observed network alone.
Differences from the source:
- generalization: node set N = {1,...,n} and a finite set T of types → arbitrary node type V, arbitrary type space T and type map L : V → T; reason: the finite case is an instance; T = Unit is the untyped Definition 3.4
- reading: g − ij, introduced only as removing a link (p.6), used for all agents in Definitions 3.1 and 3.9 → edge deletion h.deleteEdges {s(i,j)}, a no-op when ij ∉ h, with j ranging over all nodes; reason: literal notation; under it the theorem holds for every k, while restricting Definition 3.9 to ij ∈ h makes Theorem 1 false at k = 0 (two nodes, g empty: rationalizable but not 0-WARPS)
- reading: k-WARPS: "for all pairs of nodes i and j in the network" → i and j arbitrary nodes, not required to be linked or distinct; reason: Definition A.4 and the proof of Lemma 1 use no link ij; restricting to linked or distinct pairs makes Theorem 1 false (n = 5, k = 1, g = {01, 03, 24}, i = j = 0, i′j′ = 12)
- reading: Definition 3.9 with networks g, g′ → g, g′ of Definition 3.9 are universally quantified networks h, h′; the observed g enters only through the adjacency clause of ≃k; reason: Definition 3.9 binds g, g′; the proof of Lemma 1 applies it with h′ = g + i′j′
- encoding: networks (N,E), k-neighborhoods, preference relations ⪰_i ⊂ G × G → SimpleGraph V, the k-ball via the extended distance edist and the induced subgraph, relations pref a x y read as x ⪰_a y; reason: Lean conventions; same instances
Preamble
import Mathlib import Definitions.Def_ProcNetStab_Rationalizable import Definitions.Def_ProcNetStab_KWARPS
Formal statement
namespace ProcNetStab
/-- **Theorem 1** (Chiong, Qi, *Stability of Procurement Networks* (authors' manuscript, 2025),
Theorem 1, p.15): an observed network `g` is rationalizable as pairwise stable with preferences
that satisfy `k`-anonymity if and only if `g` satisfies `k`-WARPS.
**Formalization Note** Stated for every `k ∈ ℕ` (including `k = 0`), every observed network `g`,
every node type `V`, type space `T` and type map `L` (`T = Unit` gives untyped networks). `g − ij`
is edge deletion, a no-op when `ij ∉ g`; the `k`-ball uses the extended distance `edist`;
preferences are relations on all networks on `V`. -/
theorem theorem_1 {V T : Type*} (L : V → T) (g : SimpleGraph V) (k : ℕ) :
Rationalizable L g k ↔ KWARPS L g k := by sorry
end ProcNetStab
Source
Chiong, Qi, Stability of Procurement Networks (authors' manuscript, 2025), Theorem 1, p.15
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.