maxcut_single_vertex_gluing_abstract
For an additively separable game whose player sets cover all players and intersect only at a shared player, stability on each piece implies stability of the combined payoff: whenever any player changes, a changing player fails to improve the sum of its two piece payoffs. Each piece payoff vanishes outside its own player set.
Statement
theorem maxcut_single_vertex_gluing_abstract {V C : Type} (σ : V → C) (A B : Set V) (o : V) (hA : o ∈ A) (hB : o ∈ B) (hcover : ∀ v, v ∈ A ∨ v ∈ B) (hinter : ∀ v, v ∈ A → v ∈ B → v = o) (a b : (V → C) → V → ℕ) (ha0 : ∀ p v, v ∉ A → a p v = 0) (hb0 : ∀ p v, v ∉ B → b p v = 0) (hstableA : ∀ τ, (∃ v, v ∈ A ∧ τ v ≠ σ v) → ∃ v, v ∈ A ∧ τ v ≠ σ v ∧ a τ v ≤ a σ v) (hstableB : ∀ τ, (∃ v, v ∈ B ∧ τ v ≠ σ v) → ∃ v, v ∈ B ∧ τ v ≠ σ v ∧ b τ v ≤ b σ v) : ∀ τ, (∃ v, τ v ≠ σ v) → ∃ v, τ v ≠ σ v ∧ a τ v + b τ v ≤ a σ v + b σ v
- Source
- General gluing mechanism for the Max-k-Cut strong-equilibrium existence problem OP-85.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- maxcut_single_vertex_sum_strong_equilibriumIf a finite graph is covered by two induced subgraphs meeting in one vertex with no edge between their exclusive parts, and a coloring…
The proof, explained
The theorem is proved by contradiction: suppose there is a deviation $\tau \ne \sigma$ under which every changing player strictly increases their combined payoff $a(\tau, v) + b(\tau, v) > a(\sigma, v) + b(\sigma, v)$. Because each piece payoff vanishes outside its own player set, any player in $A \setminus \{o\}$ or $B \setminus \{o\}$ depends on only one payoff; thus any non-improving player guaranteed by piece stability must be the unique shared player $o$. Applying this to the initial deviation forces $o$ itself to have changed. Finally, applying the stability of both pieces to $o$ reveals that $o$ cannot strictly improve under either $a$ or $b$, so its combined payoff cannot strictly increase, contradicting the assumption.
Under the assumption that no changing player fails to improve their combined payoff, every player who changes strategy must strictly increase their total payoff.
Assuming classical logic, we introduce a modified strategy profile $\tau$ with at least one changed player (`hchanged`). To argue by contradiction, we suppose (`hbad`) that no changing player has a non-increasing combined payoff $a(\tau, v) + b(\tau, v) \le a(\sigma, v) + b(\sigma, v)$. It follows directly (`hgain`) that every changing player $v$ must strictly improve their total payoff: $a(\sigma, v) + b(\sigma, v) < a(\tau, v) + b(\tau, v)$.
classical intro τ hchanged by_contra hbad have hgain : ∀ v, τ v ≠ σ v → a σ v + b σ v < a τ v + b τ v := by intro v hv by_contra hn exact hbad ⟨v, hv, by omega⟩
Any changing player in $A$ whose payoff $a$ does not strictly increase must be the shared player $o$.
Suppose $v \in A$ changes strategy and satisfies $a(\tau, v) \le a(\sigma, v)$. If $v \ne o$, then since the intersection $A \cap B$ contains only $o$ (`hinter`), $v \notin B$. The payoff function $b$ vanishes outside $B$ (`hb0`), so $b(\tau, v) = b(\sigma, v) = 0$. The strict gain inequality for $v$ then reduces to $a(\sigma, v) < a(\tau, v)$, contradicting $a(\tau, v) \le a(\sigma, v)$.
have left_root : ∀ v, v ∈ A → τ v ≠ σ v → a τ v ≤ a σ v → v = o := by intro v hv hdiff hle by_contra hne have hnot : v ∉ B := fun hmem => hne (hinter v hv hmem) have hg := hgain v hdiff rw [hb0 τ v hnot, hb0 σ v hnot] at hg omega
Any changing player in $B$ whose payoff $b$ does not strictly increase must be the shared player $o$.
Symmetrically, suppose $v \in B$ changes strategy and satisfies $b(\tau, v) \le b(\sigma, v)$. If $v \ne o$, then $v \notin A$ by `hinter`. Since the payoff function $a$ vanishes outside $A$ (`ha0`), $a(\tau, v) = a(\sigma, v) = 0$. The strict gain inequality reduces to $b(\sigma, v) < b(\tau, v)$, contradicting $b(\tau, v) \le b(\sigma, v)$.
have right_root : ∀ v, v ∈ B → τ v ≠ σ v → b τ v ≤ b σ v → v = o := by intro v hv hdiff hle by_contra hne have hnot : v ∉ A := fun hmem => hne (hinter v hmem hv) have hg := hgain v hdiff rw [ha0 τ v hnot, ha0 σ v hnot] at hg omega
The shared player $o$ must have changed strategy ($\tau(o) \ne \sigma(o)$).
By assumption, some player $v$ changed strategy. Because $A$ and $B$ cover all players (`hcover`), $v$ belongs to either $A$ or $B$. If $v \in A$, stability on piece $A$ (`hstableA`) provides a changing player $w \in A$ with $a(\tau, w) \le a(\sigma, w)$. By `left_root`, $w = o$, so $\tau(o) \ne \sigma(o)$. If instead $v \in B$, stability on piece $B$ (`hstableB`) similarly produces a changing player in $B$ with non-increasing payoff $b$, which by `right_root` must be $o$. Thus in either case, $\tau(o) \ne \sigma(o)$.
have horoot : τ o ≠ σ o := by obtain ⟨v, hv⟩ := hchanged rcases hcover v with hvA | hvB · obtain ⟨w, hwA, hwd, hwle⟩ := hstableA τ ⟨v, hvA, hv⟩ have : w = o := left_root w hwA hwd hwle simpa [this] using hwd · obtain ⟨w, hwB, hwd, hwle⟩ := hstableB τ ⟨v, hvB, hv⟩ have : w = o := right_root w hwB hwd hwle simpa [this] using hwd
The combined payoff of the shared player cannot strictly increase, yielding a contradiction.
Because $o$ changed strategy and belongs to both $A$ and $B$ (`hA`, `hB`), we apply piece stability on $A$ to obtain a changing player $x \in A$ with $a(\tau, x) \le a(\sigma, x)$, and on $B$ to obtain $y \in B$ with $b(\tau, y) \le b(\sigma, y)$. By `left_root` and `right_root`, both $x$ and $y$ must be $o$, giving $a(\tau, o) \le a(\sigma, o)$ and $b(\tau, o) \le b(\sigma, o)$. Summing these two inequalities yields $a(\tau, o) + b(\tau, o) \le a(\sigma, o) + b(\sigma, o)$, which contradicts the strict gain inequality (`hgain`) for $o$. Linear arithmetic (`omega`) closes the goal.
obtain ⟨x, hxA, hxd, hxle⟩ := hstableA τ ⟨o, hA, horoot⟩ obtain ⟨y, hyB, hyd, hyle⟩ := hstableB τ ⟨o, hB, horoot⟩ have hx : x = o := left_root x hxA hxd hxle have hy : y = o := right_root y hyB hyd hyle subst x subst y have hg := hgain o horoot omega
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem maxcut_single_vertex_gluing_abstract {V C : Type} (σ : V → C) (A B : Set V) (o : V) (hA : o ∈ A) (hB : o ∈ B) (hcover : ∀ v, v ∈ A ∨ v ∈ B) (hinter : ∀ v, v ∈ A → v ∈ B → v = o) (a b : (V → C) → V → ℕ) (ha0 : ∀ p v, v ∉ A → a p v = 0) (hb0 : ∀ p v, v ∉ B → b p v = 0) (hstableA : ∀ τ, (∃ v, v ∈ A ∧ τ v ≠ σ v) → ∃ v, v ∈ A ∧ τ v ≠ σ v ∧ a τ v ≤ a σ v) (hstableB : ∀ τ, (∃ v, v ∈ B ∧ τ v ≠ σ v) → ∃ v, v ∈ B ∧ τ v ≠ σ v ∧ b τ v ≤ b σ v) : ∀ τ, (∃ v, τ v ≠ σ v) → ∃ v, τ v ≠ σ v ∧ a τ v + b τ v ≤ a σ v + b σ v := by classical intro τ hchanged by_contra hbad have hgain : ∀ v, τ v ≠ σ v → a σ v + b σ v < a τ v + b τ v := by intro v hv by_contra hn exact hbad ⟨v, hv, by omega⟩ have left_root : ∀ v, v ∈ A → τ v ≠ σ v → a τ v ≤ a σ v → v = o := by intro v hv hdiff hle by_contra hne have hnot : v ∉ B := fun hmem => hne (hinter v hv hmem) have hg := hgain v hdiff rw [hb0 τ v hnot, hb0 σ v hnot] at hg omega have right_root : ∀ v, v ∈ B → τ v ≠ σ v → b τ v ≤ b σ v → v = o := by intro v hv hdiff hle by_contra hne have hnot : v ∉ A := fun hmem => hne (hinter v hmem hv) have hg := hgain v hdiff rw [ha0 τ v hnot, ha0 σ v hnot] at hg omega have horoot : τ o ≠ σ o := by obtain ⟨v, hv⟩ := hchanged rcases hcover v with hvA | hvB · obtain ⟨w, hwA, hwd, hwle⟩ := hstableA τ ⟨v, hvA, hv⟩ have : w = o := left_root w hwA hwd hwle simpa [this] using hwd · obtain ⟨w, hwB, hwd, hwle⟩ := hstableB τ ⟨v, hvB, hv⟩ have : w = o := right_root w hwB hwd hwle simpa [this] using hwd obtain ⟨x, hxA, hxd, hxle⟩ := hstableA τ ⟨o, hA, horoot⟩ obtain ⟨y, hyB, hyd, hyle⟩ := hstableB τ ⟨o, hB, horoot⟩ have hx : x = o := left_root x hxA hxd hxle have hy : y = o := right_root y hyB hyd hyle subst x subst y have hg := hgain o horoot omega